acceptodds
Under review as a conference paper at ICLR 2027

OT-Dispatch Net: Learning Dynamic Dispatch Policies via Optimal Transport

Abstract

In this paper, we study the multiple traveling salesman problem (mTSP) in a dynamic setting, termed DmTSP, where multiple agents jointly serve a set of requests that arrive sequentially and must be assigned without knowledge of future demand. Compared with mTSP, DmTSP poses a key challenge of jointly determining request allocation across agents and individual assignments while accounting for their downstream routing effects, which remains unexplored. To tackle DmTSP, we propose OT-Dispatch Net, a reinforcement learning framework based on optimal transport (OT). Specifically, OT-Dispatch Net uses an agent marginal and transport costs to model request allocation and agent-request preferences, respectively, allowing OT to couple allocation and assignment decisions in a unified dispatch plan. A soft-quota decoder is further developed to map the resulting transport plan to feasible joint assignments. The policy is trained using a potential-based reward function designed to capture the downstream routing effects induced by dispatch decisions. We theoretically characterize the impact of approximation errors on dispatch quality and show that workload stability can be preserved under bounded decision error. Experiments across synthetic and real-world replay settings demonstrate its superior performance over existing learning-based methods.

Primary area:
optimization
Keywords:
reinforcement learning, optimal transport, neural combinatorial optimization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_FUW7OpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes OT-Dispatch Net, a bilevel sequential framework for DmTSP. The proposed method can simultaneously tackle the optimal dispatch amount and the dispatch solution. Experiments on synthetic and New York ride-hailing prove the efficiency of the proposed method.

Critical strengths
  1. The proposed method seems good, with clear mathematical guarantees, and addresses a real and complex problem. Many previous methods fail to jointly optimize the dispatch amount and decision.

  2. The writing is clear and well structured.

Critical weaknesses
  1. The motivation of this paper, especially the criticism of previous works, is not clear enough. Many order dispatch solutions in the ride-sharing and food delivery fields have already taken the amount factor into consideration by encoding the onboard orders into the observation and designing proper order bundling methods.

  2. In the experiments, the setup is too naive. Mostly, in ride-hailing simulation with the NYC dataset, we consider the number of agents from hundreds to ten thousand. It is unclear what the scaling capacity of the proposed method is.

  3. Comparisons to recent order dispatch solutions in ride-sharing and food delivery are missing.

Questions for authors

My major concern is whether the proposed method can be trained successfully in real large-scale scenarios. In practical mTSP tasks, the main challenge is that the large dimension caused by the number of trips and vehicles hinders efficient training.

2 comments

Dear Reviewer FUW7,

Thank you for the detailed and constructive review. We address each point below.

To W1:

Our motivation is to improve dispatch decisions by jointly representing allocation quantities and assignment preferences. To this end, we propose an OT-based dispatch framework that jointly learns these two components and couples them through marginal constraints.

Admittedly, existing ride-sharing and food-delivery methods account for workload. NeurADP [3] encodes accepted requests as an ordered sequence with remaining delay information, OSPO [1] represents onboard orders and remaining capacity, and DOUBLE-PDF [2] incorporates order bundling. We have added a paragraph in Related Work to discuss these mechanisms and clarify how OT-Dispatch Net differs from these methods.

In these matching-based methods, onboard-order information informs assignment scores, and the number of new requests each agent receives follows from matching. OT-Dispatch Net makes the target allocation share an explicit policy output. It jointly learns each agent’s share of the incoming batch and agent–request costs, then couples them through entropic OT marginal constraints. A soft-quota decoder produces executable assignments, and both outputs are trained using downstream service rewards.

To strengthen our motivation, two results support this distinction. Fixing the marginal to uniform worsens AvgWait and Makespan in all three ablation settings (Figure 2), and our method outperforms the adapted OSPO and DOUBLE-PDF baselines (Table 11).

To W2 and the question on scalability:

