机场登机口分配 - 副本.doc

四川理工学院毕业论文

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

学 生：彭叶
学 号：09071040115
专 业：数学与应用数学
班 级：应数2009.1
指导老师：熊廷见

四川理工学院理学院

二0 13 年 4 月

四 川 理 工 学 院
毕业设计（论文）任务书

设计（论文）题目：《图论最大流理论在登机口分配中的应用》
学院： 四川理工学院 专业： 数学与应用数学 班级：2009.1 学号： 09071040115
学生： 彭 叶 指导教师： 熊廷见
接受任务时间 2013.03
教研室主任 （签名）　二级学院院长 （签名）

1．毕业设计（论文）的主要内容及基本要求
分析机场登机口在日常运转中的分配不够优化的现状，利用图论中的最大流理论，探讨如何运用这个理论来优化机场登机口的分配状况。解决大多数机场登机口在运输过程中所面临的问题。

2．指定查阅的主要参考文献及说明。
要求参考文献达到十五本及其以上

3．进度安排

设计（论文）各阶段名称
起 止 日 期
1
确定论文题目，接受任务

2
查阅文献资料，完成文献综述和开题报告

3
完成论文初稿

4
修改并完成论文直至定稿

5
论文答辩

摘 要

随着现代生活水平的提高，与物质精神文明的发展，远程旅游的人们越来越多，再加上中外来往交流的越发频繁，跟地区间的往来也很常见，出游人们对现代交通运输的要求越来越高，乘坐飞机出行的游客数量迅速增长。航空公司的运输压力也越发的大，机场航班一再的增加，飞机起降的次数日益频繁，对机场的布置与各机场登机口的设计要求也非常高。现在的登机口的分配面临着很严峻的考验。大多数机场往往通过采用以往常接待游客的方法来接待游客，根本就没办法满足旅客出游效率。现在机场对登机口的分配以及人员调度、应急举措的不完善经常导致许多载客数量较大的飞机停靠在距离安检或者行李取放大厅比较远的登机口，有的还会因为远近机位登机口的航班密度的安排布置上面的不合理，使各个登机口的航班组合不能最大限度的利用起来而使登机口的可用效率降低。没有实现让游客出游达到最便捷的状态。登机口的分配利用并不充分合理。针对这些普遍存在的资源不太优化的现象本文通过图论最大流理论的优越性对机场登机口合理化分配中的应用做了一些探讨。
以进出港旅客的总步行距离最短为主要优化目的，运用图论中的网络最大流理论来解决登机口的分配与怎样优化来保证机场快速运输和处理一些紧急情况保证畅通安全快速的为旅客服务，提高登机口的利用效率，体现民航旅客运输的便捷性与舒适性。

关键词：图论；最大流理论；登机口；网络流；最优化

ABSTRACT

With the development of life level and material and spiritual civilization, people who want to have long distance travel are increasing. Besides, travelers have higher needs on modern transportation due to the frequent communication between countries and regions so that the population of people taking plane goes up rapidly. As a result, the pressure in transport that the scheduled flight increases constantly becomes bigger and bigger. And then, the need to decoration in airport and design of boarding gate is quite high. It is a great challenge to distribute the boarding gates. Most airports always take the traditional measure to greet visitors, which is not satisfied with the efficiency of traveling. According to the allocation of boarding gate, personnel assignment and incomplete emergency measures, now many big planes stays far from security check or luggage placed hall. What’s worse, the available efficiency may go down because of unreasonable allocation boarding gate and density of flight. It is not convenient for visitors to travel with this allocation. In terms of these common phenomenon, this paper use the advantages of graph theory of max-flow to discuss the allocation in boarding gate.
The main purpose is to optimize the whole walking distance for inward and outward travelers by network maximum flow theory used to resolve the allocation of boarding and how to optimize transport and emergency situations. In that way, it can improve the working efficiency, which can show convenience and comfort.

Key words: graph theory; network maximum flow theory; boarding gate; network flow; optimization

