控制与决策  2020, Vol. 35 Issue (11): 2743-2751  
0

引用本文 [复制中英文]

龚举华, 张则强, 管超, 刘思璐. 复合类别航站楼分配问题的改进和声搜索算法[J]. 控制与决策, 2020, 35(11): 2743-2751.
[复制中文]
GONG Ju-hua, ZHANG Ze-qiang, GUAN Chao, LIU Si-lu. Solving composite airport gate allocation problem with improved harmony search[J]. Control and Decision, 2020, 35(11): 2743-2751. DOI: 10.13195/j.kzyjc.2019.0242.
[复制英文]

基金项目

国家自然科学基金项目(51205328, 51675450);教育部人文社会科学研究青年基金项目(18YJC630255);四川省科技计划项目(2019YFG0285)

作者简介

龚举华(1990-), 男, 博士生, 从事制造系统及优化的研究, E-mail:gongjuhua@my.swjtu.edu.cn;
张则强(1978−), 男, 教授, 博士生导师, 从事工业工程、制造系统与智能优化等研究, E-mail:zhangzq@home.swjtu.edu.cn;
管超(1994-), 男, 博士生, 从事制造系统及优化的研究, E-mail:17175371524@163.com;
刘思璐(1993-), 女, 博士生, 从事制造系统及优化的研究, E-mail:liusilulsl@126.com

通讯作者

张则强, E-mail:zhangzq@home.swjtu.edu.cn

文章历史

收稿日期:2019-03-04
修回日期:2019-08-09
复合类别航站楼分配问题的改进和声搜索算法
龚举华 , 张则强 , 管超 , 刘思璐     
西南交通大学 机械工程学院,成都 610031
摘要:随着航空运输业的蓬勃发展, 如何在硬件条件受限的情况下尽量提高机场的运行效率来满足日益增长的航班起降需求, 日益受到关注.为了对机场航站楼登机门分配问题进一步优化, 提出一种考虑登机门复合类别的航站楼分配问题, 并建立数学模型, 描述在航线类别、班机型号以及最短停靠间隔对于登机门选取的约束下, 带有临时停机坪辅助的登机门分配优化问题.在模型经过精确算法验证的基础上, 为适应登机门问题特性并求解中大规模问题, 首次引进和声搜索算法, 增加复杂约束条件, 对编码解码、初始解产生以及寻优过程进行改进, 提出一种更高效的改进和声搜索算法对模型进行求解.通过使用Lingo软件和Matlab软件对中小规模算例分别进行精确求解和智能算法求解, 对比表明所提出智能算法的有效性、全局搜索能力以及求解效率.再通过对大规模问题的求解, 表明所提出算法在现有条件下能够减小转机旅客的总转机路程, 取得了较好的效果.
关键词登机门    复合类别    AGAP    精确算法    智能算法    和声搜索    
Solving composite airport gate allocation problem with improved harmony search
GONG Ju-hua , ZHANG Ze-qiang , GUAN Chao , LIU Si-lu     
School of Mechanical Engineering, Southwest Jiaotong University, Chengdu 610031, China
Abstract: 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.
Keywords: airport gate    composite category    AGAP    accurate algorithm    intelligent algorithm    harmony search    
0 引言

随着我国近年来国际国内各层次交流不断加深, 航空业也经历了一个蓬勃发展期.随着空港航班数量的不断增加, 如何为日益增多的航空旅客提供高效舒适的地面服务成为一个难题.当前, 空港主要通过航站楼登机门和停机坪接驳车辆两种方式进行旅客的登机和下机程序, 其中通过登机门直接进行班机与航站楼的对接, 无疑是更为安全高效、环保便捷的一种方式, 但是却给机场指挥塔的登机门分配提出了更高的要求.

