Paper deep dive
Conveyor Parcel Routing with Order-Contiguous Arrivals
Takuro Kato, Keisuke Okumura
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 7/8/2026, 2:48:20 PM
Summary
This paper addresses parcel routing in warehouse conveyor networks by formalizing the problem as online Multi-Agent Path Finding with Order-Contiguity (online MAPF-OC). It introduces Dual-Ordering Prioritized Planning (DOPP), a complete polynomial-time algorithm that uses a three-level structure to search order-level arrival sequences, refine agent-level priorities, and synthesize collision-free, order-contiguous paths via prioritized planning. Experiments demonstrate DOPP's scalability and ability to generate high-quality plans with tight time budgets on realistic warehouse layouts.
Entities (11)
Relation Signals (8)
Takuro Kato → affiliatedwith → Toyota Industries Corporation
confidence 95% · Takuro Kato1 &Keisuke Okumura2 1Toyota Industries Corporation, Japan
Keisuke Okumura → affiliatedwith → AIST
confidence 95% · 2National Institute of Advanced Industrial Science and Technology (AIST), Japan
DOPP → solves → online MAPF-OC
confidence 95% · To efficiently solve online MAPF-OC, we propose Dual-Ordering Prioritized Planning (DOPP)
order-contiguity → appliesto → conveyor network
confidence 90% · 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
online MAPF-OC → extends → MAPF
confidence 90% · 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.
DOPP → hascomplexity → polynomial-time
confidence 90% · we propose Dual-Ordering Prioritized Planning (DOPP), a complete polynomial-time algorithm with a three-level structure
DOPP → uses → prioritized planning
confidence 90% · synthesizes feasible solutions via prioritized planning (PP) Erdmann and Lozano-Pérez (1987); Silver (2005).
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2605.13035v1
- Canonical: https://arxiv.org/abs/2605.13035v1
Trouble viewing inline? Open PDF directly →
Full Text
58,081 characters extracted from source content.
Expand or collapse full text
Conveyor Parcel Routing with Order-Contiguous Arrivals Takuro Kato1 &Keisuke Okumura2 1Toyota Industries Corporation, Japan 2National Institute of Advanced Industrial Science and Technology (AIST), Japan takuro.kato@mail.toyota-shokki.co.jp, okumura.k@aist.go.jp Abstract 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, (i) refines agent-level priorities, and (i) 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. 1 Introduction Figure 1: Conveyor-based fulfillment system in warehouse logistics. Parcels retrieved at the outfeed of an automated storage system (e.g., grid-based robotic storage systems Salzman and Stern (2020); Chen et al. (2021)) enter a directed one-way conveyor network and are routed online to workstations under collision avoidance. The order-contiguity constraint requires parcels of the same order to arrive contiguously (i.e., without interleaving by other orders) at each workstation. Photos sourced from Bastian Solutions (2025). In modern fulfillment centers, parcels retrieved at the outfeed of an automated storage system are injected into the conveyor network and delivered to workstations. Figure 1 illustrates a typical setup. While conveyors are a standard component of intra-facility transport, networks with many merges and splits are prone to congestion and blocking. Thus, even if the upstream storage system releases parcels quickly and the terminal workstations process parcels sufficiently fast, overall throughput can still be constrained by delays within the intermediate conveyor network. Therefore, efficient outfeed-to-workstation routing is crucial for system performance. Such a scenario can be naturally abstracted as multi-agent path finding (MAPF) Stern et al. (2019), which has been widely studied in warehouse automation to synthesize the collision-free motion of many robots performing upstream retrieval. However, parcel routing on conveyor networks, which often form the downstream transport layer, has received comparatively less attention. We model this transport as online MAPF Švancara et al. (2019), where agents (i.e., parcels) are released over time at the storage outfeed, traverse the directed conveyor network under collision avoidance, are processed at workstations by human/robotic operators, and then exit. Beyond collision avoidance captured by online MAPF, practical fulfillment operations impose an additional requirement: parcels must be grouped by order and handled together at the same workstation. If parcels of different orders interleave in the arrival sequence, operators must re-sort them, increasing workload and processing delay. This poses a novel order-contiguity constraint: at each workstation, parcels with the same order must arrive consecutively, without interleaving with other orders, thereby forming a consecutive block. To this end, we formalize online MAPF with order-contiguity (online MAPF-OC). To solve this, we propose a search-based anytime algorithm, called Dual-Ordering Prioritized Planning (DOPP), consisting of a three-level optimization process: (i) it first searches over order-level priorities to determine the arrival sequence of orders at workstations; (i) it refines priorities within orders at the agent level; and (i) given these priorities, it synthesizes collision-free and order-contiguous paths via prioritized planning (P) Erdmann and Lozano-Pérez (1987); Silver (2005). DOPP is complete and runs in polynomial time; it quickly constructs a feasible solution and then iteratively improves the makespan over time. We evaluate DOPP on various conveyor-network maps, including realistic layouts derived from operational warehouses, demonstrating its practical scalability within tight time budgets and strong makespan performance relative to an ad-hoc reactive policy. 2 Related Work Parcel transport. Routing and control for baggage/parcel transport systems have been widely studied, including approaches for online route choice and flow coordination in track-like networks Tarau et al. (2010); Zeinaly et al. (2015). These approaches typically focus on coarse routing decisions, while junction-level coordination relies on local rule-based checks Klotz et al. (2013), thereby limiting opportunities for globally efficient scheduling. For conveyor systems, often targeting specific conveyor layouts, several optimization-based schemes have been studied Ago et al. (2007); Novak et al. (2023), which reduce routing to structured problems solvable by off-the-shelf solvers, such as MILP or network-flow formulations. However, this direction introduces a large number of variables and is computationally prohibitive, making it unsuitable for online planning at scale. This motivates our search-based MAPF approach for online synthesis of collision-free parcel trajectories on general directed graphs. Multi-agent path finding (MAPF) is a generic abstraction for coordinating multiple entities on a shared graph under collision avoidance with prominent applications in warehouse automation Stern et al. (2019). To date, various MAPF solvers have been proposed, ranging from computationally heavy but optimal approaches Sharon et al. (2015) to scalable but suboptimal approaches Okumura (2023b). To capture persistent warehouse-like operations, lifelong MAPF has been proposed, where each agent receives a new goal upon reaching its current one Ma et al. (2017). Online MAPF models a stream of agents that appear over time, while previously revealed agents may already be executing their plans Švancara et al. (2019). Our conveyor routing problem inherits this lifelong/online nature but additionally introduces an operational requirement on the arrival sequence at each destination. As another closely related variant, MAPF-PC (with precedence constraints) Zhang et al. (2022) assumes that each agent is given a sequence of goals together with precedence constraints between goal-completion events. In contrast, our focus, MAPF-OC, imposes an order-level non-interleaving constraint at each destination: parcels sharing an order must arrive as a contiguous block, while the order of these blocks is a decision variable optimized for the makespan objective. Beyond warehouse robotics, MAPF-based techniques have been applied to broad domains, such as rail networks Li et al. (2021a) and autonomous intersection coordination Li et al. (2023); Yan et al. (2024); we similarly extend the application scope of MAPF to conveyor systems. Figure 2: Online replanning at τr _r. Executed trajectories up to τr _r are fixed and form the initial state of the snapshot. Visible agents are classified as finished (already disappeared; black), unfinished (still on the conveyor or not entered yet; green), and newly visible (revealed within the lookahead HrH_r; blue). The snapshot at τr _r plans trajectories for unfinished and newly visible agents from τr _r onward. Visible Agents rA^r i oio_i sis_i gig_i timint_i 11 u↑u v↓v 2020 22 u↑u v↓v 2828 33 u↓u v↓v 2525 44 u↓u v↓v 2929 55 u↓u v↑v 3131 66 u↑u v↑v 3434 Figure 3: Example of snapshot with τr=30 _r=30, Hr=5H_r=5, and k=4k=4. The colors correspond to order labels. Agent 11 arrives at its destination at t=30t=30 and stays in service during t=31,…,34t=31,…,34, and disappears at t=35t=35. To preserve order-contiguity at destination v↓v , agents 33 and 44 wait until agent 22 passes the junction. This waiting blocks the entry cell, so although t5min=31t_5 =31, the entry of agent 55 is delayed to t5=33t_5=33. By t=35t=35, the remaining parcels are queued so that future arrivals at destinations form consecutive order blocks (i.e., order-contiguous). 3 Problem Definition This section formalizes MAPF-OC. We present the system model and constraints, and define the offline/online problems. 3.1 System Model Conveyor network. We model the conveyor network as a directed graph G=(V,E)G=(V,E). Each vertex v∈Vv∈ V represents a unit-capacity conveyor segment, and each directed edge (u,v)∈E(u,v)∈ E represents one-way transport. We distinguish entry vertices ⊂VS⊂ V, where parcels are injected into the conveyor network, and destination vertices ⊂VG⊂ V, corresponding to workstations in the physical system (leftmost and rightmost cells in Fig. 1, respectively). Agents and orders. Each parcel corresponds to an agent i∈i that moves on G in discrete time t∈ℕ≥0t _≥ 0 and is associated with a tuple ⟨oi,si,gi,timin⟩ o_i,s_i,g_i,t_i , where oi∈o_i is an order label, si∈s_i is an entry vertex, and gi∈g_i is its destination. We assume a fixed order-to-destination assignment d:→d:O and set gi=d(oi)g_i=d(o_i), and require that gig_i is reachable from sis_i in G. Each agent has an earliest entry time timint_i . The actual entry time tit_i is a decision variable and can be any ti≥timint_i≥ t_i . Upon reaching its destination, an agent must stay there for a service time of k steps and then leaves the network. This models the handling time at the workstation (e.g., unloading/packing). We assume a uniform k for simplicity. 3.2 Constraints Time-dependent path for an agent i∈i is a function πi:ℕ≥0→V∪⊥ _i:N_≥ 0→ V∪\ \, where πi(t) _i(t) denotes the location at time t and ⊥ represents “outside the network.” We define the destination arrival time Ti:=mint∣πi(t)=giT_i:= \t _i(t)=g_i\. A path πi _i is valid if there exists an entry time ti≥timint_i≥ t_i such that πi(t)=⊥(t<ti),πi(ti)=si, _i(t)= \ (t<t_i), _i(t_i)=s_i, πi(t+1)∈πi(t)∪v∣(πi(t),v)∈E(ti<t<Ti), _i(t+1)∈\ _i(t)\∪\v ( _i(t),v)∈ E\(t_i<t<T_i), πi(t)=gi(Ti≤t≤Ti+k),πi(t)=⊥(t>Ti+k). _i(t)=g_i\;(T_i≤ t≤ T_i+k), _i(t)= \;(t>T_i+k). That is, an agent waits or moves to an outgoing neighbor each step, must stay at its destination during service, and then leaves the network. A set of paths π=πi∣i∈π=\ _i i \ is collision-free if |i∈∣πi(t)=v|≤1|\i _i(t)=v\|≤ 1 for all v∈Vv∈ V and t∈ℕ≥0t _≥ 0. Note that swap collisions are impossible on a directed one-way network. Order-contiguity. Given a destination g∈g , let (i1,…,im)(i_1,…,i_m) be the agents with destination g sorted by increasing arrival times, i.e., Ti1<⋯<TimT_i_1<·s<T_i_m. We say π satisfies order-contiguity at g if for any 1≤p<q<r≤m1≤ p<q<r≤ m, oip=oir⇒oip=oiqo_i_p=o_i_r o_i_p=o_i_q. Thus, the arrival sequence at each destination can be partitioned into consecutive order blocks. The set of paths π is order-contiguous if it satisfies the above for all g∈g . 3.3 Offline MAPF with Order-Contiguity The offline setting corresponds to the one-shot MAPF problem: an instance specifies G and a finite set of agents A. A set of paths π=πi∣i∈π=\ _i i \ is a feasible solution if it is valid, collision-free, and order-contiguous. We define the makespan of π as maxi∈(Ti+k) _i \,(T_i+k). 3.4 Online MAPF with Order-Contiguity Batch-based replanning. In practice, conveyor systems operate continuously for extended periods (e.g., several hours to a full day). Planning the entire operation in one-shot is impractical, both because the problem scale becomes enormous and because future order information may be incomplete or change over time. We therefore replan in batches over rounds r∈1,…,rendr∈\1,…,r_end\. Let τr _r be the replanning timestep of round r, with τ1:=0 _1:=0 and τr+1>τr _r+1> _r. We define the lookahead as Hr:=τr+1−τrH_r:= _r+1- _r. At replanning time τr _r, we call agents whose earliest entry time is before τr+Hr _r+H_r, visible, defined as: r:=i∈∣timin<τr+Hr.A^r:=\i t_i < _r+H_r\. (1) We assume that all agents of the same order are revealed within a single replanning window (single-window reveal). This assumption is not merely for modeling simplicity: without sufficient order information, the order-contiguity constraint can become ill-posed online, since newly revealed parcels of an already-processed order may force unavoidable violations of contiguity. Formally, for each o∈o , there exists an index ror_o such that τro≤timin<τro+1∀i∈j∈∣oj=o. _r_o≤ t_i < _r_o+1 ∀ i∈\j \ o_j=o\. (2) Snapshot problem. The initial state of the snapshot at replanning time τr _r is given by the executed trajectories until τr _r, as depicted in Fig. 2. In addition, newly visible agents in the current lookahead window are given. Agents that have already finished service and disappeared by τr _r remain known, but are excluded from replanning. At replanning time τr _r, a snapshot plan πrπ^r is a feasible solution if (i) πir(t)=πir−1(t) _i^r(t)= _i^r-1(t) for all agents i∈r−1i ^r-1 and all t≤τrt≤ _r, and (i) the resulting trajectories for agents in rA^r are valid, collision-free, and order-contiguous over the entire time horizon. Let TirT_i^r denote the arrival time of agent i under πir _i^r, and define the snapshot makespan as maxi∈r(Tir+k) _i ^r\,(T_i^r+k). A feasible solution is snapshot-optimal if it minimizes this makespan. Figure 3 illustrates examples of a snapshot instance and a feasible solution. Lifelong objective. In this online setting, agents keep becoming visible over replanning steps, and we assume the arrival stream eventually terminates. We aim to minimize the completion time of the last agent, although no online algorithm can guarantee to achieve this global optimum in general Švancara et al. (2019). We therefore optimize the snapshot makespan at each replanning time as a practical surrogate for this objective. Computational complexity. Finding a snapshot-optimal solution is NP-hard. This follows from the NP-hardness of makespan-minimizing MAPF shown in Ma et al. (2016): their reduction can be adapted to our snapshot setting by considering a single replanning window and assigning each agent to a distinct order. Thus, in this work, we do not aim to compute optimal solutions; rather, our focus is on establishing suboptimal yet scalable real-time planning. 4 Dual-Ordering Prioritized Planning In MAPF-OC, agents can wait outside the network before entering and leave their destination after a bounded service time. These structural conditions correspond to a well-formed setting, under which prioritized planning (P) is guaranteed to find a feasible solution in polynomial time Čáp et al. (2015). Motivated by this, we develop a P-based anytime algorithm, termed Dual-Ordering Prioritized Planning (DOPP), which quickly constructs a feasible solution to the snapshot problem defined in Sec. 3.4, then improves the makespan as time permits. Repeated over replanning rounds, DOPP yields a lifelong execution; the offline setting is the special case of a single round. We focus on P for practicality, among the mainstream MAPF paradigms: CBS and its extensions Sharon et al. (2015); Li et al. (2021b) are ill-suited to real-time planning with hundreds of agents, while PIBT and its successors Okumura et al. (2022); Okumura (2023b) are known to perform poorly in narrow corridors Okumura (2023a). Besides, enforcing order-contiguity in PIBT necessitates conservative operation, which reduces efficiency, as we observe empirically in Sec. 5. In the following, we first provide an overview of DOPP, and then describe initialization for obtaining a feasible plan, followed by theoretical properties and anytime refinement. 4.1 Overview Structure. DOPP searches priority constraints at high level and runs P at low level, similar to PBS Ma et al. (2019) for classical MAPF. To enforce order-contiguity, DOPP maintains precedence constraints at both order level and agent level, yielding a three-level structure: Level 3 searches order precedence, Level 2 searches agent priority subject to Level 3, and Level 1 applies P under the resulting priorities. Pseudocode and conceptual illustration are shown in Alg. 1 and Fig. 4, respectively. Priority constraints. Let r:=oi∣i∈rO^r -2.84526pt:= -2.84526pt\o_i i ^r\ be the visible orders at τr _r, where rA^r is the set of visible agents in Eq. (1). DOPP maintains two sets of constraints: an order-precedence set ≺r _O^r over rO^r and an agent-priority set ≺r _A^r over rA^r. An element o≺o′o o of ≺r _O^r (or i≺ji j of ≺r _A^r) means that o (resp. i) has higher priority than o′o (resp. j). Replanning policy. In the online setting, while it is possible to replan priorities of all visible agents at each replanning time τr _r, DOPP instead adopts a committed-suffix policy to preserve well-formedness. That is, agents that are already on the network at τr _r are given higher priority so that they are cleared from the network first. The relative priorities among these agents are inherited from the previous plan for consistency. As a result, DOPP optimizes priorities for agents/orders that have not entered the network at τr _r yet. Figure 4: Workflow of DOPP. Initialization constructs an order precedence (Level 3) and an order-consistent agent priority (Level 2), and then computes a feasible snapshot solution by P (Level 1). Refinement performs neighborhood search: Level 3 perturbs the pending-order subsequence (window permutation), while Level 2 perturbs the agent order within a selected pending order. Algorithm 1 High-level of DOPP (snapshot at τr _r) 1:Visible agents rA^r, previous snapshot solution πr−1π^r-1 2:Initialize precedence constraints ≺r,≺r _O^r, _A^r⊳ Section 4.2 3:Topologically sort ≺r _A^r to obtain rL_A^r (a total order over rA^r) 4:πr←π^r← run Level 1 with rL_A^r and ≺r _O^r 5:while ¬interrupt() interrupt() do 6: Construct neighbor constraints ≺~r,≺~r _O^r, _A^r ⊳ Section 4.4 7: Topologically sort ≺~r _A^r to obtain ~r L_A^r 8: π~r← π^r← run Level 1 with ~r L_A^r and ≺~r _O^r 9: if makespan(π~r)<makespan(πr)makespan( π^r)<makespan(π^r) then 10: πr←π~rπ^r← π^r; ≺r←≺~r _O^r← _O^r; ≺r←≺~r _A^r← _A^r 11:return πrπ^r⊳ Snapshot solution at τr _r Agents and orders classification. Herein, to illustrate DOPP, we call an agent active if it is already on the conveyor at τr _r; otherwise it is pending: actr:=i∈r∣πir−1(τr)∈V,pendr:=r∖actr.A_act^r -2.84526pt:= -2.84526pt\i ^r -2.84526pt -2.84526pt _i^r-1( _r)∈ V\,A_pend^r -2.84526pt:= -2.84526ptA^r -1.42262pt -1.42262ptA_act^r. (3) Likewise, an order is active if it has at least one active agent; otherwise it is pending: actr:=o∈r∣∃i∈actr:oi=o,pendr:=r∖actr.O_act^r -2.84526pt:= -2.84526pt\o ^r -2.84526pt -2.84526pt∃ i _act^r -1.42262pt: -1.42262pto_i=o\,O_pend^r -2.84526pt:= -2.84526ptO^r -1.42262pt -1.42262ptO_act^r. (4) 4.2 Initialization We detail how to quickly compute an initial solution via P (lines 2–4 in Alg. 1). As P conducts agent-wise path planning based on priorities assigned to each agent, we need to obtain a total ordering over agents, while being careful about maintaining the feasibility of P. The Level 2 and Level 3 procedures construct such an order. Level 3: order precedence. We initialize the order-precedence constraints ≺r _O^r as follows: (i) place all active orders before pending ones to avoid breaking ongoing arrival blocks, (i) inherit the relative precedence among active orders from the previous round, and (i) set precedence among pending orders by an earliest-entry heuristic. Formally, let ≺−1:=∅ _O^-1:= for r=0r=0. For r≥0r≥ 0, we define ≺r _O^r as the union of the following constraints: ≺r:= _O^r:=\ o≺o′∣o∈actr,o′∈pendr o o o _act^r,o _pend^r\ (5) ∪ ∪\ o≺o′∣o,o′∈actr,(o≺o′)∈≺r−1 o o o,o _act^r,(o o )∈ _O^r-1\ (6) ∪ ∪\ o≺o′∣o,o′∈pendr,ρo<ρo′, o o o,o _pend^r, _o< _o \, (7) where ρo:=mintimin∣i∈r,oi=o _o:= \\,t_i i ^r,\ o_i=o\,\. Ties in ρo _o are broken uniformly at random. Level 2: agent priority. We initialize the agent-priority constraints ≺r _A^r to be consistent with the order precedence and to preserve feasibility across replanning rounds. Intuitively, we (i) enforce order-consistency, i.e., agents of higher-precedence orders are planned before those of lower-precedence orders; then, (i) for active orders o∈actro _act^r, those having at least one agent on the conveyor at τr _r, inherit the pairwise precedence among their agents from the previous round; and (i) for pending orders o∈pendro _pend^r, those having no agent on the conveyor at τr _r, initialize precedence among their agents with timint_i . Formally, let ≺−1:=∅ _A^-1:= for r=0r=0. For r≥0r≥ 0, define ≺r _A^r as the union of the following constraints: ≺r:= _A^r:=\ i≺j∣i,j∈r,(oi≺oj)∈≺r i j i,j ^r,(o_i o_j)∈ _O^r\ (8) ∪ ∪\ i≺j∣oi=oj,oi∈actr,(i≺j)∈≺r−1 i j o_i=o_j,o_i _act^r,(i j)∈ _A^r-1\ (9) ∪ ∪\ i≺j∣oi=oj,oi∈pendr,timin<tjmin. i j o_i=o_j,o_i _pend^r,t_i <t_j \. (10) We then apply topological sort to ≺r _A^r in order to obtain a total ordering over rA^r, denoted by rL_A^r, which is used in Level 1. Ties in timint_i are broken uniformly at random. Level 1: P. Level 1 synthesizes a snapshot solution by applying standard P under rL_A^r: agents are planned sequentially using space-time A* Silver (2005) while avoiding previously planned paths. We must additionally enforce order-contiguity by applying destination blocking, which forbids agent i from occupying its destination gig_i before time Γi _i: Γi:=maxTjr+k+1∣j∈r,gj=gi,(oj≺oi)∈≺r. _i:= \T_j^r+k+1 j ^r,g_j=g_i,(o_j o_i)∈ _O^r\. If the set is empty, we set Γi:=0 _i:=0. Since rL_A^r respects ≺r _O^r, this yields order-contiguous arrivals. 4.3 Theoretical Analysis DOPP’s initialization in Sec. 4.2 ensures that the snapshot instance at each τr _r falls into a well-formed setting: agents may wait outside the network, and destinations are released after bounded service. This reduces the snapshot feasibility of MAPF-OC to feasibility under P (Level 1). Therefore, running Level 1 once under the initialized priorities yields a feasible snapshot solution in polynomial time. Full proofs are provided in Appendix. Lemma 1. For every round r, ≺r _O^r and ≺r _A^r admit a total ordering over rO^r and rA^r, respectively, via topological sorting. Lemma 2. At every round r, the snapshot solution produced by Level 1 is order-contiguous. Theorem 1. At each replanning time τr _r, DOPP constructs a feasible snapshot solution in polynomial time. 4.4 Refinement The solution obtained by initialization is feasible but is based on heuristically chosen priorities, leaving room for makespan improvement. In the batch-based replanning assumed in Sec. 3.4, planning for the next batch can proceed while the current batch is being executed, providing additional computation time. DOPP therefore performs an anytime refinement (lines 5–10 in Alg. 1) that searches better priority constraints at Level 3 and/or Level 2, while preserving well-formedness. Implementation details are provided in Appendix. Order-precedence refinement. Level 3 refines ≺r _O^r by modifying the constraints in Eq. 7, while keeping the constraints in Eq. 5 and 6 unchanged; this preserves well-formedness by retaining precedence among active orders. We perform neighborhood search (NS) over pending orders by selecting a contiguous window of WL3W_L3 orders and sampling KL3K_L3 candidate perturbations within it (Fig. 4, bottom). For each candidate, we rebuild ≺~r _O^r accordingly, re-initialize the corresponding agent-priority constraints, and evaluate it by running Level 1. These candidate evaluations are independent and can be parallelized. Small-A|V||V|==69, λ==11, |r||A^r|==300Small-B|V||V|==72, λ==11, |r||A^r|==300Medium-A|V||V|==159, λ==11, |r||A^r|==300Medium-B|V||V|==162, λ==11, |r||A^r|==300Complex|V||V|==229, λ==33, |r||A^r|==500Large|V||V|==360, λ==33, |r||A^r|==1000One-shotLifelong← /LBImpr.(%)→ . Util.(%)→← /LBAvg. Util.(%)→ time k Figure 5: Results for one-shot and lifelong experiments. Headers give the map name, graph size |V||V|, arrival rate λ, and the number of visible agents per window |r||A^r|, along with the layout (yellow: entries S; red: destinations G). Upper rows shows the results for the one-shot problem: makespan M/MLBM/M_LB, relative makespan improvement over Vanilla DOPP by anytime refinement, Impr. (%):=100⋅(MVanilla−M)/MVanilla Impr.\,(\%):=100·(M_Vanilla-M)/M_Vanilla, and the utilization U¯ U. Lower rows show those for the lifelong problem: makespan and utilization over 10 consecutive online windows. Each curve shows the mean over 20 instances. Shaded areas indicate the standard deviation for representative methods. Agent-priority refinement. Level 2 refines ≺r _A^r by modifying the constraints in Eq. 10, while keeping the constraints in Eq. 8 and 9 unchanged; this preserves well-formedness by retaining priorities among active agents. We perform NS by selecting a pending order o∈pendro _pend^r and sampling KL2K_L2 alternative orderings of its agents. For each candidate, we rebuild the constraints ≺~r _A^r accordingly and evaluate it by rerunning Level 1. Combination strategy. Refinement can be applied at Level 3 only, at Level 2 only, or by combining both. For example, we may (i) refine ≺r _O^r and, for each candidate, rebuild ≺r _A^r using the initialization rule and evaluate it by rerunning Level 1; and/or (i) additionally refine ≺r _A^r for each Level 3 candidate, generating multiple candidates before rerunning Level 1. We compare these strategies in Sec. 5. 5 Evaluation This section evaluates the effectiveness of DOPP in terms of snapshot quality, runtime, scalability, anytime behavior, and lifelong performance. All solvers are implemented in C++ and run on a MacBook Pro (Apple M3 Max, 128 GB128\,GB RAM). 5.1 Setup Maps. We use directed conveyor maps shown in Fig. 5 (top row), designed to cover both typical warehouse layouts and stress-test settings. Small-A/B are simple maps that capture basic topology, and Medium-A/B are practical-scale maps derived from existing conveyor systems. To stress-test beyond typical layouts, we also include Complex and Large maps to evaluate planners in more complex and large-scale environments. Herein, we denote the length of exit-buffer as LbufL_buf (e.g., 88 for Medium-A/B). Parcel generation. At each time t=0,1,…t=0,1,…, we generate λ new agents with the earliest entry time timin=t_i =t. To maintain a comparable workload density across map scales, λ is set to 11 for Small/Medium-A/B, and 33 for Complex and Large. For each planning time τr _r, we set the number of agents visible per window |r||A^r| to 300300 for Small/Medium-A/B, 500500 for Complex, and 1,0001,000 for Large. In the lifelong scenario, the next planning time τr+1 _r+1 is set to maxi∈rtimin _i ^rt_i . Agents are generated in order blocks: we sample an order size lol_o uniformly at random from 1,…,Lbuf\1,…,L_buf\, generate lol_o agents for the order, and then switch to the next order. Each agent chooses its entry sis_i at random from the map-specific set S. Destinations are assigned per order to maintain a balanced workload across G by selecting the destination with the current minimum cumulative count and updating the count after assignment. These settings are intended to mimic typical fulfillment operations. DOPP variants. For snapshot experiments, we evaluate five variants of DOPP: Vanilla (no refinement, i.e., initial solution), Level3-NS (refine only Level 3; rebuild Level 2 as in initialization for each Level 3 candidate), Level2-NS (refine only Level 2; keep Level 3 fixed), Sequential NS (first refine Level 3, then refine Level 2 for the best Level 3 candidate), and Nested NS (for each Level 3 candidate, refine Level 2 to generate multiple candidates). For neighborhood search, we use WL3=7W_L3=7 and KL3=KL2=10K_L3=K_L2=10. These hyperparameters were set via a pilot study; see Appendix. We use a 60 s60\,s refinement budget per snapshot instance: Level2/3-NS run for 60 s60\,s, Sequential NS runs Level 3 for 40 s40\,s then Level 2 for 20 s20\,s, and Nested NS uses 60 s60\,s total for Level 3 with a 1 s1\,s cap for each inner Level 2 call. Level 3 refinement is parallelized with up to 16 threads. Baseline. We also evaluate the baseline PIBT-AC, which runs PIBT Okumura et al. (2022)—a representative MAPF algorithm that prevents collisions locally—and enforces order-contiguity via admission control (AC). For each destination g, while an order to g is active, agents of other orders destined for g are not admitted into the network, and the lock is released when the remaining agents of the active order are within LbufL_buf steps of g. This provides an intuitive and scalable rule-based solution to MAPF-OC. Note that adapting other MAPF solvers, such as CBS variants, is non-trivial due to the order-contiguity constraint. Furthermore, these methods are not well suited for real-time planning on large-scale problems, which led to the current experimental design. Metrics. We use the normalized makespan M/MLBM/M_LB, where M=maxi(Ti+k)M= _i(T_i+k), MLB=maxi(timin+dist(si,gi)+k)M_LB= _i (t_i +dist(s_i,g_i)+k ), and distdist is the shortest travel time on G; hence MLBM_LB serves as the makespan lower bound. We also report average destination utilization U¯ U (%) to diagnose whether performance is limited by destination capacity. When U¯ U is close to 100%, improving makespan requires increasing destination capacity (e.g., adding workstations) rather than better routing. Concretely, for each destination g, let xg(t)=1x_g(t)=1 iff ∃i:πi(t)=g∃ i: _i(t)=g (otherwise 0), and denote ta(g)=mint∣xg(t)=1t_a(g)= \t x_g(t)=1\ and tb(g)=maxt∣xg(t)=1t_b(g)= \t x_g(t)=1\. The utilization is U(g):=100⋅(∑t=ta(g)tb(g)xg(t))/(tb(g)−ta(g)+1)U(g):=100· ( _t=t_a(g)^t_b(g)x_g(t) )/(t_b(g)-t_a(g)+1), and U¯ U is the average over destinations. 5.2 Results We first solve the snapshot offline problem (Sec. 3.3) to analyze the behavior of DOPP variants, and then evaluate the representative ones on the lifelong setting (Sec. 3.4). Snapshot quality. Figure 5 (upper) summarizes makespan, improvement over Vanilla DOPP, and destination utilization across six maps while sweeping the service time k. Across all maps and k, DOPP consistently outperforms PIBT-AC, and even Vanilla achieves strong makespans. The advantage over PIBT-AC is striking on Small-A/B, where admission control induces long waits relative to the map size, whereas DOPP remains close to the lower bound for k≤3k≤ 3. As k increases, the utilization approaches saturation, and the makespan degrades for all methods, suggesting that performance becomes dominated by workstation capacity rather than routing decisions. The benefit of refinement is most visible at intermediate k values where both routing conflicts and destination bottlenecks matter; in these cases, Level3-NS yields the best results, followed by Sequential NS. This highlights that order precedence (Level 3) is a primary driver of performance. The same trend appears on Medium-A/B, where the gap among DOPP variants is particularly pronounced, and it persists on the Complex and Large maps, demonstrating robustness to complex layouts and larger instances. Small-AMedium-ALarge Figure 6: Runtime at representative snapshot settings in Fig. 5. Each point shows the mean over 20 instances. Figure 7: DOPP’s scalability on Medium-A. Runtime and makespan against the number of visible agents |r||A^r| are shown. Service time k is set to five. Each point shows the mean over 20 instances. Medium-A (|r|=300|A^r|=300) Large (|r|=1,000|A^r|=1,000) Figure 8: Anytime refinement on Medium-A (left) and Large (right), over 20 instances. Top: relative makespan improvement of Level3-NS over Vanilla DOPP after a planning budget 10/30/60/18010/30/60/180 ss. Bottom: best-so-far makespan versus runtime under the 180 s180\,s budget across the various service time k. Runtime and scalability. Figure 6 reports runtime at representative snapshot cases sampled from the one-shot results in Fig. 5. PIBT-AC is extremely lightweight and runs in 50 ms50\,ms even on Large (|r|=1,000|A^r|=1,000) with k=3k=3, while Vanilla DOPP remains practical (≈0.53 s≈$0.53\,s$) despite achieving much better solution quality. Runtime increases mildly as k grows due to longer makespans and deeper space-time searches, but remains below 0.1 s0.1\,s on Small/Medium-A and below 1 s1\,s even on Large. Figure 7 stresses Vanilla on Medium-A by increasing the number of visible agents. Runtime grows with |r||A^r| but stays below 1 s1\,s even with |r|=1,200|A^r|=1,200. This scalability performance covers practically relevant horizons for conveyor control, since far-future parcels are less certain in online operation. The normalized makespan improves with larger |r||A^r|, because the denominator MLBM_LB increases with later release times while M stays close to MLBM_LB. Anytime behavior. We analyze how solution quality improves with additional computation time. In Fig. 8, the top row quantifies the benefit of refinement by plotting the relative makespan improvement of Level3-NS over Vanilla DOPP under different time budgets. Medium-A largely saturates by 10 s10\,s (≈7.5%≈7.5\% improvement at k=6k=6), whereas Large continues to improve as time permits (e.g., exceeding 10%10\% improvement at k=3k=3) due to its instance scale. The bottom row plots best-so-far makespan versus time, showing that most gains are obtained early on Medium-A. On Large, rapid initial improvements are followed by slower but persistent progress up to the time limit. Lifelong performance. Finally, we evaluate the online setting by solving 10 consecutive windows111Pilot experiments with longer scenarios showed similar qualitative trends.. Figure 5 (lower) shows that the snapshot improvements translate to lifelong replanning—DOPP continues to produce effective replans, resulting in consistently lower makespan than PIBT-AC. Refinement via Level3-NS remains beneficial in the lifelong setting; for example, on Medium-A with k=5k=5, Vanilla finds a feasible plan in 0.3 s0.3\,s per window on average, and Level3-NS removes about 92%92\% of the excess over the lower bound (from 1.0931.093 to 1.0071.007). Vanilla is slightly slower than in one-shot runs (Fig. 6) because agents carry over across windows, but the overhead is modest since P dominates its runtime and scales linearly with the number of planned agents. As an implementation note, replanning intervals τr+1−τr _r+1- _r span hundreds of timesteps across maps in our setup, so the 60 s60\,s refinement budget fits within each replanning cycle. These results indicate that the gains observed in snapshot planning carry over to settings where decisions must be made repeatedly online, with the system state evolving from previous decisions. 6 Conclusion We formulated online MAPF-OC on conveyor networks and presented DOPP, an anytime algorithm that quickly finds feasible solutions and improves makespan as time permits. Experiments demonstrated practical scalability and strong solution quality. This work enriches an application example of foundational MAPF algorithms beyond typical warehouse sortation. Future work includes extending online MAPF-OC to incorporate the parcel entry positions and destination assignment for more advanced logistics automation. References Ago et al. [2007] Masatoshi Ago, Tatsushi Nishi, and Masami Konishi. Simultaneous optimization of storage allocation and routing problems for belt-conveyor transportation. Journal of Advanced Mechanical Design, Systems, and Manufacturing, 2007. Bastian Solutions [2025] Bastian Solutions. Sawtooth merge / goods-to-person workstation. https://w.bastiansolutions.com/solutions/technology/sortation/merges-combiners/sawtooth/, https://w.bastiansolutions.com/solutions/technology/conveyor-systems/bastian-solutions-conveyor/goods-to-person-workstation/, 2025. Accessed: 2025-12-24. Chen et al. [2021] Zhe Chen, Javier Alonso-Mora, Xiaoshan Bai, Daniel D. Harabor, and Peter J. Stuckey. Integrated task assignment and path planning for capacitated multi-agent pickup and delivery. IEEE Robotics and Automation Letters (RA-L), 2021. Erdmann and Lozano-Pérez [1987] Michael Erdmann and Tomás Lozano-Pérez. On multiple moving objects. Algorithmica, 1987. Klotz et al. [2013] Thomas Klotz, Jens Schönherr, Norman Seßler, Bernd Straube, and Karsten Turek. Automated formal verification of routing in material handling systems. IEEE Transactions on Automation Science and Engineering (T-ASE), 2013. Li et al. [2021a] Jiaoyang Li, Zhe Chen, Yi Zheng, Shao-Hung Chan, Daniel Harabor, Peter J. Stuckey, Hang Ma, and Sven Koenig. Scalable rail planning and replanning: Winning the 2020 flatland challenge. In Proc. Int. Conf. on Automated Planning and Scheduling (ICAPS), 2021. Li et al. [2021b] Jiaoyang Li, Wheeler Ruml, and Sven Koenig. Eecbs: Bounded-suboptimal search for multi-agent path finding. In Proc. AAAI Conf. on Artificial Intelligence (AAAI), 2021. Li et al. [2023] Jiaoyang Li, The Anh Hoang, Eugene Lin, Hai L. Vu, and Sven Koenig. Intersection coordination with priority-based search for autonomous vehicles. In Proc. AAAI Conf. on Artificial Intelligence (AAAI), 2023. Ma et al. [2016] Hang Ma, Craig Tovey, Guni Sharon, T. K. Satish Kumar, and Sven Koenig. Multi-agent path finding with payload transfers and the package-exchange robot-routing problem. In Proc. AAAI Conf. on Artificial Intelligence (AAAI), 2016. Ma et al. [2017] Hang Ma, Jiaoyang Li, T.K. Satish Kumar, and Sven Koenig. Lifelong multi-agent path finding for online pickup and delivery tasks. In Proc. Int. Conf. on Autonomous Agents & Multiagent Systems (AAMAS), 2017. Ma et al. [2019] Hang Ma, Daniel Harabor, Peter J. Stuckey, Jiaoyang Li, and Sven Koenig. Searching with consistent prioritization for multi-agent path finding. In Proc. AAAI Conf. on Artificial Intelligence (AAAI), 2019. Novak et al. [2023] Antonin Novak, Matous Pikokus, and Zdenek Hanzalek. Optimization of circular conveyor belt systems with multi-commodity network flows. In Proc. Int. Conf. on Operations Research and Enterprise Systems (ICORES), 2023. Okumura et al. [2022] Keisuke Okumura, Manao Machida, Xavier Défago, and Yasumasa Tamura. Priority inheritance with backtracking for iterative multi-agent path finding. Artificial Intelligence (AIJ), 2022. Okumura [2023a] Keisuke Okumura. Improving lacam for scalable eventually optimal multi-agent pathfinding. In Proc. Int. J. Conf. on Artificial Intelligence (IJCAI), 2023. Okumura [2023b] Keisuke Okumura. Lacam: Search-based algorithm for quick multi-agent pathfinding. In Proc. AAAI Conf. on Artificial Intelligence (AAAI), 2023. Salzman and Stern [2020] Oren Salzman and Roni Stern. Research challenges and opportunities in multi-agent path finding and multi-agent pickup and delivery problems. In Proc. Int. Conf. on Autonomous Agents & Multiagent Systems (AAMAS), 2020. Sharon et al. [2015] Guni Sharon, Roni Stern, Ariel Felner, and Nathan R. Sturtevant. Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence (AIJ), 2015. Silver [2005] David Silver. Cooperative pathfinding. In Proc. AAAI Conf. on Artificial Intelligence and Interactive Digital Entertainment (AIIDE), 2005. Stern et al. [2019] Roni Stern, Nathan Sturtevant, Ariel Felner, Sven Koenig, Hang Ma, Thayne Walker, Jiaoyang Li, Dor Atzmon, Liron Cohen, T. K. Kumar, Roman Barták, and Eli Boyarski. Multi-agent pathfinding: Definitions, variants, and benchmarks. In Proc. Ann. Symp. on Combinatorial Search (SoCS), 2019. Tarau et al. [2010] Alina N. Tarau, Bart De Schutter, and Hans Hellendoorn. Model-based control for route choice in automated baggage handling systems. IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2010. Čáp et al. [2015] Michal Čáp, Peter Novák, Alexander Kleiner, and Martin Selecký. Prioritized planning algorithms for trajectory coordination of multiple mobile robots. IEEE Transactions on Automation Science and Engineering (T-ASE), 2015. Švancara et al. [2019] Jiří Švancara, Marek Vlk, Roni Stern, Dor Atzmon, and Roman Barták. Online multi-agent pathfinding. In Proc. AAAI Conf. on Artificial Intelligence (AAAI), 2019. Yan et al. [2024] Zhongxia Yan, Han Zheng, and Cathy Wu. Multi-agent path finding for cooperative autonomous driving. In Proc. IEEE Int. Conf. on Robotics and Automation (ICRA), 2024. Zeinaly et al. [2015] Yashar Zeinaly, Bart De Schutter, and Hans Hellendoorn. An integrated model predictive scheme for baggage-handling systems: Routing, line balancing, and empty-cart management. IEEE Transactions on Control Systems Technology, 2015. Zhang et al. [2022] Han Zhang, Jingkai Chen, Jiaoyang Li, Brian C. Williams, and Sven Koenig. Multi-agent path finding for precedence-constrained goal sequences. In Proc. Int. Conf. on Autonomous Agents & Multiagent Systems (AAMAS), 2022. Appendix Appendix A Proofs We provide omitted proofs for lemmas and theorems in Sec. 4.3. Lemma 1. For every round r, ≺r _O^r and ≺r _A^r admit a total ordering over rO^r and rA^r, respectively, via topological sorting. Proof. We prove the claim for ≺r _O^r and ≺r _A^r separately. Order precedence ≺r _O^r. We argue by induction on r. At r=0r=0, visible orders are totally ordered by the key ρo _o with tie-breaking. Assume ≺r−1 _O^r-1 induces a total ordering on the visible orders of round r−1r-1. In round r, DOPP places every active order before every pending order (Eq. (5)), inherits the relative precedence among active orders from ≺r−1 _O^r-1 (Eq. (6)), and totally orders pending orders by sorting ρo _o with tie-breaking (Eq. (7)). Thus any two distinct orders in rO^r are comparable, and ≺r _O^r admits a total ordering via topological sorting. Agent priority ≺r _A^r. We argue by induction on r. We show that ≺r _A^r admits a total ordering over rA^r by establishing that any two distinct agents i,j∈ri,j ^r are comparable. If oi≠ojo_i≠ o_j, then ≺r _O^r totally orders oio_i and ojo_j, and Eq. (8) transfers this order to i and j; hence i and j are comparable in ≺r _A^r. Now consider the case oi=oj=o_i=o_j=o. If o∈actro _act^r, then by the single-window reveal assumption (Eq. (2)), all agents of order o were already visible in round r−1r-1 and hence were included in ≺r−1 _A^r-1. By the induction hypothesis, ≺r−1 _A^r-1 admits a total ordering over these agents, and Eq. (9) preserves their pairwise precedence in round r; hence i and j are comparable. If o∈pendro _pend^r, then all agents of o are pending and are ordered by tmint with tie-breaking (Eq. (10)), hence i and j are comparable. Hence every pair of distinct agents in rA^r is comparable, and ≺r _A^r admits a total ordering via topological sorting. ∎ Lemma 2. At every round r, the snapshot solution produced by Level 1 is order-contiguous. Proof. We show that destination blocking in Level 1, introduced in Sec. 4.2, enforces order-contiguity. Fix a destination g∈g and consider the agents destined to g sorted by increasing arrival times Ti1r<⋯<TimrT_i_1^r<·s<T_i_m^r. Suppose for contradiction that the arrival sequence at g is not order-contiguous. Then there exist indices 1≤p<q<r≤m1≤ p<q<r≤ m such that oip=oiro_i_p=o_i_r and oip≠oiqo_i_p≠ o_i_q. Let o:=oir(=oip)o:=o_i_r(=o_i_p) and o′:=oiqo :=o_i_q. By Lemma 1, either o≺o′o o or o′≺o o holds. If o≺o′o o , then for agent iqi_q we have Γiq≥Tirr+k+1, _i_q\ ≥\ T_i_r^r+k+1, because iri_r is an agent of the higher-precedence order o assigned to the same destination g. Hence Tiqr≥Γiq>TirrT_i_q^r≥ _i_q>T_i_r^r, contradicting Tiqr<TirrT_i_q^r<T_i_r^r. The case o′≺o o symmetrically contradicts Tipr<TiqrT_i_p^r<T_i_q^r. Therefore no such triple exists and arrivals at g are order-contiguous. ∎ Theorem 1. At each replanning time τr _r, DOPP constructs a feasible snapshot solution in polynomial time. Proof. We first establish completeness (existence of a feasible snapshot solution returned by P under the constructed priorities), and then bound the computational complexity. Completeness. We prove by induction on r that Level 1 always plans all agents in rA^r without failure, producing a snapshot-feasible solution. For the case r=0r=0, Lemma 1 ensures that the initialized precedences ≺0 _O^0 and ≺0 _A^0 admit total orderings over 0O^0 and 0A^0. Thus P under the induced total agent order produces a collision-free snapshot plan, and order-contiguity follows from Lemma 2. Hence π0π^0 is feasible. Active agents. Consider the active agents actrA_act^r. By definition in Eq. (3), every agent in actrA_act^r was already planned at τr−1 _r-1. Level 1 plans all active agents before any pending agent, and preserves their relative priority from round r−1r-1 (Eq. (5) and Eq. (9)). By the induction hypothesis, πr−1π^r-1 is snapshot-feasible, so a feasible continuation exists at τr _r for all active agents. Therefore, P succeeds for all agents in actrA_act^r. Pending agents. After planning agents in actrA_act^r, let t⋆t be any time strictly after all already planned agents have disappeared from the network. A finite t⋆t exists because every agent that reaches its destination leaves the network after k steps. When planning a pending agent i∈pendri _pend^r, choose an entry time ti≥maxtimin,t⋆,Γi.t_i≥ \t_i ,t , _i\. Then follow any directed path from sis_i to gig_i, which exists under the reachability assumption in Sec. 3. Since the network is empty after t⋆t , this yields a valid collision-free path that also respects destination blocking. Repeating this for all pending agents shows that P succeeds for all agents in pendrA_pend^r. Finally, order-contiguity follows from Lemma 2. Thus the resulting snapshot solution is feasible. Polynomial time. Levels 3 and 2 consist of sorting and topological sorting over rO^r and rA^r, thus run in polynomial time. For Level 1, we provide a finite horizon that always contains a feasible solution. We define, Cactr:=maxi∈actr(Tir−1+k+1)if actr≠∅,τrotherwise,C_act^r:= cases _i _act^r (T_i^r-1+k+1 )&if A_act^r≠ ,\\ _r&otherwise, cases and tmaxr:=maxi∈pendrtiminif pendr≠∅,τrotherwise.t_ ^r:= cases _i _pend^rt_i &if A_pend^r≠ ,\\ _r&otherwise. cases Let D:=|V|−1D:=|V|-1 and define T¯r:=maxCactr,tmaxr,τr+|pendr|(D+k+1). T^r:= \C_act^r,\,t_ ^r,\, _r\+|A_pend^r|\,(D+k+1). When planning an agent, Level 1 searches on the time-expanded graph truncated at T¯r T^r, which has O(|V|⋅T¯r)O(|V|· T^r) vertices and O(|E|⋅T¯r)O(|E|· T^r) edges. Space-time A* search on this graph runs in polynomial time in |V|,|E|,|V|,|E|, and T¯r T^r. Repeating this for all agents in rA^r yields an overall polynomial running time. ∎ Appendix B Implementation Details of Refinement We describe the implementation of the neighborhood searches in Level 3 and Level 2 introduced in Sec. 4.4. Order-precedence refinement (Level 3). Let rL_O^r be a total ordering over rO^r obtained by topologically sorting ≺r _O^r, and let ,pendrL_O,pend^r be the subsequence of rL_O^r containing only pending orders in pendrO_pend^r. We select a contiguous window of WL3W_L3 orders in ,pendrL_O,pend^r, and sample KL3K_L3 perturbed sequences by randomly permuting its elements. For each perturbed sequence ~,pendr=(o1,…,om) L_O,pend^r=(o_1,…,o_m), we construct candidate precedence constraints among pending orders as the chain ≺~,pendr:=ol≺ol+1∣l=1,…,m−1 _O,pend^r:=\o_l o_l+1 l=1,…,m-1\, and form ≺~r _O^r by replacing Eq. 7 with ≺~,pendr _O,pend^r while keeping Eq. 5 and 6 unchanged. We then re-initialize the agent-priority constraints under ≺~r _O^r and evaluate the candidate by running Level 1. Agent-priority refinement (Level 2). Let rL_A^r be the total ordering over rA^r obtained in initialization by topologically sorting ≺r _A^r. We select a pending order o∈pendro _pend^r and extract the subsequence of its agents from rL_A^r. We then sample KL2K_L2 perturbed orderings of these agents, yielding ~,or=(i1,…,iq) L_A,o^r=(i_1,…,i_q). For each candidate, we encode it as a chain priority constraint among agents of o, ≺~,or:=il≺il+1∣l=1,…,q−1 _A,o^r:=\i_l i_l+1 l=1,…,q-1\, and build ≺~r _A^r by replacing the corresponding part of Eq. 10 while keeping Eq. 8 and 9 unchanged. Then, we evaluate each candidate by running Level 1. Appendix C Pilot Study for Hyperparameter Selection Setup. We conducted a pilot study to select the hyperparameters for neighborhood search in Level 2 and Level 3. We used the same protocol as the snapshot evaluations in Sec. 5. For Medium-A, we fixed λ=1λ=1, |r|=300|A^r|=300, and k=5k=5; for Large, we fixed λ=3λ=3, |r|=1000|A^r|=1000, and k=6k=6. For each setting, we solved 20 instances and report the average normalized makespan (Makespan/LB) over snapshots. The k values were chosen because the refinement effect of DOPP is most pronounced in these regimes. Results. Table 1 summarizes sensitivity to KL2K_L2 (Level 2), and Table 2 summarizes sensitivity to (WL3,KL3)(W_L3,K_L3) (Level 3). Entries marked “–” are omitted: for WL3=3W_L3=3, the window admits only 3!=63!=6 permutations, so we tested only KL3∈3,10K_L3∈\3,10\ and skipped larger values. These results show that moderate values of KL2K_L2 and KL3K_L3 perform best. Larger KL2K_L2 and KL3K_L3 spend too much time enumerating permutations for a single window, reducing the number of distinct candidates explored within the given refinement time budget. Based on these results, we set WL3=7W_L3=7 and KL3=KL2=10K_L3=K_L2=10 for experiments in Sec. 5. KL2K_L2 Medium-A Large 3 1.076 1.913 10 1.075 1.922 50 1.104 1.937 100 1.103 1.943 500 1.123 1.935 Table 1: Results of pilot study for Level 2: sensitivity to KL2K_L2 (average Makespan/LB over 20 instances; best in bold). KL3K_L3 WL3W_L3 3 10 50 100 500 Medium-A 3 1.07 1.06 – – – 7 1.06 1.05 1.06 1.06 1.06 15 1.07 1.06 1.07 1.07 1.07 50 1.13 1.13 1.13 1.13 1.13 Large 3 1.86 1.86 – – – 7 1.83 1.82 1.86 1.86 1.87 15 1.82 1.81 1.83 1.86 1.87 50 1.95 1.93 1.93 1.94 1.94 Table 2: Results of pilot study for Level 3: sensitivity to (WL3,KL3)(W_L3,K_L3) (average Makespan/LB over 20 instances; best in bold, “–” indicates omitted combinations).