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
Digital Signal Processing and Artificial Intelligence for Automatic Learning, Vol. 2, No. 1, 2023.
DOI: https://doi.org/10.6025/dspaial/2023/2/1/1-9
Link: https://www.dline.info/dspai/fulltext/v2n1/dspaiv2n1_1.pdf
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.