为了寻求更为高效合理的机场航班-登机门分配方案, 这一类问题被归纳为机场登机门分配问题(the airport gate assignment problem, AGAP).这一问题最早由Steuart[1]进行了相关研究, 他提出一个简单随机模型, 并提出一种根据航班信息估计机场所需的登机门数量的方法.此后, Bihr[2]针对航站楼登机门的乘客转机问题提出了概念模型, 并对7架班机规模的只考虑登机门占用不发生冲突的简单问题进行了求解. Haghani等[3]在Bihr的基础上, 考虑了本地到达旅客的行走距离, 并使用了启发式算法对最大30班机规模的问题进行了求解, 但求解的仍然是只考虑登机门占用不发生冲突的简单问题. Xu等[4]在考虑旅客转机时间最短的基础上, 加入了同一登机门相邻两班机间的最小时间间隔约束.一方面, Yan等[5]在基本问题的基础上, 加入旅客等待时间最短, 将问题扩展为多目标问题, 并对多至145班机规模的实际问题进行了求解.其后, Ding等[6-7]在简单问题的基础上, 首次考虑了由于班机数量过多, 部分班机无法停靠在登机门, 而需要在临时停机坪进行停靠的情况, 并将尽量多的航班停靠在登机门作为一个目标函数进行优化.此后, 不同的文献[8-10]对AGAP的目标函数和求解方法进行了一定的探索, 然而并未就模型的约束条件进行更加贴近实际的修改与论证.梁存利[11]对于有约束的登机门分配问题采用了混合遗传算法进行求解, 并采用了新的编码寻优方式. Hou[12]的文章考虑了班机与登机门的特性匹配. Liu等[13]在机型与登机门匹配的基础上考虑了安全性约束.

在最近的研究中, Liu等[14]在考虑班机型号的情况下对登机门空闲时间均衡性进行了优化, 并采用遗传算法进行求解. Aktel等[15]比较了禁忌搜索算法和模拟退火算法对AGAP的求解效果. Kaliszewski等[16]在AGAP上对比了精确算法和一种新的基于帕累托优化的多目标算法. Sun等[17]考虑了航线类别对登机门选择的约束, 并采用带有帕累托方法对外部档案进行更新的贪婪算法进行了问题的求解, 但并未考虑实际情况下, 登机门在相邻班机停靠当中所需要的最短间隔时间. Deng等[18-19]考虑了机型匹配和临时停机坪的停靠情况, 同时加入登机门在相邻班机停靠当中所需要的最短间隔时间约束, 并采用改进的蚁群算法进行求解, 但未就航线类别对登机门选取的影响进行讨论.

前述文献对机场登机门分配问题开展了卓有成效的研究, 但对于考虑登机门复合类别的航站楼分配问题并未涉及; 而在实际机场运营中这种问题普遍存在.

基于此, 本文在AGAP的现有研究基础上, 针对实际的机场运行规则, 综合考虑航线类别、班机机体型号以及登机门相邻班机最短间隔时间约束, 并在班机数溢出航站楼停靠条件时, 引入临时停机坪进行辅助停靠的基础上, 以转机旅客总转机路程最短作为优化目标, 建立了新的考虑登机门复合类别的航站楼分配问题模型.为求解实际中的大规模问题, 首次将和声搜索(harmony search, HS)算法引入此类问题, 并在其基础上进行改进以适应于此类问题的求解.与其他智能算法相比, 和声搜索算法通过随机的概率指导和声向量及每一维和声分量进行随机变异, 并不断改进[20].

1 问题描述

本文所研究的问题是考虑登机门复合类别的航站楼分配问题, 在模型建立之前, 先对问题进行以下假设.

假设1  每个登机门的国内/国际、到达/出发以及宽体窄体等功能属性固定已知, 班机转场计划里的航班只能分配到与之属性相吻合的登机门.

假设2  每架班机转场的到达和出发两个航班必须分配在同一登机门进行, 其间不能挪移别处.

假设3  所有班机只能按照规定的时间起降, 不考虑延误和提前.

假设4  机场设有临时停机坪, 用以停放没有合适的登机门进行停放的班机, 临时停机坪数量无上限.

假设5  转机旅客从任意一个登机门出发前往另一登机门的路程固定已知, 若转机旅客需从临时停机坪下机或者转机前往临时停机坪, 则以一个惩罚值代替转机行走路程.

根据以上问题和假设条件, 建立了关于此问题的整数规划模型, 模型中的变量符号以及含义见表 1.

