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.