DOPP algorithm routes warehouse parcels in order-contiguous blocks

In warehouse logistics, parcels leaving automated storage systems must navigate conveyor networks to various workstations. Beyond simple collision avoidance, a critical requirement is order-contiguous arrivals: parcels belonging to the same order must arrive as a consecutive block at each delivery point. This prevents downstream workers from re-sorting mixed orders, a major bottleneck in high-throughput fulfillment centers. Kato and Okumura formalize this as online multi-agent path finding with order-contiguity (online MAPF-OC), where each parcel is an agent that appears over time and exits upon delivery.

To solve this efficiently, the authors propose Dual-Ordering Prioritized Planning (DOPP). DOPP features a three-level hierarchical structure: it first searches over order-level arrival sequences, then refines agent-level priorities, and finally uses prioritized planning to synthesize feasible paths. The algorithm runs in polynomial time and guarantees completeness—it will find a solution if one exists. Experiments on layouts derived from actual warehouses demonstrate DOPP's practical scalability and ability to generate high-quality plans even under strict time constraints. This work bridges multi-agent path finding and real-world logistics constraints, offering a deployable solution for automated warehouses.