2025 · COMPUTERS & OPERATIONS RESEARCH

Generalized variable neighborhood search algorithm for vehicle routing problem with time windows and synchronization

Masmoudi, Malek, Borchani, Rahma, Jarboui, Bassem

Journal
COMPUTERS & OPERATIONS RESEARCH
Année
2025
Volume
183
Article
107193
Mois
NOV
DOI
10.1016/j.cor.2025.107193

Abstract

The problem addressed in this paper is the Vehicle Routing Problem with Time Windows and Synchronization (VRPTW-S), a variant of the Vehicle Routing Problem where each customer must be served within a specific time window, and some customers must be visited by more than one vehicle at the same time. A Generalized Variable Neighborhood Search (GVNS) algorithm is provided and composed of Random-Insertion heuristic, neighborhood structures, shaking procedure, Basic sequential Variable Neighborhood Descent (B-VND), and augmented evaluation function with dynamic penalties that are specifically tailored to the characteristics of the VRPTW-S. The parameters of our GVNS are tuned through a Design of Experiments (DoE) approach on randomly generated instances. The experimentation is conducted on two benchmark datasets with a total of 84 instances. Numerical results show that the GVNS outperforms the existing best-performing solving approaches in terms of effectiveness, efficiency, and robustness. Among the 84 benchmark instances, the GVNS successfully attains 52 bestknown solutions, including all 20 proven optimal solutions, and introduces 18 new best solutions.

Lire l'article complet