表 1 变量符号及含义

本文主要研究考虑登机门复合类别的航站楼分配问题, 在AGAP的现有研究基础上, 针对实际的机场运行规则, 综合考虑航线类别、班机机体型号以及登机门相邻班机最短间隔时间约束, 并在班机数溢出航站楼停靠条件、引入临时停机坪进行辅助停靠的基础上, 以转机旅客总转机路程最短作为优化目标, 研究新的考虑登机门复合类别的航站楼分配问题模型, 即

(1)
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
(12)

其中:式(1)为目标函数, 分为两个部分, 第1部分为

(13)

表示总转机旅客行走路程.式(13)中第1项表示从航站楼第i架班机k口进入机场到第j架班机在l口重新登机的转机旅客总路程, 第2项表示需从临时停机坪下机进入航站楼或者需要从航站楼转机到临时停机坪的旅客的惩罚函数值, 第3项表示旅客从临时停机坪转机到临时停机坪的惩罚函数值.第2部分为

(14)

表示在总转机旅客行走路程最短的情况下, 尽量减少停靠在临时停机坪的班机数量.式(2) ~ (9)为约束条件, 式(2)表示每架班机只停在一个登机门或临时停机坪处; 式(3)和(4)为约束0, 1变量zijk, zijk=1表示第i架班机和第j架班机都停在登机门k, 且ij前面, 否则为0;式(5)对同一个登机门上的班机起降时间进行约束, 使得相邻班机之间留出规定准备时间间隔; 本文在之前的AGAP基础上, 考虑起降航线类别和登机门类别相匹配的问题; 式(6)和(7)对宽体和窄体班机和相应登机门进行匹配; 式(8)对降落航线和登机门类别进行匹配; 式(9)对起飞航线和登机门类别进行匹配; 式(10)和(11)对变量类型进行限制.

2 改进和声搜索算法

遗传算法作为一种经典的智能算法得到了广泛的应用, 与遗传算法的新染色体产生过程中仅考虑一对亲代染色体的方式相比, 和声搜索算法在产生新和声的过程中, 同时考虑和声记忆库中的所有已存在和声; 同时, 和声搜索算法的优化过程不需要设置决策变量的初始值.以上优势便于和声搜索算法增加寻优过程的灵活性, 并有利于寻找更好的解.登机门问题由于存在大量的约束条件, 可行解在邻域解中所占比重不高, 采用和声搜索算法并利用其搜索的灵活性, 有利于对可行解的探索, 提升运算效率.

和声搜索算法是由Geem等[21]提出的一种新型智能优化算法.算法的思想来源于对音乐演奏中不同乐器的和声的模拟.

基本的和声搜索算法通过记忆库取值概率(harmony memory considering rate, HMCR)和微调概率(pitch adjusting rate, PAR)对寻优过程进行调节, 具体过程如下:首先由HMS(harmony memory size)个初始解组成和声记忆库(HM), 即

(15)

变量以HMCR的概率在和声记忆库内进行学习, 否则在全局范围内进行取值; 在学习和声记忆库的过程中, 再以PAR的概率对取值进行微调.得出新的和声之后, 若其目标函数值优于HM内的最差解, 则进行和声记忆库更新, 不断重复以上过程进行迭代直到满足循环终止条件.

和声搜索算法问世以来, 被应用于如0-1背包问题[20]、竞争选址问题[22]以及大规模系统可靠性问题[23], 被应用于登机门分配问题尚属首次.

基础的和声搜索算法在新解产生过程当中没有加入约束条件对过程进行限制, 然而本文所研究的考虑登机门类别的航站楼登机门分配问题具有复杂的约束条件, 随机生成的新解很可能不是一个满足约束的可行解; 另外, 在初始解的产生过程中, 同样存在类似问题.因此, 需对初始解的产生以及和声搜索过程进行相应的设计以满足问题要求.

2.1 初始化和声记忆库 2.1.1 编码方式

