Learning large neighborhood search for vehicle routing in airport ground handling

• Main Authors: ZHOU, Jianan, WU, Yaoxin, CAO, Zhiguang, SONG, Wen, ZHANG, Jie, CHEN, Zhenghua
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2023
• Subjects: Airport ground handling; Airports; Atmospheric modeling; data-driven optimization; deep learning; Genetic algorithms; graph neural network; large neighborhood search; learning to optimize; Maintenance engineering; Optimization; Routing; Vehicle routing; Databases and Information Systems
• Online Access: https://ink.library.smu.edu.sg/sis_research/8192; https://ink.library.smu.edu.sg/context/sis_research/article/9195/viewcontent/learning.pdf
• Institution: Singapore Management University

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.