Vehicle Routing Problem with Time Windows - Example

VEHICLE ROUTING PROBLEM WITH TIME WINDOWS Your name Subject Date Introduction A major problem facing the transport industry is the establishment of routes connecting a certain area to several other areas. In our daily lives we rely heavily on transportation be it going to school, work, visiting friends, marketing, and trade. Transportation accounts for a substantial percentage of national income in many countries around the world. The Vehicle routing problem with time windows has been a major concern. It describes a situation where the overall aim is to reduce transportation cost of moving goods from one area to another. However the solving of the VRPTW is quite complex and several approaches have been suggested. Heuristic approach The most widely used approach is the heuristic approach. The advantage of this approach being that it is simple to calculate. This approach is founded upon algorithms and applies in our day to day activities. In this respect an algorithm should be very dynamic and well rounded so as to be applied to different circumstances. The results found from algorithms are not in any way predictable and different scenarios generate unique results thus making it difficult to compare solutions. The heuristic is bound to be time consuming but then again it should not take too long and research results should be released on time. To solve this we make use of averages. The average should as much as possible represents the actual results and deviations should be minimal. One can obtain very reliable results by spending too much time on a heuristic but them again the solution should be timely so as not to be out of date. Thus this two facts need to be taken into consideration when coming up with a solution; it should be accurate and at the same time be useful at the time it is released. When we take the two facts into consideration we come up with a Pareto optimal solution. Empirical analysis is used to test the accuracy of the solution. The set back with this approach is achieving fairness. Another setback is that only favorable results are reported and the not so favorable are left out. Also the duration it took to get the results is not stated. It is important to give a solution and state the duration it took to obtain the solution. Route construction heuristic Two methods are discussed, the sequential methods and parallel methods. The sequential method creates one way of travel while the parallel method creates multiple ways of travel. Customers are grouped into one big course that is divided into smaller courses. The first big travel is taken to have no limits on the number of people and duration. The saving method is popular and describes a situation where each person is served by a particular course. To save on costs the customers are meant to travel using one course and a constraint is set on the waiting time of customers. The second method refers to a situation where the distance between the customers is considered and if a customer is close to a seed customer at a particular course he or she is added to the course. If no more customers are found on the course and there are still some customers left without a course a new course is formed. Solomon suggest two critical stages the first stage being obtaining a group of customers traveling a course and the second stage being the determination of which customers leave first and which ones follow. Different personalities have come up with their own methods and some make reference to the method suggested by Solomon, example of such are Ioannou et al, and Foisy Potvin. However each of these personalities makes adjustments to Solomon’s original idea. Another problem is the vehicle routing problem with soft time windows (VRPSTW). The main aim of VRPSTW is to reduce the waiting time for customers such that if a customers does not arrive at a particular time the vehicle leaves. This reduces both the duration of a trip and also the number of vehicles needed to make the trips. Three heuristics have been suggested to cope with this problem. The first being the reasoning behind the solution to the capacitated location problem with time windows (CLPTW) which suggest the choosing of a certain point where customers are picked up by vehicles stationed at those points. Customers are picked based on the customer closest to the point is picked instead of the one located further away from the chosen point of departure. Problem Description The Vehicle Routing Problem (VRP) is somewhat related to the TSP problem being a combinatorial optimization problem that is NP-hard and involves movement between locations. It consists of finding efficient ways for a fleet with a certain number of vehicles to deliver goods to a certain number of customers. The Vehicle Routing Problem with TimeWindows (VRPTW) is represented as destinations listed in the order they will be visited. A solution is represented as an array of locations, [l1; l2; : : : ; ln+v] where l is a customer location, n is the number of customers and v is the number of vehicles. Let di(i+1) be the distance between two adjacent locations on the route. Description of the extended SOLOMON's instances The first original 56 VRPTW instances were designed by Prof. Marius M. Solomon in 1983. It contained 100 customers. Below is VRPTW presented with 200 customers? The design is the same as the original 100 customer problems. This involves fleet size, travel time of vehicles, vehicle capacity, spatial distribution of customers and time window. The new instances are divided into three categories: Problem's name VEHICLE NUMBER CAPACITY K Q CUSTOMER CUST NO. XCOORD. YCOORD. DEMAND READY TIME DUE DATE SERVICE TIME 0 x0 y1 q0 e0 l0 s0 1 x1 y2 q1 e1 l1 s1 ... ... ... ... ... ... ... 100 x100 y100 q100 e100 l100 s100 Solution improvement methods To improve solutions we make use of the local search algorithm whereby we consider the next result obtained and if it is more accurate than the previous result, we replace the previous result with the new one and the searching process goes on. Two strategies are identified the first-accept strategy (FA) which selects the first result that precedes the current result and the best-accept strategy (BA) which selects the best result from the given set of results. The edge-exchange algorithm is the most common method of improving solutions whereby a travel is improved by exchanging its edges with different ones and this process continues up to the point where no more improvements can be made. A seed customer refers to the initial customer at the point of departure, other customers are assigned to the initial seed customer and this is done by making use of the greedy heuristic strategy where only the customers that are closest to the seed customer are attached to the seed customer and this not only reduces time but also reduces the travel distance from one point to another. The 2-opt strategy is also of great importance and it works by putting together two courses and placing the last customer of a given course after the first customer of the other course thus ensuring the smooth running of each course. Ejection chains refer to the process of eliminating a customer from one course and placing another customer on the course. In such a sequence it is always the case that one customer remains without a course and the sequence continues until a point is reached where a customer is moved to another way of travel and this does not result into another customer being removed from the way of travel to create space for the new customer. The parallel methodology seeks to improve a number of courses at the same time. An understanding is reached between the customer and the courses, such that each customer makes a deal with the least cost way of travel and the courses choose the best customer to serve. After this process the courses reduce to one and the best result is found. The various methodologies proposed by different personalities have strengths and weaknesses. The approach suggested by Schrimpf et al (2000) is said to be the most favorable and that of Prosser and Shaw (1996) was considered to be the least favorable. Conclusion From the above discussions we have seen that heuristic approaches help in solving the VRPTW problem. A good heuristic should be timely, dynamic, well rounded and should produce accurate and reliable results. Although we cannot say exactly which method will generate an optimal solution, the decision of which method to use is to be determined by the individual making the decision based on his preference. List of references Prosser, P., P. Shaw. 1996. Study of greedy search with multiple improvement heuristics for vehicle routing problems. University of Strathclyde, Glasgow, Scotland. Foisy, C., J.-Y. Potvin. 1993. Implementing an insertion heuristic for vehicle routing on parallel hardware. Comput.Oper.Res. 20 737–745 Schrimpf, G., J. Schneider, H. Stamm-Wilbrandt, G. Dueck. 2000. Record breaking optimization results using the ruin and recreate principle. J.Comput. Phys. 159 139–171 Read More