A Two-Echelon Covering Tour Vehicle Routing Problem with Drones for Post-Disaster Relief
Dang Viet Anh Nguyen, Rajesh Piplani, Aldy Gunawan · N/A · 2026
Framework
N/A
License
N/A
Stars
N/A
Summary
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.
Abstract Summary
Key Points
- 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.
Literature review
The 2E-CTVRP is related to five streams of research: vehicle routing in humanitarian operations, two-echelon vehicle routing, truck–drone routing, covering tour problems, and routing under uncertainty in post-disaster settings. This section reviews these streams and positions the 2E-CTVRP relative to them.
Since the first applications of vehicle routing to humanitarian relief [ 31 ] , research on routing models for disaster operations has expanded steadily.
Problem description and mathematical formulation
The 2E-CTVRP addresses post-disaster humanitarian delivery through a coordinated two-echelon system. It is motivated by the 2025 flooding in Thai Nguyen Province, Vietnam, where severe rainfall submerged residential areas and destroyed critical road infrastructure.
The problem reflects situations in which displaced residents gather at evacuation points while damaged bridges and roads prevent trucks from reaching the affected communities.
Proposed Algorithm
In the response phase of a disaster, routing decisions must be made under tight time constraints and may have to be revised as information on damage, road accessibility, and demand becomes available. Solution methods for the 2E-CTVRP should therefore provide high-quality solutions within short computation times.
The computational results in Section 5 show that the MILP formulation of Section 3 is solved to proven optimality within one hour only for instances with up to nine satellites.
Computational experiments
Since no benchmark instances exist for the 2E-CTVRP, we generate a new set of instances that reflects the spatial characteristics of victim locations after a disaster. The generator follows the approaches used for two-echelon vehicle routing problems [ 7 , 6 , 64 ] and for truck–drone routing [ 39 ] .
Victims tend to move to safer locations and form clusters within the affected area; these clusters are generated following Perboli et al. [45] . The affected area is a circle with a radius of 1000 distance units, corresponding to 10 km.
Impact of the truck fleet on relief operations
This section compares the two truck fleets with respect to three dimensions of humanitarian logistics: efficiency, efficacy, and equity [ 24 ] . The analysis uses the best solutions found by GRASP-ILS-PR for the 90 instances of the main set, which form 45 pairs of instances that differ only in the truck fleet.
Let $e_{i}=a_{i}+t^{\prime}_{i\sigma(i)}$ denote the time at which the demand of the centroid assigned to satellite $v_{i}$ is delivered, where $a_{i}$ is the arrival time of the truck at $v_{i}$.
Sources and Demonstrations
Figures are reproduced from Nguyen et al. See the full paper for experimental details and the project page, when the paper links one, for demonstrations and videos.
Related Papers
A Sim-to-Real Integration Pipeline for Training and Deployment of Chunk-Based VLA Manipulation Policies
Mathilde Kappel, Clémence Grislain, Mohamed Chetouani et al.
Vision-Language-Action (VLA) models have become a prominent paradigm for mapping multimodal inputs, including semantic instructions, visual observations of the scene, and proprioceptive observations, to robot actions.
An Analysis of Streaming Deep Reinforcement Learning for Adaptive Continual Learning in Robotics
Teeratham Vitchutripop, Alyssa Quarles, Wenhe Zhang et al.
Over the course of a lifetime, robots may encounter novel scenarios unaccounted for in its original training that result in performance degradation. One common approach to mitigating this issue is to further grow the offline training dataset in hopes of producing a policy robust to these changes.
Behavioral Cloning Mystery
Seohong Park, Sergey Levine
Behavioral cloning (BC), despite its simplicity, exhibits many counterintuitive phenomena in the real world. For example, the performance of BC often keeps increasing as the model overfits more to the dataset, and fully closed-loop policies often completely fail without action chunking.
Beyond Reconstruction: What Matters in Action Tokenization for Robot Policies?
Haoran Chen, Jingtian Ji, Samuel Wheeler et al.
Autoregressive action-token policies such as vision-language-action models require action tokenizers to translate discrete token sequences into precise control actions in continuous space. Many action tokenizers learn the mapping between tokens and actions via a reconstruction objective.