本文的一个可行解为一组将n架班机分配到m个登机门的分配方案, 为便于采用HS进行求解, 需要将分配方案进行编码, 且不同方案需要对应不同的编码序列.本文采用一种一维数列作为编码方式, 其位数等同于班机编号, 第i位中的数字代表这一编号的班机所停靠的登机门序号, 若班机停靠于临时停机坪, 则取0作为相应登机门编号.

2.1.2 产生初始解

初始解的产生采用以下方式进行:首先将所有班机按降落时间从早到晚进行排序; 按登机门编号生成一个起飞时间记录列表; 从前到后依次为班机安排合适类型的登机门, 并且同时满足与前一架班机保留足够的时间间隔, 若有多个合适的登机门, 则随机选取一个, 并更新起飞时间记录列表; 若没有合适的登机门可供选择, 则安排班机进入临时停机坪停靠; 重复以上操作, 直到最后一架班机分配完成, 并产生相应的一维和声.

2.1.3 产生初始和声记忆库

通过以上方式, 产生一个初始可行解的集合, 并将每个和声进行初步的邻域搜索优化, 优化方式为分组进行和声搜索, 规定一个较小的不变迭代次数Inigen, 当达到次数是输出优化后的HM, 生成新的优化后的初始可行解集合, 并计算每个优化后的初始解的目标函数值(总转机旅客行走路程), 通过比较, 选取HMS个较优的初始解组成初始和声记忆库.

2.2 新和声产生方式

和声搜索过程同样受到登机门类型和已停靠班机的约束, 需要避免登机门的错配和保证足够的相邻班机间隔时间; 除此之外, 更换一架班机停靠的登机门同样需要考虑对后续班机起降造成的影响.为解决上述问题, 在引用文献[11]的函数基础上进行相应修改来辅助邻域搜索过程, 首先需定义函数

(16)

根据上文排列好的班机序号, 构造航班时间关系矩阵R=(rij), 其中aidi, 若aidj, 则rij=1, 否则为0.

设有可行解T, 登机门l, T的第i位(待修改的和声位)左边基因值为l对应的基因位置的集合为L, 它的右边基因值为l对应的基因位置的集合为R.

Left函数:若集合L不是空集, 则Left(T, i, l)=rij; 若集合L为空集, 则规定Left(T, i, l)=1.

Right函数:若集合R不是空集, 则Right(T, i, l)=rij; 若集合R为空集, 则规定Right(T, i, l)=1.

在进行和声邻域搜索的过程中, 对搜索范围内的解首先进行一次筛选, 将待搜索的原和声作为可行解T, 假设待改变的和声为可行解的第i位, 将和声搜索范围内的登机门分别作为l代入Left函数和Right函数, 若计算出的Left(T, i, l)×Right(T, i, l)=1, 则表示此l替换之后的新解仍为可行解; 否则, 表示此新解为不可行解.

2.3 改进和声搜索算法

通过以上工作, 结合登机门问题的复杂约束情况, 对编码解码、初始解产生以及寻优过程进行改进之后, 再对基本的和声搜索算法进行相应修改, 编写了如图 1所示的改进和声搜索算法.

图 1 改进和声搜索算法求解考虑登机门类别的航站楼登机门分配问题流程

算法步骤如下.

Step 1:设置算法参数.和声记忆库容量HMS, 停机坪转机距离惩罚值D, 最大不变迭代次数Maxgen, 和声初始化筛选迭代次数Inigen.

step 2:根据上文方法构造初始和声记忆库.

step 3:初始化迭代计数器iter=1.

step 4:计算初始HM内和声目标函数值, 选取最优初始和声作为变异基准, 若最优初始和声不止一个, 则随机选取一个作为基准.

step 5:初始化和声更新位计数器postion=1;

step 6:进入和声更新, 生成随机数j, 若j > HMCR, 则执行step 7;若j≤ HMCR, 则执行step 8.

step 7:对于postion位, 从所有可行域内随机选取新和声位替换旧和声位, 而后令postion=postion+1, 若postion≤ n, 则返回step 6, 否则执行step 10.

step 8:对于postion位, 从HM内相同位随机选取可行域内的新和声位替换旧和声位, 而后令postion=postion+1.

