基于NSGA-Ⅱ的多目标航班登机口调度研究

Study on multi-objective airport gate scheduling based on NSGA-Ⅱ

民航客运量的增加加剧了各机场的候机紧张程度,增加登机口对中转旅客的航班衔接具有重要的影响。本文针对登机口候机紧张和中转旅客航班衔接的问题,对多目标航班登机口调度问题进行研究,建立多目标航班登机口调度问题的数学模型,设计最小化登机口总使用量、最小化旅客最大总步行时间的目标函数。针对建立的多目标问题模型,提出基于NSGA-Ⅱ的求解方法,以快速非支配排序及拥挤距离为适应度评价方法,根据航班登机口调度问题与柔性作业车间调度问题的共性特点进行类比,提出一种问题假设与数据处理方法,将所有航班处理为各个工件的工序,采用工序排序和加工机器分配两部分结合的编码方法,最后以某机场当日51个航班15个登机口调度问题为例,验证了模型及提出的算法。结果表明,登机口的总使用量和旅客最大总步行时间的目标函数并非线性关系,采用单目标优化算法求解,无法兼顾两个目标,使用本文提出的NSGA-Ⅱ算法求解,可以最终确定一组Pareto解集,该解集中的每个解都能得到兼顾。

The increase in passenger traffic volume in civil aviation has increased the waiting intensity of airports.Increasing the airport gates has an important impact on the flight connections of transit passengers.In view of the tight waiting time at the boarding gates and the flight connection problem of the transit passengers,the multi-objective flight airport gate scheduling was studied in this paper,a mathematical model of the multi-objective airport gate scheduling,and an objective function that minimized the total usage of the gate and minimized the maximum total walking time of the passenger was designed.A solution method bases on NSGA-II was proposed to deal with the established model.The fast non-dominated sorting and crowded distance were used as the fitness evaluation methods,a problem hypothesis and data processing method was employed to effectively process the flight into the operations belonging to each job.According to the common characteristics of airport gate scheduling problem and flexible job shop scheduling problem,the coding method combining operation sequencing and machine allocation was adopted.Finally,an example was given to verify the model and the proposed algorithm by using 15 departure gates on 51 flights on the same day.The calculation results showed that the total usage of the gate and the objective function of the passenger’s maximum total walking time were nonlinear.The sole target optimization algorithm could not balance the two objectives.The proposed NSGA-II algorithm could finally determine a set of Pareto solution sets,and could take into account each solution in the solution set.