Abstract
This paper describes the parallelization of a two-phase metaheuristic for the vehicle routing problem with time windows and a central depot (VRPTW). The underlying objective function combines the minimization of the number of vehicles in the first search phase of the metaheuristic with the minimization of the total travel distance in the second search phase. The parallelization of the metaheuristic follows a type 3 parallelization strategy (cf. Crainic and Toulouse (2001). In F. Glover and G. Kochenberger (eds.). State-of-the-Art Handbook in Metaheuristics. Norwell, MA: Kluwer Academic Publishers), i.e. several concurrent searches of the solution space are carried out with a differently configured metaheuristic. The concurrently executed processes cooperate through the exchange of solutions. The parallelized two-phase metaheuristic was subjected to a comparative test on the basis of 358 problems from the literature with sizes varying from 100 to 1000 customers. The derived results seem to justify the proposed parallelization concept.
Similar content being viewed by others
References
Chiang, W.-C. and R.A. Russell. (1996). “Simulated Annealing Metaheuristics for the Vehicle Routing Problem with Time Windows.” Annals of Operations Research 63, 3–27.
Chiang, W.-C. and R.A. Russell. (1997). “A Reactive Tabu Search Metaheuristic for the Vehicle Routing Problem with Time Windows.” INFORMS Journal on Computing 9(4), 417–430.
Clarke, G. and J.W. Wright. (1964). “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points.” Operations Research 12, 568–581.
Crainic, T.G. and M. Toulouse. (1998). “Parallel Metaheuristics.” In T.G. Crainic and G. Laporte (eds.), Fleet Management and Logistics. Norwell, MA: Kluwer Academic Publishers, pp. 205–251.
Crainic, T.G. and M. Toulouse. (2001). “Parallel Strategies for Meta-Heuristics.” In F. Glover and G. Kochenberger (eds.), State-of-the-Art Handbook in Metaheuristics. Norwell, MA: Kluwer Academic Publishers, to appear.
Desrochers, M., J.K. Lenstra, M.W.P. Savelsbergh, and F. Soumis. (1988). “Vehicle Routing with TimeWindows: Optimization and Approximation.” In B.L. Golden and A.A. Assad (eds.), Vehicle Routing: Methods and Studies. Amsterdam: Elsevier Sciences Publishers, pp. 65–84.
Enslow, H.P. (1978). “What is a ‘Distributed’ Data Processing System?” Computer 11, 13–21.
Gambardella, L.M., E.D. Taillard, and G. Agazzi. (1999). “MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows.” Technical Report IDSIA-06-99, Istituto Dalle Molle di Studi sull'Intelligenza Artificiale, Lugano, CH.
Garcia, B.-L., J.-Y. Potvin, and J.-M. Rousseau. (1994). “A Parallel Implementation of the Tabu Search Heuristic for Vehicle Routing Problems with Time Window Constraints.” Computers &;; Operations Research 21(9), 1025–1033.
Gehring, H. and J. Homberger. (1999). “A Parallel Hybrid Evolutionary Metaheuristic for the Vehicle Routing Problem with Time Windows.” In K. Miettinen, M.M. Mäkelä, and J. Toivanen (eds.), Proceedings of EUROGEN99—Short Course on Evolutionary Algorithms in Engineering and Computer Science, pp. 57–64. Reports of the Department of Mathematical Information Technology, No. A 2/1999, University of Jyväskylä, Finland.
Gietz, M. (1994). Computergestützte Tourenplanung mit zeitkritischen Restriktionen. Heidelberg: Physica.
Glover, F. (1989). “Tabu Search—Part I.” ORSA Journal on Computing 1(3), 190–206.
Glover, F. (1990). “Tabu Search—Part II.” ORSA Journal on Computing 2(1), 4–32.
Glover, F., J.P. Kelley, and M. Laguna. (1995). “Genetic Algorithms and Tabu Search: Hybrids for Optimization.” Computers &;; Operations Research 22, 111–134.
Glover, F. and M. Laguna. (1993). “Tabu Search.” In C.R. Reeves (ed.), Modern Heuristic Techniques for Combinatorial Problems. Oxford: Blackwell Scientific Publications, pp. 70–150.
Hansen, P. and N. Mladenovic. (1999). “An Introduction toVariable Neighborhood Search.” In S. Voss, S. Martello, I.H. Osman, and C. Roucairol (eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization. Norwell, MA: Kluwer Academic Publishers, pp. 433–458.
Homberger, J. and H. Gehring. (1999). “Two Evolutionary Metaheuristics for the Vehicle Routing Problem with Time Windows.” In G. Laporte and F. Semet (eds.), Metaheuristics for Location and Routing Problems. Information Systems and Operational Research 37(3) (special issue), 297–318.
Lenstra, J.K. and A.H.G. Rinnooy Kan. (1981). “Complexity of Vehicle Routing and Scheduling Problems.” Networks 11, 221–227.
Liu, F.-H. and S.-Y. Shen. (1999). “A Route-Neighborhood-Based Metaheuristic for Vehicle Routing Problem with Time Windows.” European Journal of Operational Research 118, 485–504.
Or, I. (1976). “Traveling Salesman-Type Combinatorial Problems and their Relation to the Logistics of Blood Banking.” Ph.D. thesis, Department of Industrial Engineering and Management Science, Northwestern University, Evanston, IL.
Osman, I.H. (1993). “Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem.” Annals of Operations Research 41, 421–451.
Potvin, J.-Y. and S. Bengio. (1996). “The Vehicle Routing Problem with TimeWindows—Part II: Genetic Search.” INFORMS Journal on Computing 8, 165–172.
Potvin, J.-Y., T. Kervahut, B.-L. Garcia, and J.-M. Rousseau. (1996). “The Vehicle Routing Problem with Time Windows—Part I: Tabu Search.” INFORMS Journal on Computing 8(2), 158–164.
Potvin, J.-Y. and J.M. Rousseau. (1995). “An Exchange Heuristic for Routing Problems with Time Windows.” Journal of the Operational Research Society 46, 1433–1446.
Retzko, R. (1995). Flexible Tourenplanung mit selbstorganisierenden Neuronalen Netzen. Göttingen: Unitext.
Russell, R.A. (1995). “Hybrid Heuristics for the Vehicle Routing Problem with Time Windows.” Transportation Science 29(2), 156–166.
Schulze, J. and T. Fahle. (1999). “A Parallel Algorithm for the Vehicle Routing Problem with Time Window Constraints.” In J.E. Beasley and Y.M. Sharaiha (eds.), Combinatorial Optimization: Recent Advances in Theory and Praxis, Annals of Operations Research 86 (special issue), pp. 585–607.
Schütz, G. (1997). Verteilt-parallele Ansätze zur Distributionsplanung. Wiesbaden: Gabler.
Solomon, M.M. (1987). “Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints.” Operations Research 35, 254–265.
Solomon, M.M., E.K. Baker, and J.R. Schaffer. (1988). “Vehicle Routing and Scheduling Problems with Time WindowConstraints: Efficient Implementations of Solution Improvement Procedures.” In B.L. Golden and A.A. Assad (eds.), Vehicle Routing: Methods and Studies. Amsterdam: Elsevier Science Publishers, pp. 85–105.
Solomon, M.M. and J. Desrosiers. (1988). “TimeWindow Constrained Routing and Scheduling Problems.” Transportation Science 22, 1–13.
Taillard, E.D. (1993). “Parallel Iterative Search Methods for Vehicle Routing Problems.” Networks 23, 661–673.
Taillard, E.D., P. Badeau, M. Gendreau, F. Guertin, and J.-Y. Potvin. (1996). “A Tabu Search Heuristic for the Vehicle Routing Problem with Soft Time Windows.” Technical report CRT-95-66, Centre de recherche sur les transports, Université de Montréal, Montréal, Canada.
Thangiah, S.R., K.E. Nygard, and P.L. Juell. (1991). “GIDEON: A Genetic Algorithm System for Vehicle Routing with Time Windows.” In Proceedings of the 7th Conference on Artificial Intelligence for Applications. Miami, FL: IEEE Press, pp. 322–328.
Thangiah, S.R., I.H. Osman, and T. Sun. (1995). “Hybrid Genetic Algorithms, Simulated Annealing and Tabu Search Methods for Vehicle Routing Problems with TimeWindows.” Technical Report UKC/OR94/4, Institute of Mathematics &;; Statistics, University of Kent, Canterbury, UK.
Toulouse, M., T.G. Cranic, and M. Gendreau. (1996). “Issues in Designing Parallel and Distributed Search Algorithms for Discrete Optimization Problems.” Publication CRT-96-36, Centre de recherche sur les transports, Université de Montréal, Montréal, Canada.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Gehring, H., Homberger, J. Parallelization of a Two-Phase Metaheuristic for Routing Problems with Time Windows. Journal of Heuristics 8, 251–276 (2002). https://doi.org/10.1023/A:1015053600842
Issue Date:
DOI: https://doi.org/10.1023/A:1015053600842