step 9:进入和声微调, 生成随机数k, 若k> PAR, 则执行step 10;若k≤ PAR, postion≤ n, 则返回step 6, 否则执行step 10.

step 10:计算新和声目标函数值, 与和声库HM内的各和声目标值进行比较, 若优于现有和声库的最差解, 则替换最差解, 返回setp 3;否则, 进入step 11.

step 11:令iter=iter+1, 若iter < Maxgen, 则返回step 4, 否则进入step 12.

step 12:对和声记忆库中的解进行优化, 尽量将和声中的0用登机门编号数字替换, 减少停靠在临时停机坪的班机数量, 并重新计算目标函数值, 终止程序, 输出和声记忆库.

3 算例验证及分析

本文所用适用于考虑登机门复合类别的航站楼分配问题的和声搜索算法由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公司新推出的一款适用于线性和非线性领域的通用优化求解器, 它属于运筹学研究所常用到的软件工具之一.

3.1 模型及算法验证

为验证本文所提出考虑登机门复合类别的航站楼分配问题模型, 以及说明所用改进和声搜索算法的求解效果, 分别选取了25班机6登机门和65班机14登机门两组小规模算例, 并同时采用Lingo编写所提出模型和Matlab编写改进和声搜索算法进行求解.

对于25规模算例, 由Lingo所求得的精确解的目标值为101, 所有班机于航站楼停靠, 没有班机进入临时停机坪, 所得的登机门分配情况如表 2所示.

表 2 25规模登机门分配精确解

相同问题采用改进和声搜索算法求解, 算法参数为:登机口最小准备时间(即相邻班机停靠同一登机口的最小时间间隔)为I=45 min, 和声记忆库容量HMS=10, 停机坪转机距离惩罚值AP =登机门个数×相邻登记门间距×3;最大不变迭代次数Maxgen=100, 和声初始化筛选迭代次数Inigen=1.除了得到以上精确解以外, 还得到如表 3所示4个相同目标值的解, 并且同样所有班机于航站楼停靠, 没有班机进入临时停机坪.

表 3 改进和声搜索算法求25规模登机门分配问题的解

对于相同的小规模问题, 改进和声搜索算法相比Lingo的精确算法求到了更多的相同目标值下的精确解, 具有更好的全局寻优性能.

对于65规模算例, 首先由Lingo对算例进行求解, 由于算例规模较大, 在限定的1 800 s时间之内, 求得了以下目标值为33的可行解, 并有10架班机停靠于临时停机坪.对于相同问题, 采用的算法参数为:登机口最小准备时间为I=45 min, 和声记忆库容量HMS=10, 停机坪转机距离惩罚值AP=登机门个数×相邻登记门间距×3, 最大不变迭代次数Maxgen=1 000, 和声初始化筛选迭代次数Inigen=10.采用改进和声搜索算法求解, 耗时115.937 s, 得到如表 4所示目标值为32的较优解, 且仅有3架班机停靠于临时停机坪.

表 4 Lingo和改进和声搜索算法求得的65规模登机门分配可行解

以上结果表明, 改进和声搜索算法除具有较好的全局寻优性能以外, 求得较优解的时间相比精确算法大幅缩短, 具有更高的求解效率.

3.2 大规模算例求解

本文所用算例取材自上海浦东国际机场, 选取机场内起降的所有与某一天(从0时至24时)有关的航班作为研究对象.所研究的班机共303架, 即包含303次降落任务和303次起飞任务, 包括3个部分:第1部分为在所选取的一天(从0时至24时)内起飞的已经在前一天较晚时候降落的班机; 第2部分为在所选取的一天(从0时至24时)内降落和起飞的班机; 最后还包括在所选取的一天(从0时至24时)内降落但是没有起飞的班机.班机信息包括航班降落时刻、航班起飞时刻、降落航线类别、起飞航线类别以及班机机体型号.

另外, 本文所研究的算例共包含69个种类不一的登机门, 对于适用航线类别共分3类, 如表 5所示.

表 5 登机门编号与适用航线类别表

