多重博弈的Dijkstra算法快递行业航空网络应用研究(修改版)1.8Word文档下载推荐.doc

1、为每个航空枢纽到其他航空枢纽的需求量，下标i和j代表各个航空枢纽的编号。Tij：为每个航空枢纽到其他航空枢纽所需要的飞行时间，下标i和j代表各个航空枢纽的编号。假设飞机飞行的时间越短，则消耗燃料越少，成本越小，同时飞行距离与飞行时间成正比，各航空枢纽间的飞行时间不同。对于快件需求量，根据现实情况，每两个枢纽之间的往返需求量是不同的。2.算法模型分析本算法模型中采取了需求量作为其第一变量，每条最优线路都会走满足最大需求量的路线，所以采用求最短路径的Dijkstra算法来计算。但是由于Dijkstra是求最短路径的算法，所以在计算之前，需要对需求量的数据进行一定的处理，对需求量数据进行翻转。在使用

2、Dijkstra算法计算的时候每走一条路线就对该路线加一分，相同的路线走一次就再加一分，以此使得路线与路线之间产生优劣的差异关系，相互博弈，最终比较得出各个路线之间的优劣，得出最终的结果。在这个算法模型中各航空枢纽间的飞行时间作为其第二变量，各个航空枢纽之间所需要的飞行时间不同，而飞行时间越短，飞机消耗的成本越低。将各个航空枢纽间的飞行时间与Dijkstra算法计算出的最终路线进行再次博弈。多重博弈后，选择出满足需求量和相对低成本的路线，算法结束。三、算法设计1将各航空枢纽的业务需求量（进量和出量之和）进行从大到小的排序，建立处理数轴。以数0作为数轴的起点，选出业务需求量最大的数据Xij，作为

3、数轴终点，并将终点数据的二分之一（1/2Xij）作为此数轴的中间数轴。2将大于中间数轴1/2Xij的数字排到中间数轴右侧，小于中间数轴的数字排到数轴左边。用中间数轴1/2Xij右侧的需求量Xij分别减去中间数轴，得出一数字Xij，再用中间数轴减去此数字，即1/2Xij-Xij，设为Hij，此数字必然小于中间数轴，将此数翻转排列到中间数轴左侧；用中间数轴减去分别中间数轴左侧的业务需求量Xij，得出一数字Xij，再用中间数轴加上此数字，即1/2Xij+Xij，设为Hij，此数字必然大于中间数轴1/2Xij，将此数翻转排列到中间数轴右侧，如图1所示：图1 最初处理数轴将处理数轴中的需求量数据和翻转后

4、数据分离，留下翻转后数据。如图2所示：图2 最终处理数轴通过数据处理后，就将较大需求量转换为较小的数字，方便之后的运算。3根据第2步的数据处理结果，利用Dijkstra算法求出最短路线。Dijkstra在无向图 G=（V,E） 中，假设每条边 Ei 的长度为 wi，找到由顶点 V0 到其余各点的最短路径。Dijkstra算法描述如下：关于标识说明，如节点标识为20,4：第一个数表示从开始节点到该节点的距离，第二个数表示从开始节点到该节点的路径上的请一个节点的编号。步骤1：给节点1永久标识0,S。0标识节点1到自己的距离为0，S表示节点为起始点。步骤2：考察从节点1能直接到达的节点，并给出暂时标

5、识。步骤3：从暂时标识节点中确定具有最小距离的节点，并且标记该节点为永久标识。如果所有节点全被永久标识，转到步骤5。步骤4：从新标记的永久标识开始，考察从新标识的永久标识所能直接直接到达的未被永久标识的节点。（1）如果考察节点为暂时标识节点，则把新标识的永久标识节点距离值与新标识的永久标识节点直接到达该点的距离值相加。如果其和小于暂时标识点的距离值，则重新确定最小距离值为该点的距离值。（2）如果考察的节点为未标识的节点，则把新标识的永久标识节点距离值与新标记的永久标识节点直接到达该点的距离值相加。作为该点的暂时标识。返回步骤3。步骤5：永久标识既确定了从节点1到每一个节点的最短距离，也确定了最

