On delivery policies for a truck-and-drone tandem in disaster relief

This paper introduces the traveling salesman problem with a truck and a drone under incomplete information (TSP-DI). TSP-DI is motivated by the deliveries of emergency supplies under unknown road conditions in the immediate aftermath of a disastrous event. The urgency may force the immediate dispatch of relief vehicles, such that road damages blocking the truck’s planned route are detected ’on-the-fly’. The relief transport must schedule deliveries anticipating possible unplanned truck detours, enforce (planned) drone detours for early checking of key road segments, and consider the dynamic nature of road condition information. In this paper, we perform a competitive analysis of a widely used delivery policy for TSP-DI in practice – the online re-optimization policy (Reopt) – and compare it to several alternative delivery strategies. Competitive analysis examines the worst-case performance of the strategies and is particularly important in the context of disaster relief, where worst-case outcomes must be avoided. Our analysis shows that Reopt is dominated by alternative delivery policies in terms of the competitive ratio even at a medium level of damage on the road. It also underscores the importance of surveillance detours performed by the drone, even if the surveillance delays the start of the deliveries.