Benders Decomposition Approaches for a Group of Related Vehicle Routing Problems with Synchronization

• Grant number: 25/23338-4
• Support Opportunities: Scholarships abroad - Research Internship - Master's degree
• Start date: February 01, 2026
• End date: May 31, 2026
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Maristela Oliveira dos Santos
• Grantee: Gabriel Vinicius Bacci
• Supervisor: Leandro Callegari Coelho
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil
• Institution abroad: Université Laval, Canada
• Associated to the scholarship: 24/19351-2 - The Active and Passive Vehicle Routing Problem: Exact Methods Based on Bender Decomposition, BP.MS

Abstract

Many routing problems in the literature impose synchronization requirements between vehicles, some able to move autonomously and others that must be physically coupled to travel, arising in settings such as container transport in seaports and in-plant materials handling. This project studies such synchronization-oriented VRP variants that are closely related to the Active and Passive Vehicle Routing Problem (APVRP). Our main objective is to adapt and broaden the scope of an exact approach based on Logic-Based Benders Decomposition (LBBD), originally devised for the APVRP, so that it can be applied to related synchronization problems reported in the literature while accounting for their specificities. We also aim to enhance the efficiency of this approach, for the APVRP, by reformulating the subproblem as a scheduling model, and designing a specialized algorithm that leverages Constraint Programming (CP). Furthermore, we seek to investigate other subproblem formulations and possible strategies to solve them, for other routing problems in the literature, similar to APVRP. The proposed approaches will be assessed through computational experiments on benchmark instances available in the literature. (AU)