A Hybrid Genetic Algorithm Based on Imitation Learning for the Airport Gate Assignment Problem
Airport gates are the main places for aircraft to receive ground services. With the increased number of flights, limited gate resources near to the terminal make the gate assignment work more complex. Traditional solution methods based on mathematical programming models and iterative algorithms are...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-03-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/25/4/565 |
| _version_ | 1797605561433325568 |
|---|---|
| author | Cong Ding Jun Bi Yongxing Wang |
| author_facet | Cong Ding Jun Bi Yongxing Wang |
| author_sort | Cong Ding |
| collection | DOAJ |
| description | Airport gates are the main places for aircraft to receive ground services. With the increased number of flights, limited gate resources near to the terminal make the gate assignment work more complex. Traditional solution methods based on mathematical programming models and iterative algorithms are usually used to solve these static situations, lacking learning and real-time decision-making abilities. In this paper, a two-stage hybrid algorithm based on imitation learning and genetic algorithm (IL-GA) is proposed to solve the gate assignment problem. First of all, the problem is defined from a mathematical model to a Markov decision process (MDP), with the goal of maximizing the number of flights assigned to contact gates and the total gate preferences. In the first stage of the algorithm, a deep policy network is created to obtain the gate selection probability of each flight. This policy network is trained by imitating and learning the assignment trajectory data of human experts, and this process is offline. In the second stage of the algorithm, the policy network is used to generate a good initial population for the genetic algorithm to calculate the optimal solution for an online instance. The experimental results show that the genetic algorithm combined with imitation learning can greatly shorten the iterations and improve the population convergence speed. The flight rate allocated to the contact gates is 14.9% higher than the manual allocation result and 4% higher than the traditional genetic algorithm. Learning the expert assignment data also makes the allocation scheme more consistent with the preference of the airport, which is helpful for the practical application of the algorithm. |
| first_indexed | 2024-03-11T05:02:50Z |
| format | Article |
| id | doaj.art-2aea2787a35146d3990442acbd3ebe56 |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-03-11T05:02:50Z |
| publishDate | 2023-03-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-2aea2787a35146d3990442acbd3ebe562023-11-17T19:07:52ZengMDPI AGEntropy1099-43002023-03-0125456510.3390/e25040565A Hybrid Genetic Algorithm Based on Imitation Learning for the Airport Gate Assignment ProblemCong Ding0Jun Bi1Yongxing Wang2School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, ChinaSchool of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, ChinaSchool of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, ChinaAirport gates are the main places for aircraft to receive ground services. With the increased number of flights, limited gate resources near to the terminal make the gate assignment work more complex. Traditional solution methods based on mathematical programming models and iterative algorithms are usually used to solve these static situations, lacking learning and real-time decision-making abilities. In this paper, a two-stage hybrid algorithm based on imitation learning and genetic algorithm (IL-GA) is proposed to solve the gate assignment problem. First of all, the problem is defined from a mathematical model to a Markov decision process (MDP), with the goal of maximizing the number of flights assigned to contact gates and the total gate preferences. In the first stage of the algorithm, a deep policy network is created to obtain the gate selection probability of each flight. This policy network is trained by imitating and learning the assignment trajectory data of human experts, and this process is offline. In the second stage of the algorithm, the policy network is used to generate a good initial population for the genetic algorithm to calculate the optimal solution for an online instance. The experimental results show that the genetic algorithm combined with imitation learning can greatly shorten the iterations and improve the population convergence speed. The flight rate allocated to the contact gates is 14.9% higher than the manual allocation result and 4% higher than the traditional genetic algorithm. Learning the expert assignment data also makes the allocation scheme more consistent with the preference of the airport, which is helpful for the practical application of the algorithm.https://www.mdpi.com/1099-4300/25/4/565gate assignmentimitation learninggenetic algorithmdeep neural network |
| spellingShingle | Cong Ding Jun Bi Yongxing Wang A Hybrid Genetic Algorithm Based on Imitation Learning for the Airport Gate Assignment Problem Entropy gate assignment imitation learning genetic algorithm deep neural network |
| title | A Hybrid Genetic Algorithm Based on Imitation Learning for the Airport Gate Assignment Problem |
| title_full | A Hybrid Genetic Algorithm Based on Imitation Learning for the Airport Gate Assignment Problem |
| title_fullStr | A Hybrid Genetic Algorithm Based on Imitation Learning for the Airport Gate Assignment Problem |
| title_full_unstemmed | A Hybrid Genetic Algorithm Based on Imitation Learning for the Airport Gate Assignment Problem |
| title_short | A Hybrid Genetic Algorithm Based on Imitation Learning for the Airport Gate Assignment Problem |
| title_sort | hybrid genetic algorithm based on imitation learning for the airport gate assignment problem |
| topic | gate assignment imitation learning genetic algorithm deep neural network |
| url | https://www.mdpi.com/1099-4300/25/4/565 |
| work_keys_str_mv | AT congding ahybridgeneticalgorithmbasedonimitationlearningfortheairportgateassignmentproblem AT junbi ahybridgeneticalgorithmbasedonimitationlearningfortheairportgateassignmentproblem AT yongxingwang ahybridgeneticalgorithmbasedonimitationlearningfortheairportgateassignmentproblem AT congding hybridgeneticalgorithmbasedonimitationlearningfortheairportgateassignmentproblem AT junbi hybridgeneticalgorithmbasedonimitationlearningfortheairportgateassignmentproblem AT yongxingwang hybridgeneticalgorithmbasedonimitationlearningfortheairportgateassignmentproblem |