基于遗传算法的航班—登机口分配优化

董洁霜，赵 炎，刘魏巍 DONG Jieshuang,ZHAO Yan,LIU Weiwei

（上海理工大学 管理学院，上海 200093）

(Management School,University of Shanghai for Science&Technology,Shanghai 200093,China)

0 引言

随着航空事业的发展，机场在满足旅客快速增长的同时，航班—登机口的合理分配，旅客中转效率和机场运作效率的提高，对大型机场而言，显得非常重要[1]。关于登机口分配优化研究中，主要有三类研究方法：数学规划方法、人工智能方法和系统仿真方法[2]。Gonçalves等[3]学者提出中转时间最短的0-1整数规划模型。L.Soi-Hoi等[4]学者建立了一个基于停机位时刻分配的专家系统。国内学者张学明[5]首次提出基于知识库和三级推理机模式的机位自动分配系统。李耐毅、郑志武等[6-7]学者利用仿真软件对登机口分配情况进行模拟研究。陆迅[8]通过仿真建模对机场旅客进行了研究。本文考虑机场的航班时间安排，航班类型、登机口的类型和数量，旅客的流程时间，以0-1整数规划为理论基础，建立双目标优化模型，选用遗传算法，运用MATLAB编程求解，得到航班—登机口最优分配方案。

1 问题描述

某机场航站楼T具有出发、到达、出入境和候机功能，卫星厅S可以候机，但没有出入境功能。航站楼T有28个登机口，卫星厅S有41个登机口，两者之间一次单程时间只需要8分钟，旅客无需等待。中转流程是指中转旅客从乘坐前一航班到达至后一航班出发时间的过程，一共有国内（D）和国际（I）、航站楼（T）和卫星厅（S）组合成16种不同的场景。每个登机口的国内/国际、到达/出发、宽体机/窄体机属性，飞机有宽体机和窄体机两种。

2 目标函数

2.1 模型的假设

登机口与航班必须符合一对一的分配原则，且被分配的航班类型与所使用的登机口属性相匹配，即国际航班只能使用国际登机口，且其间航班不能挪至别处；假设每架航班到达和出发的登机口必须是同一个登机口；只有在没有符合要求的固定登机口的情况下，飞机才会被分配到临时机位，且临时机位的数量没有限制。

2.2 基于旅客中转流程时间最少的双目标优化模型

要使机场运营效率最高，需要将有限的登机口合理地分配给较多数量的航班，即使用最少的登机口，保证停靠在临时机位的飞机数量最少。引入决策变量xij，当航班可以停靠于登机口j时，xij值为1，否则为0，且满足以保证每个到达航班使用登机口是唯一的，其中，i=1,2,…,n，j=1,2,…,7。建立登机口最优目标函数：

式中：k为第j类第k个登机口，xi8为第i架飞机停靠在临时机位，M为惩罚因子。设nih为从航班i到航班h的旅客数目；为搭乘航班h离开的所有旅客的数目；ckk'为中转旅客从登机口k到登机口k'所用的时间。设yijk表示第i架飞机停在第j类第k个登机口，当该飞机可以停靠时，yijk值为1，否则值为0。建立关于旅客中转总体流程时间Z2最少的目标函数[7,3]：

其中：

3 遗传算法设计

遗传算法对大规模复杂问题的求解有良好的表现，可以快速收敛[9-10]。本模型的求解，虽然变量过多可能会对求解造成影响，但是经过对目标函数求解的改进，可使模型较快的收敛。算法流程如图1所示：

图1 算法流程图

算法对基因的编码进行了改变，将其设置为1到8的随机整数，并通过调整φi的大小，可以确定登机口的具体位置，如图2所示。

4 算例分析

4.1 算例数据

中转旅客中转的最短时间数据如表1所示：

4.2 算例结果

通过遗传算法不断迭代求解得到航班—登机口最优方案。其中，31.93%的中转旅客可以在30分钟内完成中转，所有的旅客都可以在一个小时内完成航班换乘。此时，在290架飞机中，共213架飞机可以分配至52个登机口机位上，其中航站楼T使用28个登机口，卫星厅S使用24个登机口，剩余的77架飞机被安排停靠到临时机场。具体如图3、图4和表2所示：

图2 登机口位置划分图

表1 中转旅客中转的最短时间数据表

图3 算法迭代图

图4 中转旅客换乘时间比率

5 结束语

本文针对机场航班—登机口分配问题，考虑航班时间计划、登机口类型和数量、航班类型、中转旅客的流程时间，建立了双目标优化模型，并利用MATLAB软件对模型进行了求解。通过对算例的分析，验证了模型的可行性，其研究成果可为机场管理部门提供参考。

表2 登机口分配使用情况明细表 单位：min