龚举华(1990-), 男, 博士生, 从事制造系统及优化的研究, E-mail:
张则强(1978−), 男, 教授, 博士生导师, 从事工业工程、制造系统与智能优化等研究, E-mail:
管超(1994-), 男, 博士生, 从事制造系统及优化的研究, E-mail:
刘思璐(1993-), 女, 博士生, 从事制造系统及优化的研究, E-mail:
随着航空运输业的蓬勃发展, 如何在硬件条件受限的情况下尽量提高机场的运行效率来满足日益增长的航班起降需求, 日益受到关注.为了对机场航站楼登机门分配问题进一步优化, 提出一种考虑登机门复合类别的航站楼分配问题, 并建立数学模型, 描述在航线类别、班机型号以及最短停靠间隔对于登机门选取的约束下, 带有临时停机坪辅助的登机门分配优化问题.在模型经过精确算法验证的基础上, 为适应登机门问题特性并求解中大规模问题, 首次引进和声搜索算法, 增加复杂约束条件, 对编码解码、初始解产生以及寻优过程进行改进, 提出一种更高效的改进和声搜索算法对模型进行求解.通过使用Lingo软件和Matlab软件对中小规模算例分别进行精确求解和智能算法求解, 对比表明所提出智能算法的有效性、全局搜索能力以及求解效率.再通过对大规模问题的求解, 表明所提出算法在现有条件下能够减小转机旅客的总转机路程, 取得了较好的效果.
The development of air transport industry can not be separated from the support of airports.How to improve the operation efficiency of airports to meet the increasing demand of flight takeoff and landing under the limited hardware conditions has attracted more and more attention.In order to further optimize the allocation of airport gates in airport terminal buildings, this paper presents a model of airport gate allocation considering the composite categories of airport gates.The model describes the optimization of airport gate allocation with apron assistance under the constraints of airline type, flight type and minimum parking interval.Based on the accurate algorithm validation of the model, a more efficient improved harmony search algorithm is proposed to solve the model.In order to adapt to the characteristics of the medium and large scale problems, the improved harmony search algorithm is introduced by adding complex constraints, with improvements on encoding and decoding, and the initial solution generation and optimization process with.By using Lingo and Matlab respectively on small-scale and medium-scale examples, the result shows that the proposed improved harmony search algorithm is more effective and has advantages over the accurate algorithm in global search ability and solution efficiency.By solving large-scale problems, the proposed algorithm reduces the total transit distance of passengers and achieves good results under the condition of guaranteeing the utilization efficiency of the airport gates.
随着我国近年来国际国内各层次交流不断加深, 航空业也经历了一个蓬勃发展期.随着空港航班数量的不断增加, 如何为日益增多的航空旅客提供高效舒适的地面服务成为一个难题.当前, 空港主要通过航站楼登机门和停机坪接驳车辆两种方式进行旅客的登机和下机程序, 其中通过登机门直接进行班机与航站楼的对接, 无疑是更为安全高效、环保便捷的一种方式, 但是却给机场指挥塔的登机门分配提出了更高的要求.
为了寻求更为高效合理的机场航班-登机门分配方案, 这一类问题被归纳为机场登机门分配问题(the airport gate assignment problem, AGAP).这一问题最早由Steuart[
在最近的研究中, Liu等[
前述文献对机场登机门分配问题开展了卓有成效的研究, 但对于考虑登机门复合类别的航站楼分配问题并未涉及; 而在实际机场运营中这种问题普遍存在.
基于此, 本文在AGAP的现有研究基础上, 针对实际的机场运行规则, 综合考虑航线类别、班机机体型号以及登机门相邻班机最短间隔时间约束, 并在班机数溢出航站楼停靠条件时, 引入临时停机坪进行辅助停靠的基础上, 以转机旅客总转机路程最短作为优化目标, 建立了新的考虑登机门复合类别的航站楼分配问题模型.为求解实际中的大规模问题, 首次将和声搜索(harmony search, HS)算法引入此类问题, 并在其基础上进行改进以适应于此类问题的求解.与其他智能算法相比, 和声搜索算法通过随机的概率指导和声向量及每一维和声分量进行随机变异, 并不断改进[
本文所研究的问题是考虑登机门复合类别的航站楼分配问题, 在模型建立之前, 先对问题进行以下假设.
根据以上问题和假设条件, 建立了关于此问题的整数规划模型, 模型中的变量符号以及含义见
变量符号及含义
符号 | 含义 |
班机编号 | |
登机口编号 | |
航站楼登机门数目 | |
在航站楼有降落起飞任务的班机数目 | |
登机门编号集合 | |
班机的编号集合 | |
第 |
|
第 |
|
登机门上前一班机离港与后一班机进港的最小间隔时间 | |
0, 1变量, 班机机体系数, 1表示宽体机型, 0表示窄体机型 | |
0, 1变量, 登机门适用的机体系数, 1表示宽体机型, 0表示窄体机型 | |
|
表示班机降落时的航线情况, (0, 1)表示国内航线, (1, 0)表示国际航线 |
|
表示班机起飞时的航线情况, (0, 1)表示国内航线, (1, 0)表示国际航线 |
表示登机门的类别, (0, 1)表示仅针对国内航线, (1, 0)表示仅针对国际航线, (1, 1)表示通用登机门 | |
0, 1变量, |
|
0, 1变量, |
|
0, 1变量, |
|
从班机 |
|
表示转机乘客从 |
|
对于需要从临时停机坪上的班机进行转机或者需要登机到临时停机坪的旅客, 对其行走路线的惩罚值 | |
一个足够大的整数 |
本文主要研究考虑登机门复合类别的航站楼分配问题, 在AGAP的现有研究基础上, 针对实际的机场运行规则, 综合考虑航线类别、班机机体型号以及登机门相邻班机最短间隔时间约束, 并在班机数溢出航站楼停靠条件、引入临时停机坪进行辅助停靠的基础上, 以转机旅客总转机路程最短作为优化目标, 研究新的考虑登机门复合类别的航站楼分配问题模型, 即
其中:式(1)为目标函数, 分为两个部分, 第1部分为
表示总转机旅客行走路程.式(13)中第1项表示从航站楼第
表示在总转机旅客行走路程最短的情况下, 尽量减少停靠在临时停机坪的班机数量.式(2) ~ (9)为约束条件, 式(2)表示每架班机只停在一个登机门或临时停机坪处; 式(3)和(4)为约束0, 1变量
遗传算法作为一种经典的智能算法得到了广泛的应用, 与遗传算法的新染色体产生过程中仅考虑一对亲代染色体的方式相比, 和声搜索算法在产生新和声的过程中, 同时考虑和声记忆库中的所有已存在和声; 同时, 和声搜索算法的优化过程不需要设置决策变量的初始值.以上优势便于和声搜索算法增加寻优过程的灵活性, 并有利于寻找更好的解.登机门问题由于存在大量的约束条件, 可行解在邻域解中所占比重不高, 采用和声搜索算法并利用其搜索的灵活性, 有利于对可行解的探索, 提升运算效率.
和声搜索算法是由Geem等[
基本的和声搜索算法通过记忆库取值概率(harmony memory considering rate, HMCR)和微调概率(pitch adjusting rate, PAR)对寻优过程进行调节, 具体过程如下:首先由HMS(harmony memory size)个初始解组成和声记忆库(HM), 即
变量以HMCR的概率在和声记忆库内进行学习, 否则在全局范围内进行取值; 在学习和声记忆库的过程中, 再以PAR的概率对取值进行微调.得出新的和声之后, 若其目标函数值优于HM内的最差解, 则进行和声记忆库更新, 不断重复以上过程进行迭代直到满足循环终止条件.
和声搜索算法问世以来, 被应用于如0-1背包问题[
基础的和声搜索算法在新解产生过程当中没有加入约束条件对过程进行限制, 然而本文所研究的考虑登机门类别的航站楼登机门分配问题具有复杂的约束条件, 随机生成的新解很可能不是一个满足约束的可行解; 另外, 在初始解的产生过程中, 同样存在类似问题.因此, 需对初始解的产生以及和声搜索过程进行相应的设计以满足问题要求.
本文的一个可行解为一组将
初始解的产生采用以下方式进行:首先将所有班机按降落时间从早到晚进行排序; 按登机门编号生成一个起飞时间记录列表; 从前到后依次为班机安排合适类型的登机门, 并且同时满足与前一架班机保留足够的时间间隔, 若有多个合适的登机门, 则随机选取一个, 并更新起飞时间记录列表; 若没有合适的登机门可供选择, 则安排班机进入临时停机坪停靠; 重复以上操作, 直到最后一架班机分配完成, 并产生相应的一维和声.
通过以上方式, 产生一个初始可行解的集合, 并将每个和声进行初步的邻域搜索优化, 优化方式为分组进行和声搜索, 规定一个较小的不变迭代次数Inigen, 当达到次数是输出优化后的HM, 生成新的优化后的初始可行解集合, 并计算每个优化后的初始解的目标函数值(总转机旅客行走路程), 通过比较, 选取HMS个较优的初始解组成初始和声记忆库.
和声搜索过程同样受到登机门类型和已停靠班机的约束, 需要避免登机门的错配和保证足够的相邻班机间隔时间; 除此之外, 更换一架班机停靠的登机门同样需要考虑对后续班机起降造成的影响.为解决上述问题, 在引用文献[
根据上文排列好的班机序号, 构造航班时间关系矩阵
设有可行解
Left函数:若集合
Right函数:若集合
在进行和声邻域搜索的过程中, 对搜索范围内的解首先进行一次筛选, 将待搜索的原和声作为可行解
通过以上工作, 结合登机门问题的复杂约束情况, 对编码解码、初始解产生以及寻优过程进行改进之后, 再对基本的和声搜索算法进行相应修改, 编写了如
改进和声搜索算法求解考虑登机门类别的航站楼登机门分配问题流程
算法步骤如下.
Step 1:设置算法参数.和声记忆库容量HMS, 停机坪转机距离惩罚值
step 2:根据上文方法构造初始和声记忆库.
step 3:初始化迭代计数器iter=1.
step 4:计算初始HM内和声目标函数值, 选取最优初始和声作为变异基准, 若最优初始和声不止一个, 则随机选取一个作为基准.
step 5:初始化和声更新位计数器postion=1;
step 6:进入和声更新, 生成随机数
step 7:对于postion位, 从所有可行域内随机选取新和声位替换旧和声位, 而后令postion=postion+1, 若postion≤
step 8:对于postion位, 从HM内相同位随机选取可行域内的新和声位替换旧和声位, 而后令postion=postion+1.
step 9:进入和声微调, 生成随机数
step 10:计算新和声目标函数值, 与和声库HM内的各和声目标值进行比较, 若优于现有和声库的最差解, 则替换最差解, 返回setp 3;否则, 进入step 11.
step 11:令iter=iter+1, 若iter < Maxgen, 则返回step 4, 否则进入step 12.
step 12:对和声记忆库中的解进行优化, 尽量将和声中的0用登机门编号数字替换, 减少停靠在临时停机坪的班机数量, 并重新计算目标函数值, 终止程序, 输出和声记忆库.
本文所用适用于考虑登机门复合类别的航站楼分配问题的和声搜索算法由Matlab (R2010b)编程实现, 电脑配置为Intel Core i5 2.7 GHz CPU 4.0 GB RAM, 在Windows 7系统下运行, 算法主要参数有和声记忆库容量HMS, 停机坪转机距离惩罚值AP, 最大不变迭代次数Maxgen以及和声初始化筛选迭代次数Inigen.经实验分析, 和声搜索算法参数HMCR统一设置为0.9, PAR统一设置为0.3.
本文采用Lingo11.0软件对中小规模问题进行精确求解, Lingo软件是由Lindo公司新推出的一款适用于线性和非线性领域的通用优化求解器, 它属于运筹学研究所常用到的软件工具之一.
为验证本文所提出考虑登机门复合类别的航站楼分配问题模型, 以及说明所用改进和声搜索算法的求解效果, 分别选取了25班机6登机门和65班机14登机门两组小规模算例, 并同时采用Lingo编写所提出模型和Matlab编写改进和声搜索算法进行求解.
对于25规模算例, 由Lingo所求得的精确解的目标值为101, 所有班机于航站楼停靠, 没有班机进入临时停机坪, 所得的登机门分配情况如
25规模登机门分配精确解
gate | flight |
G1 | 6 10 13 23 |
G2 | 2 11 15 21 |
G3 | 1 5 17 |
G4 | 20 |
G5 | 4 8 14 18 22 25 |
G6 | 3 7 9 12 16 19 24 |
相同问题采用改进和声搜索算法求解, 算法参数为:登机口最小准备时间(即相邻班机停靠同一登机口的最小时间间隔)为
改进和声搜索算法求25规模登机门分配问题的解
gate | flight |
G1 | 6 10 13 23 |
G2 | 2 5 11 15 21 |
G3 | 17 |
G4 | 1 20 |
G5 | 3 7 9 12 14 18 22 25 |
G6 | 4 8 16 19 24 |
G1 | 6 10 13 23 |
G2 | 1 11 15 21 |
G3 | 2 17 |
G4 | 5 20 |
G5 | 3 7 9 12 14 18 22 25 |
G6 | 4 8 16 19 24 |
G1 | 6 10 13 23 |
G2 | 1 11 15 21 |
G3 | 5 17 |
G4 | 2 20 |
G5 | 3 7 9 12 16 18 22 25 |
G6 | 4 8 14 19 24 |
G1 | 6 10 13 23 |
G2 | 1 5 11 15 21 |
G3 | 2 17 |
G4 | 20 |
G5 | 3 7 9 12 14 19 24 |
G6 | 4 8 16 18 22 25 |
对于相同的小规模问题, 改进和声搜索算法相比Lingo的精确算法求到了更多的相同目标值下的精确解, 具有更好的全局寻优性能.
对于65规模算例, 首先由Lingo对算例进行求解, 由于算例规模较大, 在限定的1 800 s时间之内, 求得了以下目标值为33的可行解, 并有10架班机停靠于临时停机坪.对于相同问题, 采用的算法参数为:登机口最小准备时间为
Lingo和改进和声搜索算法求得的65规模登机门分配可行解
Lingo | time=1 800 s | obj=33 |
gate | flight | |
G1 | ||
G2 | ||
G3 | 4 20 43 59 | |
G4 | 5 10 | |
G5 | 7 33 49 | |
G6 | 2 15 36 47 54 | |
G7 | 1 24 51 62 | |
G8 | 3 27 44 55 | |
G9 | 6 41 52 65 | |
G10 | 12 19 23 26 32 40 50 58 | |
G11 | 8 11 16 31 45 56 63 | |
G12 | 14 21 28 48 57 64 | |
G13 | 18 25 34 42 | |
G14 | 22 29 39 60 | |
IHS | time=115.937 s | obj=32 |
gate | flight | |
G1 | 59 | |
G2 | 43 | |
G3 | 4 20 | |
G4 | 5 10 24 36 47 54 | |
G5 | 7 27 35 51 | |
G6 | 2 33 41 52 62 | |
G7 | 1 37 53 | |
G8 | 3 44 55 | |
G9 | 6 15 49 65 | |
G10 | 9 19 25 30 38 45 56 63 | |
G11 | 8 11 17 23 26 32 40 50 58 | |
G12 | 4 22 28 34 42 57 64 | |
G13 | 12 18 29 39 60 | |
G14 | 21 31 48 61 |
以上结果表明, 改进和声搜索算法除具有较好的全局寻优性能以外, 求得较优解的时间相比精确算法大幅缩短, 具有更高的求解效率.
本文所用算例取材自上海浦东国际机场, 选取机场内起降的所有与某一天(从0时至24时)有关的航班作为研究对象.所研究的班机共303架, 即包含303次降落任务和303次起飞任务, 包括3个部分:第1部分为在所选取的一天(从0时至24时)内起飞的已经在前一天较晚时候降落的班机; 第2部分为在所选取的一天(从0时至24时)内降落和起飞的班机; 最后还包括在所选取的一天(从0时至24时)内降落但是没有起飞的班机.班机信息包括航班降落时刻、航班起飞时刻、降落航线类别、起飞航线类别以及班机机体型号.
另外, 本文所研究的算例共包含69个种类不一的登机门, 对于适用航线类别共分3类, 如
登机门编号与适用航线类别表
登机门编号 | 登机门类型 | 用途 |
G1 ~ G22 | 国际航班登机门 | 只能执行国际航班的起降任务 |
G23 ~ G30 | 通用登机门 | 可以执行国际航班和国内航班的起降任务 |
G31 ~ G69 | 国内航班登机门 | 只能执行国内航班的起降任务 |
值得说明的是, 对于通用登机门, 可以停靠所有类别的班机, 包括:起降均为国内航线的班机, 起降均为国际航线的班机, 降落航线为国内航线、起飞航线为国际航线的班机以及降落航线为国际航线、起飞航线为国内航线的班机.前两类班机还可以分别在各自专用的登机门类别进行停靠, 而后两类班机只能停靠于通用登机门.
对于班机机体型号, 分为宽体和窄体两大类, 分别只能停靠在各自适合的登机门.
关于转机旅客的行走距离, 假设所有的登机门都分布在直线型航站楼两侧, 并且登机门是均匀排列, 即旅客沿航站楼过道方向上每经过一个登机门行走的距离相等, 且为一个单位距离, 除此以外, 当乘客从一个登机门到达另一个登机门, 无论这两个登机门是处于航站楼的同侧还是两侧, 都要先来到航站楼内部的主通道, 所以忽略乘客穿过航站楼过道的距离, 认为乘客的行走距离只与沿航站楼主过道方向的行走距离有关.
算法的参数设置如下:登机口最小准备时间(即相邻班机停靠同一登机口的最小时间间隔)为
在以上条件下, 通过Matlab程序对问题进行求解.通过分别使用基本和声搜索算法和本文改进和声搜索算法对大规模问题求解, 分别得到50个目标函数值.基本和声搜索算法所得50个目标值的均值为68 519.02, 标准差为1 468.78;改进和声搜索算法所得50个目标值的均值为66 007.96, 标准差为1 277.38.可知改进和声搜索算法相比基本和声搜索算法在求解的均值和标准差上均有优势, 表明本文对算法针对登机门问题的改进具有明显的效果, 对算法收敛性和稳定性均有提升.
在通过改进和声搜索算法得到的解中, 最优目标函数值为63 930.
登机门占用情况甘特图
登机门停靠班机架次
登机门使用率
通过对实际问题的分析与求解, 改进的和声搜索算法将303架班机合理分配进入69个匹配的航站楼登机门以及临时停机坪, 将转机旅客的总转机行走路程进行优化, 增加了旅客的转机效率和舒适程度.与此同时, 通过对问题的分析结果可以看到, 航站楼登机门的配置尚有优化的空间, 可以通过航班的变动情况和执飞班机的机型, 对登机门的类别进行相应的调整, 以最大化利用现有的登机门资源, 便于更多的班机在登机门进行停靠.
本文在现有AGAP问题的研究基础上, 针对实际的机场运行规则, 综合考虑航线类别、班机机体型号以及登机门相邻班机最短间隔时间约束, 并在班机数溢出航站楼停靠条件时, 引入临时停机坪进行辅助停靠的基础上, 以转机旅客总转机路程最短作为优化目标, 建立了新的考虑登机门复合类别的航站楼分配问题模型.
通过精确算法和所提出的改进和声搜索算法对小规模问题进行求解, 验证了模型的正确性、所提出算法的有效性、全局搜索能力以及求解效率.通过进一步对大规模实际问题进行求解, 对实际规模的登机门分配问题进行了优化, 减小了转机旅客的总转机路程.此外, 所得结论对航站楼登机门的布置方式具有一定的指导意义.
责任编委:梁樑.
Steuart G N. Gate position requirements at metropolitan airports[J]. Transportation Science, 1974, 8(2):169-189.
Bihr R A. A conceptual solution to the aircraft gate assignment problem using 0, 1 linear programming[J]. Computers and Industrial Engineering, 1990, 19(2): 280-284.
Haghani A, Chen M C. Optimizing gate assignment at airport terminals[J]. Transportation Research A: Policy and Practice, 1998, 32(6): 437-454.
Xu J F, Bailey G. The airport gate assignment problem: Mathematical model and a tabu search algorithm[C]. Proceedings of Hawaii International Conference on System Sciences. Maui: IEEE, 2001: 1-10.
Yan S Y, Huo C M. Optimization of multiple objective gate assignments[J]. Transportation Research A: Policy and Practice, 2001, 35(5): 413-432.
Ding H, Lim A, Rodrigues B, et al. New heuristics for over-constrained flight to gate assignments[J]. Journal of the Operational Research Society, 2004, 55(7): 760-768.
Ding H, Lim A, Rodrigues B, et al. The over-constrained airport gate assignment problem[J]. Computers and Operations Research, 2005, 32(7): 1867-1880.
Dorndorf U, Drexl A, Nikulin Y, et al. Flight gate scheduling: State-of-the-art and recent developments[J]. Omega-International Journal of Management Science, 2007, 35(3): 326-334.
Wei D X, Liu C Y. Fuzzy model and optimization for airport Gate assignment problem[C]. IEEE International Conference on Intelligent Computing and Intelligent Systems (ICIS'09). Shanghai: IEEE, 2009: 828-832.
Drexl A, Nikulin Y. Multicriteria airport gate assignment and pareto simulated annealing[J]. ⅡE Transactions, 2008, 40(4): 385-397.
梁存利.有约束的登机门分配问题混合遗传算法[J].计算机工程, 2010, 36(15): 182-184.
Liang C L. Hybrid genetic algorithm for constrained airport gate assignment problem[J]. Computer Engineering, 2010, 36(15): 182-184.
Hou Z X. Measuring technology and mechatronics automation in electrical engineering[M]. New York: Springer, 2012: 347-355.
Liu S, Chen W H, Liu J Y. Optimizing airport gate assignment with operational safety constraints[C]. The 20th International Conference on Automation and Computing. Cranfield: IEEE, 2014: 61-66.
Liu S, Chen W H, Liu J Y. Robust assignment of airport gates with operational safety constraints[J]. International Journal of Automation and Compution, 2016, 13(1): 31-41.
Aktel A, Yagmahan B, Ozcan T, et al. The comparison of the metaheuristic algorithms performances on airport gate assignment problem[C]. The 19th European Operational Research Societies Working Group on Transportation Meeting (EWGT). Istanbul: Elsevier, 2017, 22: 469-478.
Kaliszewski I, Miroforidis J, Stanczak J. The airport gate assignment problem-multi-objective optimization versus evolutionary multi-objective optimization[J]. Computer Science-AGH, 2017, 18(1): 41-52.
Sun W X, Cai X Y, Xia C, et al. Greedy based pareto local search for bi-objective robust airport gate assignment problem[C]. The 11th International Conference on Simulated Evolution and Learning. Shenzhen: Springer, 2017: 694-705.
Deng W, Zhao H M, Yang X H, et al. Research on a robust multi-objective optimization model of gate assignment for hub airport[J]. Transportation Letters——The International Journal of Transportation Research, 2018, 10(4): 229-241.
Deng W, Sun M, Zhao H M, et al. Study on an airport gate assignment method based on improved ACO algorithm[J]. Kybernetes, 2018, 47(1): 20-43.
欧阳海滨, 高立群, 孔祥勇, 等.一种求解0-1背包问题的二进制修正和声搜索算法[J].控制与决策, 2014, 29(7): 1175-1180.
Ouyang H B, Gao L Q, Kong X Y, et al. A binary modified harmony search algorithm for 0-1 knapsack problem[J]. Control and Decision, 2014, 29(7): 1175-1180.
Geem Z W, Kim J H, Loganathan G V. A new heuristic optimization algorithm: Harmony search[J]. Simulation, 2001, 76(2): 60-68.
于宏涛, 高立群, 吕勇军.基于混合和声搜索算法求解竞争选址问题[J].控制与决策, 2013, 28(7): 1083-1086.
Yu H T, Gao L Q, Lv Y J. Hybrid harmony search algorithm for competitive location problem[J]. Control and Decision, 2013, 28(7): 1083-1086.
欧阳海滨, 高立群, 孔祥勇.求解大规模系统可靠性问题的修正和声搜索算法[J].控制与决策, 2015, 30(9): 1567-1574.
Ouyang H B, Gao L Q, Kong X Y, et al. Modified harmony search algorithm for solving large scale system reliability problem[J]. Control and Decision, 2015, 30(9): 1567-1574.