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

图论最大流理论

在机场登机口分配中的应用教师:张金山联系方式:zjscdut@163.com;主要参考书籍:1.数学建模与数学实验,赵静,但琦2.数学实验,萧树铁3.数学建模方法及其应用,韩中庚4.数学建模导论,陈理荣

数学建模简介

理想与现实什么是数学建模?

数学建模是利用数学方法解决实际问题的一种实践。即通过抽象、简化、假设、引进变量等处理过程后，将实际问题用数学方式表达，建立起数学模型。数学建模所涉及的问题都是现实生活中的实际问题，范围广、学科多，包括工业、农业、医学、生物学、政治、经济、军事、社会、管理、信息技术等方面。

1、问题的描述（背景）随着机场航班日起降架次的增多和乘飞机出行旅客数量的迅速增长，现有的登机口资源正面临着日益严峻的考验。目前，大多数机场通过借鉴其他机场的做法，或根据以往的经验来进行登机口分配和调度，往往导致很多载客数量较多的大中型飞机停靠在距安检或者行李提取大厅较远的登机口；或由于远、近机位登机口航班密度安排不合理，使得每个登机口的航班组合没有达到最优，从而降低了登机口的利用效率。

相关信息

根据某机场一天中部分时段的航班计划，将各航班信息汇总表1所示

航站楼布局登机口、安检区与行李提取大厅的位置

安检区与行李提取大厅不同层但位置相近安检区与行李提取大厅(不)同层但位置不同在保证机场安全、高效运行的前提下，尽可能提高登机口利用效率，体现民航旅客运输的便捷性与舒适性。2、问题分析旅客步行距离最短模型的优化目标与约束条件优化目标1)使进、出港旅客的总步行距离最短，满足旅客对航空运输“便捷性”的需求；2)使现有设施使用效率达到最高，优化资源配置。约束条件1)机型与机位类型相匹配；2)分配登机口时，一个航班必须被分配且仅能被分配至一个登机口；3)应满足最短过站时间和同机位安全间隔时问的要求；4)“航班对”的限制：由于在机场停靠的绝大部分航班既担负着进港航班任务，又担负着出港航班任务，因此，尽量将此类飞机尽可能安排在同一个登机口，降低航空公司运营成本。除此之外，根据各机场的性质和特点不同，还需考虑登机口分配的优先原则、航班过夜、飞机维修等约束条件。3、模型的建立与求解

3.1数据收集与整理利用表l中已知航班信息作为实例分析的数据来源，采用最广泛的航站楼布局形式即假定安检区和行李提取大厅分别位于航站楼的上、下两层，位置近似相同，以此来说明该模型的构建方法和应用过程。3.2优化分配网络模型的构建3.2.1进、出港旅客步行距离最短模型建立与实证分析对于国内大部分干线和支线机场而言，始发或终到旅客所占比例甚多，从长时间的数据统计来看，这两部分旅客所占比例相当，因此，可将其步行距离视为近似相等。以下就是进、出港旅客步行距离最短模型的实施步骤：步骤1按照登机口启用时间的先后顺序，由左至右把每个航班作为网络图上的一个节点，在考虑各种约束条件的基础上，将节点之间进行有向连线，方向为由离港时间早的航班指向晚的，由此形成一个由节点和箭头构成的网络图。不难理解，网络图中从起点到终点的每一条有向路径上的节点都是可以安排在一个登机口上的航班组合，如图3所示。步骤2在图3上，按照各节点的时间顺序对其进行二次编号G(A，B)，G表示航班编号；A表示航班G的前一个航班的编号(若为起始航班，则其编号为本次航班的号码)；B表示航班载客人数的累计，即前一个航班A的实际载客人数与本次航班G的实际载客人数之和。需要注意的是，若A前有两个或多个已编号航班，则择选B最大的那个航班作为G的前一个航班，如图4所示。步骤3将每架航班的人数看成是网络图中的流量，从登机口结束使用的这个网络图的最大流量就表示可以使用同一个登机口的人数最多的航班组合。从终点开始逆向寻找一条至起点航班人数最多的路径，并把这条路径上的航班安排在距安检出口最近的登机口。在图4中，01→04→07即为网络图中旅客流量最大的航班组合，可将这3个航班按照登机口启用先后顺序安排至离安检区最近的登机口。步骤4在调度网络图上去掉已安排过的航班节点及与其相关联的箭线，再从新的起点开始寻找一条至终点航班人数最多的路径，并把这条路径上的航班安排在距安检出口次近的登机口，如图5所示。在图5中，02→03→05→08为网络图中旅客流量最大组合，可将这4个航班按照登机口启用先后顺序安排至离安检区次近的登机口。步骤5重复步骤4，按照上述方法直到所有的航班安排完为止。本例中剩下06号航班，可将其安排至3号登机口。3.3.1算法的复杂度分析如前所述，该模型总运算次数不会超过n，而网络图中航班节点的总数也不会超过n，故总运算次数不会大于n2，即其计算复杂度为o(n2)。3.3算法复杂度分析和最优性证明2.3.2算法的最优性证明为了说明算法是最优算法，现在登机口调度网络图上增加一个虚拟起始节点s和一个虚拟终结节点t，并将虚拟起始节点s与所有起始航班节点用箭头相连，同样，将所有终结节点与虚终结节点t也用箭头相连，如图6所示。由于各航班节点是按时间顺序由左至右排列的，因此，图6所示的网络图是一个具有两端点s和t的无环路网络图。其中每一条从s到t的有向路径，都是可在同一个登机口安排航班组合的可行方案。如果把各节点的航班人数作为以该节点为终点的各箭线的权值，则该网络图就相