（模式识别与智能系统专业论文）民用机场值机柜台优化配置问题研究.pdf

摘要 在大多数大型枢纽机场，值机柜台是一种紧缺的资源。由于资金和场地等客观因素 的制约，面对不断增多的航班和旅客，机场方面无法大规模的扩充值机柜台，只能寻求 挖掘现有值机柜台的潜力，提高现有值机柜台的使用效率。因而，研究值机柜台配置问 题对于机场而言具有重要的现实意义。 本论文的研究对象是机场航站楼内非全开放式共用值机柜台。考虑到对于每一个开 通的航班，机场有责任为其提供必要的值机柜台，因此本论文对值机柜台优化配置的研 究着眼于如何使用机场现有的数量固定的值机柜台满足所有航班的值机需求。通过对值 机柜台配置问题进行细致的分析，并借鉴国内外的研究成果，本论文得出了对单个航班 得到的值机柜台资源进行综合评价的函数；在此基础上提出使得所有航班的评价函数值 总和最优的数学模型，并构建相应的改进遗传算法求解该配置问题。在值机柜台资源充 足时，该算法能够按照每个航班的需求为航班分配足够的值机柜台资源：在值机柜台资 源不足时，该算法能够尽可能多地为每个航班分配值机柜台资源，使得所有航班的评价 函数值总和最优。最后用v c + + 编写程序实现改进遗传算法，通过实例计算对性能进行 检验和分析，以及与其他模型和算法的效果对比。 关键词：值机柜台配置，资源受限，优化，遗传算法 a b s t r a c t w i t ht h es t e a d yg r o w t ho ft h ea v i a t i o n ，t h ec h e c k i nc a p a c i t yh a sb e e ns c a r c er e s o u r c ei n m a n yl a r g eh u b s i ti sr e q u i r e df o rt h ea i r p o r tt or e s e a r c hh o wt ou t i l i z et h ee x i s t i n gc h e c k - i n f a c i l i t ye f f e c t i v e l ys i n c ei t i si m p o s s i b l et oa d dm o r ec h e c k i nc o u n t e r sb e c a u s eo ft h e f i n a n c i n ga n di n s i d es p a c eo fb u i l d i n ge t c i nt h i sp a p e r , t h ec o m m o nu s ec h e c k - i nc o u n t e ri nt h et e r m i n a lb u i l d i n gi sc o n s i d e r e d n l ei n t e r e s t i n gi sh o wt os e r v e ra l lf l i g h t sw i t ht h ee x i s t i n gc h e c k - i nc o u n t e r s ，s i n c ei ti sa n o b l i g a t i o nf o rt h ea i r p o r tt op r o v i d ec h e c k i nc o u n t e r st oe a c hf l i g h tw h i c h h a sb e e na c c e p t e d i nt h i sp a p e r , af u n c t i o ni sc r e a t e df i r s t ，v i aa n a l y z i n gt h ec h e c k i na s s i g n m e n tc l e a r l ya n d s t u d y i n gt h er e f e r e n c e s ，t oe v a l u a t et h e c h e c k i nr e s o u r c e sa s s i g n e d t oaf l i g h t ，t h e na m a t h e m a t i cm o d e li sc o n s t r u c t e dt oo p t i m i z et h et o t a lo ft h ee v a l u a t i n gv a l u e so fa l lf l i g h t s ， a f t e rt h a tag e n e t i ca l g o r i t h mi sd e v e l o p e dt os o l v et h ec h e c k i na s s i g n m e n tp r o b l e mb a s eo n t h em o d e l ，l a t e ro nap r o g r a mi sd e v e l o p e db yv c + + a n du s et h ep r a c t i c a li n f o r m a t i o no f f l i g h tp l a nt ov a l i d a t et h eg e n e t i ca l g o r i t h m ，f i n a l l yt h eo p e r a t i o nr e s u l t sb yt h eg e n e t i c a l g o r i t h mi sc o m p a r e dw i t ht h o s eb yo t h e rm e t h o d t h eg e n e t i ca l g o r i t h mi se f f e c t i v e ，i tc a n s a t i s f ye a c hf l i g h tc o m p l e t e l yw i t hc h e c k i nc o u n t e rr e s o u r c ea c c o r d i n go nt h er e q u e s tw h i l e t h e r ea r ee n o u g hc h e c k - i nr e s o u r c e ，o ri tc a nc r e a t ea no p t i m a la s s i g n m e n tt h a tc a ng t v e s f l i g h t sc h e c k i nr e s o u r c ea ss o o na sp o s s i b l ew h i l et h e r ea r en o te n o u g hc h e c k - i nr e s o u r c e k e y w o r d ：c h e c k - i nc o u n t e ra s s i g n m e n t ，l i m i t e dr e s o u r c e ，o p t i m i z a t i o n ，g e n e t i ca l g o r i t h m 中国民用航空学院学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究：【作及取得的研究成果。尽我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得中国民用航空学院或其它教育机构的学位或证二婷而使用过的材料。与我一同工作的 同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：日期： 中国民用航空学院学位论文使用授权声明 中国民用航空学院、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复 印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文 的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文 的全部或部分内容。论文的公布( 包括刊登) 授权中国民用航空学院研究生部办理。 研究生签名：锵导师签名： 中国民航夫学硕i ：学位论文 1 1 课题研究背景 第一章绪论 无论是过去还是未来，民航运输业都是一个发展迅速的行业。虽然9 1 1 事件使人们 一度对乘坐民航飞机的安全性产生怀疑，选择乘坐民航班机的旅客人数锐减，使世界民 用航空运输业暂时陷入困境。在9 1 1 事件发生之后，各国政府在全世界范围内联合开展 反恐行动，安全保卫部门投入使用各种先进检测仪器，在地面和空中施行各种防范恐怖 活动的措施。这些举措有效地杜绝了和飞机有关的恐怖活动的发生，挽回了人们对飞机 航班的信心。同时相对于其他交通运输工具，飞机具有的无可比拟的速度优势，是人类 社会能够保持快节奏的政治、经济、文化交流的中举力量之。因此，当人们在从9 l l 事件引发的恐慌中平静下来，能够冷静客观的对待飞机航班的安全性问题之后，乘坐民 航航班的旅客人数逐渐恢复，民航运输业得到了新的发展。对于中国这样疆域辽阔、人 口众多、社会政治经济文化各方面发展都很迅速的国家，民航运输业更具有重要的意义， 有更好的发展前景。 和其他的交通运输工具相比，乘坐民航航班出行的费用比较高，因而相当长的时闻 内选择乘坐航班出行的旅客以可以报销乘机费用的公务人员为主，根据民航协会用户工 作委员对从1 9 9 8 年l o 月到1 9 9 9 年4 月之间乘坐国内航班的乘客进行抽样调查结果【2 u i 显 示，公务出行人员占全部被调查旅客的5 8 5 3 ，旅游人员的比例为2 9 9 5 ，探亲人员 只占1 1 5 1 。但是调查也显示，选择乘坐民航班机出行的自费旅客为4 3 8 8 ，公费旅 客为5 6 1 2 ，而1 9 9 6 年相应的数据为3 1 6 7 和6 8 3 3 。1 9 9 6 年到1 9 9 9 年是中国经济高速 发展的时期，同时期的民航自费旅客和公费旅客的占所有旅客的比例的变化从侧面说明 民航的发展与国家的经济发展水平密切相关1 2 1 1 ，表明国民经济的发展促进了民航的发 展，因此可以乐观的预测：随着我国国民经济的发展和人们收入水平的进一步提高，会 有越来越多的出行旅客考虑选择快捷的民航。根据民航总局提供的民航数掘1 2 “，2 0 0 6 年l 1 1 月份，全行业累计完成旅客运输量1 4 7 亿人，比去年同期增长1 5 3 。预计全年 1 6 亿人，比2 0 0 5 年增长1 5 9 。 按照民航总局制定的民航发展规划【3 6 l ，中国民航将用十五年的时闻奋起直追，在 2 0 2 0 年中国民航运输规模大概相当于美国民航2 0 0 4 年的规模。2 0 0 4 年美国民航业界大 约有6 0 0 个左右的公共商用运输机场、1 1 3 家航空公司和7 7 6 1 - 架运输飞机，全年共完成 运输总周转量1 4 5 0 亿吨千米。相比之下，2 0 0 5 年中国民航业界只有1 4 2 个公共商用机 场、2 0 家航空公司和8 6 3 架运输飞机。全年共完成运输总周转量2 6 1 亿吨千米，仅相当 美国民航2 0 0 4 年同类数据的2 4 、1 8 、i i 、1 8 。中国民航要想顺利实现民航总局 的民航规划，在从2 0 0 5 年到2 0 2 0 年内必须达到平均每年增加3 0 个机场。4 6 0 架飞机， 中国民航夫学硕i ：学位论文 以此为基础平均年增运输总周转量8 0 亿吨千米。 相对民航航班和客流量的高速度增长，机场的地面服务设施没有保持与之相应增长， 使得地面设施资源的利用受到巨大的压力。这一点也由现今每年的五一、十一黄金周和 春运期间机场内日益汹涌的人流所印证。现在机场的建设已滞后于民航整体的发展。在 首届航空运输与区域经济发展论坛上( 沈阳，2 0 0 6 ) ，民航总局机场司副司长刁永海就 指出1 3 ”，我国许多机场设施容量已达到饱和或接近饱和，面临急需改扩建的局面。其中， 全国6 0 个机场已经或即将达到饱和，1 3 个机场已处于超负荷运行3 6 个机场将于2 0 1 0 年饱和，1 1 个机场将在2 0 1 5 年饱和。 由于受空间和资金的限制，机场方面无法也不可能通过不断扩充机场的地面服务设 施的方法来应对民航旅客流的高速增长，因此如何有效地利用现有的服务设施，如何有 效地挖掘它们的潜力对机场有非常重要的现实意义。 1 2 研究目的和方法 随着航班和旅客数量的增加，由于财务和场地等因素的制约无法同步增加机场的值 机柜台数量，因此资源受限的机场值机柜台资源越来越难以应付r 常的航班值机需求。 本课题跟踪机场现场运作的实际状况，利用遗传算法灵活的组织能力和强大的求解能 力，解决在数量有限无法完全满足所有航班对值机柜台的需求的情况下的值机柜台配置 问题。 1 3 课题来源 本论文的课题来源是国家自然科学基金项目民用机场停机位配置与地面作业优化 问题研究，项目编号6 0 4 7 2 1 3 0 ，其主要内容是：面向枢纽机场的地面作业运营管理， 进行航班的到港作业，停机位配置，离港作业等一体化的离散事件系统描述，建模，运 行分析和协调控制，并采用智能优化的方法对其中的停机位配置优化问题，航班延误情 况下的停机位应急调度问题以及机场地面作业调度等资源受限问题进行研究。 1 4 论文的结构 本论文分为绪论、文献综述，值机柜台问题的描述与分析、遗传算法求解、结果分 析、总结和展望六部分。 第一章：介绍本课题的研究背景，研究目的与意义，课题来源，论文的框架结构。 第二章：介绍值机柜台的应用现状，对与共用值机柜台配置问题相关的国内外的研 究现状做一个完整的综述，并介绍本课题求解值机柜台配置问题的基本思路。 第三章：对值机柜台配置问题进行详细的分析，给出值机柜台配置中的约束条件， 中周民航大学硕 学位论文 给出值机柜台配置问题的数学描述。 第四章：设计求解值机柜台配置问题的遗传算法，包括遗传表示、初始化、交叉算 子、变异算子等。 第五章：对构建的遗传算法的实际求解效果进行检验。 第六章：对本课题的研究做一个总结，并对以后的发展做一个展望。 中嗣民航人学硕l ：学位论丘 2 1 值机柜台概述 第二章值机柜台配置问题综述 国内航班的乘客到机场乘坐飞机时，其标准的流程是：托运行李和换登机牌 安全 检查) 候机及登机，国际航班的乘客的则是：海关 托运行李和换登机牌) 检验检疫 ) 边防检查 安全检查) 候机及登机。托运行李和换登机牌这个登机环节就发生在值 机柜台。在值机柜台那里，乘客凭借个人身份证和机票，换取登机牌、办理行李托运等 乘机手续。 2 1 1 值机柜台的发展 最早的时候，民用航班少，乘坐民航班机出行的旅客也少，所有的值机柜台都设在 机场的航站楼内，由机场指派专门的工作人员在值机柜台负责为乘机的旅客办理乘机手 续。随着民用航空技术的发展，民航班机的载客量、舒适度、安全性等指标不断提高， 同时也使乘坐民航班机的费用也越来越低，让更多的普通人能够承受乘坐民航班机的开 销，同时社会的进步和经济的发展使国际国内的经济政治文化交流同益频繁因此愿意 选择乘坐民航飞机出行的人越来越多，为了分享这个利润丰厚的市场，航空公司纷纷成 立，航班数量也越来越多。伴随着航空运输市场的迅猛发展，不断增加的旅客使机场航 站楼内日渐拥挤，航站楼楼内的值机柜台资源也承受巨大压力。 为了缓解航站楼内的值机柜台的压力，便利乘客办理值机手续，机场和航空公司提 供多样化的值机服务途径，供乘客根据自己的实际情况选择最便利的一种。有的航空公 司联合一些信誉稳定的社会机构在市区开设值机柜台，让乘坐这些航空公司航班的乘客 在市区就可以办理乘机手续，甚至可以提供购票值机一条龙服务。免去乘客提前到 机场排队办理乘机手续的麻烦：有的机场大巴则提供为乘客办理行李托运、值机的手续， 乘客可以在起飞前2 4 小时内将行李送到附近的机场大巴上客点，办理值机手续；有的 机场设置无托运行李值机柜台，专门为没有行李托运的乘客服务；有的机场安装自助值 机柜台，乘客不用到专人值守的值机柜台，在自助值机柜台就可以办理领登机牌、登记 座位等乘机手续【1 5 1 , 1 2 h 。除了以上的措施之外，还出现了电子客票这一新事物。虽然航 空公司推出电子客票的初衷不是为了提到值机效率和方便乘客办理值机手续，但是电子 客票上能够记录跟多的乘客信息，而且读取方便，相当于提前在售票阶段就登记了乘客 的信息，省却在值机柜台上手工输入乘客信息的麻烦，节省了时间，提高了值机效率。 航空公司在市内开办的流动或固定的值机点虽然能够为乘客提供极大地便利，但是 难以在大城市中全面普及，只能作为航站楼内值机柜台的补充。作为新尘事物出现的自 4 - 中国民航人学颀l 学位论文 助值机柜台由于其方便乘客值机和节省机场的费用丌支而得到迅速的发展，丌始大量的 使用，但是传统的值机柜台本身仍然具备独有的优势，如办理行李托运方便、更安全和 旅客更愿意接受有人值机服务等，所以自助值机柜台的出现只会与传统的值机柜台形成 优势互补，而不会让传统的值机柜台全面引退出市场【3 1 。 2 1 2 共用值机柜台 按照租借方式的不同，机场航站楼内的传统值机柜台可以分为两种：专属值机柜台 和共用值机柜台。专属值机柜台由某个航空公司长期租借，专门用于为该公司所属各航 班的乘客办理值机手续。共用值机柜台不专属于某个航空公司，即不被某个航空公司长 期租用，可以为所有航空公司的航班提供值机服务。按照值机方式的不同，共用值机柜 台又可以分为全开放式值机柜台和非全开放式值机柜台两种。非全开放式共用值机柜被 机场管理部门根据航班计划和航班需求配置给各个航班，这种值机柜台为航班值机有时 问限制，一般在航班起飞前若干小时开始为航班提供值机服务，在航班起飞i i i f 若干分钟 停止值机，特定的航班只能在指定的几个值机柜台上值机，因此，乘坐特定航班的乘客 必须在指定的时间内到指定的值机柜台上办理值机手续。- 开放式值机柜台则没有与非全 开放式值机柜台类似的值机时间和地点的限制，任意一个开放的值机柜台都可以为任意 一个航班值机，乘坐特定航班的乘客可以在该航班尚未停止值机之静到任意一个值机柜 台上办理乘机手续。 专属值机柜台多见于欧美的机场，亚洲的机场多为共用值机柜台。在国内，一般只 有大型的航空公司在航空枢纽机场才使用专属值机柜台，如东方航空公司在北京首都国 际机场、上海虹口国际机场就拥有自己的专属柜台。使用专属值机柜台可以为乘坐公司 航班的乘客提供高效优质的值机服务，有利于提高航空公司的美誉度，同时也有利于航 空公司安排值机人员。但是长期租用所付出的成本不菲，大多数航空公司由于本身的航 班数量不多，从成本上考虑不愿意使用专属值机柜台，因此共用柜台在机场值机环节中 占有重要的地位。 就解决机场航站楼内的拥挤状况，缓解值机柜台承受的值机压力而言，全开放式值 机柜台优于非全开放式值机柜台。全开放式共用值机柜台不分航班值机的工作方式有利 于充分挖掘值机柜台的工作潜力，使值机柜台的工作强度分配均衡，可以大幅度的缩减 乘客办理乘机手续时等候的队列长度和等候时间，而且全刀= 放式共用值机柜台的配置很 简单，只须根据到达机场的乘客流量决定开放值机柜台的数量。但是全开放式值机柜台 对硬件设施和值机环节的工作人员的素质要求比较高，曾经有国内的机场因为无法应对 使用全开放式值机柜台带来的种种问题如送错行李。不得不放弃使用全丌放式值机柜 台。 虽然非全开放式共用值机柜台存在种种不足，但是在很多机场仍然使用非全开放式 值机柜台，因而研究非全开放式共用值机柜台的配置问题仍具有重要的现实意义。鉴于 中国民航大学颀i ：学位论文 非全开放式共用值机柜台的配置问题比较复杂。有必要对非全开放式共用值机柜台配鹭 问题进行系统的研究。目前值机柜台配置问题的研究对象也都是集中于非全丌放式共用 值机柜台。以后本论文提到的值机柜台配置问题均指非全开放式共用值机柜台的配置问 题。 2 1 3 值机柜台配置 在计算机规划技术未曾被引入值机柜台配罱领域时，传统的值机柜台人工配置方法 是由机场的工作人员手工在图纸上作业。通常，各家航空公司先把自己的航班计划和柜 台需求，包括航班数、航班起飞时间、每个航班值机所需要的柜台数和所需的值机时间 等，提交机场管理部门，机场管理部门综合所有航班的情况制定值机柜台配置方案。人 工作业时，遵循“先到先服务”( f i r s tc o m ef i r s ts e r v e r ，f c f s ) 的原则，按照航班起飞 的时间先后顺序，为每一架航班分配值机柜台，最后得到一个可行的值机柜台配置方案。 机场管理部门会按照航空公司提出的值机柜台数量要求和时自j 要求，给航班指派柜 台资源。然而，实际的情况是值机柜台的数量有限，当从机场出发的航班很多时，或是 在繁忙的时段，常会无法按照航空公司的要求给航班指派柜台。遇到这种情况时，制定 值机柜台配置方案的工作人员就要想办法减少分配给航班的柜台数量或者缩减柜台为 航班值机的时间。在人工制定值机柜台配置方案时，没有通用的决策机制或者算法可以 确定应该为航班指派多少值机柜台，或者应该让柜台为航班值机多少时间。制定方案的 员工完全凭借个人的经验做出自己判断。 当机场的航班数量比较少时，机场有关部门采用人工方式配置值机柜台尚还可行， 但是仍然是一项耗时费力的工作。当机场的航班数量很多时，用人工方法制定值机柜台 配置方案成为一项不可能的任务。首先，在人工作业方式中，员工只能依靠自己的经验 对配置值机柜台过程中出现的各种问题做出判断。对出现的问题判断得准确与否，对各 种因素考虑得周到与否，直接关系到最后生成的值机柜台配置方案的质量，而员工的工 作经验和工作水平不可能做到整齐划一，而是参差不齐，因此手工制定的值机柜台配置 方案的质量必定是因人而异。其次，在人工配置值机柜台的过程中，当需要工作人员预 测一个特定的航班到底需要多少值机柜台，并且需要值机柜台在什么时候丌放，才能保 证航班值机需要时，他们只是根据自己以往的工作经验的做粗略的估计，也无法知道自 己做的这种判断是否准确，事实上，影响到航班对值机柜台资源的需求的因素很多，如 航班的座位数、航班上座率、航班旅客到达机场的模式等，但是由于受人工计算能力的 制约，这些因素在人工配置值机柜台的过程中被忽略了。第三，当工作人员把几个值机 柜台分配给某个特定的航班时，并不清楚这次的分配对后面的航班有什么影响，当没有 办法为后面的航班分配值机柜台时，就需要返回来对前面的分配进行调整，所以从某种 意义上来说人工配置值机柜台的过程就是一个不断试错的过程，在航班数量和值机柜台 数量都很多的时候，这个过程十分的繁琐、复杂，持续的时间很长，不能对环境出现的 中国民航大学硕卜学位论文 一些变化快速地做出反应。 计算机规划技术被引入值机柜台配置是基于如下的背景：进入二十一世纪之后，民 航运输业得到极大的发展，各个机场的航班数量持续增加，是过去的好多倍，为了满足 航班值机的需求，机场内的值机柜台也是数量大增。数目巨大的航班和值机柜台使值机 柜台配置的手工操作负担沉重，效率低下，急需引入先进的配置手段和技术。这时候计 算机技术已达到相当的水平，运算速度更快，功能更强的计算机型号不断地推出，计算 机在各行各业迅速地推广和应用。和计算机相关的各种应用软件、算法不断的被开发出 来，不断得到丰富和完善。理所当然，机场的管理当局把使用计算机制定值机柜台配置 方案当成必然的选择。 使用计算机来制定值机柜台配置方案的好处是显而易见的。首先，在特定的机场， 所有值机柜台配置方案所依据的条件和约束都是一样的，合格的计算机程序都能够稳定 地运行，因此有值机柜台配置方案质量参差不齐的现象；其次，由于计算机具有人不能 比拟的强大计算功能，计算机程序可以考虑很多在人工方法中无法考虑的复杂因素，如 行李传送带的负载平衡、值机柜台的布局对航站楼内的拥挤程度的影响等，可以轻易地 产生配冕方案用于对比参考，可以对更多的约束条件进行分析，从而得到的值机柜台配 置方案比人工生成的更为合理，用的时间也比人工的少；第三，与人工配置时只能对航 班的值机柜台需求做粗略估计不同，计算机可以通过分析航班起飞时删对乘客到达机场 的模式影响、航班目的地对乘客携带行李数量多寡的影响和工作人员为乘客办理乘机手 续的速度等，精确地预测值机环节要达到某个特定的服务指标应该给每个航班分配多少 值机柜台资源，并从系统上进行优化。 2 2 文献综述 当前国内外对机场值机柜台配置问题的探讨不多，专门对值机柜台配置问题进行探 讨的只有c h u r l 、y a h 和n i c o 的研究论文。 2 2 1c h u n 的论文 c h t m 就值机柜台配置问题发表三篇论文m 1 6 m ”。在文献【5 1 中，c h t m 提出了用约束 满足算法求解值机柜台配置问题，在文献 6 v o 介绍用i l o gs o l v e r 软件制定基于约束 满足算法的值机柜台配置方案，在文献【7 】中介绍用使用i r s s ( i n t e l l i g e n tr e s o u r c e s i m u l a t i o ns y s t e m ) 系统精确预测每个航班对值机柜台资源的需求。 总体上，c h u n 对值机柜台配霞问题的主要思想体现在文献【5 】。这篇论文于1 9 9 6 年 发表。c h u n 根据当时香港机场的营运现状，提出了把值机柜台配置问题转化为多维放 置问题( m u l t i d i m e n s i o n a lp l a c e m e n tp r o b l e m ) ，利用求解约束满足问题 ( c o n s t r a i n t - s a t i s f a c t i o np r o b l e m ) 的算法来获得值机柜台的配置方案。 中国民航人学颂l 。学位论史 按照c h u n 的描述【5 i ，香港国际机场在1 9 8 6 年到1 9 9 6 年的十年f - 日j 乘机旅客数量年 增1 0 。旅客流的不断增加，航班数量的持续增长，使香港机场成长为世界第三大客运 机场和世界第二大货运机场。1 9 9 6 年香港机场共接待1 5 0 ，0 0 0 架航班，平均每天接待 7 5 ，0 0 0 个乘客，达到了香港机场容量的饱和点。由于无法为新航班提供必要的地面设 施服务，香港机场管理局不得不拒绝航空公司开通新航班的申请，仅1 9 9 3 年管理当局 就退掉7 0 0 0 个新航班的申请。为了充分利用现有地面设施资源，以数量有限的值机柜 台资源为尽可能多的航班服务，香港机场管理局决定采用计算机制定值机柜台配置方 案。 传统的人工制定值机柜台配置方法i s l 是香港机场管理局的工作人员根据航空公司预 先向管理局提交的离港航班列表以及每个航班需要的值机柜台资源( 航班需要用的值机 柜台数量和每个柜台开放为航班值机的起止时i 日j ) ，在二维坐标( 柜台和时间) 的甘特 图上为每个航班圈占一个区域。在c h u n 的论文中，航班在甘特图上圈占的区域被称 为c o u n t e rp r o f i l e 。工作人员在甘特图上描画航班c o u n t e rp r o f i l e 的操作可以看作是把预 制的航班c o u n t e rp r o f i l e 放在甘特图上，因此，值机柜台配置问题可以看作是多维放置 问题( m u l t i - d i m e n s i o n a lp l a c e m e n tp r o b l e m ) ，求解时可以借鉴二维放置问题 ( t w o d i m e n s i o n a lp l a c e m e n tp r o b l e m ) 的求解算法。该类问题在计算机设计领域应用广 泛，大量应用在集成电路设计、印刷电路板设计等方面，有很多成熟的算法。 c h u n 开发算法m d a 1 ( m d a ，m u l t i d i m e n s i o n a ls c h e d u l i n ga l g o r i t h m ) ，用于 解决二维放置问题，在m d a 1 的基础上开发算法m d a 2 ，用于解决更多维的放置问题。 在m d a 1 中，c h u n 吸收手工制定值机柜台配置方案的成功经验。工作人员手工 为航班分配值机柜台时，首先在甘特图上寻找一块足够大空白区域，然后把航班c o u n t g r p r o f i l e 放上去。在值机柜台资源紧张的情况下，无法完全满足所有航班对值机柜台资源 的需求，必定需要调整分配给某些航班的值机柜台资源数量。手工操作中，当遇到无法 按照航班申请的柜台资源给航班分配柜台时，工作人员就会考虑压缩航班的e o u n t s l p r o f i l e ，再给它在甘特图上找一个空白区域。工作人员压缩航班的c o u n t e r p r o f i l e 时，都 是凭借自己的工作经验，粗略的估计航班对柜台的需求，比如某个航班需要6 个柜台值 机3 小时，工作人员认为在值机的第- - 4 时内该航班到达的乘客不多，第二个小时内到 达的乘客慢慢增多，第三个小时到达的乘客最多，那么他就会根据以往的经验在第一个 。 小时内给该航班2 个柜台，第二个小时增加2 个柜台，第三个小时再增加2 个柜台，这 样就得到间隔一小时的2 4 6 的阶梯状c o u n t e rp r o f i l e 。m d a 1 算法采纳手工为航班值机 柜台的基本思想。由于计算机具有强大的计算能力，在压缩航班的c o u n t e rp r o f i l e 时， 综合分析那些对航班c o u n t e rp r o f i l e 的质量影响巨大，但是在手工操作中出于条件限制 而被忽略的因素，比如乘客到达机场的期望概率、航班乘客要托运的行李数量的期望值、 乘客办理值机手续所需时间的期望值等，得到精确度更高、质量更好的c o u n t f f rp r o f i l e 压缩方案。压缩后的航班c o u n t e r p r o f i l e 可以有很多种可行的形状，m d a 一1 算法用s h i n 算子，在不改变分配给航班的柜台的数量和柜台开放值机的起止时间的荫提下，通过上 中国民航人学颈l 学位论文 下移动分配给航班的柜台来改变航班c o u n t e r p r o f i l e 的形状。放置航班c o u n t e r p r o f i l e 时， 如果无法为一种形状的c o u n t e rp r o f i l e 在甘特图上找至u 合适空白区域，则用s h i f t 算子改 变航班c o u n t e rp r o f i l e 再试一次。 m d a - 1 算法可以为值机柜台配置问题找到可行方案，但是由于航班c o u n t e rp r o f i l e 只有柜台和航班值机时白j 两种信息，无法评估航班c o u n t e rp r o f i l e 对机场服务水准的有 何影响，因此c h u n 再加上等候值机的乘客队列长度作第三维，歼发与之相应的m d a 2 算法。 在由柜台、值机时间和等候队列长度三个变量构成的三维坐标系中，与航班的值机 柜台资源配置方案相应的立体图形被称为c o u n t e rp r o f i l eg l o b 。航班乘客等候办理值机手 续的队列长度与开放的值机柜台数量有关，调整航班值机期间各个时i 日j 段内分配给航班 的值机柜台数量，就能够调整各个时间段内等候队列的长度。m d a 一2 的基本思想是利 用航班乘客抵达机场的模式( a r r i v a lp a t t e r n ) 预测那些分配给航班的值机柜台所能达到 的服务指标，根据服务指标不断地调整值机期间各个时间段分给航班的数量直到预测的 结果不大于预先设定的目标。其过程可以形象地描述成不断的揉捏一团泥块( c o t m t e r p r o f i l e g l o b ) ，使之能完全装到一个固定容积的盒子( c o n s t r a i n t b o x ) 晕。c o u n t e r p r o f i l e g l o b 由知识库的模拟器生成。模拟器自动分析航班的相关信息，比如起飞时间、目的地、 所属航空公司等，由此得到的乘客到达速率和办理值机手续的速率，根据这两个数据算 出航班的c o u n t e rp r o f i l eg l o b 。 2 2 2y a n 的论文 y a h 是文献【l 】的通讯作者( c o r r e s p o n d i n ga u t h o r ) 。文献【l 】研究对象是台湾中正国 际机场( c h i a n gk a i s h e ki n t e m a t i o n a la i r p o r t ) 的值机柜台。由于数量持续增长的航班 使数量有限的值机柜台资源吃紧，为了有效利用有限的值机柜台资源，提高服务水平， 中正国际机场的管理部门提出了采用计算机辅助制定值机柜台配置方案。 中正国际机场的值机柜台多数有两个办理乘机手续的值机窗口( s e r v i c el i n e ) ，少 数有一个值机窗口，每一个值机柜台的值机窗口的租金都一样。机场规定航空公司必须 至少为它们的每一个航班租用五个服务窗口。航空公司每周向机场有关部门提交一份航 班计划。在没有引进计计算机配置值机柜台资源之l j ，中j 下国际机场的职员用人力指派 的方法制定值机柜台配簧方案。工作人员按照“先到先服务”的原则，凭借自己的工作经 验，按照航班起飞的时白j 顺序，根据每一航班分配柜台资源。分给航班的柜台资源与航 班的需求一致，即分配给航班的柜台数量与航空公司为航班申请的数量一致，值机柜台 为航班服务的时间长度与航班值机的时问长度一致。机场规定分到同一个柜台上前后紧 随的两个航班之问有一定的缓冲时间，以应对计划外的突发事件，比如航班延迟、值机 柜台当班人员迟到或临时缺席、值机柜台机器故障、办理乘机手续不顺利导致办理时间 过长等。中正国际机场工作人员根据自己的经验，认为3 0 分钟的缓冲时日j 最合适。中 中同民航人学硕i 学位论史 正国际机场按月制定值机柜台配置方案，实际上由于航空公司每周的航班计划是一致 的。所以只要先制定一周的方案，再把一周的方案扩展，就得到个月的配置方案。 人力手工制定值机柜台配置方案的缺点是效率不高和无法做到系统优化。采用计算 机制定值机柜台可以克服这些缺点。就值机柜台配置方案的系统优化目标和由此得到的 服务水平而畜，乘客、航空公司和机场各有各的衡量标准，如乘客会要求等候办理乘机 手续的时间愈短愈好，航空公司想着降低成本，机场管理部门则想法设法提高值机柜台 资源的利用效率和服务水平，这些标准之间互相关联，互相制约，无法找到能够完全满 足各方要求的方案。因此，最理想的方法是机场管理部门综合考虑各方的愿望。设定一 个可以照顾到各方利益的优化目标。y a h 在文献【l 】中认为，受制于中正国际机场现行的 值机方式和航站楼的内部服务设施的布局，只有旅客总的行走距离和柜台指派的扰动值 是理想的优化目标，其它的目标由于与值机柜台在机场航站楼内的命局关系不大，因而 不是理想的优化目标。y a h 最终建立的0 1 整数规划解法也是以旅客总的行走距离最少 为优化目标，并兼顾柜台指派的扰动值。其中柜台扰动值反映具有相同编号但是不在同 一天起飞的航班分在同一个值机柜台的情况，用变量实际扰动值( a c t u a l i n c o n s i s t e n c yv a l u e ta v i ) 表示。 为了求解满足旅客总的行走距离最短和值机柜台指派扰动值最小这两个条件的值机 柜台配簧方案，y a h 建立五个数学模型。为了建构数学模型，y a h 给出7 个预知信息或 假设： 1 ) 一周内需要值机柜台的航班数量已知； 2 ) 已知航班隶属于哪个航空公司、每个航班所需要的柜台数量和航班的值机时间； 3 ) 每个航班的乘客数量已知； 4 ) 航站楼内的设施布局已知，包括各种服务柜台的布局和那些柜台与值机柜台之间 的距离： 5 ) 乘客从离开航班值机柜台区块到登机离丌机场所要走的平均距离已知； 6 ) 柜台配置扰动值的上限已知； 7 ) 同一值机柜台上前后紧随的两个航班使用柜台的缓冲时间为3 0 分钟。 模型1 是基本的求解模型。其直接列写出来的优化目标是使所有旅客总的行走距离 最少，柜台指派的扰动值虽然也是系统目标之一，但只在模型l 中隐式的表现只由模 型2 求出。由模型1 构造的零壹整数规划算法规模巨大，若机场有1 4 0 个柜台和2 6 0 个 值机窗口，一天有7 0 个航班，则一周有4 9 0 个航班，由模型l 得到8 0 ，0 0 0 个变量和 7 0 ，0 0 0 个约束式。为了减少计算量，y a h 采用启发式方法，相继开发三个互相配合的 启发式模型：模型3 、模型4 和模型5 。在模型3 中引进一个新的变量启发扰动值 ( h e u r i s t i ci n c o n s i s t e n c yv a l u e ，h i v ) 。用以记录某个航班分配到某个区块的值机柜台 上的次数。模型3 忽略a i v 变量的影响，先求出使一天内所有航班乘客总的行走距离最 短的值机柜台配置方案，在此基础上算出各个航班与各个值机柜台区块之日j 的h i v 值。 模型4 在模型3 的基础上，尽量把具有相同编号的航班分到h i v 值最大的相关柜台区块， 中国民航人学硕l 学位论文 由此产生最小h i v 总和值。模型5 得到基于以上模型得到的所有旅客最小行走总距离和 最小h i v 总和值。启发式方法的计算步骤如下 i ) 求解模型3 ，得到每天所有旅客行走总距离最短的值机柜台配置方案 2 ) 从步骤1 ) 中产生的方案中得到各个航班和各个值机柜台区块之间的h i v 值 3 ) 求解模型4 ，得到最小的h i v 总和值 4 ) 求解模型5 ，得到满足步骤3 ) 中算出的最小h i v 总和值的一天值机柜台最终配 置方案。 按照y a n 的方法。当现有的值机柜台资源无法满足某个航班的需求，导致该航班没 有足够的柜台可用时，算法中会添加几个人工柜台分配给该航班。一旦解决方案中有人 工柜台出现，表明此时机场的值机柜台资源已经无法满足同常的航班需求，机场必须添 置新的值机柜台。 虽然y a h 采用了启发式方法，但是当航班数目和值机柜台数目比较大时，算法的计 算量和所需的时间开销仍然很大。按照y a h 的数据，当可用的值机柜台有1 0 5 个，有 1 9 5 个值机窗口，算法为9 5 1 0 0 个航班分配值机柜台资源共花费5 5 3 2 9 分钟。 2 2 3n i c o 的论文 按照其在文献【3 】中的说法，n i c o 研究值机柜台配置问题并非为了解决机场管理部门 的难题，而是出于对于科学研究的兴趣，认为要解决机场值机环节问题必须同时需要随 机方法( 模拟仿真) 和确定性方法( 整数规划) 。 解决值机柜台配置问题的急迫性来源于现实的压力。机场的值机环节面临着值机柜 台资源有限而航班需求巨大的矛盾，问题聚焦在如何充分的利用现有的值机柜台资源为 航班服务。 n i c o 认为解决机场值机环节的困境的方法可以分成两个步骤，第一步是要明确若要 满足某个确定的服务标准，应该分给航班多少值机柜台资源比较合适；第二步是根据第 一个步骤得到的结果制定值机柜台配置方案。 第一个步骤有机地结合动画仿真和排队论各自的优点。从整体上看，值机环节可以 看成是一个排队服务系统。值机柜台是服务机构，航班的乘客是服务对象，采用先到先 服务的规则。在对航班需要多少值机柜台资源进行预测时，排队理论确实可以起到很大 的用处，它可以对值机过程进行的服务指标进行总体预测，可以帮助预先判断一个场景 是否需要作迸一步的模拟仿真，可以对仿真结果进行理论评估，或者对现实世界进行论 证。但是，排队论的应用对系统的特征有特别的要求，排队论适用于稳态系统，应用在 有状态变迁的不稳定系统则效果不佳。而值机环节恰恰有一些不稳定的因素，使值机环 节不能保持在稳定状态，n i c o 为此列举了四种情况：1 ) 旅客到达机场的模式在时间上 是不稳定的，用某个分布模式，如泊松分布，来取代实际到达模式会引起很大的误差： 2 ) 在实际的航班乘客到达模式中，总会存在某些特异的时间段，在这些时间段内到达 中国民航人学颤i 学位论文 机场的乘客数量很稀少，因此如果用平均值来表示完全是不合适的；3 ) 在某些时候。 值机环节的初始状态对值机过程影响很大时；4 ) 值机过程有时问限制时。这四种情况 的存在使值机环节难以单纯用排队论处理，而处理这种不确定的情况正好是模拟仿真方 法的优点。在值机环节使用模拟仿真方法可以一举三得，首先是可以计算航班需要的柜 台时间，其次是计算乘客等候办理乘机手续的时间，第三是可以计算在初始阶段乘客的 等候时间。引入动画技术则是为了观察和监控值机环节的变化、值机环节的动，奁变化产 生的影响和对不同的值机场景进行比较。 对值机环节使用到的值机柜台资源数量进行优化可以分成两步，首先是以满足某项 服务指标为前提，预测单个航班所需要的最少的值机柜台数：然后在基础上找出所有航 班需要的最少的值机柜台数和值机时白j 。 第一个步骤结束后，每一个航班对值机柜台的确切需求就被预测出来，接着就可以 为航班分配值机柜台，也就是进入第二个求解步骤。 值机柜台配置问题是一个n p 完全难题，要求分配给一个航班的值机柜体必须相邻。 相邻约束使得值机柜台配置问题变得复杂，应用简单的配雹规则根本不能得到值机柜台 配置问题的优化解，在此情况下，n i c o 认为整数规划方法是比较好的选择。 n i c o 以使用值机柜台数量最少为优化目标，分三种情况对值机柜台配置问题进行探 讨。第一种情况是在值机过程，航班使用的值机柜台数量固定不变。整数规划方法可以 得到使用值机柜台数量最少的配置方案。第二种情况是在机场值机柜台资源充足的情况 下，按照仿真程序算出的航班需要的最大柜台数给航班分配柜台，如满足让9 0 的乘客 在办理值机手续时等候时间不多于l o 分钟时航班最多时需要7 个值机柜台，则机场给 航班分配固定的7 个值机柜台，即这7 个值机柜台在该航班值机期f 日j 不会被再分配给其 他航班，在航班值机期间，由航空公司自行决定开放或关闭某些值机柜台，这样可以达 到节省值机人员的工作时间和优化值机环节的服务质量的目的，但是需要的柜台总数更