A 2-opt guided discrete antlion optimization algorithm for multi-depot vehicle routing problem
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
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. 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
