机场登机口分配问题的顶点着色模型与算法

梁超超,陈培军

(太原科技大学 应用科学学院，太原 030024)

随着旅行业快速发展,机场航班日起降架次的增多和乘飞机出行人数的迅速增长,现有的登机口资源正面临着越来越严峻的考验。在航空运输管理中,机场管理处于重要地位。在机场管理中,航班机位(即登机口)分配处于重要地位。针对航班-登机口分配问题,文军和孙宏[1]等提出了一种登机口分配问题的排序模型,并采用登机口标号函数建立标号算法对其进行求解。田晨和熊桂喜[2]通过运用遗传算法来求解航班-登机口分配问题。文军、李冰[3]等人提出了一种登机口分配问题的图着色模型,并通过时间片算法确定航班使用登机口的时间冲突集合,根据“先到先服务”的原则建立登机口分配的顶点序列着色算法。

但很多现有航站楼的旅客流量已达饱和状态,为了应对与日俱增的运营压力,正增设卫星厅。2018年“华为杯”第十五届研究生数学竞赛F题对这类问题的登机口分配提出了研究要求。航站楼T和卫星厅S的布局设计如图1所示。航站楼T有28个登机口,卫星厅S有41个登机口,具体数据见赛题。航班分配问题的任务可理解为在尽可能节约资源的情况下,给出能够有效分配最多的航班到适合的登机口的问题。由于登机口与机型的约束,以及航班与航班之间存在时间冲突,可将问题转化为带约束的顶点着色问题。本文的主要工作是设计了简单有效的可以应用于具有卫星厅的登机口分配的贪婪算法策略。……