PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Dang Viet Anh Nguyen, Rajesh Piplani, Aldy Gunawan

arXiv:2609.38227v1cs.RO

TL;DR

Post-disaster relief must reach victims despite incomplete location data and damaged infrastructure, while existing truck–drone and covering-tour approaches address different parts of this challenge. The paper combines them in a two-echelon covering-tour model and proposes GRASP-ILS-PR. It finds all known optimal solutions within 30 seconds and reports a fleet trade-off between cumulative arrival time and earlier, more equitable delivery.

  • Problem

    Post-disaster individual-level delivery can be impractical when victim locations are incompletely known, and existing truck–drone and covering-tour models do not combine multi-modal delivery with spatial coverage.

    Source: §1 · pp. 2–3

  • Method

    The 2E-CTVRP models trucks carrying supplies and drones to peripheral satellites, where parallel drones deliver to victim-cluster centroids; GRASP-ILS-PR combines randomized construction, a single-trajectory search, and periodic path relinking.

    Source: §7 · p. 48

  • Results

    GRASP-ILS-PR finds all known optimal solutions within 30 seconds and improves on the one-hour Gurobi incumbent by up to 11.1% on instances with 50 satellites.

    Source: §7 · p. 48

  • Takeaways & Limitations

    Few large trucks minimize cumulative arrival time in most instances, whereas many small trucks deliver supplies earlier and more equitably in every benchmark instance.

    Source: §1 · p. 4

    The instances are synthetic, and travel times and demands are deterministic; trucks wait for drones, each satellite serves one cluster, and the objective measures truck rather than victim arrival times.

    Source: §7 · p. 48

Abstract

from arXiv · show

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.

1. Introduction

The paper combines spatial coverage with two-echelon truck–drone delivery to address post-disaster relief when individual victim locations may be unknown and roads may be impaired. It introduces a mixed-integer model and hybrid search, then evaluates benchmark performance and fleet trade-offs.

1. Introduction

  • Post-disaster relief prioritizes timely aid, but damaged or congested road networks can make it difficult for ground vehicles to reach remote locations.The introduction frames time as especially important because the objective is to reduce human suffering.Source: §1 · p. 2
  • Cluster-based coverage addresses the impracticality of individual deliveries when victim numbers and precise locations are unknown, while prior truck–drone and covering-tour models each omit a key part of this setting.Truck–drone models generally assume point-to-point service; covering-tour models use ground vehicles in a single echelon.Source: §1 · pp. 2–3
  • The 2E-CTVRP combines first-echelon trucks carrying supplies and drones to peripheral satellites with second-echelon drone delivery to victim-cluster centroids.This integrates spatial coverage into a multi-modal relief system without routing to every individual victim.Source: §1 · p. 3
  • GRASP-ILS-PR uses greedy randomized construction, a single search trajectory, and periodic path relinking on cluster-to-satellite assignments.The method schedules expensive components periodically rather than running full construction, local search, and path relinking in every iteration.Source: §1 · pp. 3–4
  • GRASP-ILS-PR finds all known optimal solutions within 30 seconds, matches or improves on one-hour Gurobi incumbents for most larger instances, and outperforms the compared metaheuristics.Its results are more consistent across runs than simulated annealing using the same search components.Source: §1 · p. 4
  • The 110-instance benchmark shows that few large trucks minimize cumulative arrival time in most instances, while many small trucks deliver earlier and more equitably in every instance.The benchmark includes instances with up to 50 satellites.Source: §1 · p. 4

2. Literature review

The review spans humanitarian routing, two-echelon and truck–drone delivery, covering tours, and uncertainty. It positions the 2E-CTVRP as combining multi-truck, multi-drone delivery with cluster-based spatial coverage.

2.1. Vehicle routing in humanitarian operations

  • Humanitarian routing weighs response time, equity, satisfied demand, and cost; these measures can conflict, and studies use different arrival-time definitions.The review distinguishes min-max, min-average, and min-sum response-time objectives.Source: §2.1 · pp. 4–5

