954. Online approaches for the drone-supported distribution of relief in disaster areas
Invited abstract in session TA-17: Modeling and competitive analysis in routing and covering problems, stream Combinatorial Optimization.
Tuesday, 8:30-10:00Room: Esther Simpson 2.08
Authors (first author is the speaker)
| 1. | Marie Schmidt
|
| Institute for Computer Science, University of Würzburg | |
| 2. | Alena Otto
|
| Technical University of Munich |
Abstract
We study the problem of providing emergency supplies in disaster areas by a tandem of truck and drone. In the basic problem version, we assume that we are given a number of potential demand points. Upon visiting a potential demand point by either vehicle, we learn whether there is indeed demand for relief goods in the respective node. In that case a visit by truck is necessary to deliver the required goods. We propose a routing strategy for truck and drone and are able to prove that it has a competitive ratio of 2 if the truck is faster than the drone and 1+alpha if the drone is faster, where alpha denotes the ratio of truck and drone speed. Furthermore, for some values of alpha, we are able to show that the proposed strategy is optimal in the sense that no other strategy can achieve a better competitive ratio. After studying the basic problem variant, we transfer our ideas to problem extensions.
Keywords
- Disaster and Crisis Management
- Transportation
Status: accepted
Back to the list of papers