目 录
摘 要 3
ABSTRACT 4
第一章 图 6
1.1 图的概念 6
1.2 图的连通性 7
1.3 图论最短路问题 7
1.3.1 从一个顶点v1到一个终点vn的最短路问题 8
1.3.2 Dijkstra算法原理 8
1.3.3 Dijkstra算法步骤： 9
第二章 网络最大流 11
2.1 网络的流 11
2.2 最大流的算法 12
2.2.1算法思想 12
2.2.2 算法步骤 12
2.2.3 总结 13
第三章 图论最大流理论在机场登机口分配中的运用 14
3.1研究与方法 15
3.1.1旅客步行距离最短模型的优化目标与约束条件 15
3.1.2可步行距离最短模型的设置条件 16
3.2 结果和分析 16
3.2.1 优化分配网络模型的构建 16
3.3 结语. 18
参 考 文 献 19

第一章 图
图论是一门应用数学，它的概念和结果来源非常广泛，既有来自生产实践的问题，也有来自理论研究的问题。历史上参与研究图论问题的人，既有许多天才的数学家，也有不少业余爱好者。我们先来看一个著名的例子：
Konigsberg七桥问题
在贯穿古普鲁士Konigsberg城的Pregel河上有七座桥连接两岸及河中的两个小岛。当时困扰当地居民的一个问题是：是否存在一种走法，使走过每座桥恰好一次。虽然当时多数人相信不存在这种走法，但没有人能解释其原因。问题被提到当时在St.Peitersburg的数学教授Euler（1707-1782）面前，他把每块地用一个顶点代替，把每座桥用连接对应顶点的一条边代替，把问题抽象为一幅平面图。为解决这个具体问题，他提出了判定一般图存在这种走法的充要条件，并给出了必要性的证明。这结果发表于1736年，并被公认为第一篇图论文章，他本人也被尊崇为图论和拓扑学之父【1】。
在现实世界的许多情况下，经常会遇到在有限的某几个元素之间有没有存在某种联系或者他们之间又有怎样的联系。假如这些元素之间存在着某种联系而且这种联系还是对称的话，人们就能用“图”来模拟这种存在着的联系，我们就把这种联系能准确直观的反应出。就可以用来解决实际情况中存在的问题，我们也就从图的概念出发，开始对本文在机场登机口会遇到的一些问题的探讨。
1.1 图的概念
对于图的概念我这里先有一个例子来辅助我的定义：
假设某航空公司要为国内几个重要城市提高航空服务，他们拥有一张航空路线示意图，假设两个城市之间又该航空公司的直达航班，那么航空线路图上就会有一条连接两个城市的线，那么我们把这些具体的城市名称取消掉，剩下的这个模型就是我们需要研究的图。代表城市位置的点就是图论中所说的顶点。那些连接各个顶点之间的线就叫做图的边，旅客乘坐该航空公司的航班能否从一个城市也就是顶点到达另一个城市或者另一个顶点之间的转换，这就是图论中的图的连通问题。如果我们再在图的边上标上一个正实数来表示两个相应城市之间机票的票价，这样的图就被称为赋权图。我们要从一个城市乘该航空公司的班机到另外一个城市，怎样乘坐飞机使所花的票价最低。实际上这就是图论中求最短路的问题。

图 1.1
接下来这里就给出图的概念
图G=(V(G),E(G))是由元素被称为顶点的一个有限非空集连同被称为边的图的不同顶点有限无续对集（可能是空集）组成。 V(G) 称为G的顶点集，而E(G)称为G的边集。
一个图G的顶点集的顶点个数称为G的阶（如上图，它是一个八阶的图），用p(G)或简单地用p来表示，而它的边集的基数通常称为G的大小，用q(G)或q来表示。一个(p,q)图就是阶为p，大小为q的图。
1.2 图的连通性
对于图G的两个顶点u和v，如果在G中存在一条路，记为(u,v)路，则称u和v是连通的。如果一个图的每一对顶点都至少有一条路连接，则称该图是连通图；否则称为非连通图或分离图。G的每一个最大的连通子图称为一个连通分支。
图1.2.1 连通图

图1.2.2 非连通图

