图2-2 最短路问题
可见经典的最短路问题只考虑网络每边的长度，可以用如下的数学模型来描述：
minz???dijxiji?Vj?Vi?s?1,?s.t.?xij??xji??0,Otherwise
j?adj(i)j:i?adj(j)??1,i?t?xij?0,1其中，dij是边(i,j)的长度，xij是0-1型的决策变量（路径选择变量），边(i,j)在最短路径上时=1，否则=0。该问题是一个易解问题，经典的标号法是多项式的算法。
但在一些路径最短问题中，不但要考虑选取最短（或成本最小的）路径，而且沿某路径流动时存在资源消耗。例如根据机组适航性要求，每机组在24小时内的飞行小时一般不得超过8小时，即所谓的8-in-24规则。此时，这8小时就成为机组航班环（配对，Pairing）问题的有限资源。确定每个机组航班环是航班网络中的约束最短路问题。再如，在考虑飞机路线时，需要考虑飞机的飞行小时，一般要选择日利用率在给定范围内的航班环作为飞机的可行路线，因此飞机的飞行小时是飞机路线问题的有限资源。
一般地，约束最短路问题可以描述成如下的网络流问题：网络的每条边(i,j)的权重是一对数(dij,sij)，其中dij是该边的“长度”，sij是在该边流动时消耗的资源（可以有多个）。要求网络的始发节点到终止节点的一条满足资源消耗约束的最短路经。如图2-3所示的网络中，从源s到汇t有5条路经，最短路经是：s 5 t，该路径长度是9，消耗资源量13。如果我们限制该流可消耗资源量最大为10，则约束最短路径是：s 1 2 4 t，该路径的长度是11（>9），但资源消耗量等于10，满足资源约束条件。
i1(dij,sij)j2(4,2)),2(2(1,4)),3(6s(2,1)),1(353(5,4)4(2,1)6(6,12)(3,2)图2-3 约束最短路问题
约束最短路问题的数学模型如下：
),3(4t
minz???dijxiji?Vj?V(2-4a) (2-4b)
(2-4c)
i?s?1,?s.t.?xij??xji??0,Otherwise j?adj(i)j:i?adj(j)??1,i?t???sijxij?Si?Vj?Vxij?0,12-3-2 多商品流问题
经典的网络流问题只涉及到一种“商品”(single commodity)，即在网络上流动的只有一种商品。请大家回顾一下单商品流的数学模型是什么样子的。在最小费用流问题中，给定了网络的流量d，以及每边(i,j)的容量uij和单位流费用cij，要求网络流d在网络上的最小费用的分布模式，如图2-4所示。
i(uij,cij)jb=7212(2,(4,2)(2,1)(7,4)),3(6)s(2,3)3,3(5)(5,4)(4,3)44)t(6,12)56
图2-4 最小费用流问题（网络流b=7）
最小费用流问题的数学模型如式（2-5）所示。其中（2-5a）是目标函数，要求总费用最小，(2-5b)是节点的流量平衡约束条件，每个节点具有一个这样的约束条件，(2-5c)是边的容量约束条件，要求每条边的流量不大于容量。
minz???cijxiji?Vj?V(8,(2-5a) (2-5b) (2-5c)
i?s?d,?s.t.?xij??xji??0,Otherwise
j?adj(i)j:i?adj(j)??d,i?t?0?xij?uij;i,j?V生产实际上，我们常常碰见网络上同时流动着多种“商品”的问题，例如在航线网络上
同时流动着各种机型的飞机，一种机型的飞机就是一种“商品”，这样的问题叫做多商品流问题（multicommodity flow problem）。下面我们来为多商品流问题建模。 假设在网络上流动着K种商品，令k=1,2,...,K表示任意第k种商品，在任意边(i,j)上，商品流存在容量限制，各种商品的单位流都是占有一个单位的容量，因此各种商品流之和不能超过该边的容量uij，第k种商品的网络流量（总需求）为d，在边(i,j)上的单位流
kk费用是cij，并进一步假设受到该种商品流容量uij的限制。根据以上假设，多商品流问题的
k数学模型是
kkminz????cijxijk?1i?Vj?VK(2-6a) (2-6b)
(2-6c)
(2-6d)
s.t.?dk,i?s?kxij??xk?ji??0,Otherwise,k?1,2,?,K j?adj(i)j:i?adj(j)??dk,i?t??xk?1Kkij?uij;i,j?Vkk0?xij?uij;i,j?V,k?1,2,?,K可见，多商品流问题是最小费用流问题的直接推广，其中(2-6a)是目标函数，要求总费
用最小，(2-6b)是对每种商品，每个节点都必须满足的流平衡约束条件，(2-6d)是对每种商品，每条边都必须满足的容量限制条件，(2-6c)表示每条边上各种商品流之和不得大于该边的容量。如果网络有n个节点，m条边，那么对于每个商品，这个模型将有m个流变量，因此共有Km个决策变量。而且模型共有Kn个节点的流守恒约束，m个边的总容量约束，以及可能存在Km个各商品流的边容量约束条件。
第三章 机场运行规划
3-1 引言
3-1-1 机场生产组织
机场是组织航空运输生产的重要场所。在这里，飞机起飞、着陆、停放；旅客下机、领取托运行李，办理乘机手续、候机和登机以及转机；到达的货物在这里卸下和转运，离港的货物在这里分理、打包、装箱和装机。这里一片繁忙景象，人来客往，车辆穿梭，如果没有高效的组织，很难想象这里的运输生产可以有条不紊地进行。
机场分为陆侧(Landside)和空侧(Airside)两部分。航站楼和地面到达系统组成陆侧部分，是旅客转换交通模式的地方；跑道、滑行道和停机坪组成空侧部分（也称飞行区），是飞机活动的场所，有时也把终端区甚至进近区域（Terminal Area）划归机场空侧部分。机场组成的示意图如图3-1所示。
旅客运输生产从旅客到达航站楼入口处开始，国内航班旅客通过值机和安检，即可进入候机厅候机，航班出发前20分钟左右开始登机；国际旅客则除了值机和安检外，还需要办理出关手续（包括海关申报、检验检疫和边防检查）。到达目的地机场后，国内航班旅客下机到行李认领厅领取行李，然后转乘陆路交通离开机场；国际航班旅客还必须办理入关手续，首先通过边防检查，然后领取行李，接受卫生检验检疫和海关申报后，转乘陆路交通离开机场。
货物运输生产首先由货代收集货物，分理打包，向航空公司申请货舱舱位，再运送至机坪装机；到达目的地机场的货物下机后运到货站，在货站进行分理，然后用货车运往最终目的地。如果是国际货物还必须办理出入报关手续，通过海关和检验检疫检查。
所以，除了运输途中飞行以外，航空客货运输生产都在机场完成，运输生产的效率主要体现为机场生产组织的效率。上述的生产组织活动将在本章作详细讨论。
机场进近空域离港飞机流进港飞机流跑 道跑道入口等待区快速脱离道空侧等待停机坪滑行道系统停机坪/停机位候 机 楼机场地面出入系统陆侧车辆环行路/停车场离港客货流/车辆进港客货流/车辆城市交通系统 图3-1 机场组成示意图
3-1-2 繁忙机场和航班延误问题
首先定义机场容量：
机场容量指单位时间的生产能力，在不同的功能区，有服务旅客数、服务飞机数和服务行李数等。
机场功能设施理论可达到的最大流量叫做极限容量。在繁忙机场，常常由于容量不足而导致飞机排队等待起飞和降落；旅客排着长队等待值机、安检、领取行李。当航班不能正点起飞时，便产生航班延误。航班延误大小是指实际出发时间与计划出发时间的差值，尽管航班延误的原因有多种，但机场容量不足是重要原因。如果航空公司的机务或机组原因造成了航班延误，则只会影响一个航班，如果机场容量不足，则将造成大面积航班延误。
一般来说，当交通需求超出机场容量时，航班延误定将发生。如果使用平均需求来进行衡量，要特别注意：即使平均需求小于机场容量，航班延误也可能发生。这是因为尽管平均需求不超过机场容量，但瞬时需求（即峰值需求）可能会超过（甚至大大超过）机场容量，造成一段时间内的航班拥堵和延误。
可见交通需求的规模及其分布对航班延误有重要影响。在交通需求不变的条件下，增加机场容量能减少延误。机场容量与交通需求及航班延误之间的关系常可作为确定机场容量的