A Two-Echelon Covering Tour Vehicle Routing Problem with Drones for Post-Disaster Relief

Dang Viet Anh Nguyen; Rajesh Piplani; Aldy Gunawan

cs.ROSep 28, 2026

A Two-Echelon Covering Tour Vehicle Routing Problem with Drones for Post-Disaster Relief

Authors: Dang Viet Anh Nguyen, Rajesh Piplani, Aldy Gunawan

Organizations: Department of Technology, Management and Economics, Technical University of Denmark, Akademivej Bygning 358, 2800 Kongens Lyngby, Denmark · School of Mechanical and Aerospace Engineering, Nanyang Technological University, 50 Nanyang Avenue, 639798, Singapore · School of Computing and Information Systems, Singapore Management University, 80 Stamford Road, 178902, Singapore

Abstract

We introduce the two-echelon covering tour vehicle routing problem (2E-CTVRP) for the distribution of relief supplies after a disaster. In the first echelon, a fleet of trucks transports supplies and drones from a central depot to satellites at the periphery of the affected area. In the second echelon, drones launched in parallel from the satellites deliver the supplies to the centroids of victim clusters, which are obtained by clustering the victim locations, and each truck waits at a satellite until its drones have returned. The problem combines the assignment of satellites to trucks, the sequencing of the truck routes, and the assignment of clusters to satellites, and minimizes the sum of the arrival times of the trucks at the satellites and at the depot. We formulate the 2E-CTVRP as a mixed integer linear program and propose a hybrid metaheuristic, GRASP-ILS-PR, which combines greedy randomized construction, a single-trajectory search, and periodic path relinking on the assignment of clusters to satellites. On a new benchmark set of 110 instances, GRASP-ILS-PR finds all known optimal solutions within 30 seconds, matches or improves on the one-hour solutions of a commercial solver on most larger instances, and improves on them by up to 11% for instances with 50 satellites. It clearly outperforms a conventional GRASP with evolutionary path relinking and yields more consistent results than a simulated annealing algorithm that uses the same search components. An analysis of two fleet configurations shows that few large trucks minimize the cumulative arrival time in most instances, whereas many small trucks deliver supplies to the victims earlier and more equitably in every instance.

Figures & tables

Study	Two echelons	Trucks	Drones	Delivery	Humanitarian	Uncertainty
[ 39 ]	–	S	S	Ind.	–	–
[ 29 ]	$\checkmark$	M	M	Ind.	–	–
[ 70 ]	$\checkmark$	M	M	Ind.	–	–
[ 48 ]	–	–	M	Ind.	$\checkmark$	–
[ 11 ] a	$\checkmark$	–	M	Ind.	$\checkmark$	–
[ 64 ]	$\checkmark$	S	M	Ind.	$\checkmark$	–

Table 1: Comparison of the 2E-CTVRP with closely related studies. Trucks and drones: S = single, M = multiple, – = not used. Delivery: Ind. = drones or vehicles serve individual demand points; Cov. = demand is served through covering nodes or cluster centroids.

