Synergizing Drone Delivery Order Pooling and Road Network Monitoring through Monitoring-Task Orderization

Yulong Hu; Meng Xu; Sen Li; Nikolas Geroliminis

cs.MAOct 4, 2026

Synergizing Drone Delivery Order Pooling and Road Network Monitoring through Monitoring-Task Orderization

Authors: Yulong Hu, Meng Xu, Sen Li, Nikolas Geroliminis

Organizations: Department of Civil and Environmental Engineering, The Hong Kong University of Science and Technology, Hong Kong, China · School of Architecture, Civil and Environmental Engineering (ENAC), École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland

Abstract

This paper investigates the real-time dispatch of a shared drone fleet for on-demand food delivery and urban road network monitoring. We consider a courier-drone collaborative setting in which couriers transport orders to launchpads and drones complete the final delivery leg to kiosks. Drones may consolidate multiple origin-destination orders within one flight and make monitoring-aware route adjustments to collect real-time traffic information subject to delivery-time constraints. This yields a joint decision problem coupling dynamic order-to-drone matching, multi-order pooling, routing, and time-varying monitoring under fleet-level competition and uncertainty. We propose monitoring-task orderization, which periodically converts road-network nodes with high congestion and stale information into virtual monitoring orders. Pooling these virtual tasks with food-delivery orders creates a unified heterogeneous task set and transforms the coupled matching-and-routing problem into an order-level decision process. Building on this abstraction, we formulate a decentralized graph-interdependent Multi-Agent Markov Decision Process and develop Graph Multi-Agent Q-Learning (Graph-MAQL), which captures localized inter-agent dependencies through bipartite match coordination graphs. Agent-task value estimates are then used as edge weights in a dynamic heterogeneous bipartite matching program for globally feasible execution. Experiments using real-world data reveal strong operational synergy between delivery and monitoring. Monitoring-task orderization improves monitoring performance by 25.1% with less than a 1% reduction in delivery performance, while Graph-MAQL improves the aggregate objective by up to 20.8%, reduces deadline violations by over 40%, and transfers zero-shot to higher demand intensity without retraining.

Figures & tables

Figure 1: An illustrative example of dispatching drone fleets for on-demand delivery pooling and road network monitoring.

Figure 2: Overview of our proposed framework for dispatch of drone fleets for on-demand delivery and road network monitoring.

$\alpha$	Orders Picked Up	Deadline Violation Rate (%)	Link Coverage Rate (%)	Bottleneck Roads Monitor Frequency	Delivery Score (HKD)	Monitoring Score	Average Occupied Seats
0	4188 $\pm$ 12.2	5.0 $\pm$ 0.90	63.9 $\pm$ 1.07	3.90 $\pm$ 0.18	79639 $\pm$ 657	5555 $\pm$ 145	2.25 $\pm$ 0.03
3	4191 $\pm$ 12.3	4.3 $\pm$ 0.80	69.7 $\pm$ 0.69	4.29 $\pm$ 0.14	80129 $\pm$ 557	5926 $\pm$ 97.3	2.31 $\pm$ 0.03
6	4189 $\pm$ 14.4	6.4 $\pm$ 1.16	71.1 $\pm$ 1.04	4.59 $\pm$ 0.15	79057 $\pm$ 774	6269 $\pm$ 132.3	2.33 $\pm$ 0.04
8	4161 $\pm$ 16.2	6.6 $\pm$ 1.15	72.3 $\pm$ 0.70	4.80 $\pm$ 0.13	78129 $\pm$ 652	6550 $\pm$ 74.3	2.40 $\pm$ 0.03
10	4138 $\pm$ 13.3	9.0 $\pm$ 0.84	72.7 $\pm$ 0.61	4.90 $\pm$ 0.15	75747 $\pm$ 1027	6558 $\pm$ 104.3	2.45 $\pm$ 0.03

Table 1: Performance under varying monitoring priority weight

\alpha

without monitoring-task orderization.

$k$	Orders Picked Up	Deadline Violation Rate (%)	Link Coverage Rate (%)	Bottleneck Roads Monitor Frequency	Delivery Score (HKD)	Monitoring Score	Overall Score (HKD)
0	4191 $\pm$ 12.3	4.3 $\pm$ 0.80	69.7 $\pm$ 0.69	4.29 $\pm$ 0.14	80129 $\pm$ 557	5926 $\pm$ 97	97887 $\pm$ 710
25	4203 $\pm$ 14.4	5.6 $\pm$ 1.19	74.2 $\pm$ 0.75	5.13 $\pm$ 0.20	80105 $\pm$ 1016	6936 $\pm$ 111	100894 $\pm$ 902
50	4197 $\pm$ 15.4	5.9 $\pm$ 0.73	75.9 $\pm$ 0.63	5.68 $\pm$ 0.19	79834 $\pm$ 888	7248 $\pm$ 78	101556 $\pm$ 881
75	4194 $\pm$ 15.1	6.3 $\pm$ 1.14	75.2 $\pm$ 0.53	5.94 $\pm$ 0.18	80099 $\pm$ 904	7361 $\pm$ 70	102159 $\pm$ 893
100	4168 $\pm$ 15.8	6.8 $\pm$ 0.68	75.2 $\pm$ 1.00	6.09 $\pm$ 0.16	79362 $\pm$ 642	7413 $\pm$ 78	101576 $\pm$ 708

