Generation of distribution routes with shorter distances and fewer vehicles using the simulated annealing algorithm

Abstract

The vehicle routing problem (VRP) is still a persistent challenge in society, and can be considered a combinatorial optimization problem, where a fleet of delivery vehicles must satisfy the demand of customers sharing the same depot, minimizing the transport distance. The objective of this research is to propose a method to generate distribution routes that minimize both the number of vehicles used and the total distance traveled. To this end, an initial solution is used, on which the Greedy algorithm is applied, followed by the simulated annealing (SA) algorithm, manipulating the exchange techniques, insertion methods, parameter adjustments within the algorithm and applying the penalty as a mechanism to avoid the excessive use of trucks or the assignment of routes that exceed the allowed capacity. The proposal was validated using four datasets, as a result, the general averages of the reduction in distance, changes and penalty cost are shown: The Greedy algorithm reduced the distance by 5.71%, in trucks to 16.57%, in penalty cost to 14.71%; then, applying the SA algorithm, a better efficiency was achieved by reducing the distance by 10.36%, 20.08% in trucks and 18.64% in penalty cost. In this way, the use of vehicles in the distribution routes is optimized, which could contribute to the reduction of vehicular traffic and the reduction of CO2 emissions, thus favoring the environment.