图论最大流理论在机场登机口分配中的应用

图论最大流理论在机场登机口分配中的应用 图论最大流理论在机场登机口分配中的应 用 第28卷第5期 2010年1O月 中国民航大学 JOURNALOFCIVILAVIATIONUNIVERSITYOFCHINA Vo1.28N0.5 0ctober2010 图论最大流理论在机场登机口分配中的应用 李明捷h,石荣,蒋凤伟 (1.中国民航飞行学院a.空中交通管理学院;b.飞行技术学院,四川广汉618307;2.四川省机场集团有限公司,成都610200) 摘要:为提高登机口的利用率,提升航空旅客出行的便捷性与舒适性,提高机场的运行效率及航空公司的运营效 益.在图论中网络最大流理论的基础上.将旅客步行距离,机场资源运行效率,飞机最短过站时间,"航班 对",机型等作为约束条件,考虑航站楼布局,始发/终到及中转旅客数量等因素对登机口分配结果的影响, 建立旅客登机口分配的优化网络模型.并对该算法的复杂度和最优性进行分析和证明.最后,运用实例来验 证该方法在缩短旅客步行距离和提高机场运行资源利用率方面的可行性,该算法也可用于飞机停靠机住的 优化安排. 关键词:登机口:图论;网络最大流理论;优化 中图分类号:F560.81;O157.6文献标识码:A文章编号:1674—5590(2010)05—0013-04 ApplicationofNetworkMaximumFlowTheoryinAirportGateAssignment ,,ie,SHI0,,JIANGFeng-wei (1a.SchoolofairrrofficManagement;lb.SchoolofRightTechnology,CivilAviationFlightUniversityofChina Guanghan618307,China;2.SichuanProvinceAirportGroupCo.Ltd,Chengdu610200,China) Abstract:Inordertoenhancethegateefficiency,promotetheconvenienceandsuitabilityofairpassengers,increasethe airportoperationefficiencyandrunningbenefitoftheairlines,thispapermadetravelerswalkdistance, operationefficiencyofresource,aeroplanesstaytime,thecoordinationbetweenthein— harborandout—harbor airlinesandaeroplanetypeasrestrictedconditions,consideredsomefactorsinfluencingonthegateassignment resultsuchasthelayoutoftheterminal,departureandarrivingpassengervolumeandSOon,designedthe networkmodelforairportgateassignmentbasingonthenetworknmximumflowtheory.Itanalyzedandproved thecomplexityandoptimizationofthearithmetic.Italsousedanexampletovalidatethevalidityonshortening walkdistanceandimprovingtheefficiencyofairportoperationresource.Otherwise,thismodelcouldbe appliedtOtheoptimizationassignmentofboarding. Keywords:gate;graphtheory;networkmaximumflowtheory;optimization 随着机场航班13起降架次的增多和乘飞机出行 旅客数量的迅速增长,现有的登机口资源正面临着El 益严峻的考验.目前,大多数机场通过借鉴其他机场 的做法,或根据以往的经验来进行登机口分配和调 度,往往导致很多载客数量较多的大中型飞机停靠在 距安检或者行李提取大厅较远的登机口;或由于远, 近机位登机口航班密度安排不合理,使得每个登机口 的航班组合没有达到最优,从而降低了登机口的利用 效率. 对于中国大多数中小型机场来说,由于航班日起 降架次相对较少,到离港时间相对分散,故在机场运 行资源分配和优化问题研究时,学者们多将目光集中 在停机位资源优化与分配问题上,而较少考虑登机口 的分配和调度优化方法.南京航空航天大学的王志清 等人将图论应用到登机口分配问题中,提出旅客登机 口调度优化网络模型,具有一定的创新性,模型假设 进,出港旅客步行距离基本相等,没有考虑中转旅客 对登机口分配的影响[1].南京航空航天大学的曹燕在 其硕士学位论文中利用表上作业法对登机口分配模 型进行了考虑,但直观性不强嘲.中国民航飞行学院文 收稿日期:2010—03—08:修回日期:2010—05—07基金项目:中国民航飞行学院自 然科学基金项目(J2008—49) 作者简介:李明捷(1981一),女,新疆奎屯人,讲师,工学硕士,研究方向为机场运行管 理. 14中国民航大学2010年10月 军等人将图着色模型应用到机位分配中,使图论的思 想在资源分配中得到应用[3J.但在考虑登机口分配问 题时,由于近机位登机口与近机位一一对应,因而可 以用机位分配与优化模型来模拟登机口的分配;而远 机位登机口具有一定的特殊性,对于旅客而言,登机 口与机位是一一对应的关系,但从空间分布上来看, 其可以是一个或几个登机口对应一个或多个机位的 设置形式,也就是"一对多"或"多对多"问题,此时若 再使用停机位的分配与优化方法来解决登机口的分 配就不合理了. 本文以进,出港旅客总的步行距离最短为主要优 化目标,运用图论中的网络最大流理论来解决登机口 的分配与优化问题,在保证机场安全,高效运行的前 提下,尽可能提高登机口利用效率,体现民航旅客运 输的便捷性与舒适性. 1研究与方法 1.1旅客步行距离最短模型的优化目标与约束条件 1.1.1优化目标 1)使进,出港旅客的总步行距离最短,满足旅客 对航空运输"便捷性"的需求; 2)使现有设施使用效率达到最高,优化资源配置. 1.1.2约束条件 1)机型与机位类型相匹配; 2)分配登机口时,一个航班必须被分配且仅能被 分配至一个登机口; 3)应满足最短过站时间和同机位安全间隔时间 的要求; 4)"航班对"的限制:由于在机场停靠的绝大部分 航班既担负着进港航班任务,又担负着出港航班任 务,因此,尽量将此类飞机尽可能安排在同一个登机 口,降低航空公司运营成本. 除此之外,根据各机场的性质和特点不同,还需 考虑登机口分配的优先原则,航班过夜,飞机维修等 约束条件. 1.2旅客步行距离最短模型的设置条件 1.2.1假设条件 假设某机场有m个可用登机口,当日有//,个航 班,每个登机口的启用和停用时问,每个航班的载客 人数均已知.根据某机场一天中部分时段的航班计 划,将各航班信息汇总如表1所示. 1.2.2航站楼布局对登机口分配的影响 当登机口位置布局已知,则安检区和行李提取大 表1某机场一天中部分时段航班信息汇总表 Tab.1Flightinformationtableofanairportinthe parttimeduringaday 厅的位置将会直接影响到进,出港旅客步行距离的长 短.这里所讲的航站楼布局,主要分为两种:一是安检 区与行李提取大厅位于航站楼上,下两层中基本相同 的位置;二是安检区与行李提取大厅位于航站楼上, 下两层或同层中不同位置. 1)安检区与行李提取大厅不同层但位置相近 对于大部分机场而言,进,出港旅客总人数总体来 讲近似相等,对于图1这种设置方式,虽然进,离港旅 客的行走路径不同,但一般情况下,在进行登机口优化 分配过程中可将进,出港旅客步行距离视为相等,在进 行登机口分配时,需按照航班实际载客人数,尽量将人 数较多的航班安排在靠近安检区的登机口. … 回 j行李提取大厅 : 注:图中箭头仅表示旅客流向,与流量无关. 图1安检区与行李提取大厅布置图I Fig.1LayoutofsecuritycheckandbaggageclaimregionI 2)安检区与行李提取大厅(不)同层且位置不同 对于某些中,小机场,其安检区与行李提取大厅 采用同层或分层且相隔较远的方式设置,如图2C]所 示,在这种情况下,应根据航班人数,结合其他限制条 件进行登机口分配. 第28卷第5期李明捷,石荣,蒋凤伟:图论最大流理论在机场登机口分配中的应用 15 … 行李提取大厅安检区 图2安检区与行李提取大厅布置示意图? Fig.2LayoutofsecuritycheckandbaggageclaimregionlI 2结果与分析 2.1数据收集与整理 本文利用表1中已知航班信息作为实例分析的 数据来源,采用最广泛的航站楼布局形式,即假定安 检区和行李提取大厅分别位于航站楼的上,下两层, 位置近似相同,以此来该模型的构建方法和应用 过程. 2.2优化分配网络模型的构建 2.2.1进,出港旅客步行距离最短模型建立与实证分析 对于国内大部分干线和支线机场而言,始发或终 到旅客所占比例甚多,从长时问的数据统计来看,这 两部分旅客所占比例相当,因此,可将其步行距离视 为近似相等.以下就是进,出港旅客步行距离最短模 型的实施步骤: 步骤1按照登机口启用时间的先后顺序,由左 至右把每个航班作为网络图上的一个节点,在考虑各 种约束条件的基础上,将节点之间进行有向连线,方 向为由离港时间早的航班指向晚的,由此形成一个由 节点和箭头构成的网络图.不难理解,网络图中从起 点到终点的每一条有向路径上的节点都是可以安排 在一个登机口上的航班组合,如图3所示. , 图3登机口分配的网络图 Fig.3Networkgraphofgateassignment 步骤2在图3上,按照各节点的时间顺序对其 进行二次编号c(4,),C表示航班编号;表示航班 G的前一个航班的编号(若为起始航班,则其编号为本 次航班的号码);B表示航班载客人数的累计,即前一 个航班A的实际载客人数与本次航班G的实际载客 人数之和.需要注意的是,若A前有两个或多个已编 号航班,则择选B最大的那个航班作为G的前一个航 班,如图4所示. 图4航班的二次编号 Fig.4Secondcompositorofflights 步骤3将每架航班的人数看成是网络图中的流 量,从登机口结束使用的这个网络图的最大流量就表 示可以使用同一个登机口的人数最多的航班组合.从 终点开始逆向寻找一条至起点航班人数最多的路径, 并把这条路径上的航班安排在距安检出口最近的登 机口.在图4中,01—04—07即为该网络图中旅客流 量最大的航班组合,可将这3个航班按照登机口启用 先后顺序安排至离安检区最近的登机口. 步骤4在调度网络图上去掉已安排过的航班节 点及与其相关联的箭线,再从新的起点开始寻找一条 至终点航班人数最多的路径,并把这条路径上的航班 安排在距安检出口次近的登机口,如图5所示.在图5 中,O2—03—05—08为网络图中旅客流量最大的航班 组合,可将这4个航班按照登机口启用先后顺序安排 至离安检区次近的登机口. 图5航班的三次编号 Fig.5Thirdcompositorofflights 步骤5重复步骤4,按照上述方法直到所有的 航班安排完为止.本例中剩下06号航班,可将其安排 至3号登机口. 2.2.2中转旅客步行距离最短模型 对于大型枢纽机场以及部分干线机场而言,国际 l6中国民航大学2010年10月 转国际,国际转国内,国内转国内的中转旅客数量较 其他中小机场多.中转旅客的流程大致可以概括为: 旅客下机一中转柜台一中转休息厅一安全检查一登 机,中转旅客的所有中转过程都在隔离区内完成,旅 客不用出去重新办理登机手续.则中转休息厅相对于 安检区的位置将直接决定中转旅客在航站楼内步行 距离的长短.假设该段距离长短已定,则需考虑登机 口与安检区的相对位置,以便尽量减少该部分旅客的 步行距离. 具体分配的思路是:根据进,出港旅客步行距离 最短模型的分配结果,利用网络最大流理论,考虑在 航班间隙将中转旅客流量最大的航班安排在距离安 检区最近的登机口,以此类推,具体过程参见本文的 2.2.1节. 2.3算法复杂度分析和最优性证明 2.3.1算法的复杂度分析 如前所述,该模型总运算次数不会超过n,而网络 图中航班节点的总数也不会超过凡,故总运算次数不 会大于n,即其计算复杂度为O(n). 2.3.2算法的最优性证明 为了说明算法是最优算法,现在登机口调度网络 图上增加一个虚拟起始节点s和一个虚拟终结节点f, 并将虚拟起始节点S与所有起始航班节点用箭头相 连,同样,将所有终结节点与虚终结节点t也用箭头相 连,如图6所示. 图6加入虚拟起始节点和虚终结节点的网络图 Fig.6NetworkgraphwitlIdummyodin~pointandterminalpoint 由于各航班节点是按时间顺序由左至右排列的, 因此,图6所示的网络图是一个具有两端点s和t的 无环路网络图.其中每一条从S到t的有向路径,都是 可在同一个登机口安排航班组合的可行.如果把 各节点的航班人数作为以该节点为终点的各箭线的 权值,则该网络图就相当于一个双代号网络图, 而上面的算法等同于在此双代号网络图中寻找从s到 t的最大权值路线的算法I5J.因此,当各箭线的边权值 为该箭线指向节点的航班乘客人数时,所形成的最长 路线就是可以安排在同一个登机口的乘客人数最多 的航班安排组合,由此印证了该算法的最优性. 3结语 1)本文采用图论中的最大流理论构造了登机口 分配的网络模型,以旅客步行距离最短为主要优化目 标,方法简单,实际操作性较强. 2)较传统的登机口分配方法,该模型能够有效应 对航班延误,返场备降等突发情况,对机场运行管理 中的登机口分配工作具有一定的指导意义. 3)该模型有利于机场运行资源的均衡使用,对提 高现有资源利用率,缓解机场运行设施设备供需矛 盾,节约机场的运营和建设成本,降低航空公司的运 行成本等方面具有一定的理论研究价值. 参考文献: ,商红岩,宁宣熙.机场登机口优化调度算法及实证[J].南京 [1]王志清 航空航天大学,2007,39(6):819—823. [21曹燕.民航运输旅客流程的优化研究[D].南京:南京航空航天大 学.2005. [3】文军,李冰,王清蓉,等.机场停机位分配问题的图着色模型及 其算法IJJ.系统工程理论方法应用,2005,14(2):136—140. [41常钢,魏生民,张建龙.基于多目标规划的停机位分配建模技术 研究叫.西北大学(自然科学版),2006,36(5):725—728. [5]宁宣熙.运筹学实用教程[M】.北京:科学出版社,2002:231-239. (责任编辑:党亚茹)