Document Type : Original Article

Authors

1 Department of Mathematics, Parand Branch, Islamic Azad University, Parand, Iran.

2 Department of Mathematics, Shahid Chamran University of Ahvaz, Iran.

3 Bu-Ali Sina University, Hamedan, Iran

Abstract

One of the most important extensions of the capacitated vehicle routing problem (CVRP) is the vehicle routing problem with simultaneous pickup and delivery (VRPSPD) where customers require simultaneous delivery and pick-up service. In this paper, we propose an effective ant colony optimization (EACO) which includes insert, swap and 2-Opt moves for solving VRPSPD that is different with common ant colony optimization (ACO). ACO is a meta-heuristic algorithm inspired by the foraging behavior of real ants. Artificial ants are used to build a solution for the problem by using the pheromone information from previously generated solutions. An extensive numerical experiment is performed on 68 benchmark problem instances involving up to 200 customers available in the literature. The computational result shows that EACO not only presented a very satisfying scalability, but also was competitive with other meta-heuristic algorithms such as tabu search, large neighborhood search, particle swarm optimization and genetic algorithm for solving VRPSPD problems.

Keywords

Ai, T. J. and Kachitvichyanukul, V. 2009, “A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery”, Computers & Operations Research, 36(5), 1693- 1702.
Angelelli, E. and Mansini R. 2002. “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, 249–267.
Avci, M. and Topaloglu, S. 2015, "An adaptive local search algorithm for  vehicle  routing problem with simultaneous and mixed pickups and deliveries", Computers & Industrial Engineering, 83, 15-29.
Avci, M. and Topaloglu, S. 2016. “A hybrid metaheuristic algorithm for heterogeneous vehicle routing problem with simultaneous pickup and delivery”, Expert Systems with Applications, 53, 160-171.
Berbeglia, G., Cordeau, J. F., Gribkovskaia, I. and Laporte, G. 2007, “Static pickup and delivery problems: a classification scheme and survey”, TOP, 15(1), 1-31.
Bianchessi, N. and Righini. G. 2007, “Heuristic algorithms for the vehicle routing problem with simultaneous pickup and delivery”, Computers and Operations Research, 34(2), 578-594.
Brito, MP. and Dekker, R. 2004. @Reverse Logistics: a framework. In: Reverse logistics—quantitative models for closed-loop supply chains”, Berlin: Springer, 3–27.
 
