Improving last-mile delivery efficiency using cargo bikes and autonomous robots

The advent of unmanned vehicles, such as drones and autonomous robots, presents a promising opportunity to enhance the efficiency and quality of last-mile delivery services. This paper studies a vehicle routing problem involving multiple cargo bikes and autonomous robots, with a focus on realistic loading constraints. Unlike most existing problems that assume single-valued vehicle capacities and customer demands, we account for robots equipped with containers of varying sizes and customers receiving multiple parcels, thereby introducing three-dimensional (3D) packing constraints. To address this problem exactly, we propose a two-stage solution approach. In the first stage, we convert the parcels of each customer into the number of containers of each required size by iteratively solving a 3D packing model with dynamically generated cuts, thereby significantly simplifying the overall problem. The resulting optimization problem is formulated as a set-partitioning model, whose relaxation is strengthened with subset-row inequalities and solved using a state-of-the-art branch-price-and-cut (BPC) algorithm. The BPC algorithm incorporates a bi-directional bounded labeling algorithm, ng-route relaxation, and heuristic labeling techniques to efficiently solve pricing problems with multi-dimensional capacity constraints. Extensive computational results validate the effectiveness of the proposed approach. We further analyze the impact of robot speed, travel cost per unit time, robot utilization, and customer accessibility constraints, providing practical insights for last-mile delivery operations.