Truck drone arc covering problem with an application and case study in disaster management
针对洪水期间河流巡查的实际需求，提出卡车与无人机协同的弧覆盖问题，建立混合整数线性规划模型并设计启发式算法，案例表明无人机可较船只和卡车分别减少56.3%和28.1%的覆盖时间。
Abstract River exploration during, before, or after floods enables operators in civil protection and disaster control to better prepare for or even prevent disasters. While typically, this river exploration is done by boat, truck, helicopter, or even not at all, autonomous flying drones equipped with a camera can enhance this process. Moreover, interaction between a truck and a drone can enable the drone to be used flexibly and extend its short range. Thus, the Bavarian Red Cross equipped a truck with a drone for river coverage. Based on this real case, we introduce a truck drone arc covering problem (TD-ACP) for the application of river coverage. We formulate the TD-ACP as a mixed-integer linear program and introduce valid inequalities that strengthen the formulation and allow us to solve realistic-sized instances to optimality. In a real-world case study involving an actual river, we demonstrate that using drones for river coverage can reduce coverage time by 56.3% compared to boats and by 28.1% compared to trucks. Additionally, we propose a manual planning heuristic that is straightforward for practitioners to apply and achieves an optimality gap of 4.0% on this specific river.