Simulated Annealing Algorithm for Vehicle Routing with Stochastic Travel Times and Soft Time Windows

Jiménez-Carrión M.; Ojeda-Hidalgo K.M. · HighTech and Innovation Journal (2025) · DOI: 10.28991/hij-2025-06-03-01

Resumen

In the context of urban logistics, uncertainty in travel times poses a critical challenge for planning efficient routes. A multi-objective simulated annealing (SA) algorithm is proposed to solve the Vehicle Routing Problem with Stochastic Travel Times and Soft Time Windows (VRPSTTW), prioritizing the minimization of the number of vehicles and travel costs. The methodology follows three phases: (1) calibration of the SA on 12 Solomon instances with 100 customers, achieving an average GAP of 1.9% and a maximum of 3.4%; (2) modeling of travel times using the Box-Muller transformation on 43,200 Google Maps records, segmented into four scenarios according to peak hours and type of day; and (3) parameter tuning through a 3³ factorial design. With the optimal configuration (T₀ = 1500, α = 0.9, 4000 iterations), the algorithm solved a real instance with 100 customers in 0.5 minutes, achieving 10 vehicles, 614.7 km, 75 minutes of travel time, and a CV of 0.013%; perturbations of ±10% only increased the energy by 0.019%. Compared to recent literature, the distance was reduced by 3.2% without resorting to hybrid algorithms. The main novelty lies in integrating real traffic data and soft windows into a pure SA approach with complexity O(C·n²), offering a robust, realistic, and scalable tool for dynamic urban environments. © Authors retain all copyrights.

Instituciones: Universidad Nacional de Piura