Motivated by the fleet sizes considered in the ride-sharing and food-delivery literature, we have extended the NYC evaluation to fleets of 50 to 1,000 agents in Appendix D.8, Table 11 (revised PDF).

  1. For M=50,100,200M=50,100,200, OT-Dispatch Net is trained at the corresponding fleet size on synthetic data and evaluated on NYC instances. Figure 5 shows the training reward curve at M=200M=200.

  2. Training throughput is limited by CPU rollouts, including the routing backend; training at M=200M=200 takes about 35 hours. We could not complete direct training at M=500M=500 or 1,0001{,}000 during rebuttal. The M=200M=200 experiment nevertheless demonstrates training at a substantially larger scale than the original 5–10-agent settings.

  3. Larger fleets use hierarchical task clustering (HTC; Section 4.5, Appendix C, Algorithm 2), which requires no retraining. HTC uses a trained policy to recursively partition requests, repeatedly splitting the cluster with the largest estimated workload before matching partitions to agents. The original submission used the same procedure to deploy the M0=5M_0=5 policy at M=20M=20 (Table 1).

With HTC, mean AvgWait is 66.84 and 67.37 at M=500M=500 and 1,0001{,}000, and mean Makespan is 529.20 and 563.50, over 20 NYC instances per setting. At M=200M=200, the directly trained policy achieves 58.27 and 497.34. Dispatch latency increases from approximately 222 ms to 1.7 s and 5.4 s. HTC therefore enables deployment at 1,000 agents, with moderately higher waiting and completion times than the M=200M=200 setting and increased computation time.

To W3:

Following your suggestion, we reviewed the ride-sharing and food-delivery literature and selected OSPO [1] and DOUBLE-PDF [2] as additional baselines. Table 11 reports these comparisons. OT-Dispatch Net achieves the lowest AvgWait, Makespan, and dispatch latency at every evaluated fleet size. Relative to OSPO, the stronger baseline, AvgWait is 38.5–46.4% lower and Makespan is 17.3–21.8% lower; OSPO takes 3.5–5.1 times as long for dispatch.

Both baselines are adapted to single-location DmTSP requests and trained with the same weighted Makespan and waiting-time objective. We retain OSPO’s shared MLP, policy update rule, and Hungarian matching, and DOUBLE-PDF’s BiLSTM, attention scoring, critic updates, and matching mechanism. DOUBLE-PDF’s payment branch is disabled. Appendix D.8 (revised pdf)provides the adaptation details.

Thank you again for your detailed review. We welcome suggestions for any relevant work we may have overlooked.

References

[1] Zijian Zhao and Sen Li. One Step is Enough: Multi-Agent Reinforcement Learning Based on One-Step Policy Optimization for Order Dispatch on Ride-Sharing Platforms. NeurIPS 2026.

[2] Zijian Zhao and Sen Li. Discriminatory Order Assignment and Payment-Setting of On-Demand Food-Delivery Platforms: A Multi-Action and Multi-Agent Reinforcement Learning Framework. Transportation Research Part E 2026.

[3] Sanket Shah et al. Neural Approximate Dynamic Programming for On-Demand Ride-Pooling. AAAI 2020.

Thank you for your efforts and response. My concerns are fully addressed and I increase my score to 3.

Reviewer_LGmMOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies dynamic multi-agent dispatch with sequentially arriving requests and unknown future demand. OT-Dispatch Net learns agent allocation shares and agent–request costs, couples them through entropic optimal transport, and generates executable assignments using a soft-quota decoder trained with PPO and routing-based rewards. Synthetic benchmarks and NYC pickup-trace replays show reduced waiting times and generally improved makespan; the paper also provides approximation bounds and conditional auxiliary-workload stability analysis.

Critical strengths
  1. The paper introduces an optimal-transport-based dispatch framework that jointly learns agent allocation shares and individual agent–request preferences. Its soft-quota decoder converts continuous transport plans into feasible joint assignments while preserving tractable action likelihoods for policy-gradient training, enabling coordinated allocation and assignment decisions within a unified policy.

  2. The experiments demonstrate consistent reductions in mean waiting time across different fleet sizes and demand levels, generally accompanied by improved makespan. Results on larger fleets using hierarchical task clustering and on held-out NYC pickup traces further support the framework’s ability to transfer beyond its training settings without retraining.

Critical weaknesses
  1. The L-MCF baseline in Section 6.1 is insufficiently specified. The paper states that it uses the same cost-network architecture and is trained separately, but does not explain its training objective or how the network is updated with deterministic minimum-cost-flow execution. Since this is a closely related baseline, these missing details limit reproducibility and confidence in the comparison. The training procedure and budget should be specified.

  2. The Softmax ablation in Section 6.3 does not report its temperature value or how it was selected. Specifying this setting would make the comparison easier to reproduce and interpret.

