A parallel hybrid genetic algorithm for the vehicle routing problem with time windows. (English) Zbl 1100.90503

Berger, Jean; Barkaoui, Mohamed

Comput. Oper. Res. 31, No. 12, 2037-2053 (2004).

Summary: A parallel version of a new hybrid genetic algorithm for the vehicle routing problem with time windows is presented. The route-directed hybrid genetic approach is based upon the simultaneous evolution of two populations of solutions focusing on separate objectives subject to temporal constraint relaxation. While the first population evolves individuals to minimize total traveled distance the second aims at minimizing temporal constraint violation to generate a feasible solution. Genetic operators have been designed to capture key concepts from successful routing techniques to further enhance search diversification and intensification. A master–slave message-passing paradigm characterizes the parallel procedure. The master component controls the execution of the algorithm, coordinates genetic operations and handles parent selection while the slave elements concurrently execute reproduction and mutation operators. Providing additional speed-up, the parallel algorithm further expands on its sequential counterpart, matching or even improving solution quality. Computational results show the proposed technique to be very competitive with the best-known heuristic routing procedures providing some new best-known solutions.

MSC:

90B06	Transportation, logistics and supply chain management
90C59	Approximation methods and heuristics in mathematical programming

Software:

MACS-VRPTW; VRP; GALib

References:

[5]	Holland, J. H., Adaptation in natural and artificial systems (1975), University of Michigan Press, Ann Arbor: University of Michigan Press, Ann Arbor Ann Arbor
[7]	Goldberg, D. E., Genetic algorithms in search, optimization, and machine learning (1989), Addison-Wesley: Addison-Wesley New York · Zbl 0721.68056
[8]	Blanton, J. L.; Wainwright, R. L., Multiple vehicle routing with time and capacity constraints using genetic algorithms, (Forrest, S., Proceedings of the 5th International Conference on Genetic Algorithms (1993), Morgan Kaufmann: Morgan Kaufmann San Francisco), 452-459
[10]	Thangiah, S. R., An adaptive clustering method using a geometric shape for vehicle routing problems with time windows, (Eshelman, L. J., Proceedings of the 6th International Conference on Genetic Algorithms (1995), Morgan Kaufmann: Morgan Kaufmann San Francisco), 536-543
[11]	Thangiah, S. R.; Osman, I. H.; Vinayagamoorthy, R.; Sun, T., Algorithms for the vehicle routing problems with time deadlines, American Journal of Mathematical and Management Sciences, 13, 323-355 (1995) · Zbl 0808.90064
[12]	Potvin, J.-. Y.; Bengio, S., The vehicle routing problem with time windows Part IIgenetic search, INFORMS Journal on Computing, 8, 165-172 (1996) · Zbl 0866.90058
[16]	Homberger, J.; Gehring, H., Two evolutionary metaheuristics for the vehicle routing problem with time windows, INFOR, 37, 297-318 (1999) · Zbl 07677595
[18]	Osman, I. H., Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Annals of Operations Research, 41, 421-451 (1993) · Zbl 0775.90153
[19]	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
[21]	Gehring, H.; Homberger, J., Parallelization of a two-phase metaheuristic for routing problems with time windows, Asia-Pacific Journal of Operational Research, 18, 35-47 (2001)
[23]	Tan, K. C.; Lee, L. H.; Ou, K., Hybrid genetic algorithms in solving vehicle routing problems with time window constraints, Asia-Pacific Journal of Operational Research, 18, 121-130 (2001) · Zbl 1042.90654
[24]	Solomon, M. M., Algorithms for the vehicle routing and scheduling problems with time window constraints, Operations Research, 35, 254-265 (1987) · Zbl 0625.90047
[25]	Rochat, Y.; Taillard, E., Probabilistic diversification and intensification in local search for vehicle routing, Journal of Heuristics, 1, 147-167 (1995) · Zbl 0857.90032
[26]	Taillard, E.; Badeau, P.; Gendreau, M.; Guertin, F.; Potvin, J.-. Y., A tabu search heuristic for the vehicle routing problem with soft time windows, Transportation Science, 31, 170-186 (1997) · Zbl 0886.90070
[27]	Chiang, W.-. C.; Russell, R. A., A reactive tabu search metaheuristic for the vehicle routing problem with time windows, INFORMS Journal on Computing, 9, 417-430 (1997) · Zbl 0901.90088
[28]	Cordeau, J.-. F.; Laporte, G.; Mercier, A., A unified tabu search heuristic for vehicle routing problems with time windows, Journal of the Operational Research Society, 52, 928-936 (2001) · Zbl 1181.90034
[29]	Gambardella, L. M.; Taillard, E.; Agazzi, G., MACS-VRPTW: a multiple ant colony system for vehicle routing problems with time windows, (Corne, D.; Dorigo, M.; Glover, F., New ideas in optimization (1999), McGraw-Hill: McGraw-Hill London), 63-76
[30]	Liu, F.-. H.; Shen, S.-. Y., A route-neighborhood-based metaheuristic for vehicle routing problem with time windows, European Journal of Operational Research, 118, 485-504 (1999) · Zbl 0945.90007
[31]	Shaw, P., Using constraint programming and local search methods to solve vehicle routing problems, (Maher, M.; Puget, J.-. F., Principles and practice of constraint programming, Lecture Notes in Computer Science (1998), Springer: Springer New York), 417-431
[35]	Rousseau, L.-. M.; Gendreau, M.; Pesant, G., Using constraint-based operators to solve the vehicle routing problem with time windows, Journal of Heuristics, 8, 43-58 (2002) · Zbl 1073.90056