6、短路线。最短路线的确定采用倒推法进行。表1：任意两点之间的最短路径v1v2v3v4v5v6各行中最大数X12X13X14X15X16X23X24X25X26X34X35X36X45X464根据第3步计算出的最短路径，对路径进行多重加权处理。图3 最短路径图若现有的业务需求线路为：（1） AB（2） ABCE（3） EDBA（4） CBA（5） BD（6） ECB每条路线被经过一次，就加上1个权值，进行多重加权。根据以上的业务需求线路，进行多重加权后的结果如图4：图4 多重加权后的路径图5. 将各路线按照最后得出的权值，从大到小进行排序。以第4步中的模型为例，排序后的结果为：（1） AB（2）

7、BC（3） BD CE（4） DE6. 各个航空枢纽之间的飞行时间作为本算法模型中的第二变量，将各个航空枢纽之间飞行所需时间列表，如表2所示：表2 航空枢纽时间表ABCDEFGHITABTACTBCTADTBDTCDTAETBETCETDETAFTBFTCFTDFTEFTAGTBGTCGTDGTEGTFGTAHTBHTCHTDHTEHTFHTGHTAITBITCITDITEITFITGITHI7. 将时间因素考虑于博弈后Dijkstra算法所得出的最短路径中，进行再次博弈。若存在相同的路径权值，则取用时间Tij小者，将线路进行再次排序。若TBDTCE，则再次排序后的顺序为：（1）AB（2）BC

8、（3）CE（4）DE8. 排序之后，在地图中按照排序结果标记。以第7部中数据排序后的结果为例，首先在地图中标记出“AB”，然后标记出“BC”，再标记出“CE”，最后标记出“DE”。直到标记完毕所有航空枢纽为止，算法结束。9通过Dijkstra算法求出最短路径，利用线路的通过次数作为权值，进行第一次博弈，选出最短路径中的最优路径；利用时间的长短作为第二变量，在第一次博弈结果的基础上进行第二次博弈，选取出最优路径中的最优路径。通过多重博弈，在最短的路径中选择出最优解，再在最优解中选择出所用时间最短的路径，在节约路程的基础上节约时间，同时达到节约成本的目标。四、数据模拟1根据某快递企业实地调研结果显

9、示，该快递企业目前的航空枢纽有北京、上海、重庆、沈阳、成都、无锡、潍坊、杭州、深圳、香港十个城市。各个城市之间的航空业务需求量如表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 2

10、997 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 注：以上纵向为始发地代码（电

11、话区号后三位），横向为目的地代码（电话区号后三位）2数据处理根据1中的航空枢纽，将各个航空枢纽的业务需求量进行数据处理，目的是将大量转换为小量，方便算法的计算。处理过程如下。将各航空枢纽的业务需求量（进量和出量）进行从大到小的排序，建立处理数轴。以数0作为数轴的起点，选出业务需求量最大的数据，作为数轴终点，并将终点数据的二分之一作为此数轴的中间数轴。（1）在航空枢纽中，业务量的排名整理如表4：表4 航空枢纽业务量排名始终业务量深圳杭州63753杭州深圳58370深圳北京53138重庆香港53（2）根据表4的排名结果，将大于中间数轴的数字排到中间数轴右侧，小于中间数轴的数字排到数轴左边。即637

12、53/2=31877（取整），31877为中间数轴。（3）用中间数轴右侧的需求量分别减去中间数轴，得出一数字，再用中间数轴减去此数字，此数字必然小于中间数轴，将此数翻转排列到中间数轴左侧；用中间数轴减去分别中间数轴左侧的业务需求量，得出一数字，再用中间数轴加上此数，此数必然大于中间数轴，将此数翻转排列到中间数轴右侧。如：31877-（59370-31877）=5384,31877-（53138-31877）=10616,（31877-53）+31877=63701，最后的数据处理数轴如图5所示：图5 最初处理数轴如图6：图6 最终处理数轴3时间处理我们以时间因素为准，将各个航空枢纽之间的飞行时

13、间处理为一张时间表。表5为某快递企业目前航空枢纽间的飞行时间表：表5 业务需求城市飞行时间表 单位：分钟110150 60 135 190 190120 140 12080 170 90 145 130 310135180225 220 4求出最短路径根据第2步的数据处理结果和第3步的时间处理结果，利用Dijkstra算法求出最短路线。5多重博弈加权根据第4步计算出的最短路径，对路径进行多重加权处理。例：假设经过计算后的最短路径如图7所示，图7 最短路径图现有的业务需求线路为：（1） 成都杭州北京（2） 成都杭州（3） 成都杭州深圳（4） 北京杭州成都每条路线被经过一次，就加上1，进行多重加权

