Learning Large Neighborhood Search for Vehicle Routing in Airport Ground Handling
This addresses a complex vehicle routing problem for airport logistics, offering a scalable solution for real-world operations, though it appears incremental as it builds on existing large neighborhood search techniques.
The paper tackles the problem of scheduling multiple vehicle fleets for airport ground handling operations by formulating it as a mixed integer linear programming model and proposing a learning-assisted large neighborhood search method. The method outperforms state-of-the-art approaches, handling up to 200 flights with 10 operation types simultaneously.
Dispatching vehicle fleets to serve flights is a key task in airport ground handling (AGH). Due to the notable growth of flights, it is challenging to simultaneously schedule multiple types of operations (services) for a large number of flights, where each type of operation is performed by one specific vehicle fleet. To tackle this issue, we first represent the operation scheduling as a complex vehicle routing problem and formulate it as a mixed integer linear programming (MILP) model. Then given the graph representation of the MILP model, we propose a learning assisted large neighborhood search (LNS) method using data generated based on real scenarios, where we integrate imitation learning and graph convolutional network (GCN) to learn a destroy operator to automatically select variables, and employ an off-the-shelf solver as the repair operator to reoptimize the selected variables. Experimental results based on a real airport show that the proposed method allows for handling up to 200 flights with 10 types of operations simultaneously, and outperforms state-of-the-art methods. Moreover, the learned method performs consistently accompanying different solvers, and generalizes well on larger instances, verifying the versatility and scalability of our method.