Path pool based transformer model in reinforcement framework for dynamic urban drone delivery problem

Unmanned Aerial Vehicles (UAVs), particularly drones used for delivery, represent a rapidly expanding segment of the commercial services industry. A critical challenge for scaling operations is the real-time scheduling of a large fleet of drones. This paper addresses the dynamic urban drone delivery problem, focusing on the assignment of orders and the routing of drones. The complexity of such dynamic optimization problems increases exponentially with the drone fleet size and the intricacy of their routing networks, making traditional exact and heuristic algorithms insufficient for effective resolution. To tackle this computational complexity, we introduce a novel Path Pool-based Transformer model combined with Reinforcement Learning (PPTRL). Unlike existing transformer-based models that predict the next node using only the embedding of the previously visited node, our model employs a dependency decay pooling strategy (DDPS) that incorporates the entire path context of the drone into the decision-making process. By leveraging the full path context, our approach captures long-term dependencies in routing decisions, leading to more globally efficient paths. The experimental results confirm the efficacy of the path pool approach. Experimentally, our model achieves near-optimal performance on small-scale problems with significantly reduced runtime compared to Gurobi. For larger-scale problems, our approach surpasses both heuristics and advanced learning-based algorithms in performance. Furthermore, our method demonstrates excellent scalability and robustness against variations in fleet size and the proportion of dynamically arriving tasks and shows good capabilities in the real-world scenario.