2.2. Two-echelon vehicle routing

  • Two-echelon routing coordinates vehicles at satellites, while humanitarian variants include heuristics, exact methods, and robust models but may not scale to post-disaster decision times.The reviewed examples address pickup and delivery, uncertain demand, or drone delivery from satellites.Source: §2.2 · pp. 5–6

2.3. Truck–drone routing

  • Truck–drone routing ranges from tandem truck–drone models to multiple-truck, multiple-drone systems, but reviewed disaster-relief models deliver to individual demand points.The review also notes models that account for drone limits or explicitly consider equity.Source: §2.3 · p. 6

2.4. Covering tour problems

  • Covering tours treat unvisited demand nodes as served when they lie within a specified distance of a visited node, but humanitarian applications have not incorporated aerial last-mile delivery.Prior relief applications include locating satellite centers and offering covering options for medical-supply collection.Source: §2.4 · pp. 6–7

2.5. Uncertainty in post-disaster routing

  • The review characterizes the 2E-CTVRP as deterministic, while noting that post-disaster routing research increasingly models uncertainty in demands, travel times, and road conditions.The deterministic formulation is presented as a basis for future extensions.Source: §2.5 · p. 7

2.6. Positioning of the 2E-CTVRP

  • The 2E-CTVRP joins covering-based cluster centroids with multiple trucks and parallel drones, jointly assigning clusters and truck routes because assignments affect truck loads and satellite waits.Its objective sums truck arrival times, so drone missions at a satellite can delay subsequent truck visits.Source: §2.6 · pp. 7–8

3. Problem description and mathematical formulation

The 2E-CTVRP models post-disaster relief delivery from a central depot to isolated demand clusters through truck-served satellites and drone deliveries. It jointly determines truck routes and cluster assignments to minimize cumulative truck arrival times.

3.1. Problem description

  • The problem addresses relief delivery to isolated locations under severe infrastructure and resource constraints, representing victims by clusters whose centroids serve as drone delivery points.Victims collect supplies within walking distance of their cluster centroid.Source: §3.1 · pp. 8–9, Figure 1 · p. 9
  • Trucks carry supplies and drones from the depot, visit satellites, and return; at each satellite, parallel drones serve its assigned centroid while the truck waits for their return.Each satellite and centroid is served exactly once, and each truck visits at least one satellite.Source: §3.1 · pp. 9–10, Figure 2 · p. 13
  • The truck–drone synchronization rule is a conservative post-disaster assumption, reflecting unreliable communications, operational risks, and the need to recover drones safely.Drone resources at each satellite are represented by aggregate payload capacity rather than individual drone schedules.Source: §3.1 · p. 10
  • The problem jointly chooses satellite-to-truck allocation, truck visit order, and centroid-to-satellite assignment, minimizing truck arrival times at satellites and return times to the depot.Centroid assignments affect truck loads and satellite waiting times, which delay later arrivals.Source: §3.1 · p. 10

3.2. Mathematical formulation

  • The MILP represents depot and satellite nodes separately from centroid nodes, with truck travel times, drone flight times, truck arrival times, and satellite waiting times.The start and end depot nodes represent the same physical depot; truck capacities and drone payload capacity constrain carried and served demand.Source: §3.2 · pp. 10–11
  • Each centroid is assigned to one satellite, its demand is carried by a single truck, and drone flights must return to that satellite before the truck continues.The formulation assumes all satellite–centroid pairs meet drone flight-range requirements.Source: §3.2 · p. 11
  • The formulation enforces one-to-one satellite–centroid assignments, truck-capacity and drone-payload limits, and arrival-time propagation that also eliminates satellite-only subtours.Waiting time at each satellite must cover the round-trip flight to its assigned centroid.Source: §3.2 · p. 15

