Dynamic truck-and-drone routing problem with multiple tasks after disasters

Abstract

<p>This study addresses the dynamic routing problem for a truck-and-drone collaboration system after disasters. Specifically, the truck-and-drone system consists of multiple trucks and drones with flexible collaboration rules to serve all rescue tasks. Two critical tasks after disasters are considered in this paper, i.e., delivery and surveillance tasks. Delivery tasks involve providing essential supplies such as food, water, and medicine to affected individuals. The surveillance tasks focus on assessing the network states. Given the highly unstable post-disaster environment, where rescue tasks may arise stochastically, it is essential to dynamically update the routes of trucks and drones as new demands emerge. The objective of the proposed problem is to minimize the priority cost, which is related to the rescue arrival time and the task priority. As the survival probability decreases with time, minimizing the priority cost can maximize the number of rescued people. In this paper, we model this problem as a Markov Decision Process (MDP) and solve it using a multi-agent reinforcement learning (MARL) method, where each truck and drone acts as an agent. Leveraging the attention mechanism among nodes and agents, trucks and drones collaboratively make decisions to serve all demands in a dynamic environment. After training, our proposed method can get a near-optimal solution in deterministic scenarios. For dynamic scenarios, it can outperform other methods in terms of priority cost and quality of service. Meanwhile, the proposed method demonstrates a short solution time, highlighting its potential for application in disaster response operations.<br></p>