- 1 -
中国科技论文在线
基于最小费用流的航线网络优化问题的分
析与研究
宋薇薇，贾丽娟*
（沈阳航空航天大学民用航空学院，沈阳 110136） 5
作者简介：宋薇薇（1983-），女，讲师，主要研究方向：交通运输
摘要：航线网络是航空公司的立足之本，建立完善的航线网络，对加快航空运输的扩张和促
进社会经济发展方面具有非常重要的作用。本文以东北地区航线网络优化为例，针对东北地
区丰富的旅游资源，众多的支线机场，降低成本，提高乘客出行便利性等来提高航空公司的
效益，从而构建混合整数线性规划模型，使其可以在整个航线网络中实现最低的操作成本；10
采用改进的禁忌搜索算法和最短路径算法求解模型，从而获得东北航线布局方案，并验证了
方案的可行性。实例表明，以东北地区整个航线网络总成本最小为目标对该地区现有的航线
网络进行优化，得到东北地区的航线网络布局优化方案具有一定的现实意义。
关键词：交通运输规划与管理；航线网络；最小费用流；优化
中图分类号：U8 15
The Analysis and Research on Route Network
Optimization Problem Based on Minimum Cost Flow
SONG Weiwei, JIA Lijuan
(Civil Aviation School, Shenyang Aerospace University, Shenyang 110136) 20
Abstract: The route network is the foothold of the airlines, which establishing a perfect route network
will have a very important role in accelerating the expansion of air transport and promoting social and
economic this paper, the optimization of airline network in the northeast region of
China is taken as an example to construct a mixed integer linear programming model for the rich
tourism resources, the numerous regional airports in the northeast region, reducing the cost and 25
improving the convenience of passenger travelling, which the minimum operation cost is realized in the
whole route network. The improved tabu search algorithm and the shortest path algorithm are used to
solve the model, and the layout scheme of the northeast route is obtained and the feasibility of the
scheme is verified. The example shows that the optimization of the existing route network in the region
is the objective of optimizing the total route cost of the whole route network in Northeast China, and it 30
is of practical significance to get the route network layout optimization scheme in Northeast China.
Key words: Transportation Planning and Management;route network; minimum cost flow;
optimization
35
0 引言
随着航空运输业的快速发展，对航空公司航线网络质量提出了更高的要求，各国航空公
司都先后对自身航线网络结构进行了优化调整，以适应并促进航空运输市场的整体发展[1]。
目前，国内外大量专家学者对航线网络优化问题进行研究。戴福青[2]2007年在《单枢纽机场
选址与航线网络规划综合优化》一文中考虑到枢纽机场建设对航线网络的反作用,提出了单40
枢纽机场选址与航线网络规划综合优化问题。为了描述该问题,建立了基于空中交通均衡分
配的成本最优的数学规划模型。王超[3]等 2014年在《终端区进离场航线网络 3D优化方法》
一文中为提高终端空域飞行航线设计的安全经济性与自动化水平,对航线网络 3D 优化问题
进行了研究。针对独立航线的优化问题,采用蚁群算法优化水平方向安全经济性航线;根据终
- 2 -
中国科技论文在线
端空域航线垂直剖面数据,提出一种基于核密度估计的 3D航线垂直剖面优化方法。分析得到45
进离场航线网络优化次序原则,逐步优化各航线,最终实现航线网络的总体优化。Zhang Tao[4]
等 2011年在《Reliability-based route optimization of a transportation network with random arc
capacities and time threshold》一文中介绍了一种基于随机 Petri网的仿真方法，用于基于可靠
性的交通网络优化。容量可以在任何离散或连续分布之后处于随机状态。每个弧的传输时间
也不是固定数，而是根据其当前容量和需求而随机设置。为了解决这个问题，使用随机彩色50
Petri网来建模系统行为。
旅游市场规模进一步扩大。2009年，东北地区将建新机场，改善机场网络布局，机场
数量已经达到 13个。到 2013年，机场数量至少有 20个左右。国内旅游平均年增长率达到
10％，入境旅游和出境旅游的年平均增长率分别为 9％和 8％，人均城市和农村居民在旅游
中的年增长率将超过两倍。根据统计数据得出，2013年东北三省总共接待旅游者 亿人55
次，旅游收入共计 亿元，而东北地区 亿的人口形成了巨大的周边游客源市场，
并且因为气候的差异性，东北地区对南方客源市场具有强大的吸引力[5]。
因此，优化东北地区的航线网络对促进地区经济发展起到一定的作用。
1 航线网络优化模型的建立
在航线网络设计中，航空公司试图使用较少航班来满足市场需求，而且还希望使用较低60
的运营成本，得到较高的占座率，从而获得最大的利润。虽然乘客对高品质的服务充满了期
望，如高飞行频率，更多的直航，更少的飞行时间等，但是，在航线网络设计中，乘客的期
望与航空公司的利润之间存在冲突。因此，为了设计一个合理和有效的航线网络，必须考虑
航空公司和乘客的利益。
UMApHMP [6]是 NP-hard问题，用精确算法虽然能够得到小型问题最优解却难以解决大65
型问题，用贪婪算法等传统启发式方法求解时易陷入局部最优。因此，本文以无容量限制的
多重分派 p-枢纽中位问题(UMApHMP)为研究对象,提出了一种基于改进的禁忌搜索和最短
路径算法的方法,然后通过东北地区航线数据对其进行了检验。
模型特点
为了设计航线网络，航空运输市场做出以下假设： 70
1、航空运输市场中有n个城市，预先给定枢纽城市数为 p个。
2、由于旅客运输的特殊性（本文只考虑旅客运输），且经枢纽城市周转的次数最多 1
次。
3、一个非枢纽城市可以连接多个枢纽城市；枢纽城市之间相互完全直接相连，非枢纽
城市之间既可通过枢纽城市进行周转连接也可直接相连接。 75
4、枢纽城市之间的成本折扣因子为α，非枢纽城市与枢纽城市之间、非枢纽城市之间
的成本折扣因子为β ，且 0<α < β ≤1（且本文满足α +≤β ）。
它将从 n个城市中选择 p个城市作为中心。他们将决定城市之间的连接方式，使网络的
总运输成本最小。
建立航线网络优化模型 80
对于考虑直航的情况，可得到 NSUMApHMP的混合整数线性规划模型：
- 3 -
中国科技论文在线
∈ ∈ ∈∈ ∈
+=
Ni Nj Nk
ijkijkijijij
Ni Nj
ij YQxyQxZMinimize （1）
pH
Nk
k =
∈
（2）
NjiYy ijk
Nk
ij ∈∀=+
∈
,,1 （3）
NkjiHY k
Nk
ijk ∈∀≤
∈
,,, （4） 85
}{ NkHk ∈∀∈ ,1,0 （5）
0≥ijy ， Nji ∈∀ , （6）
0≥ijkY ， Nkji ∈∀ ,, （7）
其中Z为目标函数，
ijij
Ni Nj
ij yQx
∈ ∈
为网络中旅客直航的费用，
ijk
Ni Nj Nk
ijkij YQx
∈ ∈ ∈
为网络中
旅客经枢纽中转的费用；（2）式表示共有 p 个枢纽；（3）式表示任一城市间直航客流量90
比例和中转客流量比例之和为 1；（4）式保证 O-D流如果采用中转方式运输，中转的城市
必须是枢纽，即当某个城市不是枢纽时，没有旅客经该城市周转。
为便于描述问题模型，现将定义的符号及其表示的意义表述如下：
（1） },,2,1{ nN = 表示空运市场中的全部n个城市构成的城市集合；
（2） ijx 表示城市 i到城市 j的 O-D流； 95
（3） ijy 表示从城市 i直飞城市 j的客流量占 ijx 的比例；
（4） ijkY 表示从城市 i流经枢纽城市 k 到城市 j的客流量占 ijx 的比例；
（5） ijq 表示城市 i到城市 j的标准单位运输成本（当 ji, 为枢纽时， ijij qQ α= ；当 ji,
为非枢纽时， ijij qQ β= ）；
（6）
ijkQ 表示从起始城市 i流经枢纽城市 k 到终止城市 j 的单位流量运输成本，得100
kjikijk
qqQ ββ += ；
（7） kH 为指标变量，当城市 k 为枢纽时， 1=kH ，否则 0=kH ；
（8）Z 表示航线网络运营总成本。
2 算法设计
Tube[7]航路概念是由美国 George Mason大学提出的。利用最短路算法进行网络的优化，105
得到最终的 Tube航线网络。
禁忌搜索算法是 1986年 Glover提出的一种现代启发式算法，它是对局部领域搜索的一
种扩展,是一种全局逐步寻优算法。禁忌搜索算法通过引入一个灵活的存储结构和相应的禁
忌准则来避免迂回搜索,通过特赦准则来赦免一些被禁忌的优良状态,从而保证探索的有效
- 4 -
中国科技论文在线
性。由模型 NSUMApHMP可知,当枢纽选定后, NSUMApHMP便转化为求所有起迄城市对间110
的最短路问题。
构造最短路算法
枢纽城市 p个在整个网络中起周转作用，在具体应用最短路算法时，只需迭代 p次即
可。具体如下：假定枢纽集为 { }phhhhH ,,3,2,1 = ，构造图 )','(' NAG = 。其中
{ }nN ,,3,2,1' = ，图 'G 中每条边的长度 ijl 定义为： 当 Hji ∉, 时， ijij ql β= ；当 Hji ∈, 时，115
ijij ql α= ；当 HjHi ∉∈ , 或者 HiHj ∉∈ , 时， ijij ql β= ；令
k
ijd 表示当前的枢纽中转城市
为 k ，从点 i到点 j的最短路长；令
k
ijr 表示枢纽中转城市为 k 时，从点 i到点 j的最短路中
的一条弧的下标。则最短路算法的步骤具体如下：
（1）令 ij
o
ij ld = ， 0
0
=iid ， jd ij =
0
1),,3,2,1,( == knji
（2）对一切 ,1,1 njni ≤≤≤≤ 令 { }111,min −−− += kkjkikkijkij dddd 120
=
−−−−
−−−−
+≤
+>
1111
1111
,
,
k
kj
k
ik
i
ij
k
ij
k
kj
k
ik
k
ij
k
ik
dddr
dddr
k
ijr
若
若
（3）如果 pk = ，终止； 否则，使 1+= kk ，回到步骤②。
经过 p次迭代后，得到求最短航线路径的矩阵 ( )
nn
k
ijrR ×=
ρ ，以及每个城市之间的最短
航线距离矩阵 ( )
nn
k
ij
p dD
×
= ，对于给定枢纽下的最小运输费用可由
∈ ∈Ni Nj
p
ijij dx
（客流量*距离）计
算得到，根据矩阵 pR 通过正向追踪法，可以得到每个城市对间的具体最佳航线路径。 125
选取当前解
根据禁忌长度和特赦准则来选取当前解。
领域结构及其候选解
假定 x为NSUMApHMP的一个可行解,定义 x的邻域为只有一个枢纽和与 x中的枢纽不
同且各城市之间的航线连接由最短路算法确定后而得到的可行解,即某解的一个邻域解可通130
过一个非枢纽和一个枢纽进行单一交换后,再利用最短路算法求得。显然,其可行解的邻域中
共有 p(n-p)个可行解。如此得到的 p(n-p)个邻域解作为产生下一步解的候选解,且下一步的解
为最好的候选解,即指满足特赦准则的禁忌候选解或者是最好的非禁忌候选解。
禁忌对象和禁忌长度
与传统禁忌搜索算法不同的是，本文把枢纽城市和非枢纽城市作为禁忌对象，放入禁忌135
表中，使之相互之间进行交换，除非满足特赦准则, 通过设定禁忌长度来避免迂回搜索，设
定禁忌长度 TL = 7。
特赦准则和停止准则
采取的特赦准则主要包括:(1)若某个禁忌候选解优于当前最好解,则解禁此候选解,并把
它作用当前解和最优解；(2)若禁忌候选解和非禁忌候选解均不优于当前最好解,则选择最好140
- 5 -
中国科技论文在线
的非禁忌解作为当前解。
本文采用的改进的禁忌搜索算法采用的停止准则是运算达到预先设定的最大迭代次数
来中止运算。
算法流程图
算法流程图如图 1所示。 145
图 1 算法流程图
Fig. 1 Algorithm flowchart
3 实例分析
表 1 东北地区主要机场和城市 150
Tab. 1 Northeast airports and major cities
序号 1 2 3 4 5 6 7 8 9 10
城 市 /
机场
沈 阳 /
桃仙
大 连 /
周水子
哈尔滨
/太平
长 春 /
龙嘉
牡丹江
/海浪
延 吉 /
朝阳川
丹 东 /
浪头
佳木斯
/东郊
锦 州 /
小领子
齐齐哈
尔 / 三
家子
表 1显示了选取东北地区 10个主要机场进行航线网络优化。中国东北的航线网络布局
考虑区域机场之间的直航航班，如果我们想获得整个网络的最小总运输成本，最小成本可以
用距离*乘客流量来表示，其中距离为以上 10个机场间的航线距离，乘客流量为以上 10个155
机场的客流量。通过改进的禁忌搜索算法选取枢纽，在枢纽既定的条件下，利用最短路算法
求出各城市对间的最佳航线作为初始解，利用MATLAB编程求解，且各参数取值如下：禁
忌长度 TL=7，连续 7次得到相同解即终止运算。当枢纽个数 p分别为 2，3，4，5，β =，
枢纽间成本折扣因子α 为 时，得到结果见表 2。
160
- 6 -
中国科技论文在线
表 2 计算结果
Calculation results
p , α , β 最小费用 枢纽城市
2,, 3635366 4，2
3,, 3087959 3，2，4
4,, 2793182 3，4，1，2
5,, 2267290 3，2，4，1，6
165
表 2显示了计算结果，最小成本与中心城市数量成反比。当枢纽 p为 2时，枢纽城市
多数情况为为 4、2（长春、大连）；当枢纽 p为 3 时，枢纽城市多数情况为 3、2、4（哈
尔滨、大连、长春）；当枢纽 p为 4时，枢纽城市多数情况为 3、4、1、2（哈尔滨、长春、
沈阳、大连）；当枢纽 p为 5时，枢纽城市多数情况为 3、2、4、1、6（哈尔滨、大连、长
春、沈阳、延吉）。 170
根据表 2的结果，当 p =4，α =，β =时，得到的枢纽城市（哈尔滨、长春、沈
阳、大连）与实际相符合，最小费用为 2793182。利用MATLAB编程，根据改进的禁忌搜索
算法和最短路算法，得到具体航线路径如表 3所示：
表 3 p =4，α =，β = 时东北地区主要机场的具体航线路径 175
When p =4，α =，β =，specific routes to main airports in Northeast of China
优化路径 优化路径 优化路径 优化路径 优化路径
1-2 1-4 1-5 1-7 1-9
1-4-3 1-4-6 1-4-8 1-4-10 2-1
2-3 2-4 2-6 2-7 2-9
2-3-5 2-3-8 2-3-10 3-2 3-4
3-5 3-6 3-8 3-10 3-4-1
3-2-7 3-2-9 4-1 4-2 4-3
4-6 4-3-5 4-2-7 4-3-8 4-2-9
4-3-10 5-1 5-3 5-6 5-8
5-3-2 5-3-4 5-3-7 5-3-9 5-3-10
6-2 6-3 6-4 6-5 6-4-1
6-2-7 6-3-8 6-2-9 6-3-10 7-1
7-2 7-2-3 7-2-4 7-2-5 7-2-6
7-2-8 7-2-9 7-2-10 8-3-1 8-3-2
8-3-4 8-3-6 8-3-7 8-3-9 8-3-10
9-1 9-2 9-2-3 9-2-4 9-2-5
9-2-6 9-2-7 9-2-8 9-2-10 10-3
10-3-1 10-3-2 10-3-4 10-3-5 10-3-6
10-3-7 10-3-8 10-3-9
从表 3航线优化路径可以看出，各具体路径之间由于考虑到客源情况，在实际中，基本
没有通过支线城市进行中转，即选取直达航线。从表 3航线具体路径可得出，理论上应该新
增直航航线分析如表 4所示。 180
- 7 -
中国科技论文在线
表 4 东北地区近期新增航线
Northeast recently added routes
直航城市 优化前 城市名称 简要分析
1-2
1-4
1-5
1-青岛/北京/上海-2
1-青岛/北京-4
1-青岛/北京-5
沈阳-大连
沈阳-长春
沈阳-牡丹江
火车≈5h，交通工具很多，不需通航；
沈阳到长春，丹东，锦州交通都很便利，不需通航；
随着旅游发展，牡丹江作为分流游客的一个支线机
场，沈阳-牡丹江可以酌情考虑直航。
2-1
2-3
2-4
2-6
2-7
2-9
2-北京/青岛/天津-1
2-3
2-北京/青岛/济南-4
2-北京/青岛/上海-6
2-北京/成都/上海-7
2-9（暂无）
大连-沈阳
大连-哈尔滨
大连-长春
大连-延吉
大连-丹东
大连-锦州
火车≈5h，交通工具很多，不需通航；
火车≈10h，且都为旅游城市，已经通航；
交通工具很多，暂缓考虑通航；
大连到延吉，丹东考虑到客源不足，暂缓考虑通航；
大连到锦州火车没有直达，但考虑到客源以及其它交
通工具，酌情考虑通航；
3-2
3-4
3-5
3-青岛/北京/烟台-4
3-青岛/北京/上海-5
哈尔滨-大连
哈尔滨-长春
哈尔滨-牡丹江
由于航空公司考虑运营情况，酌情考虑直航；
交通工具很方便，可以暂缓考虑通航；
火车≈5h，牡丹江为旅游城市，旅游季节可考虑通航；
4-1
4-2
4-3
4-6
4-青岛/济南/北京-1
4-青岛/烟台/北京-2
4-青岛/烟台/北京-3
4-青岛/烟台/北京-6
长春-沈阳
长春-大连
长春-哈尔滨
长春-牡丹江
长春到沈阳/大连/哈尔滨交通工具很方便，不需通航；
火车≈9h，牡丹江为旅游城市，旅游季节可考虑通航；
5-1
5-3
5-6
5-8
5-青岛/北京-1
5-青岛/北京/大连-3
5-青岛/北京-6
5-北京-8
牡丹江-沈阳
牡丹江-哈尔滨
牡江-延吉
牡丹江-佳木斯
考虑到客源不足，以及其它交通工具比较方便，旅游
季节酌情考虑通航；
6-2
6-3
6-4
6-5
6-上海/北京/杭州-2
6-烟台/北京/郑州-3
6-4
6-北京-5
延吉-大连
延吉-哈尔滨
延吉-长春
延吉-牡丹江
考虑客源不足，及其它交通工具较方便，不需通航；
延吉-长春通航
7-1
7-2
7-青岛/北京/成都-1
7-青岛/北京/成都-2
丹东-沈阳
丹东-大连
客源不足，及其它交通工具较方便，暂缓考虑通航；
9-1
9-2
9-杭州/上海-1
9-杭州/上海-2
锦州-沈阳
锦州-大连
交通工具比较方便，不需通航；
10-3 10-北京/上海-3 齐齐哈尔-哈尔滨 考虑到客源不足，且交通工具比较方便，不需通航；
从表 4可知，在优化前绝大多数城市间都是通过北京，青岛和上海进行中转，优点是提
高了航空公司的客座率；缺点是旅客花费的时间增加，枢纽机场的流量压力增加，进而导致
延误增多。因此，若根据表 4的分析，能够将以上各直达航线开通，对于到东北旅游的游客185
而言，他们将会花较少的时间，旅游更多的城市。随着振兴老工业基地基本国策的实施，东
北地区支线航空市场的潜力较大，亟待进行规划和开发。
4 结论
随着老工业基地的振兴，在不久的将来，东北地区的民用机场将会越来越多。东北地区
航线布局的不合理，直接造成了机场定位模糊、航线重叠严重、相互竞争突出、客座率与经190
济效益低下。因此，根据改进的禁忌搜索算法和最短路算法来调整航线网络布局，对构建东
北地区枢纽辐射航线网络起到一定的促进作用。
- 8 -
中国科技论文在线
[参考文献] (References)
[1] 孙少婕.东航航线网络优化研究[J].空运商务.2012(17):12-15.
SUN S on Route Optimization of Eastern Airlines[J]. Airline (17): 12-15. 195
[2] 戴福青 .单枢纽机场选址与航线网络规划综合优化 [J].中国民航大学学报 .
2007,25(1):17-18,28.
DAI F of single hub airport location and route network planning[J]. Journal of
Civil Aviation University of ,25(1):17-18,28.
[3] 王超 ,贺超男 ,刘宏志 .终端区进离场航线网络 3D 优化方法 [J].科学技术与工200
程.2014,14(11):81-85.
WANG C, HE C N, LIU H Method of Route Network for Terminal Area Entry
and Departure[J]. Science and Technology and Engineering, 2010,14(11): 81-85.
[4] 张涛,郭波,谭跃金.基于可靠性的随机弧容量和时间阈值的航线交通网络优化[J],IUKM
2011,2011,143-156. 205
Zhang Tao; Guo Bo; Tan -based route optimization of a transportation network
with random arc capacities and time threshold[J].2011 International Symposium on Integrated
Uncertainty in Knowledge Modelling and Decision Making, IUKM 2011,2011,143-156.
[5] 刘盛楠,王阔. 东北地区旅游产业协同发展探究[J]. 区域经济.2014,(19):141.
LIU S , WANG . Research on the Coordinated Development of Tourism Industry in Northeast 210
China[J].Regional , (19):141.
[6] 柏明国.航空公司航线网络优化设计问题研究.南京航空航天大学.2006.
BO M on route network optimization design of University of Aeronautics
and Astronautics[D].2006.
[7] 王莉莉，刘兵，赵汝斌.基于 FCM的枢纽选址和 Tube航线网络设计[J].中国民航大学学215
报.2014,32(4):1-4.
WANG L , LIU B, ZHAO on hub location with FCM and design of Tube route
network[J]. Journal of Civil Aviation University of ,32 (4): 1-4.