4. Proposed Algorithm

The proposed GRASP-ILS-PR algorithm addresses the short computation times needed for disaster response on larger 2E-CTVRP instances. It combines randomized construction and feasibility repair with sampled neighborhood search, assignment-focused path relinking, and periodic intensification, diversification, and restarts.

4.1. Algorithmic framework

  • GRASP-ILS-PR carries a working solution across iterations, accepts feasible non-worsening moves, periodically applies local search and path relinking, and restarts after stagnation.This combines a high iteration rate with intensification from path relinking and diversification from randomized restarts.Source: §4.1 · pp. 16–17

4.2. Solution representation and evaluation

  • A solution is represented by truck routes T and a permutation σ assigning centroids to satellites; objective decomposition enables O(n) evaluation and shows that early-route waiting times carry greater weight.The two echelons interact through satellite waiting times, while their positional weights depend on the truck routes.Source: §4.2 · pp. 17–18

4.3. Construction heuristic

  • The construction heuristic seeds truck routes, inserts remaining satellites by randomized cheapest insertion, then assigns centroids in route-position order so early stops get first choice of nearby centroids.This ordering prioritizes short drone missions where waiting time is most costly; construction takes O(n^2) time and may require repair for capacity violations.Source: §4.3 · pp. 19–20

4.4. Repair operator

  • Because feasible routing for a fixed centroid assignment reduces to bin packing, the heuristic repairs capacity violations in up to three stages: reinsertion, route merging, and re-packing.A feasible solution exists for every constructed assignment when the instance is feasible, but the heuristic repair may fail; repeated construction-and-repair attempts can then be made.Source: §4.4 · pp. 21–22

4.5. Neighborhood operators and local search

  • Seven sampled operators modify truck routes or satellite assignments, and repeated first-improvement sweeps stop when κ samples per operator yield no improvement.N1–N6 change routes while N7 changes assignments; each sweep samples 7κ candidates and takes O(κn) time, so termination does not guarantee a local optimum over the complete neighborhoods.Source: §4.5 · pp. 23, 26

4.6. Path relinking and elite pool

  • Path relinking transforms assignments through swaps along a shortest exchange path, evaluates them with fixed truck routes, and returns the best feasible assignment found, including feasible endpoints.The elite pool stores assignments rather than routes, allowing assignments found earlier to be evaluated with current routes; infeasible intermediate assignments may be traversed but are not returned.Source: §4.6 · pp. 26–28

4.7. The GRASP-ILS-PR algorithm

  • GRASP-ILS-PR accepts feasible non-worsening perturbations, periodically applies local search and bidirectional path relinking, and restarts after stagnation while retaining the best solution and elite pool.Between restarts, the current objective never increases; perturbations take O(n) time, local-search sweeps O(κn), and relinking calls O(n^2), with the latter steps invoked periodically.Source: §4.7 · pp. 29, 31

5. Computational experiments

The computational experiments evaluate GRASP-ILS-PR against Gurobi and alternative metaheuristics across benchmark and large-scale settings, including its search design and parameter sensitivity. They also examine joint truck-route and satellite-assignment optimization and how performance varies by fleet type and instance size.

5.1. Benchmark instances

  • The benchmark comprises 90 main-set instances and 20 large-scale instances with 20 or 50 satellites, generated to represent clustered victim locations and peripheral satellites.Victims are clustered for drone delivery to centroids; the large-scale instances are used to assess performance beyond the MILP’s scale.Source: §5.1 · pp. 31–33

5.2. Experimental setup and compared methods

  • Four methods were compared on the 90 main instances, with each metaheuristic run ten times for 30 seconds using different random seeds.Solution differences were tested with paired Wilcoxon signed-rank tests, and heuristic solution evaluations were independently verified against Gurobi.Source: §5.2 · pp. 34–36

