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

Partha Sarathi Barma; Joydeep Dutta; Anupam Mukherjee

doi:10.31181/dmame1902089b

Authors

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

DOI:

https://doi.org/10.31181/dmame1902089b

Keywords:

Multi depot vehicle routing problem, Antlion Optimization (ALO), Bio-inspired Algorithm, Combinatorial Optimization

Abstract

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.

Downloads

Download data is not yet available.

References

Alinaghian, M., & Shokouhi, N. (2018). Multi-depot multi-compartment vehicle routing problem, solved by a hybrid adaptive large neighborhood search. Omega, 76, 85-99.

Berger, J., & Barkaoui, M. (2003). A hybrid genetic algorithm for the capacitated vehicle routing problem. In Genetic and evolutionary computation conference (pp. 646-656). Berlin, Heidelberg: Springer Berlin Heidelberg.

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.

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.

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-Science A, 7(4), 607-614.

Clarke, G., & Wright, J. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4), 568–581.

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.

Croes, G. A. (1958). A method for solving traveling salesman problems. Operations Research, 6, 791-812.

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(4), 626-642.

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

Ladányi, L., Ralphs, T. K., & Trotter, L. E. (2001). Branch, cut, and price: Sequential and parallel. Computational Combinatorial Optimization: Optimal or Provably Near-Optimal Solutions, 223-260.

Lalla-Ruiz, E., & Voß, S. (2020). A popmusic approach for the multi-depot cumulative capacitated vehicle routing problem. Optimization Letters, 14(3), 671-691.

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. (1987). Exact algorithms for the vehicle routing problem. Annals of Discrete Mathematics. Surveys in Combinatorial Optimization, 31, 147-184.

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., & Taillefer, S. (1988). Solving a family of multi-depot vehicle routing and location-routing problems. Transportation Science, 22, 161–172.

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.

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.

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.

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.

Ombuki-Berman, B., & Hanshar, F. T. (2009). Using genetic algorithms for multi-depot vehicle routing. In Bio-inspired algorithms for the vehicle routing problem (pp. 77-99). Berlin, Heidelberg: 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.

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.

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.

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.

Taillard, E. D. (1993). Parallel iterative search methods for vehicle routing problems. Networks, 23, 661–673.

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.

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.

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.