Leveraging Public Transit for Robotic Deliveries: A Column Generation Approach

What the paper says

ABSTRACT Autonomous mobile robots (AMRs) are small, electric, wheeled vehicles that operate at pedestrian speeds. In the last‐mile delivery service considered in this study, a fleet of AMRs is deployed across multiple recharging depots within a service area, from which they depart to perform point‐to‐point deliveries. We consider an operational setting in which AMRs are allowed to travel onboard public transit vehicles, with the objective of extending the service range and reducing energy consumption. To model this problem, we propose two mixed‐integer linear programming formulations: an arc‐based formulation and a path‐based formulation. For the latter, we develop a column generation approach coupled with a four‐stage dynamic programming algorithm to efficiently solve the underlying pricing subproblem. This solution approach is further embedded within a rolling horizon framework to address dynamic and large‐scale operational settings. A case study conducted in a subregion of Tel Aviv demonstrates the ability of the proposed methodology to handle large‐scale instances based on real‐world parameters. A sensitivity analysis highlights the effects of request time‐window widths, public transit capacity, and AMR battery range on the number of requests that can be served. Finally, the results obtained under the rolling horizon framework confirm the feasibility and practical applicability of the proposed column generation approach.