An Exact Algorithm to Solve Vehicle Routing Problem with Drones for Delivery and Surveillance Tasks After Disasters
针对灾后救援中卡车与无人机协同执行配送和监视任务，提出混合整数线性规划模型和基于分支定界与Benders分解的精确算法，以最小化优先级和惩罚成本，实验表明算法优于Gurobi求解器。
Disasters cause severe economic and human losses, and delays in rescue efforts can lead to more deaths due to damaged infrastructure. To enhance post-disaster response efficiency, this study proposes a collaborative truck-and-drone system that leverages the high capacity of trucks and the speed and flexibility of drones to overcome road accessibility challenges. Although truck-drone collaborations have been studied in commercial logistics, their application in disaster relief remains understudied, particularly for simultaneous delivery and surveillance tasks, which are critical for saving lives and assessing damage. Unlike cost- or time-focused commercial logistics, humanitarian operations require prioritizing urgency, where tasks with higher mortality risks should be prioritized. This study addresses the truck-and-drone routing problem with flexible collaboration strategies for delivery and surveillance tasks to minimize the priority and penalty costs in the disaster response. We model the problem as a mixed integer linear programming model and develop an exact method based on the branch-and-bound algorithm and the Benders decomposition approach to solve the problem. Several valid inequalities are derived based on problem properties to improve the computational efficiency. Numerical experiments demonstrate that the proposed algorithm outperforms the state-of-the-art solver Gurobi in terms of objective function value, optimality gap, and computational time. The proposed flexible truck-and-drone collaboration can significantly enhance rescue efficiency in disaster response. Funding: The work described in this paper was partially supported by the National Natural Science Foundation of China [Grants 72371216 and 72301230] and the Research Grants Council of Hong Kong, China [Grants 17205124, 25223223, and T32-707-22]. Supplemental Material: The online appendices are available at https://doi.org/10.1287/trsc.2024.0987 .