面向靠桥率及道口冲突率的航班-机位指派问题优化模型及其启发式算法研究

在给定航班时刻表条件下,对于进出港航班的机位分配,除了必须满足航班、飞机和机位之间的技术性要求之外,还要考虑尽量提高整个机场的机位利用率,且方便旅客出入港及时、安全和便捷.文章以飞机机型、所属航空公司、客运/货运航班、国内/国际航班等匹配条件为约束条件,以航班-机位分配完成率、靠桥率、道口非冲突率为目标,建立了一个航班-机位指派问题的全局优化模型.基于国内某机场的真实应用场景及其待决策变量维度的超大规模,导致模型求解成为一个NP-COMPLETE的混合整数规划问题.文章提出一种启发式快速求解算法,基于贪婪规则建立若干优先级队列的航班冲突调整方案,按照3个指标重要程度渐次探求近似最优解.而且,对于每一步贪婪规则的改进,文章都进行了算法有效性检验以及计算性能的对比实验.最终多重对比实验的结果表明,新算法的结果在与理论最优解差距不足3%的代价下,可节约超过90%求解时间.

Rates of Closed-Bridge and Crossing-Collision Oriented Optimization Model on Aircraft-Gate Assignment and Its Heuristics

Given a schedule of flights for an airport,the aircraft-gate assignment not only has to obey the technical constraints of airplanes and flights,but also improves the resource utilization and economic efficiency,and facilitates passengers to enter and leave port in a timely,safe and convenient way.In this paper,we establish an optimization model of assigning gates for aircrafts with the objectives of aircraft allocating rate,closed-bridge rate and non-collision rate of crossings,as well as subject to the constraints of flight attributes such as aircraft types,affiliated companies,cargo/passenger tasks and domestic/international flights.For the real scenario of an airport in China,this assignment model becomes a large-scale mixed integer programming with the complexity of NP-COMPLETE.This paper then proposes a greedybased heuristic algorithm,within which a priority queue is established to mediate the timetable conflicts of flights.The approximate optimal solutions are gradually explored according to aircraft allocating rate,closed-bridge rate and non-collision rate of crossings step by step.For each improvement of the algorithm,the effectiveness and performance are evaluated comparing to the results of CPLEX.Finally,the experimental results show that the heuristic algorithm can save 90% of the solution time while the loss of near optimal solutions less than 3%.