中枢辐射式航线网络分阶段航线决策研究

牟德一，王攀宇

(中国民航大学理学院，天津 300300)

航线网络的发展经历了线性航线(liner)，城市对航线网络(city to city)和中枢辐射式航线网络(hub to spoke).其中，中枢辐射式航线网络是随着航空运输业不断发展，竞争程度不断加剧的情形下产生的.较大的航空公司为了在竞争中获得有利的地位开始追求机队和航线的规模经济.这样的发展逐步形成了枢纽机场.他们将周边机场的旅客和货物利用中小型飞机汇集到枢纽机场，再将这些旅客和货物利用大型飞机运送至其他枢纽机场.这样辐射机场与枢纽机场形成了供给与被供给的关系.为了更好的发挥这种关系，减少衔接和等待时间航空公司多采用“到离航班群”设置模式，从而形成了航班波.这样就增加了高峰期枢纽机场的压力，延误的几率大大增加.张军、都业富［1］应用规模经济性理论，分析航空公司在不同需求特征条件下中枢辐射式航线网络的实用性，并说明了当航空运输需求大于MES时，中枢辐射式航线网络会出现报酬递减的现象.姜涛、朱金福［2］通过对混合航线网络的研究发现，适当的在非枢纽城市之间开辟直达航线能够使是航空公司的利润进一步增加.文献［3］通过建立多目标的航线网络优化模型来使总利润最大化.

航线网络设计是航空公司优化的核心问题.其优化的好坏关系到后续的诸多优化.赵桂红［4］分析了不同的航线网络对成本、服务要求和市场份额带来的影响，从而得出中国民航的航线网络应当将轮辐式航线模式和减轻枢纽城市压力航线模式结合起来的结论.

对中枢辐射航线网络优化设计的研究大体可分以下三步:

第1步，确定枢纽机场的位置与数量.

第2步，确定枢纽机场与非枢纽机场以何种方式连接.

第3步，对连接好的各条航线进行运力分配，以使整个航线网络成本最低或收益最大.

针对第一步的研究已经很多［5－7］.鉴于我国已经基本形成了以北京、上海和广州为枢纽机场的格局.因此本文针对第二步的内容进行研究.在选取了枢纽机场后，根据具体的需求和成本的相关数据把确定性的中枢辐射航线网络设计问题转化为最短路径进行解决［8－9］.姜涛［10］等人针对需求和成本具有不确定性的航线网络优化设计问题进行了研究，将开辟航线的费用考虑在内，建立了严格的无容量限制的多分配中枢辐射航线网络鲁棒优化模型.由于上述模型的求解都采用最短路径算法.而该算法的时间复杂性并不好.我们要设计的非严格的中枢辐射式航线网络通常涉及很多城市，再加上对于解的整数要求更加大了计算的时间.因此，本文在想构造一个严格的中枢辐射航线网络的基础上，针对影响航线选择的诸多因素，采用多属性决策法得出最适合开通的航线的排序.由决策者根据排序进行航线选择.这样既减轻了算法在时间复杂性的负担又有设计出了能减轻枢纽机场压力的非严格中枢辐射式航线网络.

1 航线选择的方法

1.1 构造严格的中枢辐射航线网络

1)相关符号说明

N:某航空公司运营 n个城市的全体，其中︱N︱=n.

H:枢纽机场的全体，其中H⊂N，︱H︱=p.

Cij:经过航线(i，j)运送一个单位客流的成本，可以有 Cij≠Cji.

Wij:从城市i到城市j的客流量.

A:航线的集合，(i，j)∈A .

航线决策模型:

目标函数(1)是使总的运输成本最小.约束条件(2)是流量守恒方程.约束条件(3)保证了只有航线(i，j)开通时才有流量通过.约束条件(4)保证了非枢纽机场之间不能连通.约束条件(5)保证枢纽机场完全连通.

2)算法设计

由于在求解优化问题上禁忌搜索算法得到了广泛的认可，我们提出了一个关于航线选择的禁忌搜索算法的设计思路.上述模型考虑是严格的中枢辐射航线网络的设计问题，因此每一个非枢纽节点只能连接到一个枢纽节点上.对于旅客流量较大的节点更适合直接连接距离它较近的枢纽节点，这样从该节点出发的运输距离很可能会缩短;而对于旅客流量相对较小的节点，旅客目的地分布的随机性较大，连接到最近的枢纽并不一定使总运输距离最短.因此实际的具体思路如下:

第1步:确定初始状态.把非枢纽节点先连接到最近的枢纽节点上，构成初始的航线网络，并计算出此时总成本F0.

第2步:从具有最小旅客流量的非枢纽节点n1开始，每一个非枢纽节点有两次在分配的机会.第1次是把该非枢纽节点非配给离它第二近距离的枢纽节点P'.第2次是分配给倒离客流量最大的节点较近的节点n'.如果n'就是离他第二近距离的枢纽，则不用进行第2次尝试，如果n'是非枢纽节点并且与n1连接到不同的枢纽节点上，则连接到与n'相连接的枢纽节点.如果最后计算值比原方案要低，则保留新的分配方案，否则维持原方案.如果所有的非枢纽节点都已经遍历，则计入第3步.

第3步:如果与某枢纽连接的非枢纽节点集合的最佳方案比原方案要好，则返回到第2步.否则停止搜索.

