The Robust Vehicle Routing Problem With Synchronization: Models and Branch-And-Cut Algorithms

• Tipo: Artigo em Revista Científica Internacional
• Data: 2025

Autores

Soares, R (Autor) FEUP; Parragh, SN (Autor) Outra; Marques, A (Autor) Outra; Amorim, P (Autor) Outra

Revista

Título: Networks

ISSN: 0028-3045

Editora: Wiley-Blackwell

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 0 Citações

Outras Informações

ID Authenticus: P-018-YGG

DOI: 10.1002/net.22287

Abstract (EN): The Vehicle Routing Problem with Synchronization (VRPSync) aims to minimise the total routing costs while considering synchronization requirements that must be fulfilled between tasks of different routes. These synchronization requirements are especially relevant when it is necessary to have tasks being performed by vehicles within given temporal offsets, a frequent requirement in applications where multiple vehicles, crews, materials, or other resources are involved in certain operations. Although several works in the literature have addressed this problem, mainly the deterministic version has been tackled so far. This paper presents a robust optimization approach for the VRPSync, taking into consideration the uncertainty in vehicle travel times between customers. This work builds on existing approaches in the literature to develop mathematical models for the Robust VRPSync, as well as a branch-and-cut algorithm to solve more difficult problem instances. A set of computational experiments is also devised and presented to obtain insights regarding key performance parameters of the mathematical models and the solution algorithm. The results suggest that solution strategies where certain standard problem constraints are only introduced if a candidate solution violates any of those constraints provide more consistent improvements than approaches that rely on tailor-made cutting planes, added through separation routines. Furthermore, the analysis of the Price of Robustness indicators shows that the adoption of robust solutions can have a significant increase in the total costs, however, this increase quickly plateaus as budgets of uncertainty increase.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 29