Questions for authors
  1. What spatial information about pending requests is retained in the agent features, and what motivates using these summaries instead of explicitly encoding the pending routes?

  2. For L-MCF in Section 6.1, what training loss and gradient estimator are used, and how does its training budget compare with OT-Dispatch Net?

  3. For the Softmax ablation in Section 6.3, what temperature was used, and was it matched to or tuned against the OT regularization setting? Were the decoder penalty and cost parameterization otherwise unchanged?

2 comments

Dear Reviewer LGmM,

Thank you for your careful review and positive assessment of our work. We address your questions on agent features, L-MCF training, and the Softmax ablation below.

To Q1:

Agent features retain the agent’s current location and normalized depot offset, together with three summaries of its pending route: pending request count, estimated route completion time, and remaining service time. For [0,100]2[0,100]^2 with depot (50,50)(50,50), the offset is Δidepot=[(xi−50)/100,(yi−50)/100]\Delta_i^{\mathrm{depot}}=[(x_i-50)/100,(y_i-50)/100]. New requests are represented through their locations, depot distances, and distance-based edges. The spatial arrangement of pending visits is reflected indirectly through the estimated route completion time, rather than represented by individual visit coordinates or their sequence.

These summaries keep the representation fixed-dimensional as routes grow while describing workload and expected availability. The dispatch policy uses current agent locations and these summaries, a trade-off of this design. Because ownership is fixed once assigned, the routing backend then uses full route information to determine insertion positions and visit order. Sections 4.1–4.2, Eq. (3), and Appendix E.1 describe the observation and graph construction.

To W1 and Q2:

We have added Appendix E.5 to specify L-MCF's training procedure and budget.

L-MCF uses the same encoder architecture as OT-Dispatch Net, with independently trained parameters, and optimizes clipped PPO with GAE. Its gradient estimator is a likelihood-ratio (score-function) estimator. Following the Gaussian score-sampling design of the PPO baseline evaluated by Hoppe et al. [1], we sample pair costs and allocation logits around their predicted means. These determine the MCF costs and integer quotas, and the resulting routing and service outcomes provide the reward. The PPO ratio uses the samples' joint Gaussian density, updating the encoder and both heads without differentiating through quota rounding or MCF. Evaluation uses the means. Eqs. (76)–(81) give the details.

For each training size (M0=5,10M_0=5,10), both methods use 200 epochs × 4,000 environment steps = 800,000 steps per run, batch size 32, 10 gradient steps per PPO update, and one candidate per training decision. Demand distributions, instance-generation rules and seeds, reward, and routing backend also match. These controls align training-data exposure and optimization settings without assuming equal wall-clock time. Table 14 summarizes the comparison.

To W2 and Q3:

In Section 6.3 and Figure 2, we use τ=0.05\tau=0.05 to match ε=0.05\varepsilon=0.05. Sinkhorn uses Gibbs weights exp⁡(−C/ε)\exp(-C/\varepsilon) and Softmax uses exp⁡(−C/τ)\exp(-C/\tau). Matching them keeps exponential cost scaling identical, so the ablation examines transport coupling without also changing temperature.

Softmax replaces Sinkhorn with P⋅j=softmax⁡(−C⋅j/τ)P_{\cdot j}=\operatorname{softmax}(-C_{\cdot j}/\tau). We retain C=−gC=-g, the learned agent marginal, and the soft-quota decoder with α=10\alpha=10 and δ=0.5\delta=0.5. OT uses the marginal to couple assignment probabilities across requests; Softmax uses it only in decoding. Keeping the cost parameterization and decoding penalty unchanged isolates the role of the transport constraints.

We also trained a separate Softmax variant with τ=1\tau=1. The table reports the three Figure 2 settings, with columns labeled by training temperature.

(M,AP)(M,\mathrm{AP})AvgWait ↓ (τ=0.05\tau=0.05)AvgWait ↓ (τ=1\tau=1)Makespan ↓ (τ=0.05\tau=0.05)Makespan ↓ (τ=1\tau=1)
(5,9)(5,9)235.91238.93819.08846.45
(20,6)(20,6)125.89130.25643.07660.27
(20,9)(20,9)164.76166.50699.88783.26

