基于贪婪-遗传算法的机场登机口分配策略.pdf

第 卷第 期 年 月系统工程与电子技术 文章编号：（）网址：收稿日期：；修回日期：；网络优先出版日期：。网络优先出版地址：基金项目：江苏省科技项目（）资助课题通讯作者引用格式：胡杰，鲍帆，石潇竹基于贪婪 遗传算法的机场登机口分配策略系统工程与电子技术，（）：犚犲 犳 犲 狉 犲 狀 犮 犲犳 狅 狉犿犪 狋：，（）：基于贪婪 遗传算法的机场登机口分配策略胡杰，鲍帆，石潇竹，（中国电子科技集团公司第二十八研究所，江苏 南京 ；空中交通管理系统全国重点实验室，江苏 南京 ）摘要：针对枢纽机场新建卫星厅导致中转旅客航班衔接时间延长、换乘失败概率增大的问题，开展了机场登机口多目标优化分配问题研究。首先，在顾及航班类型、机体类型和转场时间间隔等约束条件基础上，建立了航班 登机口多目标优化分配模型。然后，基于贪婪算法思想，按照航班“先到先分配”的原则指派登机口，以生成初始种群，并利用遗传算法实现机场登机口分配模型求解。最后，利用实例数据进行了验证，该方法能够成功为 个航班分配登机口，占航班总数 ，中转旅客最短流程时间为 的比率为 ，其所占比率最大，实验结果验证了模型和算法的有效性。关键词：枢纽机场；多目标优化；贪婪算法；遗传算法中图分类号：文献标志码：犇犗犐：犃 犻 狉 狆 狅 狉 狋犵 犪 狋 犲犪 狊 狊 犻 犵 狀犿犲 狀 狋狊 狋 狉 犪 狋 犲 犵 狔犫 犪 狊 犲 犱狅 狀犵 狉 犲 犲 犱 狔 犵 犲 狀 犲 狋 犻 犮犪 犾 犵 狅 狉 犻 狋 犺犿 ，（犜犺 犲 狋 犺犚犲 狊 犲 犪 狉 犮 犺犐 狀 狊 狋 犻 狋 狌 狋 犲，犆犺 犻 狀 犪犈 犾 犲 犮 狋 狉 狅 狀 犻 犮 狊犜犲 犮 犺 狀 狅 犾 狅 犵狔犌狉 狅 狌狆犆狅 狉 狆 狅 狉 犪 狋 犻 狅 狀，犖犪 狀 犼 犻 狀犵 ，犆犺 犻 狀 犪；犛 狋 犪 狋 犲犓犲 狔犔犪 犫 狅 狉 犪 狋 狅 狉 狔狅 犳犃 犻 狉犜狉 犪犳犳 犻 犮犕犪 狀 犪犵 犲犿犲 狀 狋犛狔 狊 狋 犲犿，犖犪 狀 犼 犻 狀犵 ，犆犺 犻 狀 犪）犃犫 狊 狋 狉 犪 犮 狋：，“，”，犓犲 狔狑狅 狉 犱 狊：；引言随着航空运输业的快速发展，航班量也随之日益增长，使得部分机场登机口出现严重不足的情形，登机口资源冲突频发，影响机场运营效率与安全，同时也降低了旅客出行满意度。为解决该问题，大型枢纽机场通过在现有航站楼的基础上新增卫星厅，以缓解机场登机口不足的压力，提高过站飞机靠桥率。通常，航站楼与卫星厅有一段间隔距离，这对过境旅客的航班衔接产生了一定的负面影响，增加了中转旅客换乘失败的机率。因此，如何解决具有卫星厅的机场登机口分配问题，最大限度地优化登机口配置，已成为当前大型机场运营亟待解决的问题之一。系统工程与电子技术第 卷机场航班 登机口分配属于运筹学多目标优化问题，其求解目标函数由机场决策者根据运营情况决定。国内外学者从乘客和机场运营两个层面建立并求解了诸多登机口分配优化模型。首先，从乘客角度考虑，等首次提出了航班登机口分配优化模型，并以最小化旅客航站楼内行走距离为目标函数实现登机口资源最优化分配。随后，等建立了机场登机口分配整数规划模型，该模型以最小化旅客航站楼内的行走总距离为优化目标，并基于分支定界算法求解优化模型，但其未考虑中转旅客航班衔接问题。等在文献研究基础上，将中转旅客的步行距离作为优化目标建立了机场登机口分配模型，采用线性松弛法和启发式算法求解该模型，结果表明，启发式算法的性能接近最优。冯程等基于传统滑行路径理念，建立了降低旅客进出机场空侧时间的登机口分配模型，采用启发式算法求解模型，取得了较好的分配效果。等从乘客服务质量角度出发，建立了以缩短乘客步行总距离和均衡各航空公司的旅客平均步行距离为目标的登机口指派模型，采用 软件进行仿真验证。上述研究表明，合理指派机场登机口位置可以有效降低乘客步行距离，提高机场服务满意度。然后，从机场运行角度出发，等以最小化登机口空档间隔时间方差为优化目标建立了具有运行安全约束的鲁棒登机口分配模型，采用遗传算法求解该问题。等通过分析主要机场航班延时数据，建立了以最小化同一登机口的前后航班冲突率为目标的登机口分配模型，采用启发式贪婪算法求解模型。等 在顾忌机场运营成本基础上，提出了鲁棒登机口分配模型，设计了一种自适应大规模领域搜索算法求解该模型。王岩华等 在考虑航班属性、机位尺寸等约束条件下，以航班靠桥率和廊桥周转率为优化目标建立了繁忙机场登机口分配模型，并利用混合集合规划方法求解算法模型，结果表明混合集合规划方法有效提升了航班靠桥率。等 针对非正常抵达航班导致的登机口分配不确定性问题，提出了一种基于航班到达时间分析的鲁棒登机口分配方案，并利用遗传算法实现模型求解，从而减小了航班计划变化对初始分配结果的影响。刘君强 等对多航站楼机场登机口分配问题进行了研究，建立了基于协同决策并考虑航司时隙交换公平性的登机口实时分配模型，采用混合集合规划进行模型求解。随着机场登机口分配模型研究的不断深入，基于多目标优化的登机口分配模型成为研究热点，多目标情况下的登机口分配模型求解较为困难 。等 建立了机场登机口分配多目标线性规划模型，考虑了乘客航站楼内行走总距离和航班延误成本两个优化目标。等 建立了机场登机口多目标优化模型，该模型综合考虑了旅客行走距离、登机口空挡间隔时间方差、分配在固定登机口航班数量和宽登机口使用率个优化目标，并采用线性加权法实现多目标优化向单目标优化的转变，然后采用粒子群算法求解该模型。等 在考虑机型、相邻登机口冲突等约束条件基础上，以最小化航班延迟数、登机口变更比例和中转失败乘客数为优化目标，建立了基于多商品流网络模型的登机口重分配模型，利用两种启发式算法完成真实数据验证。由上述国内外研究现状可知，单纯的机场登机口分配问题已经得到了较好的解决，且有成熟的产品满足航司和地勤服务公司的应用需求，但是在实现登机口优化分配的同时考虑中转旅客行走时间和距离的研究有限。针对大型枢纽机场新建卫星厅，本文在考虑航班类型、机体类型和转场时间间隔等约束条件基础上，建立了以成功分配航班数至固定登机口最多、中转旅客的总体最短流程时间最小以及固定登机口使用数量最少为优化目标的机场登机口分配模型，利用贪婪算法计算生成初始种群，并利用遗传算法实现模型求解，最后用一组大型枢纽机场的实际运营数据对本文所提出的登机口优化分配模型和算法进行验证。问题描述由于城市建设规模的快速发展，该市机场现有航站楼的旅客流量已经达到饱和状态，为了应对未来的发展，在航站楼附近新建了卫星厅，航站楼和卫星厅之间有捷运线相通，其布局设计如图所示。新建卫星厅后原有航站楼的运营保障压力得到了极大缓解，同时航班靠桥率也相应得到了提升，但是新建卫星厅对于部分中转旅客的航班衔接产生了较大的负面影响。将中转旅客换乘因素作为登机口分配优化目标之一，实现机场登机口多目标优化是目前大型枢纽机场亟待解决的问题之一。本文研究以中转旅客的总体最短流程时间最小、分配至固定登机口的航班数量最多以及登机口使用数量最少为目标的航班登机口分配问题，在有效提高机场登机口资源使用率的同时，提升中转旅客的出行满意度。图卫星厅相对于航站楼示意图 第 期胡杰等：基于贪婪 遗传算法的机场登机口分配策略 航站楼具备完整的国际机场航站楼功能，包括出发、到达、出入境和候机，而卫星厅仅可以提供出发、到达和候机功能，无出入境功能。对于中转旅客来说，换乘航班时需要有一定的时间办理相关手续，定义该时间为中转旅客最短流程时间。对于任一中转旅客，其最短流程时间由到达航班类型、登机口区域以及出发航班类型决定，共有 种不同组合场景，表给出了 种不同组合场景下的最短流程时间。表最短流程时间犜 犪 犫 犾 犲犕犻 狀 犻 犿狌犿狆 狉 狅 犮 犲 狊 狊狋 犻 犿犲 出行状态国内出发国际出发国内到达 国际到达 航班 登机口分配模型 模型假设为构建机场登机口多目标优化模型，航班 登机口的分配需要考虑如下规则。（）机场临时停机位数量满足该时段内所有未分配到固定登机口的航班停靠，且对停靠的飞机无约束。（）由同一架飞机执行的到达和出发两个航班只能分配在同一停机位，飞机停靠期间不可挪移至其他位置。（）飞机转场信息、旅客信息和登机口信息等均已知，且不考虑当天退票情况。（）机场所有登机口的功能属性不能改变，且转场航班只能停靠在与之属性相匹配的登机口。（）分配在同一登机口的相邻两个航班之间的空档间隔时间不小于 。模型建立 约束条件假设机场在某时间段内需要安排的转场航班数为犕，机场固定登机口数为犖，在该段时间内有效的中转旅客组数为犘，令犻、犼、犾分别表示第犻个转场航班、第犼个登机口和第犾组旅客（犻，犕；犼，犖；犾，犘）。令狓犻，犼为航班 登机口分配问题的决策变量，定义该变量取值为狓犻，犼，航班犻分配在登机口犼，烅烄烆其他（）根据机场实际运营情况，并考虑模型假设，建立如下的决策变量约束条件。（）唯一性约束为犖犼狓犻，犼（）式（）保证一架飞机只能安排在一个固定登机口，且中途不会被挪移。（）到达航班类型约束为（犜，犻犜，犼）狓犻，犼（）式中：犜，犻表示转场航班犻的到达航班类型；犜，犼表示登机口犼接受的到达航班类型。犜，犻表示转场航班犻来自国外，犜，犻表示转场航班犻来自国内；犜，犼表示登机口犼接受来自国外的航班，犜，犼表示登机口犼接受来自国内的航班，犜，犼表示登机口犼能接受来自国外和国内的航班。式（）保证航班的到达类型与登机口可接受的类型相匹配。（）出发航班类型约束为（犜，犻犜，犼）狓犻，犼（）式中：犜，犻表示转场航班犻的出发航班类型；犜，犼表示登机口犼接受的出发航班类型。犜，犻表示转场航班犻目的地为国外，犜，犻表示转场航班犻目的地为国内；犜，犼表示登机口犼接受发往国外的航班，犜，犼表示登机口犼接受发往国内的航班，犜，犼表示登机口犼能接受发往国外和国内的航班。式（）保证航班的出发类型与登机口可接受的类型相匹配。（）机体类型约束为（犜，犻犜，犼）狓犻，犼（）式中：犜，犻表示转场航班犻的机体类型；犜，犼表示登机口犼接受的机体类型。犜，犻表示转场航班犻为宽体机，犜，犻表示转场航班犻为窄体机；犜，犼表示登机口犼可接受宽体机，犜，犼表示登机口犼可接受窄体机。式（）保证航班的机体类型与登机口可接受的类型相匹配。（）间隔时间约束狋犽珓狋犻，犻犽狓犻，犼狓犽，犼狋犽狋烅烄烆犻（）式中：犽，犕；狋犽表示转场航班犽的到达时间；珓狋犻表示转场航班犻的出发时间；狓犽，犼表示航班犽分配在登机口犼的决策变量；狋犻表示转场航班犻的到达时间。式（）保证同一登机口的连续两个航班之间的空档间隔时间不小于 。目标函数根据机场运营情况，航班 登机口分配问题在满足上述约束条件下，需要尽可能地优化如下个目标，以高效利用机场资源，同时提高换乘旅客的舒适度。由上述定义可知，机场固定登机口数为犖，同时根据模型假设可知，临时停机位对停靠的飞机无约束，因此可以定义所有的临时停机位为第犖个登机口，应用本文所定义的符号，可建立如下目标函数。优化目标为 犑犕犻狓犻，犖（）式中：狓犻，犖表示航班犻分配在临时停机位的决策变量；犑表示被分配到临时停机位的飞机数量，即没有分配到固定登机口的飞机数量，该优化目标为尽可能多地将航班安排至固定登机口。优化目标为 犑犘犾狆犾犾（）系统工程与电子技术第 卷式中；犑为中转旅客的总体最短流程时间；狆犾表示第犾组中转旅客随行人数；犾表示第犾组中转旅客的最短流程时间，其数值如表所示，该优化目标为最小化中转旅客的总体最短流程时间。优化目标为 犑犖犼犕犻狓犻，犼犕（）式中：犑为被使用的固定登机口数量；犕为极大的正数；表示向上取整，仅有和两种情形，表示该登机口未被使用，表示该登机口被使用，该优化目标为最小化被使用登机口的数量。根据以上个优化目标的定义可知，这个目标之间是互相拮抗的，无法同时满足。目标函数的优先级为：尽可能多地将航班安排至固定登机口（犑）最小化中转旅客的总体最短流程时间（犑）最小化被使用登机口的数量（犑），即首先满足优化目标，其次满足优化目标，最后满足优化目标。实现多目标优化问题求解的第一步是将多目标优化问题转化为单目标优化问题，线性加权是多目标优化广泛使用的一种模型，通过给不同的目标函数制定相应的权重，将多目标优化问题转化为单目标优化问题 。因此，多目标优化模型可以写成如下形式：犑狑犑狑犑狑犑（）式中：犑表示总体优化目标综合效用函数；狑、狑和狑分别表示优化目标的权重值，且狑狑狑，其权重具体分配一般通过多次实验确定。综上分析，可以建立如下的多目标多约束机场登机口优化分配模型：犑狑犕犻狓犻，犖狑犘犾狆犾犾狑犖犼犕犻狓犻，犼犕 犖犼狓犻，犼狘（犜，犻犜，犼）狓犻，犼狘狘（犜，犻犜，犼）狓犻，犼狘（犜，犻犜，犼）狓犻，犼狋犽珓狋犻，犻犽狓犻，犼狓犽，犼狋犽狋烅烄烆烅烄烆犻（）算法设计将航班抽象为物体，将航班在机场转场的时间抽象为物体体积，则该问题就转化为典型的背包问题，即如何使用最少的背包装入最大的价值。求解背包问题有多种算法，比如遗传算法、贪婪算法、粒子群算法和禁忌搜索算法等 。贪婪算法以自顶而下的方式进行搜索，在问题求解的每一个阶段都做出一个在一定标准下看似最优的决策，能快速求得可行解，但通常不是全局最优解，是求解最优化问题最简便的方法之一。遗传算法对登机口分配问题没有太多的数学要求，搜索过程中不需要问题的内在性质，其在牺牲一定时间代价的情形下可以获得全局最优解。传统遗传算法的初始种群设置具有较强的随机性，其个体适应度不高，降低了算法收敛速度。为此，本文借鉴贪婪算法局部寻优的特点，设计贪婪策略，利用贪婪算法得到的航班登机口分配方案赋值遗传算法初始种群，并利用遗传算法求解最优航班 登机口分配方案。初始种群获取贪婪算法的核心是选择一种适合的贪婪策略 ，在航班 登机口优化目标中，最大化航班靠桥率，即将航班尽可能多地安排至廊桥登机口，符合贪婪算法的基本特性。因此，基于贪婪算法求解初始种群在一定程度上可以提高遗传算法求解效率，本文选择如下贪婪策略。贪婪策略：转场航班依次到达机场，按照“先到先分配”的原则对航班计划进行排序。对于每个到达航班，优先指派航班至空闲时间间隔最小的登机口，具体实现步骤如下。步骤初始化参数。将航班按照到达时间进行排序，先到达的航班优先分配登机口。设定登机口的空闲时间为上一架飞机的离港时间。步骤求解局部最优解。对于每个到达航班，寻找其与登机口空闲时间间隔最小的登机口作为局部最优解，若转场航班犻占用登机口犼，则狓犻，犼，否则狓犻，犼。步骤若某一转场航班经过多次尝试仍然无法分配到适合的登机口，则将该航班安排至临时停机位。步骤遍历待分配航班，为所有计划内的航班分配适合的登机口。用于生成初始种群的贪婪算法流程图如图所示。图贪婪算法流程图 第 期胡杰等：基于贪婪 遗传算法的机场登机口分配策略 遗传算法根据上述分析可知，航班 登机口分配问题属于多目标动态规划问题，且含有多个约束条件，是一个典型的（）问题。遗传算法是一种典型的智能优化算法，通过模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程实现模型求解，被广泛应用于求解 问题 。针对多目标、多约束的航班 登机口分配优化问题，本文利用带精英策略的遗传算法求解该问题。遗传算法从一组随机生成的初始解，也称为“种群”开始搜索，由上文分析可知，本文利用贪婪算法得到的航班 登机口分配结果赋值遗传算法初始种群。染色体是一串符号，这些染色体在后续迭代中进化就是遗传，其后代根据前一代染色体的“交叉”和“变异”运算形成，并且在每一代进化中通过计算个体的适应度来评价染色体的“好坏”，算法经过若干次迭代后，将收敛于最优染色体，即为问题的解。本文采用的遗传算法中一条染色体表示一个航班 登机口分配方案，每条染色体中包含若干个基因（基因个数由需要转场的航班对数量决定），第犻个基因表示第犻个转场航班对，基因上的数字表示对应航班停靠的登机口序号。在该染色体中，每个基因能选择的登机口序号除简易临时机位外，必须满足对应飞机和登机口在机型（宽窄）、航班到达或出发类型（国内国外）等约束条件上的完全匹配，染色体示意图如图所示，本文使用带精英策略的遗传算法进行求解，算法流程如图所示，算法实现过程如算法所示。图染色体示意图 图遗传算法流程图 算法遗传算法（）（）狋；（）犘（狋）；（）犘（狋）；（）（）（）狋狋；（）犘（狋）；（）犘（狋）；（）（）算法中犘（狋）表示遗传算法更新第狋代种群，结合图和算法，带精英策略的遗传算法具体实施步骤可表述如下。步骤初始化遗传算法参数。设定种群大小为，染色体长度即需要转场的航班对数量为犕，最大遗传代数为犌。步骤根据飞机转场信息、旅客信息以及机场登机口信息，利用贪婪算法生成遗传算法初始种群。步骤根据第节建立的登机口分配模型目标函数计算个体适应度，并对每代群体按照适应度值降序排序，取适应度值最大的个体染色体作为精英保留，适应度函数表达式为 烄烆 犉 烄烆狑犕犻狓犻，犖狑犘犾狆犾犾狑犖犼犕犻狓犻，犼犕烌烎烌烎（）式中：狑取值为；狑取值为；狑取值为；表示登机口优化分配适应度函数变量；犉 为极大的正数使得 恒大于零，并根据个体适应度值分配计算个体被遗传到下一代群体的概率及其累积概率：狆犻 犻犳犻 犻犖犘犼 犼犳犼 犼（）狇犻 犻犻 犻犼 犼狆犼 犼（）式中：犻 犻，犳犻 犻表示第犻 犻个个体的适应度值；狆犻 犻和狇犻 犻分别表示第犻 犻个个体被遗传到下一代群体的概率和累积概率。步骤对染色体进行选择操作，首先采用轮盘赌算法选择染色体，若所有的染色体具有相等的适应度值，则通过服从均匀分布的随机数对染色体进行随机性选择。系统工程与电子技术第 卷步骤对染色体进行交叉操作，生成两个随机正数狋和狋，将其作为需要截取的染色体片段，并采用双点杂交策略进行染色体交叉操作，染色体交叉操作过程示意图如图所示。图染色体交叉操作示意图 为了提高遗传算法收敛速度，在遗传进化后期引入自适应交叉算子，本文在 等 提出的自适应遗传算法基础上对遗传算子计算公式进行了改进，使得交叉算子恒大于零，减小遗传进化走向局部最优解的概率，本文提出的改进自适应交叉算子计算公式为犘犮犽（犽犽）（犳犳 ）犳 犳 ，犳犳 犽，犳犳 烅烄烆（）式中：犘犮表示交叉算子；犳 表示种群中个体最大适应度值；犳 表示每一代种群平均适应度值；犽犽，本文通过多次调整参数进行实验，设置犽为，犽为。而在遗传进化初期，为提升种群的多样性，依然采用较大的固定交叉概率进行算法迭代，因此，设置交叉算子犘犮为常数。步骤对染色体进行变异操作，生成随机正数作为需要变异染色体的基因位置，并将该位置登机口变异为犖间随机正整数。和自适应交叉算子设置类似，本文提出的改进自适应变异算子计算公式为犘犿犽（犽犽）（犳犳 ）犳 犳 ，犳犳 犽，犳犳 烅烄烆（）式中：犘犿表示变异算子；犽犽，本文通过多次调整参数进行实验，设置犽为，犽为 。在遗传进化初期，采用较大的固定变异概率进行算法迭代，设置变异算子犘犿为常数。步骤计算经选择、交叉和变异后的种群个体适应度，按照适应度值进行降序排序，淘汰适应度值最小的个体，并使用上一代精英补充，更新精英个体。遗传迭代后期为提高个体间的竞争，本文通过扩大个体适应度值的差异程度提高算法最优解搜索能力，因此进化后期调整适应度函数为 烄烆 犉 烄烆狑犕犻狓犻，犖狑犘犾狆犾犾狑犖犼犕犻狓犻，犼犕烌烎烌烎狀（）式中：狀为大于零的正整数，本文根据实际数据验证取值为。步骤重复执行步骤至步骤共计犌次，获得最优航班 登机口分配结果，停止演化，取演化最后适应度值最高的个体作为最后遗传算法求得的全局最优解。实例验证及分析 基于贪婪 遗传算法的登机口分配结果实验数据来源于国内某大型枢纽机场，其中航站楼有 个登机口，卫星厅有 个登机口。登机口的属性包括：所在终端厅（）、区域位置（）、能接受的航班到达类型（国际国内）、能接受的航班出发类型（国际国内）以及能停靠飞机的宽窄类型（宽窄）。登机口属性不可修改，且只能接受航班到达类型、出发类型、机体宽窄类型以及适合的转场计划。根据统计，当天转场航班架次为 次，在该机场共有 组中转旅客，飞机转场信息、旅客信息以及登机口信息示例如表表所示。表飞机转场信息犜 犪 犫 犾 犲犃 犻 狉 犮 狉 犪 犳 狋狋 狉 犪 狀 狊 犳 犲 狉犻 狀 犳 狅 狉犿犪 狋 犻 狅 狀转场编号到达航班出发航班到达类型出发类型机体类别到达时间出发时间 ：表旅客信息犜 犪 犫 犾 犲犘 犪 狊 狊 犲 狀 犵 犲 狉犻 狀 犳 狅 狉犿犪 狋 犻 狅 狀旅客编号 乘客数 到达航班 到达日期 出发航班 出发日期 表登机口信息犜 犪 犫 犾 犲犌犪 狋 犲犻 狀 犳 狅 狉犿犪 狋 犻 狅 狀登机口终端厅区域到达类型 出发类型 机体类别 ，第 期胡杰等：基于贪婪 遗传算法的机场登机口分配策略 根据待分配登机口的航班计划初始化遗传算法基本参数，其中，种群数量为，染色体长度犕为 ，最大遗传代数犌为 ，当遗传代数大于 时表示遗传进化进入后期。编写航班 登机口分配算法程序进行模型求解，登机口航班占用时间分配如图所示，图为航站楼和卫星厅各登机口分配航班数量及其使用率统计，图为中转旅客最短流程时间占比统计。图航班 登机口分配甘特图 系统工程与电子技术第 卷图各登机口分配航班数量统计 图中转旅客最短流程时间占比统计 分析图图，可以得到以下主要结论：（）根据图统计可知，本文所提出的算法成功为 架次航班（架飞机）分配了登机口，占航班总数的 ，共使用了 个登机口，成功分配宽体机航班架次为，分配成功率为 ，成功分配窄体机航班架次为 ，分配成功率为 。（）由图可以看出，航站楼共有 个登机口被使用，其平均使用率为 ，卫星厅共有 个登机口被使用，其平均使用率为 。由此可知，在 日一天时间内，航站楼登机口的平均使用率略高于卫星厅，主要原因是卫星厅在一定程度上会增加旅客的换乘时间，从而导致算法在优化登机口分配方案时，更倾向于将飞机优先安排至航站楼的登机口。（）由图可以看出，中转旅客最短流程时间为 的旅客数占比最大，为 ，最短流程时间为 的旅客占比相对较小，为 ，这说明大部分旅客有充足的时间用来换乘，验证了模型和方法的有效性。登机口指派结果比较分析为进一步说明本文基于贪婪 遗传算法的机场登机口优化模型求解方法的有效性，将本文登机口分配方案与采用相同数据的航班“先到先分配”随机指派结果、基于贪婪算法的登机口指派结果以及基于禁忌搜索算法 的登机口指派结果进行比较，结果如表表所示。表中转航班登机口分配结果对比犜 犪 犫 犾 犲犆狅犿狆 犪 狉 犻 狊 狅 狀狅 犳犵 犪 狋 犲犪 犾 犾 狅 犮 犪 狋 犻 狅 狀狉 犲 狊 狌 犾 狋 狊狅 犳狋 狉 犪 狀 狊 犳 犲 狉犳 犾 犻 犵 犺 狋 狊算法模型成功分配航班数量架次宽体机分配成功率窄体机分配成功率先到先分配 贪婪算法 禁忌搜索算法 贪婪 遗传算法 表航站楼犜和卫星厅犛的登机口使用情况犜 犪 犫 犾 犲犝 狊 犪 犵 犲狅 犳犵 犪 狋 犲 狊犻 狀狋 犲 狉犿 犻 狀 犪 犾犜犪 狀 犱狊 犪 狋 犲 犾 犾 犻 狋 犲犺 犪 犾 犾犛算法模型登机口使用数量个登机口平均使用率登机口平均使用率先到先分配 贪婪算法 禁忌搜索算法 贪婪 遗传算法 表中转旅客总体最短流程时间统计犜 犪 犫 犾 犲犛 狋 犪 狋 犻 狊 狋 犻 犮 狊狅 犳狋 犺 犲狋 狅 狋 犪 犾犿 犻 狀 犻 犿狌犿狆 狉 狅 犮 犲 狊 狊狋 犻 犿犲犳 狅 狉狋 狉 犪 狀 狊 犻 狋狆 犪 狊 狊 犲 狀 犵 犲 狉 狊 算法模型总体最短流程时间先到先分配 贪婪算法 禁忌搜索算法 贪婪 遗传算法 由表表可以看出，基于航班计划，按“先到先分配”随机指派策略的航班分配成功架次为 ，登机口使用数量为，其中航站楼和卫星厅的登机口平均使用率分别为 和 ，中转旅客的总体最短流程时间为 。在贪婪算法实现登机口预分配结果基础上，使用遗传算法进行迭代优化后，成功分配航班架次为 ，航班 登机口成功分配率提高了 ，登机口使用数为 个，且登机口平均使用率得到提高，中转旅客总体最短流程时间为 ，相比“先到先分配”随机指派分配结果降低了 。进一步对比文献 中基于禁忌搜索算法得到的登机口分配结果可以看出，本文所提出的第 期胡杰等：基于贪婪 遗传算法的机场登机口分配策略 登机口分配算法能够将更多的中转航班分配至固定登机口，且旅客总体最短流程时间相比禁忌搜索算法降低了 。由此可知，基于贪婪 遗传算法的登机口优化方法能够有效提高航班 登机口分配成功率，显著减小中转旅客换乘时间，且登机口的使用效率得到提升，验证了模型和算法的有效性。结论（）本文对具有卫星厅的枢纽机场登机口分配问题进行了研究，以提升中转旅客换乘满意度为优化目标，提出在最大化分配航班至固定登机口的基础上，最小化中转旅客总体最短流程时间和固定登机口使用数量，建立了适用于具有卫星厅的机场登机口分配优化模型。（）设计了遗传算法染色体表现形式，给出了基于贪婪 遗传算法的登机口分配模型求解流程和算法实现过程，并利用带精英策略的遗传算法实现登机口优化模型求解。（）利用一组实例数据对所提出的模型和算法进行了验证，结果表明本文提出的航班 登机口分配模型和算法能够有效为过站航班指派适合的登机口。参考文献，：余朝军，江驹，徐海燕，等基于改进遗传算法的航班 登机口分配多目标优化交通运输工程学报，（）：，（）：，（）：，（）：，（）：冯程，胡明华，赵征一种新的停机位分配优化模型交通运输系统工程与信息，（）：，（）：，：，（）：，（）：，：王岩华，朱金福，朱博，等繁忙机场机位分配的混合集合规划方法武汉理工大学学报（信息与管理工程版），（）：，（），（）：，：刘君强，张马兰，陈鹏超，等基于协同决策的多航站楼停机位实时分配算法南京航空航天大学学报，（）：，（）：，：，：，：，：，：，：新起点航站楼扩增评估 最终稿 ：杨朋飞，李婷，汝洪武，等机场新增卫星厅对登机口影响的评估方法应用数学和力学，（）：，（）：林闯，陈莹，黄霁崴，等服务计算中服务质量的多目标优化模型与求解研究计算机学报，（）：，（）：系统工程与电子技术第 卷，：徐克虎，孔德鹏，黄大山，等智能计算方法及其应用北京：国防工业出版社，：，（）：，：，：李云鹏，张则强，管超，等停机位分配问题的整数规划模型及启发式求解方法系统工程，（）：，（）：蒋洪讯，马仁义面向靠桥率及道口冲突率的航班 机位指派问题优化模型及其启发式算法研究系统科学与数学，（）：，（）：，：，（）：，（）：董兵，吴郑源，赖桂瑾，等具有卫星厅的机场航站楼登机口分配研究科学技术与工程，（）：，（）：作者简介胡杰（），男，高级工程师，博士，主要研究方向为智能优化算法、交通运输规划、卫星导航、信号处理。鲍帆（），女，高级工程师，硕士，主要研究方向为交通运输规划、智慧机场总体设计。石潇竹（），男，研究员，硕士，主要研究方向为智慧机场总体设计、智能优化算法。