A Fast Local Search Algorithm for the Vehicle

A Fast Local Search Algorithm for the Vehicle Routing Problem with Time Windows : A Fast Local Search Algorithm for the Vehicle Routing Problem with Time Windows OLLI BRÄYSY, GEIR HASLE SINTEF Applied Mathematics, Department of Optimisation, P.O. Box 124 Blindern, N-0314 Oslo, Norway {Olli.Braysy;Geir.Hasle}@math.sintef.no WOUT DULLAERT Ufsia-Ruca Faculty of Applied Economics, University of Antwerp Prinsstraat 13, 2000 Antwerp, Belgium wout.dullaert@ua.ac.be

Introduction : Introduction Development of a new fast local search heuristic for the VRPTW First application of Threshold Accepting as a post-optimization technique for the VRPTW A comprehensive computational study consisting of 358 benchmark problems from the literature New best-known solutions to both real-life problems of Russell (1995), and to 39% of the extended benchmarks by Gehring and Homberger (1999) Optimization Days, Montreal, Canada, May 6-8th

Slide3 : Generation of the LS solution Reduce the number of routes Reduce distance Injection trees Modified Or-Opt and CROSS exchanges Build initial solutions Hybrid construction heuristic Optimization Days, Montreal, Canada, May 6-8th PROCESS METHOD

Slide4 : Post-optimization by Threshold Accepting Intra-route distance improvement Inter-route distance improvement Initial solutions IOPT exchanges GENICROSS exchanges Generated by LS Optimization Days, Montreal, Canada, May 6-8th PROCESS METHOD

Hybrid sequential insertion heuristic : Hybrid sequential insertion heuristic Initialization: seed customer randomly selected among the farthest from the depot Insert the cheapest customer in the best feasible insertion place Weighted cost function of additional detour and waiting time Subtract the distance of the customer to the depot Speed-up techniques: Only consider geographically close customers to the route for insertion Push-forward & push-backward techniques (Solomon et al., 1988) Storage of arrival times and latest possible arrival times Calculate accumulated waiting time after each insertion place within the current route Result: Generate 5000 feasible solutions for Solomon’s 100 customer problem instances in 1 second on a 700 MHz PC Optimization Days, Montreal, Canada, May 6-8th

Injection tree heuristic (1) : Injection tree heuristic (1) GOAL: reduce number of routes Similarities with Ejection Chains (Glover, 1991 and 1992) Optimization Days, Montreal, Canada, May 6-8th

Injection tree heuristic (2) : Injection tree heuristic (2) Implementation: Consider first the shortest routes for elimination Consider first insertions in geographically close routes, distant routes are disregarded Impose a maximum tree length and a maximum on the number of trees to be stored Use breadth-first search First accept intra-route reinsertions to reduce lateness in target route Ignore insertions that increase the distance in the target route more than a dynamically adjusted limit Same speed-up techniques as for the hybrid construction heuristic Optimization Days, Montreal, Canada, May 6-8th

Distance improvement heuristics : Distance improvement heuristics GOAL: relocate or exchange segments of customers to reduce distance Modify CROSS exchanges (Taillard et al, 1997) and Or-Opt exchanges (Or, 1976) Also consider inserting the customers in the segment in inverted order Try the most promising moves first (first accept) First remove customers closest to customers on the other route Then consider first the insertion between customers closest on the other route Consider only a limited set of closest customers and closest insertion places Impose a maximum segment length Optimization Days, Montreal, Canada, May 6-8th

Threshold Accepting : Threshold Accepting Modification of Simulated Annealing by Dueck (1990,1993) Accept worse solution if its difference to the incumbent solution is smaller or equal to a deterministic threshold Local search operators used: IOPT : Or-Opt exchanges in which also the inverted route segment is considered (Bräysy, 2001) GENICROSS: based on GENIUS insertion heuristic (Gendreau et al., 1992) and CROSS exchanges (Taillard et al., 1997) In exchanging segment between routes, the second insertion is considered only if the first improved the objective function All possible insertion places for the segments in both routes are considered Also consider insertions between pairs of customers that are not consecutive Optimization Days, Montreal, Canada, May 6-8th

Threshold Accepting : Threshold Accepting Step 1. Read in a feasible solution, Si, created by the LS Set and Step 2. Repeat steps 36 for n iterations. Step 3. Order the routes in Si randomly Step 4. Try to improve the current pair of routes in Si using GENICROSS. Step 5. Try to improve both individual routes in the current pair of routes in Si using IOPT. Step 6. Lower the threshold by : If a better solution is found, store it: If no improvement has been found for k iterations, restart the search from the best solution obtained so far at a reinitialized threshold: and If , reinitialize the threshold: Step 7. Return the best solution obtained Sb. Optimization Days, Montreal, Canada, May 6-8th

Computational results : Computational results Problem set : 56 100-customer problem instances Solomon (1987) 300 extended benchmarks by Gehring and Homberger (1999) 2 real-life benchmarks of Russell (1995) The algorithms were implemented in C++ and the computational experiments were conducted using a 700 MHz PC with 128 MB memory and Windows 98 operating system. Optimization Days, Montreal, Canada, May 6-8th

Slide12 :

Slide13 :

Slide14 :

Slide15 :

Slide16 :

Slide17 :

Slide18 :

Slide19 :

Conclusions : Conclusions First application of Threshold Accepting to the VRPTW Development of a new fast construction heuristic and four new improvement heuristics 119 new best solutions obtained for 358 test problems from the literature Suggest Threshold Accepting as a versatile and fast post-optimization method More information on the research projects at SINTEF Applied Mathematics: http://www.top.sintef.no