×

A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows. (English) Zbl 1163.90357

Summary: The Vehicle Routing Problem with Time Windows (VRPTW) is a well-known and complex combinatorial problem, which has received considerable attention in recent years. This problem has been addressed using many different techniques including both exact and heuristic methods. The VRPTW benchmark problems of M. M. Solomon [Oper. Res. 35, 254–262 (1987; Zbl 0625.90047)] have been most commonly chosen to evaluate and compare all algorithms. Results from exact methods have been improved considerably because of parallel implementations and modern branch-and-cut techniques. However, 24 out of the 56 high order instances from Solomon’s original test set still remain unsolved. Additionally, in many cases a prohibitive time is needed to find the exact solution. Many of the heuristic methods developed have proved to be efficient in identifying good solutions in reasonable amounts of time. Unfortunately, whilst the research efforts based on exact methods have been focused on the total travel distance, the focus of almost all heuristic attempts has been on the number of vehicles. Consequently, it is more difficult to compare and take advantage of the strong points from each approach. This paper proposes a robust heuristic approach for the VRPTW using travel distance as the main objective through an efficient genetic algorithm and a set partitioning formulation. The tests were produced using real numbers and truncated data type, allowing a direct comparison of its results against previously published heuristic and exact methods. Furthermore, computational results show that the proposed heuristic approach outperforms all previously known and published heuristic methods in terms of the minimal travel distance.

MSC:

90B06 Transportation, logistics and supply chain management
90B10 Deterministic network models in operations research
90C59 Approximation methods and heuristics in mathematical programming
90B35 Deterministic scheduling theory in operations research

Citations:

Zbl 0625.90047
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Rochat, Y.; Taillard, E. D., Probabilistic diversification and intensification in local search for vehicle routing, Journal of Heuristics, 1, 147-167 (1995) · Zbl 0857.90032
[2] Berger, J.; Barkaoui, M.; Bräysy, O., A route-directed hybrid GA approach for the VRPTW, Information Systems and Operational Research, 41, 179-194 (2003) · Zbl 07682301
[3] Homberger J, Gehring H. Two evolutionary metaheuristics for the vehicle routing problem with time windows. INFOR, vol. 37, 1999. pp. 297-318.; Homberger J, Gehring H. Two evolutionary metaheuristics for the vehicle routing problem with time windows. INFOR, vol. 37, 1999. pp. 297-318. · Zbl 07677595
[4] Best known solutions identified by heuristics for Solomon’s benchmark problems. TOP—improved optimization methods in transportation logistics. www.top.sintef.no/vrp/index.htm; Best known solutions identified by heuristics for Solomon’s benchmark problems. TOP—improved optimization methods in transportation logistics. www.top.sintef.no/vrp/index.htm
[5] Rousseau LM. Gendreau M, Pesant G. Using constraint-based operators with variable neighborhood search to solve the vehicle routing problem with time windows. Presented at the CP-AI-OR’99 Workshop, February 25-26, University of Ferrara, Italy, 1999.; Rousseau LM. Gendreau M, Pesant G. Using constraint-based operators with variable neighborhood search to solve the vehicle routing problem with time windows. Presented at the CP-AI-OR’99 Workshop, February 25-26, University of Ferrara, Italy, 1999.
[6] Tan, K. C.; Lee, L. H.; Zhu, Q. L.; Ou, K., Heuristic methods for vehicle routing problem with time windows, Artificial Intelligence in Engineering, 15, 281-295 (2001)
[7] Achutan, N.; Cacetta, L.; Hill, S., An improved branch-and-cut algorithm for the capacitated vehicle routing problem, Tansportation Science, 37, 153-169 (2003)
[8] Ralphs, T.; Kopman, L.; Pulleyblank, W.; Trotter, L., On the capacitated vehicle routing problem, Mathematical Programming, 94, 343-359 (2003) · Zbl 1030.90131
[9] Larsen J. Parallelization of the vehicle routing problem with time windows. Ph.D. Thesis, IMM-PHD-1999-62, Department of Mathematical Modelling, Technical University of Denmark, Lyngby, Denmark, 1999.; Larsen J. Parallelization of the vehicle routing problem with time windows. Ph.D. Thesis, IMM-PHD-1999-62, Department of Mathematical Modelling, Technical University of Denmark, Lyngby, Denmark, 1999.
[10] Kohl, N.; Desrosiers, J.; Madsen, O. B.G.; Solomon, M. M.; Soumis, F., 2-Path cuts for the vehicle routing problem with time windows, Transportation Science, 33, 1, 101-116 (1999) · Zbl 1004.90015
[11] 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
[12] Whitley, D., A genetic algorithm tutorial, Statistics and Computing, 4, 65-85 (1994)
[13] Fraser, A. S., Simulation of genetic system by automatic digital computers, Australian Journal of Biological Science, 10, 484-491 (1957)
[14] Box, G. E.P., Evolutionary operation: a method of increasing industrial productivity, Applied Statistics, 6, 81-101 (1957)
[15] Forgel, L. J.; Owens e, A. J.; Walsh, M. J., Artificial intelligence through simulated evolution (1966), Wiley: Wiley New York · Zbl 0148.40701
[16] Rochenberg, I., Evolutions strategie: Optimierung Technischer Systeme nach Prinzipien der Biologischen Evolution (1973), Frommann-Holzboog: Frommann-Holzboog Stuttgart
[17] Holland JH. Adaptation in natural and artificial system. Ann Arbor, Michigan: The University of Michigan Press; 1975.; Holland JH. Adaptation in natural and artificial system. Ann Arbor, Michigan: The University of Michigan Press; 1975. · Zbl 0317.68006
[18] Darwin, C., On the origin of species (1859), Harvard University Press: Harvard University Press MA
[19] Thangiah SR, Osman IH, Sun T. Hybrid genetic algorithm simulated annealing and tabu search methods for vehicle routing problem with time windows, Technical Report 27, Computer Science Department, Slippery Rock University, 1994.; Thangiah SR, Osman IH, Sun T. Hybrid genetic algorithm simulated annealing and tabu search methods for vehicle routing problem with time windows, Technical Report 27, Computer Science Department, Slippery Rock University, 1994.
[20] Homberger, J., Verteilt-parallele Metaheuristiken zur Tourenplanung (2000), Gaber: Gaber Wiesbaden
[21] Homberger, J.; Gehring, H., Parallelization of a two-phase metaheuristic for routing problems with time windows, Journal of Heuristics, 8, 251-276 (2002) · Zbl 1012.68793
[22] Mester D. An evolutionary strategies algorithm for large scale vehicle routing problem with capacitate and time windows restrictions. Working Paper, Institute of Evolution, University of Haifa, Israel, 2002.; Mester D. An evolutionary strategies algorithm for large scale vehicle routing problem with capacitate and time windows restrictions. Working Paper, Institute of Evolution, University of Haifa, Israel, 2002.
[23] Bent R, Van Hentenryck P. A two-stage hybrid local search for the vehicle routing problem with time windows. Technical Report CS-01-06, Department of Computer Science, Brown University, 2001.; Bent R, Van Hentenryck P. A two-stage hybrid local search for the vehicle routing problem with time windows. Technical Report CS-01-06, Department of Computer Science, Brown University, 2001. · Zbl 1079.90591
[24] Schrimpf, G.; Schneider, J.; Stamm-Wilbrandt, H.; Dueck, G., Record breaking optimization results using the ruin and recreate principle, Journal of Computational Physics, 159, 139-171 (2000) · Zbl 0997.90105
[25] Shaw P. A new local search algorithm providing high quality solutions to vehicle routing problems. Working Paper, University of Strathclyde, Glasgow, Scotland, 1997.; Shaw P. A new local search algorithm providing high quality solutions to vehicle routing problems. Working Paper, University of Strathclyde, Glasgow, Scotland, 1997.
[26] Berger J, Barkaoui M, Bräysy O. A parallel hybrid genetic algorithm for the vehicle routing problem with time windows. Working paper, Defense Research Establishment Valcartier, Canada, 2001.; Berger J, Barkaoui M, Bräysy O. A parallel hybrid genetic algorithm for the vehicle routing problem with time windows. Working paper, Defense Research Establishment Valcartier, Canada, 2001.
[27] Shaw P. Using constraint programming and local search methods to solve vehicle routing problems. In Principles and Practice of Constraint Programming—CP98, Pisa, Italy, 1998.; Shaw P. Using constraint programming and local search methods to solve vehicle routing problems. In Principles and Practice of Constraint Programming—CP98, Pisa, Italy, 1998.
[28] Czech ZJ, Czarnas P. A parallel simulated annealing for the vehicle routing problem with time windows. Proceedings of the tenth euromicro workshop on parallel, distributed and network-based processing, Canary Islands, Spain, 2002, p. 376-83.; Czech ZJ, Czarnas P. A parallel simulated annealing for the vehicle routing problem with time windows. Proceedings of the tenth euromicro workshop on parallel, distributed and network-based processing, Canary Islands, Spain, 2002, p. 376-83.
[29] Cordeau J-F, Laporte G, Mercier A. A unified tabu search heuristic for vehicle routing problems with time windows. Working Paper CRT-00-03, Centre for Research on Transportation, Montreal, Canada, 2000.; Cordeau J-F, Laporte G, Mercier A. A unified tabu search heuristic for vehicle routing problems with time windows. Working Paper CRT-00-03, Centre for Research on Transportation, Montreal, Canada, 2000.
[30] Taillard, E.; Badeau, P.; Gendreau, M.; Geurtin, F.; Potvin, J. Y., A tabu search heuristic for the vehicle routing problem with time windows, Transportation Science, 31, 170-186 (1997) · Zbl 0886.90070
[31] Ibaraki T, Kubo M, Masuda T, Uno T, Yagiura M. Effective local search algorithms for the vehicle routing problem with general time windows. Working Paper, Department of Applied Mathematics and Physics, Kyoto University, Japan, 2001.; Ibaraki T, Kubo M, Masuda T, Uno T, Yagiura M. Effective local search algorithms for the vehicle routing problem with general time windows. Working Paper, Department of Applied Mathematics and Physics, Kyoto University, Japan, 2001.
[32] Kilby P, Prosser P, Shaw P. Guided Local Search for the Vehicle Routing Problem. Second International Conference on Metaheuristics—MIC97, 1997.; Kilby P, Prosser P, Shaw P. Guided Local Search for the Vehicle Routing Problem. Second International Conference on Metaheuristics—MIC97, 1997. · Zbl 0985.90019
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.