（河北省石家庄市石家庄铁道大学，050043）
摘要：本文通过分析我国当前多式联运体系的现状，提出一个专门用于描述多式联运系统的运输网络结构图，并使用基于现实情况给出图的优化方案，最后根据图论中的最短路径算法给出该体系下最佳的多式联运方案。
关键词：多式联运；运输网络；Dijkstra算法
1.我国多式联运研究现状与发展趋势
多式联运作为一种集约、高效的现代化运输组织模式，在国际上早已得到了广泛的推广应用。欧美发达国家自上世纪80年代以来，通过各种政策措施大力发展多式联运，尤其是跨入21世纪后均把多式联运作为交通运输系统优化的主导战略，目前已经形成了发展形式多样、设施装备先进、标准体系完善、运输组织顺畅、政策保障有力的多式联运推进体系，多式联运比例不断增长且发展势头强劲。
然而根据我国国家发改委综合运输研究所所长汪鸣在多式联运协同发展论坛中所作的报告：目前我国多式联运占整个货运量的比例不到2%，有的时候占2%多一点。而欧美发达国家的这个数据有30%、50%和80%的不等。
由于国内各大物流企业对于多式联运与日俱增的需求，吸引了越来越多的国内外学者进行研究。张建勇等从实现总成本最小化的原则出发，建立了一种多式联运网络的最优分配模型，从定量角度分析了多式联运系统的合理组织模式[2]。王涛等对多种运输方式的运输特性进行分析后，提出了运输方式组合优化模型，并给出求解算法[3]。
这些优秀的学者的工作系统地研究了多式联运的最短可行路径及运输方式优化组合等相关问题，但对于运输时间和费用的研究还不够完善，因此本章节旨在通过对多种运输方式进行分析的基础上，以我国苏锡常杭运输体系为核心，通过应用图论的相关算法，为企业进行多式联运提供决策依据。
2.多式联运系统的网络描述
为了得到更直观准确的信息，为决策者进行决策提供依据，同时方便后期算法的开展运用，在此需要建立一个专门用于描述多式联运系统的运输网络图。
同时，为了提炼出主要特征，防止多余的因素对运输网络的构建所造成的影响，在这里，我们不妨引用图论构建图的方法，整个网络由节点以及每两个节点之间的一条或相互平行的多条连线所组成。
2.1基本假设
●企业把货物从起始点运送到目的地，中途经过若干个节点，任意相邻的两个节点之
●间有若干种运输方式。
●在复杂的多式联运运输网络中，每个节点处都可能发生运输方式的转换，但各种运输方式之间的衔接只能在节点发生。
●每次转换将对应一条新的路径。
2.2网络的构建过程
设某物流公司需要将一批货物从货物的中心地点O运送到目的地D，中途经过n个城市，这里给出样例图，如图2-1所示：
图2-1 网络构建样例图
2.3权重说明
不同城市之间，所包含的运输方式数量不同，且考虑到实际地图中的连通性特点，同一城市可能会作为多个节点出现。
同时，考虑到物流公司往往有固定的装运场地，并为了防止其对于最终成图所造成的干扰，这里暂时不考虑出门装运以及门到门配送，即“前一公里（O到P1,j，j=1,2,…,k1）”与“后一共公里（Pn,j到D，j=1,2,…,kn）”所产生的费用和所需要的时间。
对于该网络，各条弧上的权重分为两类:费用权重、时间权重。在这里：
费用权重=两城市之间的运费+中转费用；
时间权重=两城市之间的运输时间+中转时间；
2.4模型推导
在这里，我们定义
3.引入Dijkstra（最短路径）算法
3.1算法简述
Dijkstra算法（中文名：迪杰斯特拉算法）是由荷兰计算机科学家Edsger Wybe Dijkstra提出。其主要作用是寻找某固定图下的两个点的最短路径，举例来说，如果图中的顶点表示城市，而边上的权重表示城市间开车行经的距离，该算法可以用来找到两个城市之间的最短路径。对于多式联运系统的运输网络图而言，当我们确定了图上的各个节点城市以及不同城市之间运输所承担的费用，我们就可以通过该算法来给出最节约成本的运输路线。
3.2基本思想
Dijkstra算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题，算法最终得到一个最短路径树。
Dijkstra算法采用的是一种贪心的策略，声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合：T，初始原点s的路径权重被赋为0（dis[s] = 0）。若对于顶点s存在能直接到达的边（s,m），则把dis[m]设为w（s, m）,同时把所有其他（s不能直接到达的）顶点的路径长度设为无穷大。
初始时，集合T只有顶点s。然后，从dis数组选择最小值，则该值就是源点s到该值对应的顶点的最短路径，并且把该点加入到T中，此时完成一个顶点，再然后，查看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短，如果是，那么就替换这些顶点在dis中的值。之后，再从dis中找出最小值，重复上述动作，直到T中包含了图的所有顶点。
4.算法运用方式
4.1优化多式联运网络权重
对于一个完整多式联运的网络，它不仅包括了节点与节点之间的弧的权重（所需费用，花费时间），还包括了节点上切换不同的交通方式所承担的时间和费用成本。
而最短路径算法本身只针对图上各个弧的权重来进行推导，最终给出成本最低的路径，节点本身更多是一种标识。
因此需要对构建的多式联运网络图进行进一步的优化，为了让它能够顺利使用最短路径算法，在这里，将各个节点本身所承担的时间和费用成本移加到其所连接的弧上，为了详细说明，举一个简单的例子，如图4-1所示：
图4-1 多式联运样例图
目前有一批货物从城市A出发，目的地为F，图上的权重分别代表运输方式、所需时间、所需费用，且由于是同一批货物，转换的时间、费用相对固定，这里给出不同运输方式的转换费用，如表4-1所示：
表4-1转换运输方式的时间与费用代价
基于上表，我们就可以给出优化后的网络结构图，如图4-2所示：
图4-2 优化后的网络结构图
网络上的节点本身不再承担任何代价，本身只作为标识存在。
4.2算法的推演
对于企业而言，最优先考虑的肯定是成本问题，因此对于算法的使用，以多式联运上每条路径上的费用为运算基础，时间为限制条件，进行运算。将整个图以邻接矩阵的形式表示出来，输入MATLAB中，得到最佳的运输流程：
从城市A选择铁路运输到城市B，再从城市B选择公路运输到城市E，最后从城市E通过铁路运输到城市F。整个过程时间代价为：21；费用代价为：29。
当然，如果时间上超过了所允许的范围，在这里，我们还可以退而求次，选择费用代价次小的运输路线。
参考文献
[1]韩润春，运筹学[M]，中国铁道出版社，2010
[2]张建勇、郭耀煌，一种多式联运网络的最优分配模式研究[A]，CNKI，2002
[3]王涛、王刚，一种多式联运网络运输方式的组合优化模式[A]，CNKI，2005
作者简介：房子源（1998-），男，满族，河北承德人，在校本科生，研究方向：大数据。
论文作者:房子源 马雯秋 李梦琳
论文发表刊物:《信息技术时代》2018年4期
论文发表时间:2019/1/21
标签：多式论文; 算法论文; 路径论文; 节点论文; 权重论文; 顶点论文; 最短论文; 《信息技术时代》2018年4期论文;