5.3. Comparison with the MILP and alternative metaheuristics

  • GRASP-ILS-PR matched all 62 proven optima and found 82 best-known solutions across 90 instances, with a −0.012% average best-run deviation from Gurobi.It clearly outperformed GRASP-EvPR; against SA, best-run quality was similar, but GRASP-ILS-PR was significantly more consistent across runs.Source: Table 8 · p. 36, §5.3 · pp. 37–38

5.4. Analysis of the algorithm design

  • Under a fixed time limit, GRASP-ILS-PR’s more frequent application of search components preserved quality as instances grew, while adding evolutionary path relinking gave no significant improvement.GRASP-EvPR’s average best-run deviation rose from 0.08% at n = 11 to 1.54% at n = 15, whereas GRASP-ILS-PR’s remained at or below zero; the evolutionary-rel linking test found no significant difference (p = 0.46).Source: §5.4 · pp. 38–39

5.5. Parameter sensitivity

  • GRASP-ILS-PR was robust to moderate parameter changes, while restart patience was the only tested parameter with a noticeable effect.With ρ = 5000, the average objective value deteriorated by 0.11% (p < 0.001); varying one parameter at a time meant interactions were not investigated.Source: §5.5 · pp. 39, 41

5.6. Large-scale instances

  • For the large-scale instances, metaheuristic runs used a 120-second limit, while Gurobi had a 3600-second limit and eight threads per instance; deviations were measured against each instance’s best-known solution.Six Gurobi instances were solved in parallel; this setup assesses performance beyond the size the MILP can solve.Source: §5.6 · p. 41
  • 5.10% and 11.52% are Gurobi’s average incumbent deviations for the small- and large-truck fleets, respectively, on n = 50 instances.Gurobi reaches the one-hour limit on all 20 instances, with MIP gaps of 48.1% to 96.7%; the model is not viable for 50 satellites.Source: §5.6 · pp. 41, 43, Table 11 · p. 42
  • 17 of 20 large-scale instances’ best-known solutions are found by GRASP-ILS-PR, with 0.02% average deviation; for n = 50, it improves on Gurobi by 1.3% to 11.1%.On set M-50-50-1, GRASP-ILS-PR finds all five best-known solutions. It provides the best solutions on most large-scale instances within two minutes.Source: §5.6 · pp. 41–43, Table 11 · p. 42
  • 7.14% average deviation from best-known solutions for GRASP-EvPR accompanies GRASP-ILS-PR’s better results on all 20 instances, while its comparison with SA varies by fleet.GRASP-ILS-PR beats SA in the best run on 14 instances, ties on 4, and loses on 2; SA is better in the average run on 7 of 10 small-truck instances, where many short, capacity-constrained routes make satellite moves important.Source: §5.6 · p. 42
  • 1.48% average-run deviation on set M-50-50-1 shows that GRASP-ILS-PR’s variability increases with instance size and its search may not converge within 120 seconds.The passage advises longer or multiple independent runs in practice for these instances.Source: §5.6 · p. 42

5.7. Illustrative solution

  • Both illustrated fleet solutions are Gurobi-proven optimal, and the longest drone missions occur at each route’s final satellite to limit delays to later arrivals.The longest waits are 0.57 h and 0.62 h at the last satellites in the large- and small-truck solutions, respectively; short missions tend to be assigned to earlier satellites.Source: §5.7 · p. 43, Figure 7 · p. 43
  • 2.6% lower objective value with four small trucks occurs in this instance, although the large-truck fleet has the lower objective in 37 of 45 pairs; assignments differ for 4 of 9 satellites.The differing assignments confirm that the optimal satellite-to-centroid assignment depends on route positions and waiting-time weights, so both echelons must be optimized jointly.Source: §5.7 · pp. 43, 45, Table 12 · p. 44

6. Impact of the truck fleet on relief operations

The preferred fleet depends on whether performance includes truck returns: large trucks usually minimize cumulative arrival time, while small trucks deliver supplies sooner and more equitably. These comparisons use GRASP-ILS-PR solutions for 45 paired fleet instances.

