Robust Route Planning for Sidewalk Delivery Robots

Abstract

Sidewalk delivery robots are a promising solution for last-mile freight distribution. Yet, they operate in dynamic environments characterized by pedestrian flows and potential obstacles, which make travel times highly uncertain and can significantly affect their efficiency. This study addresses the robust route planning problem for sidewalk robots by explicitly accounting for travel time uncertainty generated through simulated interactions between robots, pedestrians, and obstacles. Robust optimization is integrated with simulation to reproduce the effect of obstacles and pedestrian flows and generate realistic travel times. Three different approaches to derive uncertainty sets are investigated, including budgeted, ellipsoidal, and support vector clustering (SVC)-based methods, together with a distributionally robust shortest path (DRSP) method based on ambiguity sets that model uncertainty in travel-time distributions. A realistic case study reproducing pedestrian patterns in Stockholm's city center is used to evaluate the efficiency of robust routing across various robot designs and environmental conditions. Results show that, when compared to a conventional shortest path (SP) method, robust routing significantly enhances operational reliability under variable sidewalk conditions. The ellipsoidal and DRSP approaches outperform the other methods in terms of average and worst-case delay. Sensitivity analyses reveal that robust approaches are higher for sidewalk delivery robots that are wider, slower, and more conservative in their navigation behaviors, especially in adverse weather and high pedestrian congestion scenarios.