值得说明的是, 对于通用登机门, 可以停靠所有类别的班机, 包括:起降均为国内航线的班机, 起降均为国际航线的班机, 降落航线为国内航线、起飞航线为国际航线的班机以及降落航线为国际航线、起飞航线为国内航线的班机.前两类班机还可以分别在各自专用的登机门类别进行停靠, 而后两类班机只能停靠于通用登机门.

对于班机机体型号, 分为宽体和窄体两大类, 分别只能停靠在各自适合的登机门.

关于转机旅客的行走距离, 假设所有的登机门都分布在直线型航站楼两侧, 并且登机门是均匀排列, 即旅客沿航站楼过道方向上每经过一个登机门行走的距离相等, 且为一个单位距离, 除此以外, 当乘客从一个登机门到达另一个登机门, 无论这两个登机门是处于航站楼的同侧还是两侧, 都要先来到航站楼内部的主通道, 所以忽略乘客穿过航站楼过道的距离, 认为乘客的行走距离只与沿航站楼主过道方向的行走距离有关.

算法的参数设置如下:登机口最小准备时间(即相邻班机停靠同一登机口的最小时间间隔)为I=45 min; 和声记忆库容量HMS=10;停机坪转机距离惩罚值AP =登机门个数×相邻登记门间距×3;最大不变迭代次数Maxgen=5 000;和声初始化筛选迭代次数Inigen=50.对于停机坪转机距离惩罚值AP的设置, 主要考虑到尽量减少转机乘客从临时停机坪上下机的情况出现, 以尽量减少因此可能带来的转机失败的风险, 并且更多地保证转机乘客的舒适度.

在以上条件下, 通过Matlab程序对问题进行求解.通过分别使用基本和声搜索算法和本文改进和声搜索算法对大规模问题求解, 分别得到50个目标函数值.基本和声搜索算法所得50个目标值的均值为68 519.02, 标准差为1 468.78;改进和声搜索算法所得50个目标值的均值为66 007.96, 标准差为1 277.38.可知改进和声搜索算法相比基本和声搜索算法在求解的均值和标准差上均有优势, 表明本文对算法针对登机门问题的改进具有明显的效果, 对算法收敛性和稳定性均有提升.

在通过改进和声搜索算法得到的解中, 最优目标函数值为63 930. 图 2列出了求解得到的问题的解的具体情况, 图 2中纵坐标为登机门编号, 横坐标为时间, 以分钟表示, 一个横条代表一架班机的停靠时间段和停靠登机门的情况.图中共有111架班机停靠于临时停机坪, 192架班机停靠于航站楼, 图 2中0分表示所研究的上一日的0时0分, 即实际研究的时间段为1 440 min到2 880 min这段时间(即3天中的中间一天).由图 2可以知道, 机场每一个工作日都有大量班机前一天停靠在登机门或者当天并未飞离机场, 所以研究机场一天之内的登机门分配问题, 将这一天前一天、当天以及后天的所有与当天有联系的航班考虑在内是十分必要的, 且对分配结果有较大影响.从图 2中还可以看到, 机场大量的航班都是经停航班, 且停靠时间较短, 因此在满足最小登机口准备时间的约束条件下, 仍然具有很大的分配空间, 该问题具有较大的研究价值.

图 2 登机门占用情况甘特图

图 3为每一个登机门在一天当中的停靠班机架次.如前文所述, 登机门G1 ~ G22为国际航班登机门, G23 ~ G30为通用登机门, G31 ~ G69为国内航班登机门.由图 3可以看到, 停靠班机最多的登机门集中在G29 ~ G36, 处于通用登机门和国内航线登机门的交界处, 此处集中了大量的具有转机旅客的班机, 有效缩短了转机旅客的转机行走距离; 另外, G57以前的国际航班登机门和国内航班登机门基本都分别停靠了1 ~ 5架次的班机, 得到了充分的利用, 并且国内航班登机门停靠的班机架次还具有随着远离密集停靠区, 架次向下减少的趋势, 表明对转机旅客的行走优化是有效的.

图 3 登机门停靠班机架次