定理1.1 如果G是具有n个顶点的连通图，则G中至少有n-1条边(n≥2)， 也就是说，在一个具有n个顶点n-1条边的连通图中，如果删去任意一边，图便不通了，我们称这样的图为最小连通图【2】。
证明：对顶点个数n用归纳法。当n=2时，若图连通，则两顶点至少有一条边相连，即结论成立。假设当n=k时结论成立.
考察n=k+1的情形。首先证明，如果边数m＜n，则图G中至少有一个顶点的度为1，这是因为，如果对于V中的任意顶点v都有d(v)≥2,则2m≥2n，即m≥n，这与m＜n矛盾。于是证明了，如果m＜n，则必有顶点u，使d(u)=1。现在从G中删去顶点u及其锁关联的边，得到一个具有k个顶点的连通图。由归纳假设知该图至少有k-1条边，再将u及其关联的那条边添加回去，则恢复原图G。于是它有k+1个顶点，至少有k条边。如果边数m≥n，而n=k+1，则m≥k+1＞k，结论也成立。故命题对n=k+1时成立，由数学归纳法，定理2.1证完。
1.3 图论最短路问题
在图论中最短路问题是图论应用的基本问题，很多实际问题如线路的设计问题，运输分配，运输网络最小费用流等诸如此类的问题都可以通过建立最短路问题模型来求解。最短路问题通常都是在赋权图中讨论的，本质上是网络流问题的一种特殊情况。
所谓最短路问题就是要在赋权图G=(V,E)中指定的一对顶点vi、vj间众多的线路中找到一条权和最小的路。这样的路称为从vi到vj的最短路 。
最短路问题的讨论一般有几种类型：
（1）两指定点之间的最短路；
（2）图中各对定点之间的最短路；
（3）某指定点到其他所有顶点之间的最短路；
（4）两个指定点之间通过某些指定点之间的最短路；
（5）第二，第三……第n条最短路等问题。
1.3.1 从一个顶点v1到一个终点vn的最短路问题
解决该问题的一个较好方法是由Dijkstra于1959年提出的算法，它不仅求出从v1到vn的最短路，实际上还求出了从v1到其余各顶点的最短路。
在叙述Dijkstra算法以前，我们给出有助于说明这个算法的一些基本事实。设u0是一个连通赋权图G的给定顶点，S为V(G)的一个包含u0的子集且=V(G)-S【3】。u0到的距离定义为
d(u0,)=.
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。
1.3.2 Dijkstra算法原理
首先，引进一个辅助向量D，它的每个分量D表示当前所找到的从始点v到每个终点vi的最短路径的长度。如D[3]=2表示从始点v到终点3的路径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为：若从v到vi有弧，则D为弧上的权值；否则置D为∞。显然，长度为 D[j]=Min{D | vi∈V} 的路径就是从v出发的长度最短的一条最短路径。此路径为(v，vj)。 那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是vk，则可想而知，这条路径或者是(v，vk)，或者是(v，vj，vk)。它的长度或者是从v到vk的弧上的权值，或者是D[j]和从vj到vk的弧上的权值之和。 一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v，x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的最短路径的长度必是D[j]=Min{D | vi∈V-S} 其中，D或者是弧(v，vi)上的权值，或者是D[k](vk∈S)和弧(vk，vi)上的权值之和。迪杰斯特拉算法描述如下： 1）arcs表示弧上的权值。若不存在，则置arcs为∞（在本程序中为MAXCOST）。S为已找到从v出发的最短路径的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点vi可能达到的最短路径长度的初值为D=arcs[Locate Vex(G，v),i] vi∈V 2）选择vj，使得D[j]=Min{D | vi∈V-S} 3）修改从v出发到集合V-S上任一顶点vk可达的最短路径长度。
1.3.3 Dijkstra算法步骤：
1. 初使时令 S={V0},T={其余顶点}，T中顶点对应的距离值。若存在<V0,Vi>，d(V0,Vi)为<V0,Vi>弧上的权值；若不存在<V0,Vi>，d(V0,Vi)为；
2. 从T中选取一个其距离值为最小的顶点W且不在S中，加入S；
3. 对其余T中顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值缩短，则修改此距离值；
4.重复上述步骤2、3，直到S中包含所有顶点，即W=Vi为止。
例1.如下图所示赋权图G，求从顶点v1到v11的最短路。
图 1.3.1

（1） 给顶点v1标p标号0，并用方框把0框起来，给与顶点v1邻接的顶点v2，v3，v4分别标上T标号，d(v2)=l12=2，d(v3)=l13=8,d(v4)=l14=1.其余顶点的T标号均为，并把它们分别用圆圈圈起来，如下图。
图 1.3.2

