A Branch-and-Price Algorithm for Modular Autonomous Vehicle Routing Problem with Pickup and Delivery

Abstract

The development of on-demand transportation and Modular Autonomous Vehicles (MAVs) presents opportunities for dynamic capacity adjustment. However, existing MAV routing models are primarily restricted to fixed transit corridors, limiting their full potential. To bridge this gap, this paper introduces a novel MAV routing problem with pickup and delivery in a fully flexible environment. We propose a model aimed at minimizing total travel costs and penalties for unserved requests, while explicitly incorporating the cost-saving platooning effects of docked MAVs. The problem is formulated as an arc-flow model and reformulated using Dantzig-Wolfe decomposition. To achieve optimal solutions, we develop a branch-and-price algorithm incorporating a labeling algorithm to solve the pricing subproblem. Numerical results show that our exact algorithm outperforms solver in terms of solution speed.