An improved route minimization algorithm for the vehicle routing problem with time windows

Mirosław Błocho, Zbigniew J Czech

Abstract


A route minimization algorithm for the vehicle routing problem with time windows is presented. It was elaborated as an improvement of the algorithm proposed by Nagata and Bräysy (A powerful route minimization heuristic for the vehicle routing problem with time windows, Operations Research Letters 27, 2009, 333-338). By making use of the improved algorithm the two new-best solutions for Gehring and Homberger’s (GH) benchmarks were found. The experiments showed that the algorithm constructs the world-best solutions with the minimum route numbers for the GH tests in a short time.

Keywords


vehicle routing problem; guided local search; heuristics; approximation algorithm

Full Text:

PDF

References


Czech Z. J.: A Parallel Simulated Annealing Algorithm as a Tool for Fitness landscapes Exploration. Parallel and Distributed Computing. InTech, 2010, chapter 13, p. 247-271.

Gehring H., Homberger J.: Parallelization of a two-phase metaheuristic for routing problems with time windows. Asia-Pacific Journal of Operational Research 18, 2001, p. 35-47.

Ibaraki T., Imahori S., Nonobe K., Sobue K., Uno T., Yagiura M.: An iterated local search algorithm for the vehicle routing problem with convex time penalty functions. Discrete Applied Mathematics 156, 2008, p. 2050-2069

Lenstra. J., and Rinnooy Kan, A.: Complexity- of vehicle routing and scheduling problems. Networks 11, 1981, p. 221-227.

Lim A., Zhang X.: A two-stage heuristic with ejection pools and generalized ejection chains for the vehicle routing problem with time windows. Informs Journal on Computing 19, 2007, p. 443-457.

Nagata Y.: Efficient evolutionary algorithm for the vehicle routing problem with time windows: Edge assembly crossover for the VRPTW. Proc. of the 2007 Congress on Evolutionary Computation, 2007, p. 1175-1182.

Nagata Y, Bräysy O.: A Powerful Route Minimization Heuristic for the Vehicle Routing Problem with Time Windows. Operations Research Letters 37, 2009, p. 333-338.

Nagata Y. Bräysy O., Dullaert W. (2010) A Penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. Computers & Operations Research 37, 2010, p. 724-737.

Pisinger D., Ropke S.: A general heuristic for vehicle routing problems. Computers & Operations Research 34, 2007. p. 2403-2435.

Prescott-Gagnon E., Desaulniers G., Rousseau L.-M.: A branch-and-price-based large neighborhood search algorithm for the vehicle routing problem with time windows. Working Paper, University of Montreal, Canada, 2007.

Toth P., and Vigo D., (Eds ): The vehicle routing problem. SLAM Monographs on Discrete Mathematics and Applications, Philadelphia, PA, 2002.

Voudouris C., Tsang E.: Guided local search. Handbook of Metaheuristics. Kluwer, 2003, p. 185-218.




DOI: http://dx.doi.org/10.21936/si2011_v32.n3B.218