（2）在所有的T标号中取最小者：d(v4)=1，把v4的T标号改成P标号，并用方框框起来，重新计算其它各顶点的T标号：
与顶点v4邻接的顶点是v3和v7，由
min{d(v7),d(v4)+l47}=min{,1+9}=10
min{d(v3),d(v4)+l43}=min{8,1+7}=8
故将顶点v7的T标号修改成10，顶点v3的T标号仍为8，与v4不邻接的顶点的T标号仍为，如下图。

图1.3.2

图 1.3.3

（3） 重复上面的做法，直到所有顶点都标上P标号，如下图。
图 1.3.4

从上图可知，v1到vi（i=2,3，……，11）各顶点的最短路长分别是2,7,1,3,6,9,5,11,10,13，上图中的粗线表示v1到vi（i=2,3，……，11）的最短路。
我们已经了解到，图论起源于一系列孤立的，彼此之间鲜有联系的结论；休闲娱乐的结论和完全数学的定理都一样地为这门科学的发展发挥重要作用。早期图论教科书的作者都喜欢总结许多已有的结论，同时也展望下一步的发展方向【4】。在很大程度上，图论的发展受助于对一些听起来简单但解决起来非常困难的问题的无数次尝试，比如我们这里要研究的图论最大流理论在机场登机口分配中的运用的话题。

第二章 网络最大流
高速发展的现代社会几乎是在依靠着各种各样的网络系统来连接管理控制的，所以对网络从数学的角度上去进行分析研究已成为一项非常重视且重要的探讨课题，近些年来随着各大网络的飞速发展，对网络最大流问题的研究也在不同程度上取得了很大的进步。根据网络最大流的现状，存在的一些问题和算法做了一些借鉴和分析。
2.1 网络的流
设N(V,A)是一个有向的图，满足：
（1）V中有两个顶点子集X和Y, X中任意一个顶点的入度为零，Y中任意一顶点的出度为零；
（2）弧集A上定义一个非负函数U,则称N为一个网络。
X中的顶点称为源，Y中的顶点称为汇，既非源又非汇的顶点称为中间点。函数U称为N的容量函数，容量函数在弧a=(i，j)上的值称为弧的容量，记为u(a)=u(i,j)。一般地，u(i,j)≠u(j,i)。一条弧的容量可以看作某种物质或信息沿着这条弧所能输送的最大速率或看作输送的最大数量【5】.
在网络流图N中，如果每条边eij都给定一个非负实数fij，满足
①、fij≤cij，eij∈N；
②、=，i≠s，t；
③、==w。
那么这一组fij就叫做该网络的容许量，w称为它的流量。在网络N的一个容许流分布f里，满足fij=cij的边称为饱和边，否则是非饱和边。如果一个容许流分布使得网络的流量w0为极大，即
=max，
就说w0是网络的最大流。
2.2 最大流的算法
2.2.1算法思想
在求解网络最大流的一个有效方法就是标号法。其基本思想是从某个可行流出发，若网络图中没有给定可行流，则可以设为零流或按可行流的条件给定，用给顶点标号的方法来构造，在标号过程中，有标号的顶点表示是图中的点，没有标号的点表示不是图中的点，一旦顶点有了标号，表明找到了一条增广链，对此增广链上的流进行调整，对调整后的可行流重新进行标号，试图寻找新流的增广链。如此反复下去，如果标号过程进行不下去，即vt得不到标号，则说明不存在增广链，也就说明已经得到了最大流，并且同时得到一个最小截集。
2.2.2 算法步骤
寻求网络最大流的标号法一般包括两个步骤：标号过程和调整过程。
2.2.2.1 标号过程
在标号过程中，网络图中的点分为两部分，即标号的点和未标号的点，标号的点又分为已检查的点和未检查的点。每个标号vj的标号包括两部分，即第一个标号表明vj的标号是从哪一点得到的，其中“+”是表示vj的标号是通过前向孤(vi，vj)所得，“-”表示vj的标号是通过后向孤(vi，vj)所得，以便于找出增广链；第二个标号是为确定增广链的调整量用的。具体标号过程如下：第一步：给出发点vs标上(0,+),这时vs是标号而未检查的点，其余的点都是未标号点。第二步：取一个标号而未检查的点vi，对一切未标号的点vj，按以下规则处理：①若孤(vi，vj)A，vj未标号，且fij≤cij，则给vj标号(-vi,l(vj)) ，其中l(vj)=min(l(vi),(cij-fij))。若孤(vi，vj)A，vj未标号，且fij＞0，则给vj标号(-vi,l(vj)) ，其中l(vj)=min(l(vi),fij)。这时，vj成为标号而未检查的点。第三步：重复第二步。一旦vt被标上号，即表示得到了一条从vs到vt的增广链u。转入调整过程；若所有标号都已检查过了，vt不能得到标号，而且不存在其他可标号的顶点时，算法终止，这时的可行流就是最大流。
2.2.2.2 调整过程
第一步：按vt及其他点的第一个标号，利用“反向追踪”的办法，找到增广链u。如设vt的第一个标号为vk，则孤(vk，vt)是u上的孤，接下来检查vk的第一个标号，若为vi，则找出(vi，vk)，再检查vi的第一个标号，依此类推，直到vs为止。这是被找出的链即为增广链。第二步，调整增广链u上的流量。令调整量=l(vi),即vi的第二个标号。①当(vi，vj)u+时，=fij+②当(vi，vj)u-时，=fij-(vi，vj)u时，=fij。这样就得一个新的流。第三步：去掉所有标号，对新的可行流重新进行标号过程。
2.2.3 总结
网络最大流问题的应用是一项十分有意义的研究工作。对于实际问题中寻求网络最大流解法，可以帮助我们很快的解决问题。在下一章节中，我们就将它运用到机场登机口的分配之中。

