A 2-opt guided discrete antlion optimization algorithm for multi-depot vehicle routing problem

  • Partha Sarathi Barma Department of Computer Science and Engineering, NSHM Knowledge Campus Durgapur, India
  • Joydeep Dutta Department of Computer Science and Engineering, NSHM Knowledge Campus Durgapur, India
  • Anupam Mukherjee Department of Mathematics, National Institute of Technology Durgapur, India
Keywords: Multi depot vehicle routing problem, Antlion Optimization (ALO), Bio-inspired Algorithm, Combinatorial Optimization


The Multi-depot vehicle routing problem (MDVRP) is a real-world variant of the vehicle routing problem (VRP) where the customers are getting service from some depots. The main target of MDVRP is to find the route plan of each vehicle for all the depots to fulfill the demands of all the customers, as well as that, needs the least distance to travel. Here all the vehicles start from different depots and return to the same after serving the customers in its route. In MDVRP each customer node must be served by only one vehicle which starts from any of the depots.  In this paper, we have considered a homogeneous fleet of vehicles. Here a bio-inspired meta-heuristic method named Discrete Antli-on Optimization algorithm (DALO) followed by the 2-opt algorithm for local searching is used to minimize the total routing distance of the MDVRP. The comparison with the Genetic Algorithm, Ant colony optimization, and known best solutions is also discussed and analyzed.


Download data is not yet available.


Alinaghian, M., & Shokouhi, N. (2018). Multi-depot multi-compartment vehicle routing problem, solved by a hybrid adaptive large neighborhood search. Omega, 76, 85-99. DOI: https://doi.org/10.1016/j.omega.2017.05.002

Berger, J., & Barkaoui, M. (2003). A hybrid genetic algorithm for the capacitated vehicle routing problem. In Proceedings of the 2003 International Conference on Genetic and Evolutionary Computation, (646–656). Berlin: Springer-Verlag. DOI: https://doi.org/10.1007/3-540-45105-6_80

Bezerra, S., Souza, S., & Souza, M. (2018). A GVNS Algorithm for Solving the Multi-Depot Vehicle Routing Problem. Electronic Notes in Discrete Mathematics, 66, 167-174. DOI: https://doi.org/10.1016/j.endm.2018.03.022

Chao, I.M., Golden, B.L. & Wasil, E. (1993). A new heuristic for the multi-depot vehicle routing problem that improves upon best-known solutions. American Journal of Mathematical and Management Sciences, 13, 371–406. DOI: https://doi.org/10.1080/01966324.1993.10737363

Chen, A.L., Yang, G.K. & Wu, Z.M. (2006). Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem. Journal of Zhejiang University, 7 (4), 607–614. DOI: https://doi.org/10.1631/jzus.2006.A0607

Clarke, G., & Wright, J. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568–581. DOI: https://doi.org/10.1287/opre.12.4.568

Creviera, B., Cordeaua, J.F. & Laporte, G. (2007). The multi-depot vehicle routing problem with inter-depot routes. European Journal of Operational Research, 176, 756-773. DOI: https://doi.org/10.1016/j.ejor.2005.08.015

Croes, G.A. (1958). A method for solving traveling salesman problems. Operations Research, 6, 791-812. DOI: https://doi.org/10.1287/opre.6.6.791

Dutta, J., Barma, P., Kar, S., & De, T. (2019). A Modified Kruskal's Algorithm to Improve Genetic Search for Open Vehicle Routing Problem. International Journal of Business Analytics, 6, 55-76.

Fisher, M.L. (1994). Optimal solution of vehicle routing problems using minimum k-trees. Operations Research, 42, 626–642. DOI: https://doi.org/10.1287/opre.42.4.626

Guimarães, T., Coelho, L., Schenekemberg, C., & Scarpin. C. (2019). The two-echelon multi-depot inventory-routing problem. Computers and Operations Research, 101, 220-233.

Ladanyi, L., Ralphs, T.K., & Trotter, L.E. (2001). Branch, cut, and price: Sequential and parallel. Computational combinatorial optimization, Berlin: Springer. DOI: https://doi.org/10.1007/3-540-45586-8_6

Lalla-Ruiz, E. & Vob, S. (2019). A popmusic approach for the multi-depot cumulative capacitated vehicle routing problem. Optimization Letters, 19, 1–21.

Lang, M.X. (2018). Study on the model and algorithm for multi-depot vehicle scheduling problem. Journal of Transportation Systems Engineering and Information Technology, 16(15), 65–70.

Laporte, G., Nobert, Y. & Arpin, D. (1984). Optimal solutions to capacitated multi-depot vehicle routing problems. Congressus Numerantium, 44, 283–292.

Laporte, G., & Nobert, Y. (1987). Exact algorithms for the vehicle routing problem. Annals of Discrete Mathematics. Surveys in Combinatorial Optimization, 31, 147-184. DOI: https://doi.org/10.1016/S0304-0208(08)73235-3

Laporte, G., Nobert, Y., & Taillefer, S. (1988). Solving a family of multi-depot vehicle routing and location-routing problems. Transportation Science, 22, 161–172. DOI: https://doi.org/10.1287/trsc.22.3.161

