Efficient Graph-Based Multi-Story Path Planning with Optimized Elevator Selection for Indoor Delivery Robots

摘要

Multi-story path planning (MSPP) for indoor delivery robots presents unique challenges in modern logistics systems, particularly in efficiently handling multiple deliveries across different floors. This paper proposes a graph-based path planning algorithm that optimizes delivery routes in multi-story buildings while maintaining computational efficiency. The algorithm, with a complexity of O(|E|log|V|), integrates three key components: (1) a floor-based parcel grouping strategy, (2) an optimized Dijkstra-based path planning system, and (3) an efficient elevator selection mechanism. The modular design allows for adaptability to diverse building layouts and logistics scenarios. Evaluated in a 15-story simulation with varying parcel counts (n = 1 to 7), the algorithm demonstrated minimal runtime increase (1.28 s to 1.35 s) while ensuring optimal path selection. Delivery distances ranged from 48 m (single-parcel) to 126 m (seven parcels), demonstrating the system’s scalability and efficiency in complex multi-story environments. Unlike traditional methods such as A*, the proposed approach guarantees optimality while effectively addressing vertical navigation challenges. These results validate its practical applicability in smart building environments and modern logistics systems, offering a robust solution for real-world delivery challenges.