A Hybrid NSGA-III and Reinforcement Learning Algorithm for Truck-Drone Emergency Delivery in Damaged Road Networks

Abstract

Natural disasters often result in large-scale road destruction, which causes delays in the delivery of supplies. Truck-drone partnerships could be an appropriate solution to address such a problem. This research focuses on collaborative emergency distribution using trucks and drones in disrupted road networks. The proposed damage model involves three layers of coupling, namely edge damage, travel time penalty, and reachability coupling, which helps capture the gradual reduction in road accessibility, in contrast to simpler damage models. The study also proposes a three-objective optimization model targeting minimized delay, operating cost, and demand satisfaction. NSGA-III is combined with a reinforcement learning technique to enhance its performance by integrating an adaptive operator scheduler module that uses Q-learning to generate a schedule of crossovers and mutations based on the current population dynamics in each generation. Reinforcement learning is used only for generating schedules rather than for generating the solutions themselves, thereby avoiding problems such as unstable training due to inadequate samples, which plague deep reinforcement learning techniques. The results from comparative experiments conducted on the Solomon VRPTW dataset and on the real-life road network in Wenchuan after the disaster reveal that the proposed approach attains the highest hypervolume on the Solomon benchmark and matches the strongest baseline on the Wenchuan case, while the three-layer damage modeling consistently outperforms the simplified model of edge removal across the disruption levels of the Wenchuan case study.