多重博弈的Dijkstra算法快递行业航空网络应用研究(修改版)1.8Word文档下载推荐.doc
《多重博弈的Dijkstra算法快递行业航空网络应用研究(修改版)1.8Word文档下载推荐.doc》由会员分享，可在线阅读，更多相关《多重博弈的Dijkstra算法快递行业航空网络应用研究(修改版)1.8Word文档下载推荐.doc（20页珍藏版）》请在冰点文库上搜索。
为每个航空枢纽到其他航空枢纽的需求量，下标i和j代表各个航空枢纽的编号。
Tij：
为每个航空枢纽到其他航空枢纽所需要的飞行时间，下标i和j代表各个航空枢纽的编号。
假设飞机飞行的时间越短，则消耗燃料越少，成本越小，同时飞行距离与飞行时间成正比，各航空枢纽间的飞行时间不同。
对于快件需求量，根据现实情况，每两个枢纽之间的往返需求量是不同的。
2.算法模型分析
本算法模型中采取了需求量作为其第一变量，每条最优线路都会走满足最大需求量的路线，所以采用求最短路径的Dijkstra算法来计算。
但是由于Dijkstra是求最短路径的算法，所以在计算之前，需要对需求量的数据进行一定的处理，对需求量数据进行翻转。
在使用Dijkstra算法计算的时候每走一条路线就对该路线加一分，相同的路线走一次就再加一分，以此使得路线与路线之间产生优劣的差异关系，相互博弈，最终比较得出各个路线之间的优劣，得出最终的结果。
在这个算法模型中各航空枢纽间的飞行时间作为其第二变量，各个航空枢纽之间所需要的飞行时间不同，而飞行时间越短，飞机消耗的成本越低。
将各个航空枢纽间的飞行时间与Dijkstra算法计算出的最终路线进行再次博弈。
多重博弈后，选择出满足需求量和相对低成本的路线，算法结束。
三、算法设计
1．将各航空枢纽的业务需求量（进量和出量之和）进行从大到小的排序，建立处理数轴。
以数0作为数轴的起点，选出业务需求量最大的数据Xij，作为数轴终点，并将终点数据的二分之一（1/2Xij）作为此数轴的中间数轴。
2．将大于中间数轴1/2Xij的数字排到中间数轴右侧，小于中间数轴的数字排到数轴左边。
用中间数轴1/2Xij右侧的需求量Xij分别减去中间数轴，得出一数字X’ij，再用中间数轴减去此数字，即1/2Xij-X’ij，设为Hij，此数字必然小于中间数轴，将此数翻转排列到中间数轴左侧；
用中间数轴减去分别中间数轴左侧的业务需求量Xij，得出一数字X’ij，再用中间数轴加上此数字，即1/2Xij+X’ij，设为Hij，此数字必然大于中间数轴1/2Xij，将此数翻转排列到中间数轴右侧，如图1所示：
图1最初处理数轴
将处理数轴中的需求量数据和翻转后数据分离，留下翻转后数据。
如图2所示：
图2最终处理数轴
通过数据处理后，就将较大需求量转换为较小的数字，方便之后的运算。
3．根据第2步的数据处理结果，利用Dijkstra算法求出最短路线。
Dijkstra在无向图G=（V,E）中，假设每条边E[i]的长度为w[i]，找到由顶点V0到其余各点的最短路径。
Dijkstra算法描述如下：
关于标识说明，如节点标识为[20,4]：
第一个数表示从开始节点到该节点的距离，第二个数表示从开始节点到该节点的路径上的请一个节点的编号。
步骤1：
给节点1永久标识[0,S]。
0标识节点1到自己的距离为0，S表示节点为起始点。
步骤2：
考察从节点1能直接到达的节点，并给出暂时标识。
步骤3：
从暂时标识节点中确定具有最小距离的节点，并且标记该节点为永久标识。
如果所有节点全被永久标识，转到步骤5。
步骤4：
从新标记的永久标识开始，考察从新标识的永久标识所能直接直接到达的未被永久标识的节点。
（1）如果考察节点为暂时标识节点，则把新标识的永久标识节点距离值与新标识的永久标识节点直接到达该点的距离值相加。
如果其和小于暂时标识点的距离值，则重新确定最小距离值为该点的距离值。
（2）如果考察的节点为未标识的节点，则把新标识的永久标识节点距离值与新标记的永久标识节点直接到达该点的距离值相加。
作为该点的暂时标识。
返回步骤3。
步骤5：
永久标识既确定了从节点1到每一个节点的最短距离，也确定了最短路线。
最短路线的确定采用倒推法进行。
表1：
任意两点之间的最短路径
v1
v2
v3
v4
v5
v6
各行中最大数
X12
X13
X14
X15
X16
X23
X24
X25
X26
X34
X35
X36
X45
X46
4．根据第3步计算出的最短路径，对路径进行多重加权处理。
图3最短路径图
若现有的业务需求线路为：
（1）A→B
（2）A→B→C→E
（3）E→D→B→A
（4）C→B→A
（5）B→D
（6）E→C→B
每条路线被经过一次，就加上1个权值，进行多重加权。
根据以上的业务需求线路，进行多重加权后的结果如图4：
图4多重加权后的路径图
5.将各路线按照最后得出的权值，从大到小进行排序。
以第4步中的模型为例，排序后的结果为：
（1）A—B
（2）B—C
（3）B—DC—E
（4）D—E
……
6.各个航空枢纽之间的飞行时间作为本算法模型中的第二变量，将各个航空枢纽之间飞行所需时间列表，如表2所示：
表2航空枢纽时间表
A
B
C
D
E
F
G
H
I
TAB
TAC
TBC
TAD
TBD
TCD
TAE
TBE
TCE
TDE
TAF
TBF
TCF
TDF
TEF
TAG
TBG
TCG
TDG
TEG
TFG
TAH
TBH
TCH
TDH
TEH
TFH
TGH
TAI
TBI
TCI
TDI
TEI
TFI
TGI
THI
7.将时间因素考虑于博弈后Dijkstra算法所得出的最短路径中，进行再次博弈。
若存在相同的路径权值，则取用时间Tij小者，将线路进行再次排序。
若TBD>
TCE，则再次排序后的顺序为：
（1）A—B
（2）B—C
（3）C—E
（4）D—E
8.排序之后，在地图中按照排序结果标记。
以第7部中数据排序后的结果为例，首先在地图中标记出“A—B”，然后标记出“B—C”，再标记出“C—E”，最后标记出“D—E”。
直到标记完毕所有航空枢纽为止，算法结束。
9．通过Dijkstra算法求出最短路径，利用线路的通过次数作为权值，进行第一次博弈，选出最短路径中的最优路径；
利用时间的长短作为第二变量，在第一次博弈结果的基础上进行第二次博弈，选取出最优路径中的最优路径。
通过多重博弈，在最短的路径中选择出最优解，再在最优解中选择出所用时间最短的路径，在节约路程的基础上节约时间，同时达到节约成本的目标。
四、数据模拟
1．根据某快递企业实地调研结果显示，该快递企业目前的航空枢纽有北京、上海、重庆、沈阳、成都、无锡、潍坊、杭州、深圳、香港十个城市。
各个城市之间的航空业务需求量如表3所示：
表3各航空枢纽间业务需求
010
北京
021
上海
023
重庆
024
沈阳
028
成都
510
无锡
536
潍坊
571
杭州
755
深圳
852
香港
010北京
13585
2339
9219
4825
11433
11911
11978
21460
1799
021上海
20425
1974
6909
3810
8803
21265
5780
023重庆
750
589
338
459
273
598
1766
53
024沈阳
6190
3073
519
839
2070
2207
2997
4188
735
028成都
3036
1059
604
1281
1057
1416
3628
157
510无锡
16331
1697
5880
4807
8247
33784
8294
536潍坊
9092
6419
784
2533
1699
5006
5672
12446
2829
571杭州
23857
4524
9332
9145
13788
58370
18852
755深圳
53138
44075
6925
14984
13746
48691
24409
63753
852香港
2309
6347
142
858
210
6422
2125
9601
注：
以上纵向为始发地代码（电话区号后三位），横向为目的地代码（电话区号后三位）
2．数据处理
根据1中的航空枢纽，将各个航空枢纽的业务需求量进行数据处理，目的是将大量转换为小量，方便算法的计算。
处理过程如下。
将各航空枢纽的业务需求量（进量和出量）进行从大到小的排序，建立处理数轴。
以数0作为数轴的起点，选出业务需求量最大的数据，作为数轴终点，并将终点数据的二分之一作为此数轴的中间数轴。
（1）在航空枢纽中，业务量的排名整理如表4：
表4航空枢纽业务量排名
始……终
业务量
深圳……杭州
63753
杭州……深圳
58370
深圳……北京
53138
重庆……香港
53
（2）根据表4的排名结果，将大于中间数轴的数字排到中间数轴右侧，小于中间数轴的数字排到数轴左边。
即63753/2=31877（取整），31877为中间数轴。
（3）用中间数轴右侧的需求量分别减去中间数轴，得出一数字，再用中间数轴减去此数字，此数字必然小于中间数轴，将此数翻转排列到中间数轴左侧；
用中间数轴减去分别中间数轴左侧的业务需求量，得出一数字，再用中间数轴加上此数，此数必然大于中间数轴，将此数翻转排列到中间数轴右侧。
如：
31877-（59370-31877）=5384,31877-（53138-31877）=10616,（31877-53）+31877=63701，最后的数据处理数轴如图5所示：
图5最初处理数轴
如图6：
图6最终处理数轴
3．时间处理
我们以时间因素为准，将各个航空枢纽之间的飞行时间处理为一张时间表。
表5为某快递企业目前航空枢纽间的飞行时间表：
表5业务需求城市飞行时间表
单位：
分钟
110
150
60
135
190
190
120
140
120
80
170
90
145
130
310
135
180
225
220
4．求出最短路径
根据第2步的数据处理结果和第3步的时间处理结果，利用Dijkstra算法求出最短路线。
5．多重博弈加权
根据第4步计算出的最短路径，对路径进行多重加权处理。
例：
假设经过计算后的最短路径如图7所示，
图7最短路径图
现有的业务需求线路为：
（1）成都—杭州—北京
（2）成都—杭州
（3）成都—杭州—深圳
（4）北京—杭州 —成都
每条路线被经过一次，就加上1，进行多重加权。
根据以上的业务需求线路，进行多重加权后的结果如图8：
图8多重加权后的路径图
6．排序及标记
将各路线按照最后得出的权值，从大到小进行排序。
以5中数据为例，排序后的结果为：
（1）成都—杭州
（2）杭州—北京
（3）杭州—深圳
排序之后，在地图中按照排序结果标记。
以4中数据排序后的结果为例，首先在地图中标记出“成都—杭州”，然后标记出“杭州—北京”，再标记出“杭州—深圳”……。
直到标记完毕所有航空枢纽为止。
以上六个步骤可以通过计算机进行实现，可进行实际操作，在电子地图上生成图像，增强可视性效果。
本例生成的图像如图9：
图9计算机生成的最优航空网络图（黑线部分）
至此，通过航空枢纽确定—最短路径确定—多重加权—制定线路，可以保证某快递企业航空网络的时效性高于现状，成本低于现状。
经过计算，本算法的准确性和实用性较其他相关算法更为有效，也更贴近现实。
本算法易于计算机实现，处理效率相对其他相关算法更为快捷。
五、结语
航空网络是快件传递中重要的渠道之一，它不是某个单一因素就能影响的，而是多因素，多方面，多层次的快件网络。
可以基于时间效率、成本效率两个维度建立一个统一的模型，同时对两个维度进行有效规划和实现。
之前的相关研究中，大多数研究主要是针对民航或者航空枢纽选址问题进行了研究，并未对快递行业中的航空网络的特殊性进行考虑。
针对以上情况，本文结合博弈论和最短路径算法Dijkstra算法，对基于多重博弈的Dijkstra算法规划航空网络，对航空网络的最优路径进行了研究，以实现快递航空网络的低成本与高时效的目标。
同时用计算机编程实现该算法，适用性较强。
随着近代快递业得飞速发展，对与航空网络的资源优化和配置也越来越重视，本文研究快递行业的航空网络的规划，可以对快递航空业建立规划航空模型提供参考，一定程度上提升和优化航空网络的效率，并降低其成本。
当然越贴近于现实的假设会使得算法越复杂，本算法在假设上比较近于现实，但并未完全与现实相符合，当然这也是进一步要研究的方向。
参考文献
[1]姜涛,朱金福.航空公司选择枢纽机场的鲁棒优化方法.系统工程，2006，24卷,6期，6。
[2]舒湘,杨铭,王延平.航空项目资源资源均衡优化问题的蚁群-模拟退火算法.学术论文，2010，13期，77-81
[3]周鸿,欧建新,李政道.航空货运中心物流系统建模及仿真研究.系统仿真学报，2008，20卷，6期，5-6.
[4]戴福青,王瑞.单枢纽机场选址与航线网络规划综合优化.中国民航大学学报，2007,25卷，第1期，17-20
[5]俞桂杰,彭语冰,褚衍昌.复杂网络理论及其在航空网络中的应用.复杂系统与复杂性科学，2006,3卷，第1期，79-84
[6]伯明国,朱金福.航空公司航线网络设计的一种三阶段方法.南京航空航天大学学报.2006，38卷，第2期，181-185
[7]王姣娥,莫辉辉,金凤君.中国航空网络空间结构的复杂性.地理学报.2009,8期,5-7
[8]杨晗熠.枢纽确定单连接轴-辐网络结构在中国民用航空网络中的应用.北京理工大学学报.2010，12卷，第2期，27-30
[9]Hannula,M,Huttunen,K,Koskelo,J,Laitinen,T,Leino,T.Comparisonbetweenartificialneuralnetworkandmultilinearregressionmodelsinanevaluationofcognitiveworkloadinaflightsimulator.ComputersinBiologyandMedicine.2008,5-7.
[10]柏明国等.枢纽航线网络的构建方法及应用.系统工程，2006,5期，3-9.
[11]刘宏鲲，周涛.中国城市航空网络的实证研究与分析.物理学报，2007,56卷，第1期，106-112
[12]金凤君.我国航空客流网络发展及其地域系统研究.地理研究，1999,20卷，第1期，31-39
[13]戴福青.单枢纽机场选址与航
升级会员 