Efficiency

  • The large-truck fleet has the lower objective value Z1 in 37 of 45 pairs, while small-truck values are 7.6% higher on average.Z1 includes one return time per truck, so the preferred fleet depends on whether truck returns are part of the criterion.Source: §6 · pp. 45, 47, Table 13 · p. 45
  • 25.5% lower demand-weighted average delivery time is achieved by the small-truck fleet in all 45 pairs.The ranking is reversed for this victim-centered measure, which includes drone flight times and excludes truck returns to the depot.Source: §6 · pp. 45, 47

Efficacy

  • 33.4% earlier completion is achieved by the small-truck fleet on average across all 45 pairs, with completion times of 1.06–1.99 h versus 1.64–4.02 h for large trucks.Small trucks deliver more demand per hour for every satellite count; their average utilization is 69%, versus 51% for large trucks.Source: §6 · p. 47

Equity

  • 48.2% smaller arrival-time spread Z3 is achieved by the small-truck fleet in all 45 pairs.Its spread ranges from 0.43 to 1.20 h, compared with 0.79 to 2.99 h for large trucks; faster drones reduce the spread by 37.6% for large trucks and 19.2% for small trucks.Source: Figure 8 · p. 46, §6 · p. 47

Managerial implications

  • Few large trucks minimize cumulative arrival time, including returns, in most instances, and their advantage grows with drone speed.Increasing drone speed from 40 to 80 km/h reduces Z1 by 22.3% on average for large trucks and 12.4% for small trucks.Source: §6 · p. 47
  • Many small trucks deliver supplies earlier on average, complete deliveries earlier, and distribute arrival times more equitably in every benchmark instance.Small trucks are preferable when enough vehicles and drivers are available; large trucks are preferable when vehicle availability for subsequent trips matters.Source: §6 · pp. 47–48

7. Conclusion

The paper introduces the 2E-CTVRP and a hybrid method for solving it. Experiments show strong performance against the solver and alternative heuristics, while the study is bounded by synthetic instances and specific operational assumptions.

Problem and method

  • The study introduces the 2E-CTVRP, in which trucks carry supplies and drones from a depot to satellites, then drones serve victim-cluster centroids.The problem is formulated as a mixed integer linear program, and GRASP-ILS-PR combines greedy randomized construction, single-trajectory search, and periodic path relinking on centroid-to-satellite assignments.Source: §7 · p. 48

Computational results

  • GRASP-ILS-PR finds all known optimal solutions within 30 s and improves the one-hour Gurobi incumbent by up to 11.1% on instances with 50 satellites.It is at most 0.28% worse than the Gurobi incumbent on larger instances and better on several; it outperforms conventional GRASP-EvPR and has less run-to-run variation than simulated annealing.Source: §7 · p. 48

Limitations

  • The instances are synthetic, and the model assumes deterministic travel times and demands, synchronized truck–drone waiting, and exactly one cluster per satellite.The objective measures truck arrival times rather than the times supplies reach victims.Source: §7 · p. 48

Appendix A. Detailed computational results

Appendix A provides per-instance computational results for the main fleet configurations and for large-scale instances, with tables describing the reported metrics and run settings.

Table organization

Per-instance results

  • Tables A.1 and A.2 give per-instance results for the large-truck and small-truck fleets, respectively.The captions specify Gurobi incumbent, lower bound, MIP gap, and runtime with a 3600 s limit, plus metaheuristic best and average objective values over ten 30 s runs.Source: Table A.1 · p. 49, Table A.2 · p. 51

Large-scale results

  • Table A.3 reports per-instance results on large-scale instances, using a 3600 s Gurobi limit and ten 120 s metaheuristic runs.The caption states that the time limit is reached on all instances.Source: Table A.3 · p. 52
Loading 2609.38227v1…