Digital Signal Processing and Artificial Intelligence for Automatic Learning

DLINE Journals portal

Home

New Journals

Browse Journals

Journal Prices

For Authors

Print ISSN:
Online ISSN: 2583-5009

About DSPAI
	DLINE Portal Home Home Aims & Scope Editorial Board Current Issue Next Issue Previous Issue Sample Issue Upcoming Conferences Self-archiving policy Alert Services Be a Reviewer Publisher Paper Submission Subscription Contact us

How To Order
	Order Online Price Information Request for Complimentary Print Copy

For Authors
	Guidelines for Contributors Online Submission Statement of Ethics and Responsibilities Review Policies Transfer of Copyright Archiving Policy Call for Papers Author Rights

RELATED JOURNALS

Journal of Digital Information Management (JDIM)

International Journal of Computational Linguistics Research (IJCL)

International Journal of Web Application (IJWA)

Digital Signal Processing and Artificial Intelligence for Automatic Learning

Comparative of algorithms for Solving the Capacity Vehicle Routing Problem

Jesus C. Carmona-Frausto; Adriana Mexicano-Santoyo; Salvador Cervantes-Alvarez; Pascual N. Montes-Dorantes; Francisco ArgÃ‚Â¨uelles-Granados
Technological Institute of City Victoria Technological National of Mexico Mexico., University Center of the Valleys University of Guadalajara, Mexico

Abstract: This article shows a comparative study of five algorithms to solve the Capacity Vehicles Routing Problem (CVRP). The first two compared methods use the well-known k-Nearest Neighbor (kNN) algorithm; one of these searches for the Hamiltonian Cycle and then split the route into several subroutes according to the number of vehicles and customers, the other one assigns individual vehicles in order to obtain a route until the capacity of vehicle is exhausted and go back to the depot. The third of them is a Genetic algorithm with an improved cross-over operator to obtain better solutions. The four and five algorithms were Simulated Annealing and Tabu Search, respectively.The set of test instances used to compare the performance of the algorithms corresponds to the well-known set of instances used by the specialized community a proposed by Augerat in 1995. The genetic algorithm proves to find a shorter path and to be closer to the optimal values of the tested dataset, but on the contrary it takes a little longer. On the other hand, Tabu Search shows a similar behavior to Genetic algorithm but results were achieved in shortest time than the Genetic.

Keywords: CVRP, kNN, Genetic-Algorithm, Simulated Annealing, Tabu Search Comparative of algorithms for Solving the Capacity Vehicle Routing Problem

DOI:https://doi.org/10.6025/dspaial/2023/2/1/1-9

Full_Text PDF 1.28 MB Download: 72 times

References:

[1] Alesiani, F., Ermis, G., and Gkiotsalitis, K. Constrained clustering for the capacitated vehicle routing problem (cc-cvrp). Applied Artificial Intelligence 31, 1 (2022), 1–25.
[2] Augerat, P. Approche poly`edrale du probl`eme de tourn´ees de v´ehicules. Theses, Institut National Polytechnique de Grenoble - INPG, June 1995.
[3] Bozorg-Haddad, O., Solgi, M., and A., L. H. Meta-heuristic and Evolutionary Algorithms for Engineering Optimization. 2017.
[4] Caballero-Morales, S.-O., Mart´inez- Flores, J.-L., and S´anchez-Partida, D. An evolutive tabu-search metaheuristic approach for the capacitated vehicle routing problem. In Management and Industrial Engineering (2018), pp. 477–495.
[5] Escobar, J. W., and Rodrigo, L. Un algoritmo metaheur´istico basado en recocido simulado con espacio de b´usqueda granular para el problema de localizaci´on y ruteo con restricciones de capacidad. Rev. Ing. Univ. Medell´in 11, 21 (2012), 139– 150.
[6] Fitriani, N. A., Pratama, R. A., Zahro, S., Utomo, P. H., and Sri, M. T. Solving capacitated vehicle routing problem using saving matrix, sequential insertion, and nearest neighbor of producto x in grobogan district. In AIP Conference Proceedings 2326 (2021), pp. 0200071–1–0200071– 7.
[7] Jinsi, C., Peng, W., Siqing, S., and Huachao, D. A dynamic space reduction ant colony optimization for capacitated vehicle routing problem. Soft Computing 26, 1 (2022), 8745–8756.
[8] Kulkarni, S., Sohani, N., and Sehta, N. Capacitated vehicle routing using nearest neighbor algorithm in supply chain. International Journal of Engineering Research & Technology 3, 5 (2014), 1331–1334.
[9] Ilhan, l. A population based simulated annealing algorithm for capacitated vehicle routing problem. Turkish Journal of Electrical Engineering & Computer Sciences 28, 1 (2020), 1217–1235.
[10] Lin, S.-W., Lee, Z.-J., Yin, K.-C., and Lee, C.-Y. Applying hybrid metaheuristics for capacitated vehicle routing problem. Expert. Syst. Appl. 36, 1 (2009), 1505–1512.
[11] Masudin, I., Sadiyah, Risma F. andUtama, D. M., Restuputri, D. P., and Jie, F. Capacitated vehicle routing problems: Nearest neighbour vs. tabu search. International Journal of Computer Theory and Engineering 11, 4 (2019), 76–79.
[12] Nazif, H., and Lee, L. S. Optimised crossover genetic algorithm for capacitated vehicle routing problem. Applied Mathematical Modelling 36, 5 (2012), 2110–2117.
[13] Perwira Redi, A., Rohmatul Maula, F., Kumari, F., Utami Syaveyenda, N., Ruswandi, N., Uswatun Khasanah, A., and Chandra Kurniawan, A. Simulated annealing algorithm for solving the capacitated vehicle routing problem: a case study of pharmaceutical distribution. Jurnal Sistem dan Manajemen Industri 4, 1 (2020), 41–49.
[14] Rabbouch, B., Saˆadaoui, F., and Rafaa, M. Empirical-type simulated annealing for solving the capacitated vehicle routing problem. J. Exp. Theor. Artif. Intell. 31, 1 (2019), 1–16.
[15] Ram´irez-Cortes, I., Hern´andez-Aguilar, J. A., ´Angel Ruiz, M., Cruz-Chavez, M. A., and Arroyo-Figueroa, G. Design and implementation of a cvrp simulator using genetic algorithms. Research in Computing Science 147, 2 (2018), 35–47.
[16] Sanjay, K., Nagendra, S., and Neha, S. Capacitated vehicle routing using nearest neighbor algorithm in supply chain. International Journal of Engineering Research & Technology 3, 5 (2014).
[17] Santillan, J. H., Tapucar, S., Manliguez, C., and Calag, V. Cuckoo search via levy flights for the capacitated vehicle routing problem. J Ind Eng Int 14, 1 (2018), 293–304.
[18] Wang, C.-H., and Lu, J.-Z. A hybrid genetic algorithm that optimizes capacitated vehicle routing problems. Expert. Syst. Appl. 36, 2 (2009), 2921–2936.
[19] Yuanxiao, W., and Xiwe, L. A tight approximation algorithm for multi-vehicle cvrp with unsplittable demands on a line. J Syst Sci Complex 35, 1 (2022), 1902–1909.
[20] Yuelin, G., Hongguang, W., and Wanting, W. A hybrid ant colony optimization with fireworks algorithm to solve capacitated vehicle routing problem. Applied Intelligence (2022), 1–17.

DLINE Journals portal