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

Rui Zhang ()
Additional contact information
Rui Zhang: Leeds School of Business, University of Colorado Boulder, Boulder, Colorado 80309

INFORMS Journal on Computing, 2025, vol. 37, issue 5, 1328-1349

Abstract: 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.

Keywords: autonomous vehicle; routing; last-mile delivery; branch-and-price (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2023.0177 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:37:y:2025:i:5:p:1328-1349

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().