Neural Airport Ground Handling
arXiv:2303.02442 · doi:10.1109/TITS.2023.3253552
Abstract
Airport ground handling (AGH) offers necessary operations to flights during their turnarounds and is of great importance to the efficiency of airport management and the economics of aviation. Such a problem involves the interplay among the operations that leads to NP-hard problems with complex constraints. Hence, existing methods for AGH are usually designed with massive domain knowledge but still fail to yield high-quality solutions efficiently. In this paper, we aim to enhance the solution quality and computation efficiency for solving AGH. Particularly, we first model AGH as a multiple-fleet vehicle routing problem (VRP) with miscellaneous constraints including precedence, time windows, and capacity. Then we propose a construction framework that decomposes AGH into sub-problems (i.e., VRPs) in fleets and present a neural method to construct the routing solutions to these sub-problems. In specific, we resort to deep learning and parameterize the construction heuristic policy with an attention-based neural network trained with reinforcement learning, which is shared across all sub-problems. Extensive experiments demonstrate that our method significantly outperforms classic meta-heuristics, construction heuristics and the specialized methods for AGH. Besides, we empirically verify that our neural method generalizes well to instances with large numbers of flights or varying parameters, and can be readily adapted to solve real-time AGH with stochastic flight arrivals. Our code is publicly available at: https://github.com/RoyalSkye/AGH.
arXiv commentAccepted by IEEE Transactions on Intelligent Transportation Systems (TITS)
References in corpus (15)
- Adam: A Method for Stochastic Optimization
- A Comprehensive Survey on Graph Neural Networks
- Learning Combinatorial Optimization Algorithms over Graphs
- Exact Combinatorial Optimization with Graph Convolutional Neural Networks
- Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning
- Deep Reinforcement Learning for Solving the Heterogeneous Capacitated Vehicle Routing Problem
- An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
- Heterogeneous Attentions for Solving Pickup and Delivery Problem via Deep Reinforcement Learning
- Learning to Perform Local Rewriting for Combinatorial Optimization
- POMO: Policy Optimization with Multiple Optima for Reinforcement Learning
- Learning Large Neighborhood Search for Vehicle Routing in Airport Ground Handling
- Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling Networks
- NeuroLKH: Combining Deep Learning Model with Lin-Kernighan-Helsgaun Heuristic for Solving the Traveling Salesman Problem
- Efficient Neural Neighborhood Search for Pickup and Delivery Problems
- Learning the Travelling Salesperson Problem Requires Rethinking Generalization