Emergency Scheduling of Aerial Vehicles via Graph Neural Neighborhood Search
- 13 January 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Artificial Intelligence
- Vol. 6 (7) , 1808-1822
Abstract
The thriving advances in autonomous vehicles and aviation have enabled the efficient implementation of aerial last-mile delivery services to meet the pressing demand for urgent relief supply distribution. Variable Neighborhood Search (VNS) is a promising technique for aerial emergency scheduling. However, the existing VNS methods usually exhaustively explore all considered neighborhoods with a prefixed order, leading to an inefficient search process and slow convergence speed. To address this issue, this paper proposes a novel graph neural neighborhood search algorithm, which includes an online reinforcement learning (RL) agent that guides the search process by selecting the most appropriate low-level local search operators based on the search state. We develop a dual-graph neural representation learning method to extract comprehensive and informative feature representations from the search state. Besides, we propose a reward-shaping policy learning method to address the decaying reward issue along the search process. Extensive experiments conducted across various benchmark instances demonstrate that the proposed algorithm significantly outperforms the state-of-the-art approaches. Further investigations validate the effectiveness of the newly designed knowledge guidance scheme and the learned feature representations.Keywords
Funding Information
- National Natural Science Foundation of China (U2333218, 52302398)
- Beijing Natural Science Foundation (L241036)
This publication has 57 references indexed in Scilit:
- Vehicle routing with cumulative objectives: A state of the art and analysisComputers & Industrial Engineering, 2022
- A scheduling and planning method for geological disastersApplied Soft Computing, 2021
- Drone routing and optimization for post-disaster inspectionComputers & Industrial Engineering, 2021
- A hybrid large-neighborhood search algorithm for the cumulative capacitated vehicle routing problem with time-window constraintsApplied Soft Computing, 2019
- Peer-induced fairness capacitated vehicle routing scheduling using a hybrid optimization ACO–VNS algorithmSoft Computing, 2019
- A mathematical model for location of temporary relief centers and dynamic routing of aerial rescue vehiclesComputers & Industrial Engineering, 2019
- A POPMUSIC approach for the Multi-Depot Cumulative Capacitated Vehicle Routing ProblemOptimization Letters, 2019
- Routing optimization of emergency grain distribution vehicles using the immune ant colony optimization algorithmApplied Soft Computing, 2018
- Multi-rotor drone tutorial: systems, mechanics, control and state estimationIntelligent Service Robotics, 2017
- A POPMUSIC-based approach for the berth allocation problem under time-dependent limitationsAnnals of Operations Research, 2015