The matched temperature gives lower AvgWait and Makespan in all three evaluated settings.

Thank you again for your valuable feedback.

Reference

[1] Heiko Hoppe et al. Structured Reinforcement Learning for Combinatorial Decision-Making. NeurIPS 2025.

Thank you for your comprehensive response. You have addressed all of my questions and concerns. Please ensure these important details are included in the final version.

Reviewer_7TBhOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies the Dynamic Multiple Traveling Salesman Problem (DmTSP), where requests arrive online and must be assigned to agents. mTSP is a classic machine learning problem and has been well studied over the past two decades. The proposed solution, OT-Dispatch Net, learns agent-level request allocation and agent–request preferences, coupling them through entropic optimal transport. Experiments across different scenarios show reductions in average waiting time compared with state of the art. Theoretical analysis provides assignment-cost bounds and conditional stability results.

Critical strengths
  1. The dynamic aspect of the problem, and the fact that the requests are not known a priori, add importance and novelty to the problem. The paper is well written and the proposed solution is sound.

  2. Learning an agent marginal and coupling it with assignment preferences through optimal transport is an interesting idea. It directly addresses workload allocation in dynamic dispatch, and the reported ablations support the importance of this design.

  3. The performance is evaluated thoroughly, indicating a moderate improvement using the proposed solution. Theoretical analysis provides cost bounds and stability results (I did not check the proof).

Critical weaknesses
  1. For the baselines, the average over 30 instances is reported, but no variance measure is provided. For the proposed method, the average and variation across five training seeds are reported. These differences in uncertainty measures prevent reliable significance assessment of the results. Also, the performance gain in low-demand settings is relatively small (2.9%), raising questions about its applicability in such settings.

  2. The workload-stability theorem concerns an auxiliary workload process rather than actual pending requests, waiting time, or makespan. In addition, the reward depends on Cb(sk)C^b(s_k), an estimate of completion time. The paper does not describe how this estimate is calculated or provide an error analysis.

Questions for authors
  1. Can the authors provide paired confidence intervals or statistical tests against all baselines using matched evaluation instances, including the NYC experiments?

  2. How does the auxiliary workload process relate quantitatively to actual waiting time, outstanding requests, or makespan?

  3. How is the completion-time potential, Cb(sk)C^b(s_k), estimated and validated in the evaluation?

  4. In the evaluation part, the classical methods receive fixed decision-time budgets, while reported neural inference latency may exclude route insertion. How do the results change under matched end-to-end computational budgets?

2 comments

Dear Reviewer 7TBh,

Thank you for the detailed and constructive review. We address each point below.

To W1 and Q1:

We have added paired 95% confidence intervals against all baselines, including NYC, in Appendix D.7, Tables 9–10 (revised PDF). All methods were rerun on the original evaluation data and matched by instance.

All 84 AvgWait intervals favor OT-Dispatch Net, including every low-demand comparison (AP=6\mathrm{AP}=6). For Makespan, 80 of 84 intervals favor our method, three include zero, and ACO performs better at (5,6)(5,6) (difference −14.62-14.62, CI [−25.27,−3.36][-25.27,-3.36]) but has higher AvgWait. Thus, the low-demand waiting-time benefit is modest but consistently positive, with a waiting/completion trade-off against ACO at (5,6)(5,6).

To W2 and Q2:

The auxiliary workload tracks assignment-induced work and service through its queue recursion. Under Assumption 1, Theorem 2 bounds its long-run average expected total by (B+ξ)/η(B+\xi)/\eta, quantifying how bounded assignment error affects the stability guarantee. Here, ξ\xi bounds the one-step assignment-cost gap and η\eta is the reference policy’s service margin. With other constants fixed, increasing ξ\xi by Δξ\Delta\xi loosens the workload bound by Δξ/η\Delta\xi/\eta.

Thank you for raising the question of how auxiliary workload relates to physical service metrics. We have added Corollary 8 in Appendix B.5(revised pdf)to provide a quantitative link. Let Ri(k)R_i(k) denote the remaining committed route duration, including depot return. Set μi(k)=Δt\mu_i(k)=\Delta t and define dij(k)d_{ij}(k) as the out-and-back detour from the nearest remaining route stop to request jj, plus service time. If the backend returns a route no longer than the original remaining route augmented with these detours, a batch adds at most Ai(k)=∑jdij(k)Yij(k)A_i(k)=\sum_j d_{ij}(k)Y_{ij}^{(k)}. Under the corollary's initial and execution conditions,

Ri(k+1)≤[Ri(k)−Δt+Ai(k)]+,Ri(k)≤Qi(k).R_i(k+1)\le[R_i(k)-\Delta t+A_i(k)]_+,\qquad R_i(k)\le Q_i(k).

The bound (B+ξ)/η(B+\xi)/\eta then also applies to the long-run average expected total remaining route duration. After the last assignment, Makespan≤tk⋆+max⁡iQi(k⋆)\mathrm{Makespan}\le t_{k_\star}+\max_i Q_i(k_\star).

AvgWait additionally depends on service order, which the workload model does not track. We measure it directly from execution trajectories and leave an order-aware bound to future work.

To W2 and Q3:

The completion-time potential is computed deterministically from committed routes. For an active agent,

C^i(sk)=tk+τitravel(sk)+τiservice(sk),C^b(sk)=max⁡iC^i(sk).\widehat C_i(s_k)=t_k+\tau_i^{\mathrm{travel}}(s_k)+\tau_i^{\mathrm{service}}(s_k),\qquad \widehat C^b(s_k)=\max_i\widehat C_i(s_k).

Travel includes the remaining current segment, subsequent segments, and depot return; service includes unfinished and pending service. Returning agents contribute their remaining return time, while idle agents retain their actual return timestamps. The estimate is recomputed when routes change and equals Makespan at termination. Section 4.1's telescoping identity gives an undiscounted return of Φ(s0)−Obj(π)\Phi(s_0)-\mathrm{Obj}(\pi), so intermediate estimates shape per-step feedback without changing this episode objective.

Using the evaluation simulator, we tested 256 controlled five-agent states covering pending visits, active service, return travel, and post-return idling. There were 128 states each at service durations 0 and 1. Routes were fixed and arrivals disabled.

CheckMaximum absolute error (simulation time units)
Estimate versus direct execution0
Estimate versus execution in 30-unit decision steps3.43×10−53.43\times10^{-5}
Terminal potential versus latest depot return0

These results verify travel/service accounting and return-time handling for committed routes. The check concerns current-route completion rather than unknown future demand.

To Q4:

Table 1 reports dispatch latency. To account for routing costs, we have added Table 7 to report total per-decision time, including routing, and Table 8 in Appendix D.6 to compare all methods under matched end-to-end budgets (revised PDF). These budgets cover search/inference, candidate evaluation, insertion, and replanning, and are set to 0.5/1 s at (M,AP)=(5,12)(M,\mathrm{AP})=(5,12), 1/2 s at (10,9)(10,9), and 2/4 s at (20,9)(20,9).

OT-Dispatch Net achieves the lowest AvgWait and Makespan in all six comparisons, improving on the best baseline by 3.79–7.44% and 0.90–7.10%, respectively. Its advantage therefore persists when routing is included in the common budget.

Thank you again for your valuable feedback.

Thanks for the reply, please consider including the important information in the paper. I'll keep my current positive score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Response to Reviewers

We sincerely thank all reviewers for their positive feedback and constructive suggestions. We are pleased that our responses have addressed the concerns raised, and we appreciate your recognition of our revisions.

Following your suggestions, we have incorporated the important details and additional results from our responses into the revised manuscript:

  • Related work: Clarified the distinction between OT-Dispatch Net and existing ride-sharing and food-delivery methods.
  • Expanded evaluation: Added comparisons with OSPO and DOUBLE-PDF for fleets of 50–1,000 agents, including training and latency details (Appendix D.8).
  • Statistical and computational comparisons: Added paired confidence intervals, total computation times, and comparisons under matched end-to-end budgets (Appendices D.5–D.7).
  • Theory and validation: Added a quantitative connection between auxiliary workload and remaining route duration, together with completion-time potential validation (Appendices B.5 and E.8).
  • Implementation and ablations: Clarified agent features, L-MCF training, and Softmax ablation controls, and included the temperature comparison (Appendices E.1, E.4–E.5, and E.9).

These revisions are highlighted in blue in the updated PDF. Thank you again for your time and valuable feedback.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.