第三章 图论最大流理论在机场登机口分配中的运用
为提高登机口的利用率、提升航空旅客出行的便捷性与舒适性，提高机场的实行效率及航空公司的运营效益，在图论中网络最大流理论的基础上，将旅客步行距离、机场资源运行效率、飞机最短过站时间、航班对，机型等作为约束条件，考虑航站楼布局、始发/终到及中转站旅客数量等因素对登机口分配结果的影响，建立旅客登机口分配的优化网络模型，并对该算法的复杂度和最优化进行分折和证明。最后，运用实例来验证该方法在缩短旅客步行距离和提高机场运行资源利用率方面的可行性，该算法还可用于飞机停靠位的优化安排。
随着机场航班日起降架次的增多和乘飞机出行旅客数量的迅速增长，现有的登机口资源正面临着日益严峻的考验。目前，大多数机场通过借鉴其它机场的做法，或根据以往的经验来进行登机口分配和调度，往往导致很多载客数量较多的大中型飞机停靠在距安检或者行李提取大厅的较远的登机口；或由于远、近机位登机口航班密度安排不合理，使得每个登机口的航班组合没有达到最优，从而降低了登机口的利用效率。
对于中国大多数中小型机场来说，由于航班日起降架次相对较少，到离港时间相对分散、故在机场运行资源，分配在优化问题研究时，学者们多将目光集中在停机位资源优化和分配问题上，而较少考虑登机口的分配和调度优化方法。南京航空航天大学的王志清等人将图论运用到登机口分配问题中，提出旅客登机口调度优化网络模型，具有一定的创新性，模型假设进、出港旅客步行距离基本相等，没有考虑中转旅客对登机口分配的影响【6】。南京航空航天大学的曹燕在其硕士学位的论文中利用表上做法对登机口分配模型进行了考虑，但直观性不强【7】。中国民航飞行学院文军等人将图着色模型应用到机位分配中，使图论的思想在资源资源分配中得到运用【8】。但在考虑登机口分配问题时，由于近机位登机口和近机位一一对应，因而可以用机位分配与优化模型来模拟登机口的分配；而远机位登机口具有一定的特殊性，对于旅客而言，登机口与机位是一一对应，因而可以用机位分配与优化模型来模拟登机口的分配；而远机位登机口具有一定的特殊性，对于旅客而言，登机口与机位是一一对应的关系，但从空间分布上来看，其可以使一个或几个登机口对应一个或多个机位的设置形式，也就是；“一对多”或“多对多”问题，此时若再使用停机位的分配与优化方法来解决登机口的分配就不合理了。
近几年，民航客运量每年都有大幅增加，大型机场相继出现了候机楼紧张的问题，随着候机楼的面积不断扩大，登机口机位也相应增多，这种发展在满足了旅客快速增长的同时，也使得旅客从安检进入相应候机区的距离增加，候机楼内的步行时间拉长，削弱了民航运输的“便捷”程度【9-10】，在枢纽机场，这一问题尤为突出【11】。
本文以进、出港旅客总的步行距离最短为主要优化目标，运用图论中的网络最大流理论来解决登机口的分配与优化问题，在保证机场安全、高效运行的前提下，尽可能提高登机口利用效率，体现民航旅客运输的便捷性与舒适性。
3.1研究与方法
3.1.1旅客步行距离最短模型的优化目标与约束条件
3.1.1.1优化目标
登机口调度优化原则是使旅客的步行距离最短【12】，而通过优化可以达到两个目的【13-14】：
⑴使进、出港旅客的总步行距离最短，满足旅客对航空运输“便捷性“的需求；
(2)使现有设施使用效率达到最高，优化资源配置。
3.1.1.2约束条件
⑴机型与机位类型相匹配；
分配登机口时，一个航班必须被分配且仅能被分配至一个登机口；
⑶应满足最短过站时间和同机位安全间隔时间的要求；
⑷“航班对”的限制：由于在机场停靠的绝大部分航班即担负着进港航班任务，又担任着出港航班任务，因此，尽量将此类飞机尽可能安排在同一个登机口，降低航空公司运营成本。
除此之外，根据各机场的性质和特点不同，还需要考虑登机口分配的优化原则、航班过夜、飞机维修等约束条件。
3.1.2可步行距离最短模型的设置条件
3.1.2.1假设条件
假设某机场有m个可用登机口，当日有n个航班，每个登机口的启用和停用时间、每次航班的载客人数均已知。根据机场一天中部分时段的航班计划，将各航班信息汇总如表1所示。
表3.1 某机场一天中部分时段航班信息汇总表
航班编号
登机口启用时间
登机口停用时间
实际载客人数/人
01
07:30
08:45
245
02
07:45
08:25
130
03
09:00
09:45
140
04
09:10
10:15
310
05
09:50
10:35
120
06
10:00
10:45
110
07
10:55
12:00
350
08
11:00
11:45
145

