The Active and Passive Vehicle Routing Problem: Exact Methods Based on Bender Decomposition

• Grant number: 24/19351-2
• Support Opportunities: Scholarships in Brazil - Master
• Start date: April 01, 2025
• End date: August 31, 2026
• Field of knowledge: Engineering - Production Engineering - Operational Research
• Principal Investigator: Maristela Oliveira dos Santos
• Grantee: Gabriel Vinicius Bacci
• Host Institution: Instituto de Ciências Matemáticas e de Computação (ICMC). Universidade de São Paulo (USP). São Carlos , SP, Brazil
• Associated research grant: 22/05803-3 - Cutting, packing, lot-sizing, scheduling, routing and location problems and their integration in industrial and logistics settings, AP.TEM
• Associated scholarship(s): 25/23338-4 - Benders Decomposition Approaches for a Group of Related Vehicle Routing Problems with Synchronization, BE.EP.MS

Abstract

The Active and Passive Vehicle Routing Problem (APVRP) arises in important logistical operations, involving the efficient coordination between active vehicles, which move autonomously, and passive vehicles, which depend on the active vehicles for transportation. This problem is fundamental in supporting decision-making in various practical scenarios, such as container transport in ports and material handling in factories, being classified as NP-hard due to its combinatorial nature. The APVRP presents specific characteristics that make it even more challenging than traditional vehicle routing problem variants, such as the need for efficient synchronization of operations between the two types of vehicles, in addition to compatibility constraints and time windows. The objective of this work is to develop new exact solution methods for the APVRP, using the logic-based Benders decomposition technique. The aim is to propose a Branch-and-Benders-Cut algorithm that allows solving the problem more efficiently than the methods existing in the literature. To evaluate the proposed approaches, computational experiments will be conducted with test instances available in the literature, comparing the results obtained with the state-of-the-art.