Table 2: Performance under varying numbers

k

of virtual monitoring orders generated every five minutes, with monitoring-task orderization enabled and

\alpha

fixed at 3. The row

k=0

coincides with the

\alpha=3

configuration of Table 1 .

Method	Orders Picked Up	Viol. Rate (%)	Link Cov. (%)	Bttlnk. Freq.	Delivery Score	Monitor. Score	Overall Score
Greedy	3702 $\pm$ 15.8	19.0 $\pm$ 1.26	76.8 $\pm$ 0.79	6.27 $\pm$ 0.23	63238 $\pm$ 753	7617 $\pm$ 81	86059 $\pm$ 906
Independent-MAQL	4168 $\pm$ 15.8	6.8 $\pm$ 0.68	75.2 $\pm$ 1.00	6.09 $\pm$ 0.16	79362 $\pm$ 642	7413 $\pm$ 78	101576 $\pm$ 708
Graph-MAQL	4199 $\pm$ 6.8	3.9 $\pm$ 0.39	74.0 $\pm$ 0.75	5.84 $\pm$ 0.16	82332 $\pm$ 225	7231 $\pm$ 103	104000 $\pm$ 378

Table 3: Comparison of Graph-MAQL against baselines. Both learning-based policies are trained at the

1.0\times

demand level; panel (b) reports zero-shot evaluation of those same policies under approximately 5,300 orders, with no retraining. The Independent-MAQL row in panel (a) coincides with the

k=100

configuration of Table 2 . Abbreviations: Viol. Rate = deadline violation rate; Link Cov. = link coverage rate; Bttlnk. Freq. = bottleneck roads monitoring frequency.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: Visualization of the Kowloon food-delivery dataset and road-network speed map.

Explore similar work

Prediction is Better than Detection: Traffic Congestion Control using Drones
Sep 30, 2026Samira Hayat, Christian RaffelsbergerMulti-Robot Systems Traffic Signal Control
Lakeside Labs GmbH Klagenfurt, Austria
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
Locker-based Truck-Drone Routing with Integrated Considerations of Pickups, Deliveries, and No-Fly Zones
Jun 26, 2026Xuanyu Liu, Hui Hu, Jiao Zhao +2Combinatorial Optimization Vehicle Routing
College of Transportation Engineering, Chang’an University, China · Faculty of Science and Technology, University of Nottingham Ningbo China

Sep 30, 2026, cs.ROJ/K move · Enter open · S save

Prediction is Better than Detection: Traffic Congestion Control using Drones

Samira Hayat, Christian Raffelsberger

Lakeside Labs GmbH Klagenfurt, Austria

Multi-Robot Systems Traffic Signal Control Traffic Forecasting

Open paper AskPDF arXiv

A central question in deploying teams of mobile robots for persistent monitoring is how task performance scales with fleet size, and whether this scaling holds once sensing drives downstream action rather than mere observation. We study this question for a team of drones performing traffic-jam detection and prediction in a simulated road network, whose reports drive an adaptive traffic-signal controller in closed loop. We build a multi-agent simulation, with vehicles following Nagel-Schreckenberg cellular-automaton dynamics and drones patrolling junctions via a round-robin policy, and sweep fleet size, traffic level, and network size to evaluate detection rate, detection delay, and prediction rate. We show how performance plateaus for fleet size approximating the number of junctions being monitored, and offer a general fleet-provisioning rule for persistent-monitoring deployments. More significantly, adapting the signal on a predicted jam, rather than a detected one, roughly doubles the resulting reduction in jam duration, showing that the value of onboard prediction in a sensing-to-action pipeline can exceed the value of adding more robots. Prediction accuracy, not sensing coverage, is now the binding constraint on further improvement, pointing to onboard inference, not fleet size, as the more promising direction for future work.

Abstract

Explore similar work

Prediction is Better than Detection: Traffic Congestion Control using Drones

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

Locker-based Truck-Drone Routing with Integrated Considerations of Pickups, Deliveries, and No-Fly Zones