1433. The Canadian Traveler Problem with Drone Reconnaissance
Invited abstract in session TB-55: Robust and Stochastic Models in Disaster Management, stream Humanitarian Operations.
Tuesday, 10:30-12:00Room: Liberty 1.09
Authors (first author is the speaker)
| 1. | Joris Wagenaar
|
| Econometrics and Operations Research, Tilburg University |
Abstract
In this paper, we explore cooperative routing of a truck and drone under uncertain infrastructure environments, a novel problem in humanitarian logistics relevant to disaster management. Road network statuses are often initially unknown and revealed incrementally post-disaster, impacting first-responder aid distribution. The objective is for a truck to arrive as fast as possible at its destination to provide humanitarian supplies. Similar to the Canadian Traveler problem, each edge's traversal time is known, but whether it is blocked becomes clear only when the truck or drone visits an adjacent node. We propose policies for both, leveraging a drone's reconnaissance to scout road conditions and update the truck's path.
Three policies are developed for the truck: the Shortest Path policy, assuming all edges are unblocked; the Travel Alternative Diversity policy, incorporating backup paths; and the Shortest Path Waiting policy, balancing route selection with drone updates. Drone policies vary in scouting order—following the truck's route, prioritizing edges near the destination, or focusing on network-critical edges.
Computational results show significant reductions in truck travel time using drone-assisted routing across simulated and real-world networks. Our findings highlight how network characteristics and disaster scenarios influence policy performance, demonstrating the benefits of drone-assisted routing for disaster response under limited information.
Keywords
- Humanitarian Applications
- Stochastic Models
- Disaster and Crisis Management
Status: accepted
Back to the list of papers