14、。根据以上的业务需求线路，进行多重加权后的结果如图8：图8 多重加权后的路径图6排序及标记 将各路线按照最后得出的权值，从大到小进行排序。以5中数据为例，排序后的结果为：（1） 成都杭州（2） 杭州北京（3） 杭州深圳排序之后，在地图中按照排序结果标记。以4中数据排序后的结果为例，首先在地图中标记出“成都杭州”，然后标记出“杭州北京”，再标记出“杭州深圳”。直到标记完毕所有航空枢纽为止。以上六个步骤可以通过计算机进行实现，可进行实际操作，在电子地图上生成图像，增强可视性效果。本例生成的图像如图9： 图9 计算机生成的最优航空网络图（黑线部分）至此，通过航空枢纽确定最短路径确定多重加权制定线路，

15、可以保证某快递企业航空网络的时效性高于现状，成本低于现状。经过计算，本算法的准确性和实用性较其他相关算法更为有效，也更贴近现实。本算法易于计算机实现，处理效率相对其他相关算法更为快捷。五、结语航空网络是快件传递中重要的渠道之一，它不是某个单一因素就能影响的，而是多因素，多方面，多层次的快件网络。可以基于时间效率、成本效率两个维度建立一个统一的模型，同时对两个维度进行有效规划和实现。之前的相关研究中，大多数研究主要是针对民航或者航空枢纽选址问题进行了研究，并未对快递行业中的航空网络的特殊性进行考虑。针对以上情况，本文结合博弈论和最短路径算法Dijkstra算法 ，对基于多重博弈的Dijkstra

16、算法规划航空网络，对航空网络的最优路径进行了研究，以实现快递航空网络的低成本与高时效的目标。同时用计算机编程实现该算法，适用性较强。随着近代快递业得飞速发展，对与航空网络的资源优化和配置也越来越重视，本文研究快递行业的航空网络的规划，可以对快递航空业建立规划航空模型提供参考，一定程度上提升和优化航空网络的效率，并降低其成本。当然越贴近于现实的假设会使得算法越复杂，本算法在假设上比较近于现实，但并未完全与现实相符合，当然这也是进一步要研究的方向。参考文献1 姜涛,朱金福.航空公司选择枢纽机场的鲁棒优化方法.系统工程，2006，24卷,6期，6。2 舒湘,杨铭,王延平.航空项目资源资源均衡优化问题

17、的蚁群-模拟退火算法.学术论文，2010，13期，77-813 周鸿,欧建新,李政道.航空货运中心物流系统建模及仿真研究.系统仿真学报，2008，20卷，6期，5-6.4 戴福青,王瑞.单枢纽机场选址与航线网络规划综合优化.中国民航大学学报，2007,25卷，第1期，17-205 俞桂杰,彭语冰,褚衍昌.复杂网络理论及其在航空网络中的应用.复杂系统与复杂性科学，2006,3卷，第1期，79-846 伯明国,朱金福.航空公司航线网络设计的一种三阶段方法.南京航空航天大学学报.2006，38卷，第2期，181-1857 王姣娥,莫辉辉,金凤君.中国航空网络空间结构的复杂性.地理学报.2009,8期

18、,5-78 杨晗熠.枢纽确定单连接轴-辐网络结构在中国民用航空网络中的应用. 北京理工大学学报.2010，12卷，第2期，27-309Hannula,M,Huttunen,K,Koskelo,J,Laitinen,T,Leino,T.Comparison between artificial neural network and multilinear regression models in an evaluation of cognitive workload in a flight simulator.Computers in Biology and Medicine.2008,5-7.10 柏明国等.枢纽航线网络的构建方法及应用.系统工程，2006,5期，3-9.11 刘宏鲲，周涛.中国城市航空网络的实证研究与分析.物理学报，2007,56卷，第1期，106-11212 金凤君.我国航空客流网络发展及其地域系统研究.地理研究，1999,20卷，第1期，31-3913 戴福青.单枢纽机场选址与航