×

A cooperative parallel meta-heuristic for the vehicle routing problem with time windows. (English) Zbl 1074.90006

Summary: This paper presents a parallel cooperative multi-search method for the vehicle routing problem with time windows. It is based on the solution warehouse strategy, in which several search threads cooperate by asynchronously exchanging information on the best solutions identified. The exchanges are performed through a mechanism, called solution warehouse, which holds and manages a pool of solutions. This enforces the asynchronous strategy of information exchanges and ensures the independence of the individual search processes. Each of these independent processes implements a different meta-heuristic, an evolutionary algorithm or a tabu search procedure. No attempt has been made to calibrate the individual procedures or the parallel cooperative method. The results obtained on an extended set of test problems show that the parallel procedure achieves linear accelerations and identifies solutions of comparable quality to those obtained by the best methods in the literature.

MSC:

90B20 Traffic problems in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Crainic, T. G., Parallel computation, co-operation, tabu search, (Rego, C.; Alidaee, B., Adaptive memory and evolution: tabu search and scatter search (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA) · Zbl 1072.90055
[2] Crainic, T. G.; Gendreau, M., Towards an evolutionary method—cooperating multi-thread parallel tabu search hybrid, (Voß, S.; Martello, S.; Roucairol, C.; Osman, I. H., Meta-heuristics: Advances and Trends in Local Search Paradigms for Optimization (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA), 331-344 · Zbl 0970.90121
[3] Crainic, T. G.; Gendreau, M., Cooperative parallel tabu search for capacitated network design, Journal of Heuristics, 8, 6, 601-627 (2002)
[4] Crainic, T. G.; Toulouse, M., Parallel metaheuristics, (Crainic, T. G.; Laporte, G., Fleet management and logistics (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA), 205-251 · Zbl 0985.90094
[5] Crainic, T. G.; Toulouse, M., Parallel strategies for meta-heuristics, (Glover, F.; Kochenberger, G., State-of-the-art handbook in metaheuristics (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA), 475-513 · Zbl 1053.90138
[6] Crainic, T. G.; Toulouse, M.; Gendreau, M., Parallel asynchronous tabu search for multicommodity location-allocation with balancing requirements, Annals of Operations Research, 63, 277-299 (1995) · Zbl 0851.90033
[7] Cung, V.-. D.; Martins, S. L.; Ribeiro, C. C.; Roucairol, C., Strategies for the parallel implementations of metaheuristics, (Ribeiro, C.; Hansen, P., Essays and surveys in metaheuristics (2001), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA), 263-308 · Zbl 1005.90066
[8] Garcia, B. L.; Potvin, J.-. Y.; Rousseau, J. M., A parallel implementation of the tabu search heuristic for vehicle routing problems with time window constraints, Computers & Operations Research, 21, 9, 1025-1033 (1994) · Zbl 0815.90067
[9] Gambardella L, Taillard ÉD, Agazzi G. MACS-VRPTW: a multiple ant colony system for vehicle routing problems with time windows. Technical report IDSIA-9-99, IDSIA, Lugano, Switzerland, 1999.; Gambardella L, Taillard ÉD, Agazzi G. MACS-VRPTW: a multiple ant colony system for vehicle routing problems with time windows. Technical report IDSIA-9-99, IDSIA, Lugano, Switzerland, 1999.
[10] Homberger, J.; Gehring, H., Two evolutionary metaheuristics for the vehicle routing problem with time windows, INFOR, 37, 297-318 (1999) · Zbl 07677595
[11] Gehring, H.; Homberger, J., A parallel two-phase metaheuristic for routing problems with time windows, Asia-Pacific Journal of Operational Research, 18, 1, 35-47 (2001)
[12] Schulze, J.; Fahle, T., A parallel algorithm for the vehicle routing problem with time window constraints, Annals of Operations Research, 86, 585-607 (1999) · Zbl 0922.90059
[13] Taillard, É. D.; Gambardella, L. M.; Gendreau, M.; Potvin, J.-. Y., Programmation à mémoire adaptative, Calculateurs Parallèles, Réseaux et Systèmes répar tis, 10, 117-140 (1998)
[14] Taillard ÉD. Recherches itératives dirigées parallèles. Ph.D. thesis, École Polytechnique Fédérale de Lausanne, 1993.; Taillard ÉD. Recherches itératives dirigées parallèles. Ph.D. thesis, École Polytechnique Fédérale de Lausanne, 1993.
[15] Toulouse M, Crainic TG, Sansó B, Thulasiraman K. Self-organization in cooperative search algorithms. In: Proceedings of the 1998 IEEE International Conference on Systems, Man, and Cybernetics, Madisson, Wisconsin: Omnipress; 1998. p. 2379-85.; Toulouse M, Crainic TG, Sansó B, Thulasiraman K. Self-organization in cooperative search algorithms. In: Proceedings of the 1998 IEEE International Conference on Systems, Man, and Cybernetics, Madisson, Wisconsin: Omnipress; 1998. p. 2379-85.
[16] Cordeau J-F, Desaulniers G, Desrosiers J, Solomon MM, Soumis F. The VRP with time windows. In: Toth P, Vigo D. editors. The vehicle routing problem, SIAM, Monographs on Discrete Mathematics and Applications, Philadelphia, PA: SIAM; 2002a. p. 157-93, [chapter 7].; Cordeau J-F, Desaulniers G, Desrosiers J, Solomon MM, Soumis F. The VRP with time windows. In: Toth P, Vigo D. editors. The vehicle routing problem, SIAM, Monographs on Discrete Mathematics and Applications, Philadelphia, PA: SIAM; 2002a. p. 157-93, [chapter 7]. · Zbl 1076.90543
[17] Bräysy, O.; Gendreau, M., Tabu search heuristics for the vehicle routing problem with time windows, Top, 10, 2, 211-238 (2002), (see http://top.umh.es/issue10-2.html) · Zbl 1038.90005
[18] Cordeau J-F, Gendreau M, Laporte G, Potvin J-Y, Semet F. A guide to vehicle routing heuristics. Journal of the Operational Research Society 2002b;53:512-22.; Cordeau J-F, Gendreau M, Laporte G, Potvin J-Y, Semet F. A guide to vehicle routing heuristics. Journal of the Operational Research Society 2002b;53:512-22. · Zbl 1099.90506
[19] Christofides, N.; Mingozzi, A.; Toth, P., The vehicle routing problem, (Christofides, N. A.M.; Toth, P.; Sandi, C., Combinatorial Optimization (1979), Wiley: Wiley New York), 315-338
[20] Desrosiers, J.; Dumas, Y.; Solomon, M. M.; Soumis, F., Time constrained routing and scheduling, (Ball, M.; Magnanti, T. L.; Monma, C. L.; Nemhauser, G. L., Network routing. Network routing, Handbooks in operations research and management science, vol. 8 (1995), North-Holland: North-Holland Amsterdam), 35-139 · Zbl 0861.90052
[21] Desaulniers, G.; Desrosiers, J.; Ioachim, I.; Solomon, M. M.; Soumis, F.; Villeneuve, D., A unified framework for deterministic time constrained vehicle routing and crew scheduling problems, (Crainic, T. G.; Laporte, G., Fleet management and logistics (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA), 57-93 · Zbl 0966.90007
[22] Fisher, M. L., Vehicle routing, (Ball, M.; Magnanti, T. L.; Monma, C. L.; Nemhauser, G. L., Network routing. Network routing, Handbooks in operations research and management science, vol. 8 (1995), North-Holland: North-Holland Amsterdam), 1-33 · Zbl 0870.90058
[23] Gendreau, M.; Laporte, G.; Potvin, J.-. Y., Metaheuristics for the vehicle routing problem, (Toth, P.; Vigo, D., The vehicle routing problem. The vehicle routing problem, SIAM Monographs on Discrete Mathematics and Applications, vol. 9 (2002), SIAM: SIAM Philadelphia, PA), 129-154 · Zbl 1076.90545
[24] Golden BL, Assad AA, editors. Vehicle routing: methods and studies. Amsterdam: North-Holland; 1988.; Golden BL, Assad AA, editors. Vehicle routing: methods and studies. Amsterdam: North-Holland; 1988.
[25] Golden, B. L.; Wasil, E. A.; Kelly, J. P.; Chao, I. M., Metaheuristics in vehicle routing, (Crainic, T.; Laporte, G., Fleet management and logistics (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Boston, MA), 33-56 · Zbl 0997.90021
[26] Laporte, G., The vehicle routing probleman overview of exact and approximate algorithms, European Journal of Operational Research, 59, 345-358 (1992) · Zbl 0761.90034
[27] Laporte, G.; Semet, F., Classical heuristics for the vehicle routing problem, (Toth, P.; Vigo, D., The vehicle routing problem. The vehicle routing problem, SIAM Monographs on Discrete Mathematics and Applications, vol. 9 (2002), SIAM: SIAM Philadelphia, PA), 109-128 · Zbl 1076.90549
[28] Laporte, G.; Gendreau, M.; Potvin, J.-. Y.; Semet, F., Classical and modern heuristics for the vehicle routing problem, International Transactions in Operational Research, 7, 4/5, 285-300 (2000)
[29] Toth, P.; Vigo, D., Exact solution of the vehicle routing problem, (Crainic, T. G.; Laporte, G., Fleet management and logistics (1998), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA), 1-31 · Zbl 0966.90009
[30] Toth P, Vigo D, editors. The vehicle routing problem. SIAM Monographs on Discrete Mathematics and Applications, vol. 9. Philadelphia, PA: SIAM; 2002.; Toth P, Vigo D, editors. The vehicle routing problem. SIAM Monographs on Discrete Mathematics and Applications, vol. 9. Philadelphia, PA: SIAM; 2002. · Zbl 0979.00026
[31] Aiex RM, Martins SL, Ribeiro CC, Rodriguez NR. Cooperative multi-thread parallel tabu search with an application to circuit partitioning. In: Proceedings of IRREGULAR’98—Fifth International Symposium on Solving Irregularly Structured Problems in Parallel, Lecture Notes in Computer Science, vol. 1457. Berlin: Springer; 1998. p. 310-31.; Aiex RM, Martins SL, Ribeiro CC, Rodriguez NR. Cooperative multi-thread parallel tabu search with an application to circuit partitioning. In: Proceedings of IRREGULAR’98—Fifth International Symposium on Solving Irregularly Structured Problems in Parallel, Lecture Notes in Computer Science, vol. 1457. Berlin: Springer; 1998. p. 310-31.
[32] Solomon, M. M., Time window constrained routing and scheduling problems, Operations Research, 35, 254-265 (1987) · Zbl 0625.90047
[33] Chabrier A. Vehicle routing problem with elementary shortest path based column generation. Working paper, ILOG, Madrid: Spain; 2002.; Chabrier A. Vehicle routing problem with elementary shortest path based column generation. Working paper, ILOG, Madrid: Spain; 2002.
[34] Cook W, Rich JL. A parallel cutting plane algorithm for the vehicle routing problem with time windows. Working paper, Computational and Applied Mathematics, Rice University, Houston, TX, 1999.; Cook W, Rich JL. A parallel cutting plane algorithm for the vehicle routing problem with time windows. Working paper, Computational and Applied Mathematics, Rice University, Houston, TX, 1999.
[35] Kallehauge B, Larsen J, Madsen OBG. Lagrangean duality and non-differentiable optimization applied on routing with time windows—experimental results. Internal report imm-rep-2000-8, Department of Mathematical Modelling, Technical University of Denmark, Lyngby, Denmark, 2000.; Kallehauge B, Larsen J, Madsen OBG. Lagrangean duality and non-differentiable optimization applied on routing with time windows—experimental results. Internal report imm-rep-2000-8, Department of Mathematical Modelling, Technical University of Denmark, Lyngby, Denmark, 2000.
[36] Larsen J. Parellellization of the vehicle routing problem with time windows. Ph.D. thesis, Department of Mathematical Modelling, Technical University of Denmark, Lyngby, Denmark, 1999.; Larsen J. Parellellization of the vehicle routing problem with time windows. Ph.D. thesis, Department of Mathematical Modelling, Technical University of Denmark, Lyngby, Denmark, 1999.
[37] 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
[38] Glover, F., Tabu search—Part I, ORSA Journal on Computing, 1, 3, 190-206 (1989) · Zbl 0753.90054
[39] Glover, F., Tabu search—Part II, ORSA Journal on Computing, 2, 1, 4-32 (1990) · Zbl 0771.90084
[40] Glover, F.; Laguna, M., Tabu search (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA · Zbl 0930.90083
[41] Gendreau, M.; Hertz, A.; Laporte, G., A tabu search heuristic for the vehicle routing problem, Management Science, 40, 1276-1290 (1994) · Zbl 0822.90053
[42] 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
[43] Rousseau, L.-. M.; Gendreau, M.; Pesant, G., Using constraint-based operators with variable neighborhood search to solve the vehicle routing problem with time windows, Journal of Heuristics, 8, 1, 43-58 (2002) · Zbl 1073.90056
[44] Mladenović, N.; Hansen, P., Variable neighborhood search, Computers & Operations Research, 24, 1097-1100 (1997) · Zbl 0889.90119
[45] Hansen, P.; Mladenović, N., An introduction to variable neighborhood search, (Voß, S.; Martello, S.; Roucairol, C.; Osman, I. H., Meta-heuristics 98: theory and applications (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA), 433-458 · Zbl 0985.90095
[46] Hansen, P.; Mladenović, N., Developments of variable neighborhood search, (Ribeiro, C.; Hansen, P., Essays and surveys in metaheuristics (2002), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA), 415-439 · Zbl 1017.90130
[47] Bräysy, O., A reactive variable neighborhood search algorithm for the vehicle routing problem with time windows, INFORMS Journal on Computing, 15, 4, 347-368 (2003) · Zbl 1238.90136
[48] Bräysy O, Hasle G, Dullaert W. A multi-start local search algorithm for the vehicle routing problem with time windows. European Journal of Operational Research, In Press, corrected proof available online 8th October 2003.; Bräysy O, Hasle G, Dullaert W. A multi-start local search algorithm for the vehicle routing problem with time windows. European Journal of Operational Research, In Press, corrected proof available online 8th October 2003.
[49] Taillard, É. D.; 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, 2, 170-186 (1997) · Zbl 0886.90070
[50] Bräysy, O.; Dullaert, W., A fast evolutionary metaheuristic for the vehicle routing problem with time windows, International Journal on Artificial Intelligence, 12, 2, 153-172 (2003)
[51] Bent R, Van Hentenryck P. A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Science, to appear.; Bent R, Van Hentenryck P. A two-stage hybrid local search for the vehicle routing problem with time windows. Transportation Science, to appear. · Zbl 1079.90591
[52] Shaw, P., Using constraint programming and local search methods to solve vehicle routing problems, Lecture Notes in Computer Science, 1520, 417-431 (1998)
[53] Rochat, Y.; Taillard, É. D., Probabilistic diversification and intensification in local search for vehicle routing, Journal of Heuristics, 1, 1, 147-167 (1995) · Zbl 0857.90032
[54] Badeau, P.; Guertin, F.; Gendreau, M.; Potvin, J.-. Y.; Taillard, É. D., A parallel tabu search heuristic for the vehicle routing problem with time windows, Transportation Research C: Emerging Technologies, 5, 2, 109-122 (1997)
[55] Homberger J. Verteilt-parallele metaheuristiken zur tourenplanung. Technical report, Gaber, Wiesbaden, 2000.; Homberger J. Verteilt-parallele metaheuristiken zur tourenplanung. Technical report, Gaber, Wiesbaden, 2000.
[56] 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.
[57] Toulouse, M.; Crainic, T. G.; Gendreau, M., Communication issues in designing cooperative multi thread parallel searches, (Osman, I. H.; Kelly, J. P., Meta-heuristics: theory & applications (1996), Kluwer Academic Publishers: Kluwer Academic Publishers Norwell, MA), 501-522 · Zbl 0877.90067
[58] Gendreau, M.; Hertz, A.; Laporte, G., New insertion and postoptimization procedures for the traveling salesman problem, Operations Research, 40, 6, 1086-1094 (1992) · Zbl 0767.90087
[59] Gendreau, M.; Hertz, A.; Laporte, G.; Stan, M., A generalized insertion heuristic for the traveling salesman problem with time windows, Operations Research, 46, 3, 330-335 (1998) · Zbl 0987.90070
[60] Glover F. Multilevel tabu search and embedded search neighborhoods for the traveling salesman problem. Working paper, College of Business & Administration, University of Colorado, USA, 1991.; Glover F. Multilevel tabu search and embedded search neighborhoods for the traveling salesman problem. Working paper, College of Business & Administration, University of Colorado, USA, 1991.
[61] Glover, F., Ejection chains, reference structures and alternating path methods for traveling salesman problems, Discrete Applied Mathematics, 49, 231-255 (1992)
[62] Rego, C., A subpath ejection method for the vehicle routing problem, Management Science, 44, 1447-1459 (1998) · Zbl 0989.90522
[63] Rego, C., Node ejection chains for the vehicle routing problemsequential and parallel algorithms, Parallel Computing, 27, 201-222 (2001) · Zbl 0969.68176
[64] Caseau, Y.; Laburthe, F., Heuristics for large constrained vehicle routing problems, Journal of Heuristics, 5, 281-303 (1999) · Zbl 1064.90508
[65] Kindervater G, Savelsbergh M. Vehicle routing: handling edge exchanges. In: Aarts E, Lenstra JK, editors. Local search in combinatorial optimization, New York: Wiley; 1997. p. 337-60, [chapter 10].; Kindervater G, Savelsbergh M. Vehicle routing: handling edge exchanges. In: Aarts E, Lenstra JK, editors. Local search in combinatorial optimization, New York: Wiley; 1997. p. 337-60, [chapter 10]. · Zbl 0887.90060
[66] De Backer, B.; Furnon, V.; Shaw, P.; Kilby, P.; Prosser, P., Solving vehicle routing problems using constraint programming and metaheuristics, Journal of Heuristics, 6, 501-523 (2000) · Zbl 0972.68631
[67] Bentley, J., Fast algorithms for geometric traveling salesman problems, ORSA Journal on Computing, 4, 4, 388-411 (1992) · Zbl 0758.90071
[68] Le Bouthillier A, Crainic TG. Cooperative parallel method for vehicle routing problems with time windows. Publication CRT-00-55, Centre de recherche sur les transports, Université de Montréal, Montréal, QC, Canada, 2002.; Le Bouthillier A, Crainic TG. Cooperative parallel method for vehicle routing problems with time windows. Publication CRT-00-55, Centre de recherche sur les transports, Université de Montréal, Montréal, QC, Canada, 2002.
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.