3.1.2.2航站楼布局对登机口分配的影响
当登机口位置布局已知，则安检区和行李提取大厅的位置将会直接影响到进、出港旅客步行距离的长短。这里所讲的航站楼布局，主要分为两种：一是安检区与行李提取大厅位于航站楼上、下两层中基本相同的位置；二是安检区与行李提取大厅位于航站楼上、下两层或同层中不同位置。
（1）安检区与行李提取大厅不同层但位置相近
对于大部分机场而言，进、出港旅客总人数总体来讲近似相等，对于下图这种设置方式，虽然进、离港旅客的行走路径不同，但一般情况下， 在进行登机口优化分配过程中可将进、出港步行距离视为相等，在进行登机口分配时，需按照航班实际载客人数，尽量将人数较多的航班安排在靠近安检区的登机口。

（2）安检区与行李提取大厅(不)同层且位置不同
对于某些中、小机场，其安检区与行李提取大厅采用同层或分层且相隔较远的方式设置，在这种情况下，应根据航班人数，结合其它限制条件进行登机口分配。

3.2 结果和分析
本文利用表1中已知航班信息作为实例分析的数据来源，采用最广泛的航站楼布局形式，即假定安检区和行李提取大厅分布位于航站楼的上、下两层，位置近似相同，一次来说明该模型的构建方法和应用过程。
3.2.1 优化分配网络模型的构建
3.2.1.1进、出港旅客步行距离最短模型建立与实证分析
对于国内大部分干线和直线机场而言，始发和终到旅客所占比例甚多，从长时间的数据统计来看，这两部分旅客所占比例相当，因此，可将其步行距离视为近似相等。以下就是进、出港旅客步行距离最短模型的实施步骤：
步骤1 按照登机口启用时间的先后顺序，又左至右把每个航班作为网络图上的一个节点，在考虑各种约束条件的基础上，将节点之间进行有向连线，方向为由离港时间早的航班指向晚的，由此形成一个由节点和箭头构成的网络图。不难理解，网络图中从起点到终点的每一条有向路径上的节点都是可以安排在一个登机口的航班组合，如图3所示。
图3 登机口分配的网络图

