Impact of bot return policies in van-and-bot delivery systems

Sidewalk Autonomous Delivery Robots (SADRs) present a promising alternative for mitigating excessive delivery traffic in smart cities. These bots operate at pedestrian speed and work in conjunction with vans to offer efficient delivery services. Existing research emphasises the development of coordinated service schedules for vans and bots to optimise customer service. In contrast, this study examines the influence of bot return policies on their travel back to designated stations after task completion. We assess three distinct return policies that dictate the station selection for bot returns and explore the relocation of bots between stations using vans. Specifically, we present a reformulation of the fleet sizing problem as a minimum cost matching problem in a bipartite graph. This reformulation allows for the efficient calculation of optimal solutions for bot fleet sizing under different return policies within polynomial time. Notably, this computational efficiency enables the analysis of large-scale cases without sacrificing the evaluation of policies with heuristic gaps. Our findings highlight the importance of carefully selecting the appropriate return policy, as the best policies have the potential to decrease the bot fleet size by up to 70%.