×

zbMATH — the first resource for mathematics

A parallel heuristic for the vehicle routing problem with simultaneous pickup and delivery. (English) Zbl 1188.90041
Summary: This paper presents a parallel approach for solving the Vehicle Routing Problem with Simultaneous Pickup and Delivery (VRPSPD). The parallel algorithm is embedded with a multi-start heuristic which consists of a variable neighborhood descent procedure, with a random neighborhood ordering (RVND), integrated in an iterated local search (ILS) framework. The experiments were performed in a cluster with a multi-core architecture using up to 256 cores. The results obtained on the benchmark problems, available in the literature, show that the proposed algorithm not only improved several of the known solutions, but also presented a very satisfying scalability.

MSC:
90B06 Transportation, logistics and supply chain management
68W10 Parallel algorithms in computer science
90C59 Approximation methods and heuristics in mathematical programming
Software:
ALPS; BiCePS; BLIS; CHiPPS; OpenMPI
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] de Brito, M.P.; Dekker, R., Reverse logistics: a framework, (), 3-27
[2] Dethloff, J., Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and Pick-up, OR spektrum, 23, 1, 79-96, (2001) · Zbl 1015.90022
[3] Subramanian A, Cabral LAF, Ochi LS. An efficient ILS heuristic for the vehicle routing problem with simultaneous pickup and delivery. Technical Report, Universidade Federal Fluminense; 2008, available at 〈http://www.ic.uff.br/PosGraduacao/RelTecnicos/401.pdf〉.
[4] Min, H., The multiple vehicle routing problem with simultaneous delivery and Pick-up points, Transportation research, 23, 5, 377-386, (1989)
[5] Halse K. Modeling and solving complex vehicle routing problems. PhD thesis, Institute of Mathematical Statistics and Operations Research, Technical University of Denmark, Denmark; 1992.
[6] Salhi, S.; Nagy, G., A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling, Journal of the operational research society, 50, 10, 1034-1042, (1999) · Zbl 1054.90523
[7] Nagy, G.; Salhi, S., Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries, European journal of operational research, 162, 126-141, (2005) · Zbl 1132.90380
[8] Rö¨pke S, Pisinger D. A unified heuristic for a large class of vehicle routing problems with backhauls. Technical Report 2004/14, University of Copenhagen; 2004. · Zbl 1116.90019
[9] Vural AV. A GA based meta-heuristic for capacitated vehicle routing problem with simultaneous pick-up and deliveries. Master’s thesis, Graduate School of Engineering and Natural Sciences, Sabanci University; 2003.
[10] Gökçe EI. A revised ant colony system approach to vehicle routing problems. Master’s thesis, Graduate School of Engineering and Natural Sciences, Sabanci University; 2004.
[11] Gajpal, Y.; Abad, P., An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup, Computers & operations research, 36, 12, 3215-3223, (2009) · Zbl 1176.90290
[12] Crispim, J.; Brandao, J., Metaheuristics applied to mixed and simultaneous extensions of vehicle routing problems with backhauls, Journal of the operational research society, 56, 7, 1296-1302, (2005) · Zbl 1082.90148
[13] Montané, F.A.T.; Galvão, R.D., A tabu search algorithm for the vehicle routing problem with simultaneous Pick-up and delivery service, Computers & operations research, 33, 3, 595-619, (2006) · Zbl 1077.90058
[14] Chen, J.F.; Wu, T.H., Vehicle routing problem with simultaneous deliveries and pickups, Journal of the operational research society, 57, 5, 579-587, (2006) · Zbl 1113.90017
[15] Gribkovskaia, I.; Halskau, Ø.; Laporte, G.; Vlcek, M., General solutions to the single vehicle routing problem with pickups and deliveries, European journal of operational research, 180, 568-584, (2007) · Zbl 1124.90027
[16] Bianchessi, N.; Righini, G., Heuristic algorithms for the vehicle routing problem with simultaneous Pick-up and delivery, Computers & operations research, 34, 2, 578-594, (2007) · Zbl 1109.90016
[17] Wassan, N.A.; Wassan, A.H.; Nagy, G., A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries, Journal of combinatorial optimization, 15, 4, 368-386, (2008) · Zbl 1145.90327
[18] Zachariadis, E.E.; Tarantilis, C.D.; Kiranoudis, C.T., A hybrid metaheuristic algorithm for the vehicle routing problem with simultaneous delivery and Pick-up service, Expert systems with applications, 36, 2, 1070-1081, (2009)
[19] Subramanian A, Cabral LAF. An ILS based heuristic for the vehicle routing problem with simultaneous pickup and delivery. In: Proceedings of the eighth european conference on evolutionary computation in combinatorial optimisation. Lecture notes in computer science, vol. 4972. Berlin: Springer; 2008. p. 135-46.
[20] Dell’Amico, M.; Righini, G.; Salanim, M., A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection, Transportation science, 40, 2, 235-247, (2006)
[21] Angelelli E, Mansini R. A branch-and-price algorithm for a simultaneous pick-up and delivery problem. Quantitative approaches to distribution logistics and supply chain management. Berlin, Heidelberg: Springer; 2002. p. 249-67. · Zbl 1005.90510
[22] Ralphs, T.K.; Ladányi, L.; Saltzman, M.J., Parallel branch, cut, and price for large-scale discrete optimization, Mathematical programming, 98, 253-280, (2003) · Zbl 1082.90102
[23] Ralphs, T.K.; Ladányi, L.; Saltzman, M.J., A library hierarchy for implementing scalable parallel search algorithms, The journal of supercomputing, 28, 215-234, (2004) · Zbl 1062.90039
[24] Rochat, Y.; Taillard, R.D., Probabilistic diversification and intensification in local search for vehicle routing, Journal of heuristics, 1, 147-167, (1995) · Zbl 0857.90032
[25] Schulze J, Fahle T. A parallel algorithm for the vehicle routing problem with time window constraints. Annals of Operations Research 86. · Zbl 0922.90059
[26] Gendreau, M.; Guertin, F.; Potvin, J.-Y.; Taillard, E., Parallel tabu search for real-time vehicle routing and dispatching, Transportation science, 33, 4, 381-390, (1999) · Zbl 0958.90051
[27] Gendreau, M.; Laporte, G.; Semet, F., A dynamic model and parallel tabu search heuristic for real-time ambulance relocation, Parallel computing, 27, 12, 1641-1653, (2001) · Zbl 0982.68053
[28] Attanasio, A.; Cordeau, J.-F.; Ghiani, G.; Laporte, G., Parallel tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem, Parallel computing, 30, 3, 377-387, (2004)
[29] Caricato, P.; Ghiani, G.; Grieco, A.; Guerriero, E., Parallel tabu search for a pickup and delivery problem under track contention, Parallel computing, 29, 5, 631-639, (2003)
[30] Ochi, L.S.; Vianna, D.S.; Drummond, L.M.A.; Victor, A.O., A parallel evolutionary algorithm for the vehicle routing problem with heterogeneous fleet, Future generation computer systems, 14, 5-6, 285-292, (1998)
[31] Drummond, L.M.A.; Ochi, L.S.; Vianna, D.S., An asynchronous parallel metaheuristic for the period vehicle routing problem, Future generation computer systems, 17, 4, 379-386, (2001) · Zbl 1016.68176
[32] Jozefowiez, N.; Semet, F.; Talbi, E.-G., Parallel and hybrid models for multi-objective optimization: application to the vehicle routing problem, (), 271-280
[33] Berger, J.; Barkaoui, 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
[34] Alba E, Dorronsoro B. Solving the vehicle routing problem by using cellular genetic algorithms. In: Gottlieb J, Raidl GR, editors. EvoCOP. Lecture notes in computer science, vol. 3004. Berlin: Springer; 2004. p. 11-20. · Zbl 1177.90331
[35] Gehring, H.; Homberger, J., Parallelization of a two-phase metaheuristic for routing problems with time windows, Journal of heuristics, 8, 3, 251-276, (2002) · Zbl 1012.68793
[36] Bouthillier, A.L.; Crainic, T.G., A cooperative parallel meta-heuristic for the vehicle routing problem with time windows, Computers & operations research, 32, 7, 1685-1708, (2005) · Zbl 1074.90006
[37] Czarnas P. Parallel simulated annealing for the vehicle routing problem with time windows. In: 10th Euromicro workshop on parallel, distributed and network-based processing, Canary Islands Spain, 2002. p. 376-83.
[38] Polacek, M.; Benkner, S.; Doerner, K.F.; Hartl, R.F., A cooperative and adaptive variable neighborhood search for the multi depot vehicle routing problem with time windows, Bur—business research, 1, 2, 207-218, (2008)
[39] Doerner K, Hartl RF, Kiechle G, Lucká M, Reimann M. Parallel ant systems for the capacitated vehicle routing problem. In: Gottlieb J, Raidl GR, editors. EvoCOP. Lecture notes in computer science, vol. 3004. Berlin: Springer; 2004. p. 72-83. · Zbl 1177.90338
[40] Crainic TG. Parallel solution methods for vehicle routing problems. The vehicle routing problem: latest advances and new challenges. Berlin: Springer; 2008. p. 171-98.
[41] Mladenović, N.; Hansen, P., Variable neighborhood search, Computers & operations research, 24, 11, 1097-1100, (1997) · Zbl 0889.90119
[42] Osman, I.H., Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem, Annals of operations research, 41, 1-4, 421-451, (1993) · Zbl 0775.90153
[43] 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
[44] Cordeau, J.-F.; Laporte, G., Tabu search heuristics for the vehicle routing problem, (), 145-163 · Zbl 1072.90054
[45] Gabriel E, Fagg GE, Bosilca G, Angskun T, Dongarra JJ, Squyres JM, et al. Open MPI: goals, concept, and design of a next generation MPI implementation. In: Proceedings, 11th European PVM/MPI users’ group meeting, Budapest, Hungary, 2004. p. 97-104.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.