考虑中转旅客的登机口分配问题
|
摘要
为了保证中转旅客的成功换乘,提高机场资源利用效率,文章对登机口分配问题进行了研究。在考虑中转旅客换乘时间尽量短的同时,尽量减少登机口的使用个数。根据转场限定、登机口限定、属性匹配限定、空挡间隔限定,建立飞机—登机口分配的一个二次0-1整数规划模型。为改善遗传算法局部搜索能力方面的不足,设计改进的NSGA-II遗传算法,提出将分支定界法与遗传算法相结合,构造了一种内嵌分支定界寻优搜索的遗传算法,在保证算法全局搜索能力的前提下提升局部精确搜索能力。借助MATLAB编程软件进行求解,优化机场转机飞机与航站楼、卫星厅的分配,并给出成功分配到登机口的航班数量和比例、航站楼和卫星厅登机口的使用数目和被使用登机口的平均使用率等信息。
In order to ensure the successful transfer of passengers and improve the utilization efficiency of airport resources, this paper studies the problem of gate allocation. Consider transit passengers as short as possible, while minimizing the number of gate use. A quadratic 0-1 integer programming model is established according to the transition field limit, gate limit, attribute matching limit and gap interval limit. In order to improve the partial searching ability of the genetic algorithm, the improved NSGA-II genetic algorithm is designed. The branch and bound method is combined with the genetic algorithm, and a genetic algorithm is constructed to improve the local accurate searching ability under the premise of ensuring the global searching ability of the algorithm. MATLAB programming software was used to solve the problem, so as to optimize the allocation of airport transit planes,terminals and satellite halls, and to provide information such as the number and proportion of flights successfully allocated to the boarding gates, the number of boarding gates in terminals and satellite halls, and the average utilization rate of boarding gates.
In order to ensure the successful transfer of passengers and improve the utilization efficiency of airport resources, this paper studies the problem of gate allocation. Consider transit passengers as short as possible, while minimizing the number of gate use. A quadratic 0-1 integer programming model is established according to the transition field limit, gate limit, attribute matching limit and gap interval limit. In order to improve the partial searching ability of the genetic algorithm, the improved NSGA-II genetic algorithm is designed. The branch and bound method is combined with the genetic algorithm, and a genetic algorithm is constructed to improve the local accurate searching ability under the premise of ensuring the global searching ability of the algorithm. MATLAB programming software was used to solve the problem, so as to optimize the allocation of airport transit planes,terminals and satellite halls, and to provide information such as the number and proportion of flights successfully allocated to the boarding gates, the number of boarding gates in terminals and satellite halls, and the average utilization rate of boarding gates.
引文
[1] D, Zhang, Klabjan, D. Optimization for gate re-assignment[J]. Transportation Research Part B:Methodological, 2017(95):260
[2] S Liu, W H Chen, J Liu. Robust assignment of airport gates with operational safety constraints[J]. International Journal of Automation and Computing, 2016,13(1):31-41.
[3] A Bouras. The airport gate assignment problem:a survey[J]. Scientific World Journal, 2014(1):859-923.
[4] G Steuart. Gate position requirements at metropolitan airports[J]. Transportation Science, 1974,8(2):169-189.
[5] B Maharjan, T I Matis. Multi-commodity flow network model of the flight gate assignment problem[J]. Computers and Industrial Engineering, 2012,63(4):1135-1144.
[6] J Castaing, I Mukherjee, A Cohn, et al. Reducing airport gate blockage in passenger aviation:Models and analysis[J]. Computers&Operations Research, 2016(65):189-199.
[7] U Dorndorf, F Jaehn, E Pesch. Flight gate assignment and recovery strategies with stochastic arrival and departure times[J].OR Spectrum, 2017(9):39-65.
[8] C H Tang, W C Wang. Airport gate assignments for airline specific gates[J]. Journal of Air Transport Management, 2013(30):10-16.
[9] C Zhang, D Lau. MIP-based heuristics for solving robust gate assignment problems[J]. Computers&Industrial Engineering,2016(93):171-191.
[10]李耐毅.机场登机口分配仿真及优化[D].南京:南京航空航天大学(硕士学位论文),2013.
[11]陈鹏超.多航站楼多区域机位分配问题研究[D].南京:南京航空航天大学(硕士学位论文),2013.
[12]王志清,商红岩,宁宣熙.机场登机口优化调度算法及实证[J].南京航空航天大学学报,2007,39(6):819-823.
[13]杨越,王犇,刘杨.机场机位分配的一种实用方法[J].中国民航大学学报,2014,32(2):27-32.
[14]刘君强,张马兰,陈鹏超,等.基于协同决策的多航站楼停机位实时分配算法[J].南京航空航天大学学报,2015,47(1):71-76.
[15]高菁,杨旭东.基于规则的机位分配问题研究[J].计算机科学,2012,39(s2):51-53.
[16]薛清文,姜雨,刘照明,等.基于航空公司运行成本和公平性的停机位指派[J].航空计算技术,2016,46(1):64-69.
[17]曾琳燕,姜雨,罗宇骁.基于旅客步行距离的停机位均衡优化指派建模[J].武汉理工大学学报(交通科学与工程版),2014(4):895-899.
[18]李明捷,石荣协,蒋凤伟,等.图论最大流理论在机场登机口分配中的应用[J].中国民航大学学报,2010(5):1-3.
[19]李军会,朱金福,高强.基于贪婪禁忌算法的停机位指派问题研究[J].交通运输系统工程与信息,2011,11(4):173-179.
[20]卫东选.基于改进遗传算法的机场停机位分配问题研究[D].天津:中国民航大学(硕士学位论文),2006.
[21]陈骁睿.基于改进粒子群算法的机位分配问题研究[J].软件,2015(1):72-76.
[2] S Liu, W H Chen, J Liu. Robust assignment of airport gates with operational safety constraints[J]. International Journal of Automation and Computing, 2016,13(1):31-41.
[3] A Bouras. The airport gate assignment problem:a survey[J]. Scientific World Journal, 2014(1):859-923.
[4] G Steuart. Gate position requirements at metropolitan airports[J]. Transportation Science, 1974,8(2):169-189.
[5] B Maharjan, T I Matis. Multi-commodity flow network model of the flight gate assignment problem[J]. Computers and Industrial Engineering, 2012,63(4):1135-1144.
[6] J Castaing, I Mukherjee, A Cohn, et al. Reducing airport gate blockage in passenger aviation:Models and analysis[J]. Computers&Operations Research, 2016(65):189-199.
[7] U Dorndorf, F Jaehn, E Pesch. Flight gate assignment and recovery strategies with stochastic arrival and departure times[J].OR Spectrum, 2017(9):39-65.
[8] C H Tang, W C Wang. Airport gate assignments for airline specific gates[J]. Journal of Air Transport Management, 2013(30):10-16.
[9] C Zhang, D Lau. MIP-based heuristics for solving robust gate assignment problems[J]. Computers&Industrial Engineering,2016(93):171-191.
[10]李耐毅.机场登机口分配仿真及优化[D].南京:南京航空航天大学(硕士学位论文),2013.
[11]陈鹏超.多航站楼多区域机位分配问题研究[D].南京:南京航空航天大学(硕士学位论文),2013.
[12]王志清,商红岩,宁宣熙.机场登机口优化调度算法及实证[J].南京航空航天大学学报,2007,39(6):819-823.
[13]杨越,王犇,刘杨.机场机位分配的一种实用方法[J].中国民航大学学报,2014,32(2):27-32.
[14]刘君强,张马兰,陈鹏超,等.基于协同决策的多航站楼停机位实时分配算法[J].南京航空航天大学学报,2015,47(1):71-76.
[15]高菁,杨旭东.基于规则的机位分配问题研究[J].计算机科学,2012,39(s2):51-53.
[16]薛清文,姜雨,刘照明,等.基于航空公司运行成本和公平性的停机位指派[J].航空计算技术,2016,46(1):64-69.
[17]曾琳燕,姜雨,罗宇骁.基于旅客步行距离的停机位均衡优化指派建模[J].武汉理工大学学报(交通科学与工程版),2014(4):895-899.
[18]李明捷,石荣协,蒋凤伟,等.图论最大流理论在机场登机口分配中的应用[J].中国民航大学学报,2010(5):1-3.
[19]李军会,朱金福,高强.基于贪婪禁忌算法的停机位指派问题研究[J].交通运输系统工程与信息,2011,11(4):173-179.
[20]卫东选.基于改进遗传算法的机场停机位分配问题研究[D].天津:中国民航大学(硕士学位论文),2006.
[21]陈骁睿.基于改进粒子群算法的机位分配问题研究[J].软件,2015(1):72-76.