Branch-and-Price for the Capacitated Autonomous Vehicle Assisted Delivery Problem

In recent years, the exponential growth of package volumes has posed significant challenges for logistics networks, particularly in the realm of last-mile delivery. To mitigate costs while upholding service and delivery commitments, companies are increasingly investigating autonomous assisted delivery as a viable solution. In this paper, we study the Capacitated Autonomous Vehicle Assisted Delivery Problem, where an autonomous vehicle works in conjunction with a delivery person. The autonomous vehicle drops off the delivery person at designated locations, and the delivery person completes the deliveries (with a capacity constraint) on foot to the final addresses. Once the deliveries are completed, the vehicle picks up the delivery person and travels to the next reloading point. The goal is to decide on a route to serve all customers while minimizing the route completion time. We introduce an integer programming formulation with exponentially many variables and develop a branch-and-price approach. For generating promising columns, we present a tailored pulse algorithm to solve the pricing problem. Furthermore, by leveraging the structural properties of optimal solutions, we carefully design algorithmic enhancements, valid inequalities, and preprocessing steps to improve computational tractability. By conducting computational experiments based on instances derived from real-world data, we demonstrate the positive impact of these components. More importantly, we provide optimal certificates for 426 out of the 450 instances documented in the literature. Among the 100 instances in which driving could be slower than walking, we report solutions for the 40 largest instances for the first time. History: Accepted by David Alderson, Area Editor for Network Optimization. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0177 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0177 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .