Multi-Agent Training-free Urban Food Delivery System using Resilient UMST Network

Md Nahid Hasan; Vishwam Tiwari; Aditya Challa; Vaskar Raychoudhury; Snehanshu Saha

cs.MAMar 24, 2026

Multi-Agent Training-free Urban Food Delivery System using Resilient UMST Network

Authors: Md Nahid Hasan, Vishwam Tiwari, Aditya Challa, Vaskar Raychoudhury, Snehanshu Saha

Organizations: Department of Computer Science and Software Engineering, Miami University, Oxford, Ohio, USA · Department of Computer Science & Information Systems, BITS Pilani K. K. Birla Goa Campus, and APPCAIR, BITS Goa, India

Abstract

Delivery systems have become a core part of urban life, supporting the demand for food, medicine, and other goods. Yet traditional logistics networks remain fragile, often struggling to adapt to road closures, accidents, and shifting demand. Online Food Delivery (OFD) platforms now represent a cornerstone of urban logistics, with the global market projected to grow to over 500 billion USD by 2030. Designing delivery networks that are efficient and resilient remains a major challenge: fully connected graphs provide flexibility but are computationally infeasible at scale, while single Minimum Spanning Trees (MSTs) are efficient but easily disrupted. We propose the Union of Minimum Spanning Trees (UMST) approach to construct delivery networks that are sparse yet robust. UMST generates multiple MSTs through randomized edge perturbations and unites them, producing graphs with far fewer edges than fully connected networks while maintaining multiple alternative routes between delivery hotspots. Across multiple U.S. cities, UMST achieves 20--40 $\times$ fewer edges than fully connected graphs while enabling substantial order bundling with 75--83% participation rates. Compared to learning-based baselines including MADDPG and Graph Neural Networks, UMST delivers competitive performance (88-96% success rates, 44-53% distance savings) without requiring training, achieving 30 $\times$ faster execution while maintaining interpretable routing structures. Its combination of structural efficiency and operational flexibility offers a scalable and resilient foundation for urban delivery networks.

Figures & tables

Panel of Figure 1 — Figure 1: Construction of UMST Backbone for Columbus (downtown), Ohio. From left to right: (a) completely connected hotspot graph, (b) corresponding UMST graph, and (c) UMST edge count variations.

Figure 2: Average completion time vs. success rate in Chicago under bundling. UMST variants dominate the trade-off curve, with the Nash Bargaining Solution (NBS) representing the best balance between speed and reliability.

Figure 3: Vehicle distance vs. success rate in Chicago under bundling. UMST variants dominate the trade-off curve. The Nash Bargaining Solution (NBS) represents the best balance between efficiency and reliability.

City	Graph	Success	Avg Time	Vehicle	Package	Saved	Bundling
	Type	Rate (%) $\uparrow$	(sec) $\downarrow$	Dist. (km) $\downarrow$	Dist. (km) $\downarrow$	Dist. (km) $\uparrow$	Participation $\uparrow$
Chicago	Clique	$73.82\pm 0.24$	$\mathbf{477.63\pm 2.19}$	$\mathbf{13{,}134.44\pm 119.76}$	$\mathbf{17{,}771.19\pm 152.93}$	$6{,}045.61$	$4{,}520\pm 24$
	UMST	$\mathbf{88.07\pm 0.07}$	$500.37\pm 1.02$	$13{,}480.29\pm 63.43$	$22{,}952.53\pm 54.27$	$\mathbf{10{,}427.44}$	$\mathbf{7{,}690\pm 36}$
	MST	$\mathbf{98.78\pm 0.10}$	$810.03\pm 5.50$	$\mathbf{10{,}853.36\pm 45.29}$	$34{,}038.78\pm 248.44$	$\mathbf{23{,}400.54}$	$\mathbf{9{,}092\pm 10}$
	UMST	$88.07\pm 0.07$	$\mathbf{500.37\pm 1.02}$	$13{,}480.29\pm 63.43$	$\mathbf{22{,}952.53\pm 54.27}$	$10{,}427.44$	$7{,}690\pm 36$
Columbus	Clique	$82.07\pm 0.23$	$\mathbf{599.18\pm 2.00}$	$31{,}354.99\pm 91.47$	$\mathbf{42{,}992.83\pm 122.80}$	$\mathbf{2{,}058.15}$	$4{,}833\pm 47$

Table 1: Performance comparison (Mean ± Std, 10 Runs) of Clique, UMST, and MST backbones across Chicago and Columbus (9,234 deliveries per scenario). Bold values indicate better performance in each comparison. Arrows indicate optimization direction:

\uparrow

higher is better,

\downarrow

lower is better. UMST consistently occupies the middle ground between dense and sparse extremes, achieving substantially higher success rates than Clique while avoiding the excessive delivery times of MST. Across both cities, UMST maintains competitive vehicle distance and strong order bundling participation, demonstrating its ability to balance delivery reliability, efficiency, and operational flexibility more effectively than either baseline.

	Chicago		Columbus
Metric	No Bundling	Bundling	No Bundling	Bundling
Total Deliveries	$9{,}234$	$9{,}234$	$11{,}550$	$11{,}550$
Completion Rate (%) $\uparrow$	$\mathbf{100.00\pm 0.00}$	$98.65\pm 0.04$	$\mathbf{97.72\pm 0.15}$	$96.75\pm 0.16$
Success Rate (%) $\uparrow$	$\mathbf{100.00\pm 0.00}$	$96.08\pm 0.07$	$\mathbf{97.72\pm 0.15}$	$92.53\pm 0.23$
Avg Time (sec) $\downarrow$	$\mathbf{591.97\pm 3.23}$	$641.13\pm 3.34$	$\mathbf{578.43\pm 1.98}$	$653.43\pm 2.08$
Avg Delay (sec) $\downarrow$	$\mathbf{-362.99\pm 1.02}$	$-312.10\pm 0.93$	$\mathbf{-251.36\pm 0.59}$	$-174.90\pm 0.90$

Table 2: Impact of order bundling on UMST performance across Chicago and Columbus (Mean ± Std, 10 Runs). Bold values indicate better performance in each comparison. Arrows indicate optimization direction:

\uparrow

higher is better,

\downarrow

lower is better. Negative delay values indicate early arrivals. Bundling introduces only modest reductions in service quality while delivering dramatic operational gains, cutting total vehicle distance by 44–53% and achieving high consolidation rates. The results show that UMST effectively converts limited increases in delivery time into substantial efficiency, cost, and emission savings, confirming bundling as a highly favorable trade-off when supported by a flexible backbone.

	Columbus				Chicago
Metric	MADDPG	UMST	GNN	UMST	MADDPG	UMST	GNN	UMST
Total Deliveries	9,234	9,234	9,234	9,234	9,234	9,234	9,234	9,234
Completed Del. $\uparrow$	$\mathbf{9,234}$	9,103	$\mathbf{9,234}$	9,103	$\mathbf{9,234}$	9,080	$\mathbf{9,234}$	9,080
Successful Del. $\uparrow$	8,472	$\mathbf{8,868}$	$\mathbf{9,234}$	8,868	8,740	$\mathbf{8,720}$	$\mathbf{9,234}$	8,720
Failed Del. $\downarrow$	762	$\mathbf{235}$	$\mathbf{0}$	235	494	$\mathbf{360}$	$\mathbf{0}$	360
Success Rate $\uparrow$	0.918	$\mathbf{0.960}$	$\mathbf{1.0}$	0.960	0.947	$\mathbf{0.944}$	$\mathbf{1.0}$	0.944

Table 3: Comparison of UMST with learning-based baselines (MADDPG and GNN over UMST backbone) across Columbus and Chicago (9,234 deliveries). Bold values indicate better performance in each comparison. Arrows indicate optimization direction:

\uparrow

higher is better,

\downarrow

lower is better. Negative delay values indicate early arrivals. UMST achieves strong success rates and competitive distance savings while significantly outperforming learned methods in delivery time, offering a robust, training-free alternative that balances reliability, efficiency, and practical deployability.

	Columbus			Chicago
