arXiv preprint ·
A Two-Echelon Covering Tour Vehicle Routing Problem with Drones for Post-Disaster Relief
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Robotics
Quantile Head for Vision-Language-Action Models
One from Infinity: Actualizing Futures from Pretrained World Models into Robot Actions
AD-E2E-JEPA: A Joint-Embedding Predictive Architecture For End-to-End Autonomous Driving
FineART: Fine-Grained Annotated Robotic Trajectory Dataset and Vision-Language-Action Model for Bimanual Manipulation
Beyond Retrieval Relevance: Scene-Grounded Risk Entailment for Vision-Language Driving
Get the few papers worth your time in Robotics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.