Route optimisation of truck-and-drone systems for multi-type rescue tasks: a heuristic approach

This study investigates a Vehicle Routing Problem with Drones (VRPD) for multi-type rescue tasks in post-disaster response. Specifically, we consider a truck-and-drone collaborative system that can simultaneously deliver essential relief supplies and assess network conditions with drones in disaster scenarios. To enhance the rescue efficiency, drones can collaborate with different trucks and perform multi-type tasks (delivery and surveillance), making the proposed problem challenging to solve. We first provide a Mixed Integer Linear Programming (MILP) model for the proposed problem. The objective is to minimise the priority cost, which is calculated as the weighted delay cost of serving all rescue tasks and is different from most existing studies on VRPD for parcel deliveries. Then, we develop an Adaptive Simulated Annealing (ASA) algorithm. Since the priority cost depends on the intertwined influence of truck-and-drone routes, the ASA algorithm is integrated with a dynamic programming method to calculate the priority cost. The ASA algorithm can always get the (near) optimal solution on instances with fewer than 30 nodes, and solves larger instances efficiently. Numerical experiments demonstrate that enabling drones to perform multi-type tasks and allowing flexible truck-and-drone collaboration reduces the priority cost by an average of 15.7% across all tested instances, compared with the single-type task and dedicated truck-and-drone collaboration. Sensitivity analysis shows that introducing more drones can reduce the number of trucks involved in the disaster response while achieving similar performance. Moreover, this study reveals a trade-off between minimising priority cost and other objectives, such as minimising travel cost or makespan.