步骤2 在图3上，按照各节点的时间顺序对其进行二次编号BG（A，B），G表示航班编号；A表示航班G的前一个航班的编号（若为起始航班，则其编号为本次航班的号码）；B表示，航班载客人数的累计，即前一个航班A的实际，载客人数与本次航班G的实际载客人数之和。若A前有两个或多个以编号航班，则选择B最大的那个航班作为G的前一个航班，如图4.

图4 航班的二次编号

步骤3 将每架航班的人数看成是网络图中的流量，从登机口结束使用的这个网络图的最短流量就表示可以使用同一登机口的人数最多的航班组合。从终点开始逆向寻找一条至起点航班人数最多的路径，并把这条路径上的航班安排在距安检出口最近的登机口。在图4中01→04→07即为该网络图中旅客流量最多的航班组合，可将这3个航班按照登机口启用先后顺序安排至离安检区最近的登机口。
步骤4，在调度网络图上去掉已经安排过的航班节点即及其相关联的箭线，再从新的起点开始寻找一条，至终点航班人数最多的路径，并把这条路径上的航班安排在距安检出口次近的登机口，如图5所示。在图5中，02→03→05→08为网络图中旅客流量最大的航班组合，可将这4个航班按照登机口启用先后顺序安排至离安检区质近的登机口。
因为各航班节点是按时间顺序安排的，因此网络中不存在环路，所以下图所示的网络图是一个具有两端点的无环路网络图。其中每一条从起点到终点的路线，都是在一个登机口安排航班次序的可行方案。如果把各节点的航班人数作为以该节点为终点的各箭头的权值，那么该网络图就相当于一个双代号计划网络图，而上面的算法等同于在此双代号网络图中寻找从起点到终点的最大权值路线的算法【15】。

步骤5 重复步骤4，按照上述方法直到所有的航班安排完为止。本例中剩下06号航班，可将其安排到3号登机口。
3.3 结语.
从上述实例，我们可以看出，利用图论最大流理论，我们可以非常方便，快捷的将登机口利用起来，也可以最大可能的缩小旅客的步行距离，让更多的旅客对机构的服务感到满意。
在实际操作中，该方法非常简单，可以提高登机口的利用率，缓解机场适行设施设备供需矛盾、节约机场的运营和建设成本，降低航空公司的运行成本等方面都有一定的研究价值。

参 考 文 献

【1】孙惠泉.图论及其应用.北京：科学出版社，2004:1
【2】刘缵武.应用图论.长沙：国防科技大学出版社，2006：9.
【3】 蒋长浩.图论与网络流.北京：中国林业出版社，2001.7:14
【4】 范益政，汪毅，龚世才，朱明.图论导引.北京：人民邮电出版社，2007.9:337.
【5】刘缵武.应用图论.长沙：国防科技大学出版社，2006:130.
【6】王志清，商红岩，宁宣熙.机场登机口优化调度算法及实证【J】.南京航空航天大学学报，2007,39（6）：819-823.
【7】 曹燕.民航运输旅客流程的优化研究.[D].南京：南京航空航天大学，2005.
【8】 文军，李冰，王清蓉，等.机场停机位分配问题的图着色模型及其算法[J]，系统工程理论方法应用，2005,14（2）：136-140.
【9】 王志清，吴桐水 ，宁宣熙.实施“便捷工程”促进民航发展[J].中国民用航空，2003（3）：16-20.
【10】 王志清，欧阳杰，宁宣熙.航空运输便捷性优化问题研究[J].管理世界，2006（6）：147-148.
【11】 McLay P.Aisling Reynolds-petition between airport terminals:the issues facing Dublin airport[J].Transportation Research Part A:Policy and Practice,2006,40(2):181-203.
【12】 亚历山大T.韦尔斯.机场规划与管理[M].赵宏元译.北京：中国名航出版社，2004:150.
【13】Su Y Y.Srihari K.A knowledge-based aircraft gate assignment advisor[J].Computers and Industrial Engineering,1993,25(2):123-126.
【14】Bihr R.A conceptual solution to the aircraft gate assignment problem using 0,1 linear programming[J].Computers and Industrial Engineering,1990,19(3):280-284.
【15】 宁宣熙.运筹学实用教程[M].北京：科学出版社，2002:231-239.

22