Leveraging Public Transit for Robotic Deliveries: A Column Generation Approach
Authors:
Open Access
- 2 April 2026
- journal article
- Published by Wiley in Naval Research Logistics (NRL)
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.Keywords
This publication has 29 references indexed in Scilit:
- A column generation and Combinatorial Benders Decomposition algorithm for the Selective Dial-A-Ride-ProblemComputers & Operations Research, 2022
- A column generation tailored to electric vehicle routing problem with nonlinear battery depreciationComputers & Operations Research, 2022
- Cost‐optimal truck‐and‐robot routing for last‐mile deliveryNetworks, 2021
- Understanding the transport and CO2 impacts of on-demand meal deliveries: A London case studyCities, 2021
- Last-mile delivery concepts: a survey from an operational research perspectiveOR Spectrum, 2020
- An adaptive large neighborhood search heuristic for the Pickup and Delivery Problem with Time Windows and Scheduled LinesComputers & Operations Research, 2016
- Mathematical formulations for a 1-full-truckload pickup-and-delivery problemEuropean Journal of Operational Research, 2015
- A survey of resource constrained shortest path problems: Exact solution approachesNetworks, 2013
- Static pickup and delivery problems: a classification scheme and surveyTOP, 2007
- Shortest Path Problems with Resource Constraints2006