A Simulated Annealing Approach for the Homogeneous Capacitated Vehicle Routing Problem

Dalia Vanessa Arce-Ortega, Federico Alonso-Pecina (), Marco Antonio Cruz-Chávez and Jesús del Carmen Peralta-Abarca
Additional contact information
Dalia Vanessa Arce-Ortega: Center for Research in Engineering and Applied Sciences (CIICAP), Universidad Autónoma del Estado de Morelos, Cuernavaca 62209, Morelos, Mexico
Federico Alonso-Pecina: Faculty of Accounting, Administration & Informatics (FCAeI), Universidad Autónoma del Estado de Morelos, Cuernavaca 62209, Morelos, Mexico
Marco Antonio Cruz-Chávez: Center for Research in Engineering and Applied Sciences (CIICAP), Universidad Autónoma del Estado de Morelos, Cuernavaca 62209, Morelos, Mexico
Jesús del Carmen Peralta-Abarca: Faculty of Chemical Sciences and Engineering (FCQeI), Universidad Autónoma del Estado de Morelos, Cuernavaca 62209, Morelos, Mexico

Mathematics, 2025, vol. 13, issue 19, 1-20

Abstract: This study addresses the Capacitated Vehicle Routing Problem (CVRP) known to be NP-hard. In this problem, a set of customers with varying demands is considered. To solve the problem, routes were generated for several vehicles with identical capacity, which were responsible for delivering products to a set of geographically dispersed customers. The purpose of the problem is to minimize the total cost of all routes. This problem was solved by applying the metaheuristic Simulated Annealing (SA) and incorporating four different neighborhoods to improve the initial solution generated randomly. In the SA, a set of cooling factors is used. The best solution obtained by SA is refined by the use of Hill Climbing using a double neighborhood. The algorithm was tested with instances from the literature in order to measure its effectiveness in solution quality and execution time. We tested the approach with 106 instances from the literature and obtained the optimum in 93 instances. The average time in most instances was less than five minutes. Delivery companies can benefit from this approach. They only need to identify the depot, the clients, and the distance between locations, and this approach can be used with relative ease.

Keywords: combinatorial optimization; vehicle routing problem; simulated annealing; metaheuristics; local search; homogeneous capacities (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/19/3209/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/19/3209/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:19:p:3209-:d:1765848

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().