Uma abordagem em três etapas para o problema de roteamento de veículos com múltiplas restrições de sincronização

Abstract

This work presents a three-stage approach to solve the Vehicle Routing Problem with Multiple Synchronization Constraints (VRPMS), a complex extension of the Vehicle Routing Problem with Time Windows (VRPTW), in which some customers require syn chronized visits from two or more distinct vehicles. The proposed method incorporates synchronization parameters (δ and γ) that enable its applicability to different problem variants involving synchronization constraints. The approach combines an Iterated Local Search (ILS) heuristic for efficient solution generation, an exact Set Partitioning (SP) mo del for solution refinement, and a final temporal validation stage using a synchronization model. The local search employs a subsequence concatenation strategy for constraint eva luation and a two-stage search mechanism to select the best move, aiming to mitigate the impact of synchronization. Additionally, a relaxed form of synchronization constraints is adopted in both the ILS and the SP model. Extensive experiments were conducted based on the instance set proposed by Hojabri et al. (2018), considering different sizes, instance classes, and synchronization levels. The results highlight the efficiency of the proposed approach in generating high-quality solutions in reduced computational times and emphasize the impact of synchronization constraints on solution feasibility and com putational cost. The exact stage showed strong potential for solution refinement, while the synchronization model enabled a rigorous verification of the relative time windows between routes.