Metric	MADDPG	Attn-MADDPG	UMST	MADDPG	Attn-MADDPG	UMST
Total Deliveries	9,234	9,234	9,234	9,234	9,234	9,234
Completed Del. $\uparrow$	9,234	9,234	9,103	9,234	9,234	9,080
Successful Del. $\uparrow$	8,472	8,979	8,868	8,740	9,102	8,720
Failed Del. $\downarrow$	762	254	235	494	132	360
Success Rate $\uparrow$	0.918	0.972	0.960	0.947	0.986	0.944

Table 4: Comprehensive performance comparison: Vanilla MADDPG vs. Attention-Augmented MADDPG vs. UMST (

N=9,234

). Attention times converted to seconds for consistency.

Vehicle Routing

Vehicle routing studies how to assign and sequence trips for fleets while meeting capacity, time, energy, and service constraints.

See all 135 papers

Learning to Optimize: Joint Routing and Flow Allocation on Sparse Non-Euclidean Networks
Jul 26, 2026Haomiao Sun, Fang He, Congyuan Ji +1Graph Attention Networks Learning to Optimize
Department of Industrial Engineering, Tsinghua University, Beijing 100084, P.R. China · School of Management Science and Engineering, Central University of Finance and Economics, Beijing 100081, P.R. China
EAGLE: Edge-Aware Graph Learning for Proactive Delivery Delay Prediction in Smart Logistics Networks
Apr 6, 2026Zhiming Xue, Menghao Huo, Yujue WangSupply Chain Management Spatiotemporal Forecasting
College of Engineering, Northeastern University Boston, USA · School of Engineering, Santa Clara University Santa Clara, USA · Department of Chemistry and Chemical Biology, University of New Mexico Albuquerque, USA
Systems-Level Planning and Coordination of Truck-Drone Collaborative Delivery Networks
Jun 7, 2026Didem Cicek, Burak KantarciVehicle Routing Multi-Robot Coordination
School of Electrical Engineering and Computer Science at the University of Ottawa, Ottawa, ON, K1N 6N5, Canada

Jul 26, 2026J/K move · Enter open · S save

Learning to Optimize: Joint Routing and Flow Allocation on Sparse Non-Euclidean Networks

Haomiao Sun, Fang He, Congyuan Ji, Xindi Tang

Department of Industrial Engineering, Tsinghua University, Beijing 100084, P.R. China · School of Management Science and Engineering, Central University of Finance and Economics, Beijing 100081, P.R. China

Graph Attention Networks Learning to Optimize Combinatorial Optimization RL for Combinatorial Optimization Neural Combinatorial Optimization

Open paper AskPDF arXiv

We study an integrated pickup-and-delivery problem on sparse, non-Euclidean networks that jointly optimizes cyclic routing, cargo flow allocation, and cross-cycle service. The tight coupling of these operational constraints creates a complex discrete-continuous decision space with highly restricted feasible regions. To overcome these computational challenges, we propose Double-Channel Graph Attention (DCGA), an end-to-end reinforcement learning framework. DCGA isolates network reachability and demand-service logic into separate graph channels and constructs valid routes using a simulator-coupled, constraint-informed decoder. Experiments on LinerLib benchmarks demonstrate that DCGA achieves seconds-level inference and delivers state-of-the-art solution quality on instances beyond a specific scale, with its advantage over existing baselines widening significantly as problem size increases. Supported by extensive stability and ablation analyses, our results demonstrate that this structure-aware learning approach provides an effective, low-latency engine for realistic routing-and-flow optimization.

Abstract

Vehicle Routing

Explore similar work

Learning to Optimize: Joint Routing and Flow Allocation on Sparse Non-Euclidean Networks

EAGLE: Edge-Aware Graph Learning for Proactive Delivery Delay Prediction in Smart Logistics Networks

Systems-Level Planning and Coordination of Truck-Drone Collaborative Delivery Networks