- 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.