Li, F., Golden, B., & Wasil E. (2007). The Open Vehicle Routing Problem: Algorithms, Large scale Test Problems, and Computational Results. Computers and Operations Research, 34(10), 2918–2930. DOI: https://doi.org/10.1016/j.cor.2005.11.018

Li, J., Wang, R., Li, T., Lu, Z., & Pardalos, P. (2018). Benefit analysis of shared depot resources for multi-depot vehicle routing problem with fuel consumption. Transportation Research Part D: Transport and Environment, 59, 417-432. DOI: https://doi.org/10.1016/j.trd.2018.01.026

Matos A.C., & Oliveira, R.C. (2004). An Experimental Study of the Ant Colony System for the Period Vehicle Routing Problem. In: Dorigo M., Birattari M., Blum C., Gambardella L.M., Mondada F., Stützle T. (eds) Ant Colony Optimization and Swarm Intelligence. ANTS 2004. Lecture Notes in Computer Science, vol 3172. Springer, Berlin, Heidelberg.

Mirjalili, S. (2015). The Ant Lion Optimizer. Advances in Engineering Software, 83, 80-98. DOI: https://doi.org/10.1016/j.advengsoft.2015.01.010

Mukherjee, A., Panigrahi, G., Kar, S., & Maiti, M. (2019). Constrained covering solid travelling salesman problems in uncertain environment. Journal of Ambient Intelligence and Humanized Computing, 10, 125-138. DOI: https://doi.org/10.1007/s12652-017-0620-3

Ombuki-Berman B., & Hanshar, F.T. (2009). Using Genetic Algorithms for Multi-depot Vehicle Routing. In: Pereira F.B., Tavares J. (eds) Bio-inspired Algorithms for the Vehicle Routing Problem. Studies in Computational Intelligence, 161. Springer, Berlin, Heidelberg.

Rabbouch, B., Mraihi, R., & Saâdaoui, F. (2017). A Recent Brief Survey for the Multi-Depot Heterogeneous Vehicle Routing Problem with Time Windows. International Conference on Health Information Science, Hybrid Intelligent Systems, 147-157. DOI: https://doi.org/10.1007/978-3-319-76351-4_15

Reimann, M., Doerner, K. & Hartl, R.F. (2004). D-ants: Savings based ants divide and conquer the vehicle routing problem. Computers and Operations Research, 31, 563–591. DOI: https://doi.org/10.1016/S0305-0548(03)00014-5

Renaud, J., Laporte, G. & Boctor. F.F. (1996). A tabu search heuristic for the multi-depot vehicle routing problem. Computers and Operations Research, 23, 229–235. DOI: https://doi.org/10.1016/0305-0548(95)O0026-P

Silva, Á., Ferreira, L., Pereira, M., & Moreira, F. (2018). A Model for the Multi-Depot Online Vehicle Routing Problem with Soft Deadlines. International Conference on Innovation, Engineering and Entrepreneurship HELIX 2018: Innovation, Engineering and Entrepreneurship, 818-824. DOI: https://doi.org/10.1007/978-3-319-91334-6_112

Taillard, E.D. (1993). Parallel iterative search methods for vehicle routing problems. Networks, 23, 661–673. DOI: https://doi.org/10.1002/net.3230230804

Tunga, H., Bhaumik, A., & Kar, S. (2017). A method for solving bi-objective green vehicle routing problem (G-VRP) through genetic algorithm. Journal of the Association of Engineers, 1(2), 33–48. DOI: https://doi.org/10.22485/jaei/2017/v87/i1-2/158491

Vianna, D.S., Ochi, L.S., & Drummond, L.M. (1999). A parallel hybrid evolutionary metaheuristic for the period vehicle routing problem. In Rolim, J., Mueller, F., Zomaya, A.Y., Ercal, F., Olariu, S., Ravindran, B., Gustafsson, J., Takada, H., Olsson, R., & Kale, L.V. (Eds.), Parallel and distributed processing. Lecture notes in com-puter science. vol. 1586 (183–191). Berlin: Springer-Verlag. DOI: https://doi.org/10.1007/BFb0097899

Yuan, W., Wang. J., Li, J., Yan, B., & Wu, J. (2017). Two-stage heuristic algorithm for a new model of hazardous material multi-depot vehicle routing problem. UK Workshop on computational intelligence UKCI 2017: Advances in computational intelligence systems, 362-366. DOI: https://doi.org/10.1007/978-3-319-66939-7_32

Zhang, S., Zhang, W., Gajpal, Y., & Appadoo, S. (2019). Ant colony algorithm for routing alternate fuel vehicles in multi-depot vehicle routing problem. Decision Science, 251-260.

Zhou, L., Baldacci, R., Vigo, D., & Wang, X. (2018). A multi-depot two-echelon vehicle routing problem with delivery options arising in the last mile distribution. European Journal of Operational Research, 265(2), 765-778. DOI: https://doi.org/10.1016/j.ejor.2017.08.011

How to Cite
Barma, P. S., Dutta, J., & Mukherjee, A. (2019). A 2-opt guided discrete antlion optimization algorithm for multi-depot vehicle routing problem. Decision Making: Applications in Management and Engineering, 2(2), 112-125. https://doi.org/10.31181/dmame1902089b