Figure 1: Spatial distribution of victim locations forming distinct clusters, with the number in each red circle indicating the number of victim locations in the area following the 2025 flood in Thai Nguyen Province, Vietnam (source: https://thongtincuuho.org/ )

Symbol	Description
Sets
$G=(V\cup M,E_{1}\cup E_{2})$	Directed graph representing the two-echelon network
$V=V_{0}\cup V_{s}$	Set of depot and satellite nodes
$V_{0}=\{v_{0},v_{n+1}\}$	Start depot $v_{0}$ and end-depot copy $v_{n+1}$
$V_{s}=\{v_{1},\ldots,v_{n}\}$	Set of $n$ satellites
$M=\{\mu_{1},\ldots,\mu_{n}\}$	Set of $n$ cluster centroids

Table 2: Notation used in the 2E-CTVRP formulation

Figure 2: Illustration of a 2E-CTVRP solution

Figure 3: Construction of list $A$ for two truck routes

Operator	Modified component	Scope	Move	Capacity check
N1	$T$	intra-route	relocate a satellite	not required
N2	$T$	intra-route	biased swap of two satellites	not required
N3	$T$	intra-route	2-opt	not required
N4	$T$	inter-route	swap of two satellites	both routes
N5	$T$	inter-route	2-opt*	both routes
N6	$T$	inter-route	relocate a satellite	receiving route

Table 3: Neighborhood operators

Panel of Figure 4 — Figure 4: Neighborhood operators for the truck routes

Figure 5: Path relinking between two assignments of seven satellites. A pair $i$ – $j$ denotes $\sigma(i)=j$ ; underlined pairs are exchanged in the next step.

Symbol	Meaning
$t_{\max}$	Time limit (primary stopping criterion)
$n_{\max}$	Maximum number of iterations
$\kappa$	Number of candidates sampled per operator in a local search sweep
$\varphi_{\mathrm{LS}}$	Number of iterations between two calls of the local search
$\varphi_{\mathrm{PR}}$	Number of iterations between two calls of path relinking
$\rho$	Number of iterations without improvement of $S^{*}$ before a restart

Table 4: Parameters of GRASP-ILS-PR

Figure 6: Spatial distribution of the depot, the satellites, and the victims in a benchmark instance

Set	$n_{c}$	$n$	$n_{1}$	$n_{2}$	$n_{v}$	$D$	$Q$	$K$	$U$
M-05-03-1	5	3	1	2	460	5650	12 500	1	6
M-05-03-2	5	3	1	2	460	5650	3500	2	6
M-05-04-1	5	4	2	2	520	6403	12 500	1	4
M-05-04-2	5	4	2	2	520	6403	3500	3	4
M-08-05-1	8	5	2	3	730	8972	12 500	1	4
M-08-05-2	8	5	2	3	730	8972	3500	4	4

Table 5: Characteristics of the main instance sets: number of generated victim clusters (

n_{c}

), number of satellites (

n

) in the two groups (

n_{1}

n_{2}

), number of victims (

n_{v}

), total demand (

D

), truck capacity (

Q

), number of trucks (

K

), and number of drones per satellite (

U

). The drone payload capacity is

P=1000

in all instances.

Set	$n_{c}$	$n$	$n_{1}$	$n_{2}$	$n_{v}$	$D$	$Q$	$K$	$U$
M-20-20-1	20	20	10	10	2050	24 065	12 500	3	4
M-20-20-2	20	20	10	10	2050	24 065	3500	11	4
M-50-50-1	50	50	25	25	4830	58 298	12 500	6	3
M-50-50-2	50	50	25	25	4830	58 298	3500	26	3

Table 6: Characteristics of the large-scale instance sets: number of generated victim clusters (

n_{c}

), number of satellites (

n

) in the two groups (

n_{1}

n_{2}

), number of victims (

n_{v}

), total demand (

D

), truck capacity (

Q

), number of trucks (

K

), and number of drones per satellite (

U

). The drone payload capacity is

P=1000

in all instances.

Symbol	Meaning	Value
$t_{\max}$	time limit	30 s
$n_{\max}$	maximum number of iterations	$10^{8}$
$\kappa$	candidates sampled per operator in a local search sweep	5
$\varphi_{\mathrm{LS}}$	iterations between two calls of the local search	30
$\varphi_{\mathrm{PR}}$	iterations between two calls of path relinking	10
$\rho$	iterations without improvement before a restart	2000

Table 7: Parameter values of GRASP-ILS-PR.

	Gurobi				GRASP-EvPR			SA			GRASP-ILS-PR
Set	#Opt	CPU (s)	Gap (%)	#BKS	$\Delta_{\mathrm{best}}$	$\Delta_{\mathrm{avg}}$	#BKS	$\Delta_{\mathrm{best}}$	$\Delta_{\mathrm{avg}}$	#BKS	$\Delta_{\mathrm{best}}$	$\Delta_{\mathrm{avg}}$	#BKS
M-05-03-1	5	0.01	0.00	5	0.000	0.000	5	0.000	0.000	5	0.000	0.000	5
M-05-03-2	5	0.02	0.00	5	0.000	0.000	5	0.000	0.479	5	0.000	0.000	5
M-05-04-1	5	0.02	0.00	5	0.000	0.000	5	0.000	0.000	5	0.000	0.000	5
M-05-04-2	5	0.23	0.00	5	0.000	0.000	5	0.000	0.000	5	0.000	0.000	5
M-08-05-1	5	0.08	0.00	5	0.000	0.000	5	0.000	0.000	5	0.000	0.000	5

Table 8: Summary comparison of Gurobi, GRASP-EvPR, SA, and the proposed GRASP-ILS-PR by instance set; the proposed method is shown with a bold header. Gurobi: number of instances solved to proven optimality (#Opt), average runtime, average MIP gap at termination, and number of best-known solutions found (#BKS). Metaheuristics (ten runs of 30 s per instance): average relative deviation of the best (

\Delta_{\mathrm{best}}

) and average (

\Delta_{\mathrm{avg}}

) objective values from the Gurobi incumbent, in %, and number of best-known solutions found (#BKS). Negative deviations indicate improvements over the Gurobi incumbent. Each set contains five instances.

Instance	$n$	$K$	GRASP-EvPR	SA	GRASP-ILS-PR
M-05-03-60-1	3	1	41 738	756 524	365 666
M-08-05-60-1	5	1	17 829	415 163	295 854
M-10-07-60-2	7	5	7155	147 831	103 868
M-12-11-60-1	11	2	2073	64 603	100 399
M-15-13-60-1	13	3	1250	54 408	86 314
M-17-15-60-2	15	7	3607	47 957	54 978

Table 9: Average number of iterations completed within 30 s (ten runs per instance). For GRASP-EvPR, an iteration consists of a construction, a local search, and path relinking; for SA and GRASP-ILS-PR, an iteration consists of one sampled move.

Parameter	Value	Avg. objective	$\Delta$ (%)	$p$
Default configuration		19.3887	–	–
$\kappa$ (samples per operator)	3	19.3851	$-$ 0.019	0.497
	5
	10	19.3871	$-$ 0.008	0.967
$\varphi_{\mathrm{LS}}$ (local search interval)	10	19.3967	0.041	0.178
	30

Table 10: Sensitivity of GRASP-ILS-PR to its parameters: average objective value over six instances and ten runs per instance, relative difference

\Delta

from the default configuration, and

p

-value of the Wilcoxon signed-rank test on the 60 paired runs. Default values are shown in bold. Positive values of

\Delta

indicate a deterioration.

	Gurobi			GRASP-EvPR			SA			GRASP-ILS-PR
Set	Gap (%)	$\Delta$	#BKS	$\Delta_{\mathrm{best}}$	$\Delta_{\mathrm{avg}}$	#BKS	$\Delta_{\mathrm{best}}$	$\Delta_{\mathrm{avg}}$	#BKS	$\Delta_{\mathrm{best}}$	$\Delta_{\mathrm{avg}}$	#BKS
M-20-20-1	76.10	0.06	3	4.80	6.12	0	0.08	0.44	1	0.01	0.13	4
M-20-20-2	48.56	0.15	1	1.66	2.14	0	0.03	0.22	4	0.03	0.19	4
M-50-50-1	94.48	11.52	0	17.27	19.48	0	1.46	3.08	0	0.00	1.48	5
M-50-50-2	65.14	5.10	0	4.83	5.84	0	0.15	0.44	1	0.03	0.51	4
All	71.07	4.21	4	7.14	8.39	0	0.43	1.05	6	0.02	0.57	17

Table 11: Summary results on the large-scale instances. Gurobi (time limit 3600 s): average MIP gap at termination, average relative deviation of the incumbent from the best-known solution (

\Delta

), and number of best-known solutions found (#BKS). Metaheuristics (ten runs of 120 s per instance): average relative deviation of the best (

\Delta_{\mathrm{best}}

) and average (

\Delta_{\mathrm{avg}}

) objective values from the best-known solution, in %, and #BKS. Each set contains five instances; the proposed method is shown with a bold header.

Figure 7: Optimal solutions of instance M-09-09-60 with (a) the large-truck fleet and (b) the small-truck fleet. Each satellite is labeled with the truck $k$ and its position $p$ on the route ( $k.p$ ) and with the arrival time of the truck in hours. Truck routes are drawn as straight lines, although truck travel times are based on Manhattan distances; dashed lines connect each satellite to the centroid served by its drones.

Truck	Satellite	Centroid	Waiting	Arrival	Return	Load
(a) Large-truck fleet, $K=2$ , $Q=12\,500$ , objective 17.73
1	9	8	0.33	0.51	3.50	4223
	8	5	0.25	0.93
	2	4	0.30	1.57
	5	1	0.57	1.94
2	7	3	0.17	0.52	3.17	5364

Table 12: Optimal solutions of instance M-09-09-60. For each truck, the satellites are listed in the order of visit, with the assigned centroid, the waiting time, and the arrival time; the return time to the depot and the load are given in the first row of each truck. Times are in hours.

	$Z_{1}$		$\bar{T}$		$C$		$Z_{2}$		$Z_{3}$		Util. (%)
$n$	L	S	L	S	L	S	L	S	L	S	L	S
3	7.20	8.08	1.26	1.12	2.08	1.72	2761	3312	1.01	0.65	45	81
4	7.46	7.68	1.15	0.83	2.10	1.21	3117	5361	1.29	0.53	51	61
5	12.90	13.83	1.65	1.09	3.18	1.67	2909	5395	2.24	0.78	72	64
7	13.97	16.03	1.33	0.94	1.96	1.42	6312	8602	1.16	0.64	49	69
8	18.72	21.16	1.68	1.23	2.38	1.66	4923	7000	1.41	0.78	46	66

Table 13: Performance of the large-truck (L) and small-truck (S) fleets: objective value

Z_{1}

, demand-weighted average delivery time

\bar{T}

, completion time of the deliveries

C

, demand delivered per hour

Z_{2}

, spread of the arrival times at the satellites

Z_{3}

, and average truck utilization. Values are averages over the five drone speeds; times are in hours.

Figure 8: Objective value $Z_{1}$ , demand-weighted average delivery time $\bar{T}$ , and spread of the arrival times $Z_{3}$ of the large-truck and small-truck fleets for drone speeds of 40 km/h (top) and 80 km/h (bottom). Each point corresponds to one instance; the lines only connect instances with different numbers of satellites.

Appendix figures & tables3 assets

Supplementary material from the paper’s appendix.

Appendix

	Gurobi				GRASP-EvPR		SA		GRASP-ILS-PR
Instance	Obj.	LB	Gap (%)	CPU (s)	Best	Avg.	Best	Avg.	Best	Avg.
M-05-03-40-1	8.174	8.174	0.00	0.01	8.174	8.174	8.174	8.174	8.174	8.174
M-05-03-50-1	7.505	7.505	0.00	0.00	7.505	7.505	7.505	7.505	7.505	7.505
M-05-03-60-1	7.059	7.059	0.00	0.01	7.059	7.059	7.059	7.059	7.059	7.059
M-05-03-70-1	6.741	6.741	0.00	0.00	6.741	6.741	6.741	6.741	6.741	6.741
M-05-03-80-1	6.502	6.502	0.00	0.00	6.502	6.502	6.502	6.502	6.502	6.502

Appendix

Table 1: Per-instance results for the large-truck fleet (

Q=12\,500

). Gurobi: incumbent (Obj.), best lower bound (LB), MIP gap at termination, and runtime, with a time limit of 3600 s. Metaheuristics: best and average objective values over ten runs of 30 s; the proposed method is shown with a bold header. Bold values denote the best-known solution (ties within a relative tolerance of

10^{-5}

	Gurobi				GRASP-EvPR		SA		GRASP-ILS-PR
Instance	Obj.	LB	Gap (%)	CPU (s)	Best	Avg.	Best	Avg.	Best	Avg.
M-05-03-40-2	8.760	8.760	0.00	0.02	8.760	8.760	8.760	8.812	8.760	8.760
M-05-03-50-2	8.292	8.292	0.00	0.02	8.292	8.292	8.292	8.331	8.292	8.292
M-05-03-60-2	7.980	7.980	0.00	0.01	7.980	7.980	7.980	8.012	7.980	7.980
M-05-03-70-2	7.757	7.757	0.00	0.02	7.757	7.757	7.757	7.796	7.757	7.757
M-05-03-80-2	7.590	7.590	0.00	0.02	7.590	7.590	7.590	7.622	7.590	7.590

Appendix

Table 2: Per-instance results for the small-truck fleet (

Q=3500

10^{-5}

	Gurobi			GRASP-EvPR		SA		GRASP-ILS-PR
Instance	Obj.	LB	Gap (%)	Best	Avg.	Best	Avg.	Best	Avg.
M-20-20-40-1	47.896	10.177	78.75	51.069	51.535	47.966	48.105	47.896	47.995
M-20-20-50-1	43.322	9.532	78.00	45.318	45.972	43.265	43.468	43.265	43.324
M-20-20-60-1	40.132	9.975	75.14	42.182	42.541	40.146	40.299	40.142	40.176
M-20-20-70-1	37.877	9.510	74.89	39.303	39.838	37.844	37.977	37.815	37.848
M-20-20-80-1	36.021	9.468	73.72	37.320	37.970	36.067	36.188	36.021	36.055

Appendix

Table 3: Per-instance results on the large-scale instances. Gurobi: incumbent (Obj.), best lower bound (LB), and MIP gap at termination, with a time limit of 3600 s, which is reached on all instances. Metaheuristics: best and average objective values over ten runs of 120 s; the proposed method is shown with a bold header. Bold values denote the best-known solution.

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

A Cross-Layered Multi-Drone Coordination for Medical Supply Delivery during Disaster Response Management
May 10, 2026Aneesh Calyam, Subrahmanya Chandra Bhamidipati, Zack Murry +1Aerial Robotics UAV Navigation
University of Missouri–Columbia, Columbia, MO 65211, USA
Drive, Pack, Fly: The Travelling Thief Problem with Drone
Aug 17, 2026Kabir Murjani, Abhay SobhananCombinatorial Optimization Metaheuristic Optimization
Nirma University, SG Highway, Ahmedabad 382481, Gujarat, India · Indian Institute of Management Bangalore, Bannerghatta Road, Bengaluru 560076, Karnataka, India
Joint UAV Activation and Placement for Post-Disaster Wireless Restoration via a Hybrid Quantum-Inspired Evolutionary Framework
Sep 7, 2026Fatima Azzahraa Amarcha, Lahcen Hassine, Rachid Saadane +4Wireless Communications Disaster Response
LPHE, Modeling and Simulations, Faculty of Science, Mohammed V University in Rabat, Morocco. · Hassania School of Public Works (EHTP), Laboratory Engineering System, SIRC Team, Casablanca, Morocco. · Genuis Lab, School of Management, Telecommunications and Computer Science (SUPMTI), Rabat, Morocco. +3

May 10, 2026J/K move · Enter open · S save

A Cross-Layered Multi-Drone Coordination for Medical Supply Delivery during Disaster Response Management

Aneesh Calyam, Subrahmanya Chandra Bhamidipati, Zack Murry, Sharan Srinivas

University of Missouri–Columbia, Columbia, MO 65211, USA

Aerial Robotics UAV Navigation Multi-Robot Coordination Disaster Response Centralized Training with Decentralized Execution Cooperative MARL

Open paper AskPDF arXiv

Autonomous drone fleets have immense potential in medical supply delivery during disaster incident response. However, coordinating multiple drones in such settings introduces compounding challenges: dynamic environmental hazards such as wind, obstacles, and intermittent network connectivity, constrained energy budgets, and the need to serve patient locations fairly under deadlines and triage-based priority while optimizing schedule utilization. In this paper, we present CEDA, a novel CTDE Deep Q-Network algorithm for cooperative multi-drone medical delivery, designed to jointly optimize triage-priority-aware routing, multi-agent coordination, and energy-efficient navigation under dynamic uncertainty. CEDA introduces a Priority-Preserving Fair Scheduling strategy, in which a structured reward function encodes both triage weights and complementary fairness mechanisms ensuring no patient class is starved of service. We evaluate CEDA in a simulated grid environment featuring dynamic hazard zones, stochastic action failures, and dynamically spawning patients across three triage priority levels, as well as in a PX4 SITL validation using two X500 quadrotors controlled via MAVSDK in offboard position mode. Simulation results demonstrate that CEDA achieves a delivery completion rate above 85%, reduces obstacle collisions by over 90% across training, and delivers an average of 6 patients per episode with a triage efficiency of 0.82. CEDA preserves clinical priority ordering, Critical patients are served first, while achieving near-zero mortality across lower-triage classes, confirming that priority-weighted routing does not condemn Stable or Urgent patients to neglect. PX4 SITL validation further demonstrates that the learned policy remains executable and triage-coherent under practical communication constraints and realistic multi-drone coordination in disaster response settings.

Abstract

Vehicle Routing

Explore similar work

A Cross-Layered Multi-Drone Coordination for Medical Supply Delivery during Disaster Response Management

Drive, Pack, Fly: The Travelling Thief Problem with Drone

Joint UAV Activation and Placement for Post-Disaster Wireless Restoration via a Hybrid Quantum-Inspired Evolutionary Framework