Catay, B. 2010, “A new saving based ant algorithm for the vehicle routing problem with simultaneous pickup and delivery”, Expert Systems with Applications, 37, 6809–6817.
Christofides, N., Mingozzi, A. and Toth, P. 1979. The vehicle routing problem. In N. Christofides, A. Mingozzi, P. Toth, & L. Sandi (Eds.), Combinatorial optimization. Chichester, UK: Wiley.
Cruz, R.C., Silva, T.C.B.D., Souza, M.J., Coelho, V.N., Mine, M.T. and Martins, A.X., 2012. GENVNS-TS-CL-PR: A heuristic approach for solving the vehicle routing problem with simultaneous pickup and delivery. Electronic Notes in Discrete Mathematics, 39, 217-224.
Dell'Amico, M., Righini, G. and Salani, M. 2006, “A branch-and-price approach to the vehicle routing problem with simultaneous distribution and collection”, Transportation Science 40(2),  235-247.
Dethloff, J. 2001, “Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up”, OR Spektrum, 23(1), 79-96.
Dorigo, M. 1992, “optimization, Learning and natural algorithms”, Ph.D Thesis, Dip.Electtronica e Informazion, Politecnico di Milano Italy.
Emmanouil, E. Z., Christos, D. T. and Chris. T. K. 2009, “A hybrid meta-heuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service”, Expert Systems with Applications, 36(2), 1070-1081.
Gajpal, Y. and Abad, P. 2009, "An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup:, Computers and Operations Research, 36(12), 3215–3223.
Gambardella, M. Taillard, L. D. E. and Dorigo, M. 1999, “Ant colonies for the quadratic assignment problem”, Journal of the Operational Research Society, 50(2), 167–176.
Garey, M.R. and Johnson, D.S., 1979, “Computers and intractability: A guide to the theory of NP-completeness”, San Francisco: W.H. Freeman.
Goksal, F. P., Karaoglan, I. and Altiparmak, F. 2013, "A hybrid discrete particle swarm optimization for vehicle routing problem with simultaneous pickup and delivery", Computers & Industrial Engineering, 65(1), 39-53.
Hong, L. 2012, “An improved LNS algorithm for real-time vehicle routing problem with time windows”, Computers & Operations Research, 39(2), 151-163.
Kuo, Y. and Wang, C. C. 2012, “A variable neighborhood search for the multi-depot vehicle routing problem with loading cost”, Expert Systems with Applications, 39(8), 6949-6954.
Laporte, G., Mercure, H. and Nobert, Y. 1986, “An exact algorithm for the asymmetrical capacitated vehicle routing problem”, Networks, 16, 33–46
Li, F., Golden, B. and Wasil, E. 2007b, “The open vehicle routing problem: Algorithms, large-scale test problems, and computational results”, Computers and Operations Research, 34, 2918–2930.
Min, H. 1989, "The multiple vehicle routing problem with simultaneous delivery and pick-up points", Transportation Research A, 23(5), 377-386.
Maniezzo, V. and Carbonaro, A. 2000, “An ants heuristic for the frequency assignment problem”, Future Generation Computer Systems, 16(8), 927–935.
Merkle, D. and Middendorf, M. 2003, “Ant colony optimization with global pheromone evaluation for scheduling a single machine”, Applied Intelligence, 18(1), 105–111.
Min, H. 1989, “The multiple vehicle routing problem with simultaneous delivery and pick-up points”, Transportation Research A, 23(5), 377-386.
Mingyong, l. and Erbao, C. 2010, “An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows”, Applications of Artificial Intelligence, 23, 188–195
Nagy, G. and Salhi, S. 2005, “Heuristic algorithm for single and multiple depot vehicle routing problem with pickups and deliveries”, European Journal of Operational Research, 162, 126–141.
Polat, O., Kalayci, C. B. Kulak, O. and Günther, H. O. 2015, "A perturbation based variable neighborhood search heuristic for solving the  Vehicle  Routing  Problem  with  Simultaneous Pickup and Delivery with Time Limit", European Journal of Operational Research, 242(2), 369-382
Repoussis, P. P., Tarantilis, C. D. and Ioannou, G. 2006, “The open vehicle routing problem with time windows”, Journal of the Operational Research Society, 58, 355-367.
Ropke, S. and Pisinger, D. 2004, “A unified heuristic for a large class of vehicle routing problems with backhauls”, Technical Report 2004/14, University of Copenhagen.
Salhi, S. and Nagy, G. 1999, “A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling”, Journal of the Operational Research Society, 50(10), 1034-1042.
Subramanian, A., Drummonda, L. M. A., Bentes, C., Ochi, L. S. and Farias, R. 2010, "A parallel heuristic for the Vehicle Routing Problem with Simultaneous Pickup and Delivery", Computers & Operations Research, 37, 1899–1911.
Subramanian, A., Huachi, P., Penna, V., Uchoa, E. and Ochi, L. S. 2012, “A hybrid algorithm for the Heterogeneous Fleet Vehicle Routing Problem”, European Journal of Operational Research, 221(2), 285-295.
Tang, FA. and Galvao, RD. 2006, “A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service”, Computers and Operations Research, 33(3), 595–619.
Tarantilis, C., Zachariadis, E. and Kiranoudis, C. 2008, “A guided Tabu search for the heterogeneous vehicle routing problem”, Journal of the Operational Research Society, 59, 1659-1673.
Toth, P. and Vigo, D. 1997, “An exact algorithm for the vehicle routing problem with backhauls”, Transportation Science, 31, 372–385.
Vural, AV. 2003). “A GA based meta-heuristic for capacitated vehicle routing problem with simultaneous pickup and deliveries”, Master’s thesis, Graduate School of Engineering and Natural Sciences, Sabanci University.
Wassan, N. A., Wassan, A. H., Nagy, G. 2008, "A reactive tabu search algorithm for the vehicle routing problem with simultaneous pickups and deliveries", Journal of Combinatorial Optimization, 15(4), 368–386.
Wassan, N.A. and Nagy, G. 2014. “Vehicle routing problem with deliveries and pickups: Modelling issues and meta-heuristics solution approaches”, International Journal of Transportation, 2(1), 95-110.
Zachariadis, E. E., Tarantilis, C. D., Kiranoudis, C. T. 2009, "A hybrid meta-heuristic algorithm for the vehicle routing problem with simultaneous delivery and pick-up service", Expert Systems with Applications, 36(2), 1070–1081.
Zhang, T., Chaovalitwongse, W. A. and Zhang, Y. 2011, “Scatter search for the stochastic travel time vehicle routing problem with simultaneous pickups and deliveries”, Computers & Operations Research, 39, 2277–2290.
Zhao, F., Mai, D., Dun J. and Liu, W. 2009, “A hybrid genetic algorithm for the vehicle routing problem with simultaneous pickup and delivery”, Chinese Control and Decision Conference, CCDC 2009, 3928- 3933.