图 4为登机门使用率柱状图.登机门使用率指的是从登机门当天的第一架班机停靠, 到当天最后一架班机离开的时间之内, 有班机停靠在登机门上的时间的比例, 若当日0时已有班机停靠于登机门, 则从0时开始计算, 若当日24时还有班机并未起飞, 则计算到24时为止.

图 4 登机门使用率

图 4中, 黑色部分为班机占用登机门的时间百分比, 灰色部分为登机门准备时间占用百分比.因一天当中完全没有使用过的登机门随时可供其他班机使用, 影响其使用效率的原因在于当日航班的属性情况, 造成登机门与班机不能匹配, 所以仅考虑使用到的54个登机门.由图 4可以看到, 不考虑登机门准备时间, 超过77.7 %的登机门利用率大于40 %, 并且只有5个登机门的利用率小于30 %, 它们分别是G24、G26、G27、G28和G43, 占总数的9.26 %; 若考虑到登机门准备时间的设置, 登机门使用率低于40 %的登机门只有6个, 分别为G21、G24、G26、G27、G28和G43, 占比11.11 %, 使用率高于60 %的登机门共36个, 占比66.67 %.由上述结果可知, 所得分配方案中, 登机门的利用情况较好, 利用率较高.

通过对实际问题的分析与求解, 改进的和声搜索算法将303架班机合理分配进入69个匹配的航站楼登机门以及临时停机坪, 将转机旅客的总转机行走路程进行优化, 增加了旅客的转机效率和舒适程度.与此同时, 通过对问题的分析结果可以看到, 航站楼登机门的配置尚有优化的空间, 可以通过航班的变动情况和执飞班机的机型, 对登机门的类别进行相应的调整, 以最大化利用现有的登机门资源, 便于更多的班机在登机门进行停靠.

4 结论

本文在现有AGAP问题的研究基础上, 针对实际的机场运行规则, 综合考虑航线类别、班机机体型号以及登机门相邻班机最短间隔时间约束, 并在班机数溢出航站楼停靠条件时, 引入临时停机坪进行辅助停靠的基础上, 以转机旅客总转机路程最短作为优化目标, 建立了新的考虑登机门复合类别的航站楼分配问题模型.

通过精确算法和所提出的改进和声搜索算法对小规模问题进行求解, 验证了模型的正确性、所提出算法的有效性、全局搜索能力以及求解效率.通过进一步对大规模实际问题进行求解, 对实际规模的登机门分配问题进行了优化, 减小了转机旅客的总转机路程.此外, 所得结论对航站楼登机门的布置方式具有一定的指导意义.

参考文献
[1]
Steuart G N. Gate position requirements at metropolitan airports[J]. Transportation Science, 1974, 8(2): 169-189.
[2]
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.
[3]
Haghani A, Chen M C. Optimizing gate assignment at airport terminals[J]. Transportation Research A: Policy and Practice, 1998, 32(6): 437-454.
[4]
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.
[5]
Yan S Y, Huo C M. Optimization of multiple objective gate assignments[J]. Transportation Research A: Policy and Practice, 2001, 35(5): 413-432.
[6]
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.
[7]
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.
[8]
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.
[9]
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.
[10]
Drexl A, Nikulin Y. Multicriteria airport gate assignment and pareto simulated annealing[J]. ⅡE Transactions, 2008, 40(4): 385-397.
[11]
梁存利. 有约束的登机门分配问题混合遗传算法[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.)
[12]
Hou Z X. Measuring technology and mechatronics automation in electrical engineering[M]. New York: Springer, 2012: 347-355.
[13]
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.
[14]
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.
[15]
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.
[16]
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.
[17]
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.
[18]
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.
[19]
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.
[20]
欧阳海滨, 高立群, 孔祥勇, 等. 一种求解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.)
[21]
Geem Z W, Kim J H, Loganathan G V. A new heuristic optimization algorithm: Harmony search[J]. Simulation, 2001, 76(2): 60-68.
[22]
于宏涛, 高立群, 吕勇军. 基于混合和声搜索算法求解竞争选址问题[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.)
[23]
欧阳海滨, 高立群, 孔祥勇. 求解大规模系统可靠性问题的修正和声搜索算法[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.)