本文选取国内15个大中型城市作为某航空公司运营城市的全体.分别是北京，上海、广州、沈阳、乌鲁木齐、西安、长沙、成都、海口、杭州、昆明、南京、武汉、厦门、郑州.根据我国实际情况，以北京、上海、广州为枢纽机场，其他12个城市为非枢纽机场.根据文献［11］中的相关数据.得出以严格的中枢辐射航线为框架的航线网络.我们开通了北京－上海、北京－广州、广州－上海、北京－沈阳、北京－乌鲁木齐、北京－西安、北京－郑州、上海－南京、上海－武汉、上海－杭州、广州－成都、广州－厦门，广州－长沙、广州－海口、广州－昆明.这样我们用15条航线把15个城市连接起来.但这样的航线网络会产生很大的旅客延误成本，同时，航班波的出现会给枢纽机场造成很大压力.为了解决上述问题，综合考虑了影响航线选择的因素，采用多属性决策法选择出需要进一步开通的航线.

1.2 加性加权法构造航线

影响航空公司航线决策的因素有很多，秦汉轩，程希骏［12］根据航空公司长期经营的经验，对影响航线决策的各种因素进行了分析.并确定了以下5个因素进行航线决策.分别是中长期市场需求量(yi1)、短期平均客座率(yi2)、竞争力(yi3)、成本票价比(yi4)、对航线网络的影响(yi5).

根据文献［13］所提供的方法确定各因素的权重.通过成对比较各因素的权重的重要性.用本征向量法，把各因素两两比较的结果聚合起来以确定各因素的权重.对上述5个因素进行专家评分，两两比较后得到矩阵A.

再由本证向量法我们可求得权向量wT=［0.22 0.39 0.25 0.09 0.05］.

把各条待决策航线按照上述的5个因素和收集的相关数据［11］构造一个n行5列 的决策矩阵Yn5.再与权向量wT相乘后得到相应各种航线的加权和的值，按所得值的大小进行排序，排序在前的优先开通.针对上述15个城市应用该方法进行了航线决策.对于已确定的开通的15条航线以“1”来表示.因此可得到各条航线上的加权和，见表1.

表1 15个城市间的航线权重数值

由表1可知，分值最高的航线为广州－杭州，则该航线为最适宜开通的航线.相反，乌市(乌鲁木齐)－厦门航线得分最低，为最不适宜开通的航线.决策者可以根据航空公司剩余的运力情况选择所要开通的航线.如果运力充足可以先找到盈亏平衡的航线则分值排在该航线以前的航线以前的航线都可以开通.本文选取了前25条航线，构造成了可以有效减轻枢纽机场压力的非枢纽航线网络，显然成都－昆明、海口－郑州航线的开通可以有效减轻广州机场的压力.而西安－杭州的航线的开通则可减轻上海机场的压力.与此同时，该方法可操作性强，便于航空公司运用.

2 结语

中枢辐射式航线网络的航线决策一直是航空公司关注的热点问题.对于我国而言，设计出既符合我国实际国情、布局合理、可操作的航线决策方法尤为重要.本文把传统的运筹学模型决策方法与多属性决策方法相结合.根据我国实际情况及数据，以北京，上海，广州为枢纽，设计出了实用有效的、可操作性强的航线网络构造方法，可为我国快速发展的航空公司航线网络规划提供参考.

［1］张 军，都富业.发展中枢辐射航线网络战略思考［J］.中国民航学院学报，2004(6):183－186.

［2］姜 涛，朱金福.航空公司航线网络的效益分析研究［J］.工业技术经济，2006，11(25):105－107.

［3］WEN Y H，HSU C I.Interactive multiobjective programming in airline network design for international airline code－share alliance［J］.European Journal of Operational，2006(174):404－426.

［4］李桂进.我国民航的航线网络规划［J］.中国民用航空，2001(4):47－49.

［5］ALFERDO M，LAZARO C，MERCEDES L.New formulations for the uncapacitated multiple allodation hub location problem［J］.European Journal of Operational Research，2006(7):274－292.

［6］EISELT H A，VLADIMIR M.A conditional p－hub location problem with attraction functions［J］.computers ＆ Operations Research，2009，(36):3128－3135.

［7］SIBEL A，BAHAR Y K.Network hub location problems:the state of the art［J］.European Journal of Operational Research，2008(190):1－21.

［8］ERNST A T，AN K M.An exact solution approach based on shortest－paths for p－hub median problem［J］.Informs Journal on Computing，1998，10(2):149－161.

［9］SPHN J，PARK S.Efficient solution procedure and reduced size formulations for p－hub location problems［J］.European Journal of Operational Research，1998，108:118－126.

［10］姜 涛，朱金福，覃 义.中枢辐射航线网络的鲁棒优化方法研究［J］.小型微型计算机系统，2008，29(7):1366－1371.

［11］中国民用航空总局规划科技司.从统计看民航［M］.北京:中国民航出版社，2008.

［12］秦汉轩，程希骏.航空公司航线决策的一种系统方法［J］.运筹与管理，2000，9(3):56－63.

［13］DUCKSTEIN L，GERSHON M.Multicriterion analysis of avegetation management problem using ELECTER－Ⅱ［J］.Applied Mathematical Modelling，1983(7):254.