Hybrid Approach to Solve the Capacitated Vehicle Routing Problem

Gladys Bonilla, Omar Caballero-Morales

Abstract


The Capacitated Vehicle Routing Problem (CVRP) is one of the most studied problems in the field of transport logistics. This given that transport represents up to 10% of the value of a product. CVRP addresses the situation of finding the optimal number of vehicles to meet the demands of a set of customers. The assignment of vehicles to customers must be consolidated in routes of minimum cost, distance or time. Because this problem is of the NP-hard type, there are few instances that can be solved optimally. In this article, a greedy algorithm is presented to obtain approximate solutions to this problem in a fast way with the free license software Octave. For the comparison of results, instances with optimal values of the CVRPLIB database were used. The results showed that this algorithm was able to obtain feasible solutions with errors less than 14.0% for medium to large CVRP instances. In some cases, near-optimal solutions were obtained.

Keywords


vehicle routing problem; heuristic algorithm; combinatorial optimization; software design.

Full Text:

PDF

References


E. Moreno-Quintero, “Problemas de ruteo vehicular en la recolección y distribución óptimas de carga”. Publicación Técnica No 144, 2000. 90p.

C. Claude, S. Brian, R. Jean-Paul, The geography of transport systems. Third edition. 2013. Taylor & Francis Group. London:Rotledge.

C. Koc, T. Bektas, O. Jabali, G. Laporte, “The impact of depot location, fleet composition and routing on emissions in city logistics”. Transportation Research Part B: Methodological. Vol. 84, 2016, 81-102.

M. L. Fisher, “Optimal Solution of Vehicle Routing Problems Using Minimum K-trees”. Operations Research. Vol. 42, 1994, 626-642.

P. Toth, D. Vigo, “Models, relaxations and exact approaches for the capacitated vehicle routing problema”. Discrete Applied Mathematics. Vol. 123, 2002, 487-512.

R. Yesodha, T. Amudha, “A Study on Bio-Inspired Metaheuristics for Solving Vehicle Routing Problem”. Indian Journal of Science and Technology. Vol. 8 No. 25, 2015, 85 – 93.

G. Clarke, J. W. Wright, “Scheduling of vehicles from a central depot to a number of delivery points.” Operations Research. Vol. 12, 1964, 568–581, 1964.

P. Toth, D. Vigo, The Vehicle Routing Problem. 2002. SIAM. Philadelphia, PA: USA.




DOI: http://dx.doi.org/10.52155/ijpsat.v33.1.4306

Refbacks

  • There are currently no refbacks.


Copyright (c) 2022 Gladys Bonilla-Enríquez, Santiago-Omar Caballero-Morales

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.