Conveyor Parcel Routing with Order-Contiguous Arrivals
For warehouse logistics, this work addresses the practical requirement of order-contiguous arrivals to reduce downstream re-sorting effort, providing a complete polynomial-time algorithm for online multi-agent path finding.
The paper formalizes the problem of online multi-agent path finding with order-contiguity (online MAPF-OC) for conveyor parcel routing in warehouses, where parcels of the same order must arrive consecutively. The proposed Dual-Ordering Prioritized Planning (DOPP) algorithm achieves practical scalability and high-quality plans within tight time budgets, as demonstrated on various conveyor-network layouts including real-world warehouse designs.
In warehouse logistics, parcels released from the outfeed of an automated storage system must be routed through conveyor networks to workstations. Beyond collision avoidance, practical operations impose an additional requirement of order-contiguous arrivals: at each delivery point, parcels belonging to the same order must arrive as a consecutive block in the arrival sequence to reduce downstream re-sorting effort. We formalize this problem as online multi-agent path finding with order-contiguity (online MAPF-OC), where agents (i.e., parcels) appear over time and exit upon delivery. To efficiently solve online MAPF-OC, we propose Dual-Ordering Prioritized Planning (DOPP), a complete polynomial-time algorithm with a three-level structure that (i) searches order-level arrival sequences, (ii) refines agent-level priorities, and (iii) synthesizes feasible solutions via prioritized planning. Experiments on various conveyor-network layouts, including those derived from actual warehouses, demonstrate DOPP's practical scalability and ability to generate high-quality plans within tight time budgets.