A penalty-based edge assembly memetic algorithm for the vehicle routing problem with time windows. (English) Zbl 1175.90046

Nagata, Yuichi; Bräysy, Olli; Dullaert, Wout

Comput. Oper. Res. 37, No. 4, 724-737 (2010).

Summary: We present an effective memetic algorithm for the vehicle routing problem with time windows (VRPTW). The paper builds upon an existing edge assembly crossover (EAX) developed for the capacitated VRP. The adjustments of the EAX operator and the introduction of a novel penalty function to eliminate violations of the time window constraint as well as the capacity constraint from offspring solutions generated by the EAX operator have proven essential to the heuristic’s performance. Experimental results on Solomon’s and Gehring and Homberger benchmarks demonstrate that our algorithm outperforms previous approaches and is able to improve 184 best-known solutions out of 356 instances.

MSC:

90B06	Transportation, logistics and supply chain management
90B10	Deterministic network models in operations research
90C35	Programming involving graphs or networks

Keywords:

vehicle routing; time windows; memetic algorithm; penalty function

Software:

VRP

References:

[1]	Cordeau JF, Desaulniers G, Desrosiers J, Solomon MM, Soumis F. VRP with time windows. In: Toth P, Vigo D, editors. The vehicle routing problem. SIAM monographs on discrete mathematics and applications, vol. 9. Philadelphia, PA, 2002. p. 157-93. · Zbl 1076.90543
[2]	Bräysy, O.; Gendreau, M., Vehicle routing problem with time windows, part I: route construction and local search algorithms, Transportation science, 39, 1, 104-118, (2005)
[3]	Bräysy, O.; Gendreau, M., Vehicle routing problem with time windows, part II: metaheuristics, Transportation science, 39, 1, 119-139, (2005)
[4]	Golden B, Raghavan S, Wasil E, editors. The vehicle routing problem, latest advances and new challenges. In: Operations research/computer science interfaces series, vol. 43. Berlin: Springer; 2008. · Zbl 1142.90004
[5]	Jepsen M, Spoorendonk S, Petersen B, Pisinger D. A non-robust branch-and-cut-and-price algorithm for the vehicle routing problem with time windows. Technical Report no. 06/03 ISSN: 0107-8283. Department of Computer Science, University of Copenhagen; 2006.
[6]	Jepsen, M.; Spoorendonk, S.; Petersen, B.; Pisinger, D., Subset-row inequalities applied to the vehicle-routing problem with time windows, INFORMS journal on operations research, 56, 2, 479-511, (2008) · Zbl 1167.90413
[7]	Chabrier, A., Vehicle routing problem with elementary shortest path based column generation, Computers & operations research, 33, 10, 2972-2990, (2006) · Zbl 1086.90048
[8]	Irnich, S.; Villeneuve, D., The shortest path problem with resource constraints and k-cycle elimination, INFORMS journal on computing, 18, 3, 391-406, (2006) · Zbl 1241.90161
[9]	Kallehaugea, B.; Larsenb, J.; Madsena, O.B.G., Lagrangian duality applied to the vehicle routing problem with time windows, Computers & operations research, 33, 5, 1464-1487, (2006) · Zbl 1126.90038
[10]	Solomon, M.M., Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations research, 35, 2, 254-265, (1987) · Zbl 0625.90047
[11]	Gehring H, Homberger J. A parallel hybrid evolutionary metaheuristic for the vehicle routing problem with time windows. In: Proceedings of EUROGEN99, 1999. p. 57-64.
[12]	Mester, D.; Bräysy, O., Active guided evolution strategies for large scale vehicle routing problems with time windows, Computers & operations research, 32, 6, 1593-1614, (2005) · Zbl 1122.90403
[13]	Homberger, J.; Gehring, H., Two-phase hybrid metaheuristic for the vehicle routing problem with time windows, European journal of operational research, 162, 220-238, (2005) · Zbl 1132.90378
[14]	Bent, R.; Hentenryck, P., A two-stage hybrid local search for the vehicle routing problem with time windows, Transportation science, 38, 4, 515-530, (2004)
[15]	Pisinger, D.; Ropke, S., A general heuristic for vehicle routing problems, Computers & operations research, 34, 8, 2403-2435, (2007) · Zbl 1144.90318
[16]	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. · Zbl 1206.90016
[17]	Ibaraki, T.; Kubo, M.; Masuda, T.; Uno, T.; Yagiura, M., Effective local search algorithms for the vehicle routing problem with general time window constraints, Transportation science, 39, 2, 206-232, (2005)
[18]	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 2008; 156(11):2050-69. · Zbl 1153.90446
[19]	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, 3, 443-457, (2007) · Zbl 1241.90051
[20]	Nagata Y. Edge assembly crossover for the capacitated vehicle routing problem. In: Proceedings of the 7th European conference on evolutionary computation in combinatorial optimization, 2007. p. 124-53.
[21]	Moscato P. On evolution, search, optimization, genetic algorithms and martial arts towards memetic algorithms. C3P Report 826, California Institute of Technology; 1989.
[22]	Nagata Y, Bräysy O. A powerful route minimization heuristic for the vehicle routing problem with time windows, Operations Research Letters, in press.
[23]	Nagata Y, Kobayashi S. Edge assembly crossover: a high-power genetic algorithm for the traveling salesman problem. In: Proceedings of the 7th international conference on genetic algorithms, 1997. p. 450-7.
[24]	Nagata Y. Fast EAX algorithm considering population diversity for traveling salesman problems. In: Proceedings of the 6th international conference on EvoCOP2006, 2006. p. 171-82. · Zbl 06858825
[25]	Nagata Y. New EAX crossover for large TSP instances. In: Proceedings of the 9th international conference on parallel problem solving from nature, 2006. p. 372-81.
[26]	Gendreau, M.; Hertz, A.; Laporte, G., A tabu search heuristic for the vehicle routing problem, Management science, 40, 10, 1276-1290, (1994) · Zbl 0822.90053
[27]	Toth, P.; Vigo, D., The granular tabu search and its application to the vehicle routing problem, INFORMS journal on computing, 15, 4, 333-348, (2003) · Zbl 1238.90141
[28]	Badeau, P.; Guertin, F.; Gendreau, M.; Potvin, J.-Y.; Taillard, E.D., A parallel tabu search heuristic for the vehicle routing problem with time windows, Transportation research C-5, 5, 2, 109-122, (1997)
[29]	Berger, J.; Barkoui, M., A parallel hybrid genetic algorithm for the vehicle routing problem with time windows, Computers & operations research, 31, 12, 2037-2053, (2004) · Zbl 1100.90503
[30]	Bouthillier, A.; Crainic, T., A cooperative parallel meta-heuristic for the vehicle routing problem with time windows, Computers & operations research, 32, 7, 1685-1708, (2005) · Zbl 1074.90006
[31]	Nagata Y, Bräysy O. Efficient local search limitation strategies for vehicle routing problems. In: Proceedings of the 8th European conference on evolutionary computation in combinatorial optimization, 2008. p. 48-60.
[32]	Homberger, J.; Gehring, H., Two evolutionary meta-heuristics for the vehicle routing problem with time windows, INFORMS journal on computing, 37, 3, 297-318, (1999)
[33]	Voudouris, C.; Tsang, E., Guided local search, (), 185-218 · Zbl 1102.90385
[34]	Kindervater, G.; Savelsbergh, M., Vehicle routing: handling edge exchanges, (), 337-360 · Zbl 0887.90060
[35]	Potvin, J.-Y.; Rousseau, J.-M., An exchange heuristic for routing problems with time windows, Journal of the operational research society, 46, 1433-1446, (1995) · Zbl 0843.90043