基于Dijkstra算法的物流运输最短路径的研究
2011-12-29潘开灵董晶晶
中国集体经济 2011年10期
摘要：运输是物流活动的一个主要组成部分，是物流的核心环节。运输的路径优化是物流运输中的一个重要问题，也是在实际应用中的一个难以解决的问题。文章首先介绍了运输在物流中的重要性以及优化运输环节进行物流分析的必要性和可行性，接着阐述了Dijkstra算法的基本思路以及求解运输最短路径的具体步骤，通过Dijkstra算法找出运输中的最短路径，进而减短运输距离，降低物流成本，提高产品竞争力。
关键词：运输；最短路径；Dijkstra算法
物质运输将生产和消费所处的不同空间联结起来，为实现实物从生产到消费的移动起到了决定性的作用。在现代生产中，由于生产的专门化、集中化，生产与消费被分割的状态越来越严重，被分隔的距离亦越来越大，进而运输的地位也越来越高。运输在整个物流活动过程当中起着举足轻重的作用。
一、运输在物流活动中的核心作用
（一）物流系统功能要素的核心是运输
运输功能创造了货物的空间效用，储存功能创造了货物的时间效用，流通加工功能则改变了货物的形质效用，物流系统中的其他功能均围绕该三大功能进行，这是物流系统运动中被公认的规律。随着经济的全球化、一体化的发展，通过运输实现货物的空间效用呈现出明显的强化态势，通过货物的储存保管实现起时间效用则呈现弱化趋势，而通过流通加工实现改变货物的形质效用则需借助运输或配送才能呈现出强化趋势。其原因是在社会化大生产条件下，并不追求产品的生产和消费在空间位置上的一致性，且存在较大的地域位置上的差异，这种趋势造成的直接影响就是对运输的依赖性越来越大，无形中突出了运输功能的主导作用。
（二）运输是实现物流合理化的关键
以尽可能低的成本为用户提供更多更好的服务是物流合理化的关键，它是以各物流子系统合理化为基础的。但是，物流合理化并不是各子系统局部最优的简单叠加，而是根据系统原理，各子系统合理并相互协调产生结构效用，才能使系统总体功能达到最优。在当代社会，一切物质产品的生产和消费均离不开运输，这不仅是因为运输是物流系统的大动脉，其合理与否直接影响其他物流子系统的构成，而且还因为运输在物流系统的整体功能中发挥着中心环节的作用。除此以外，运输费用在全部物流费用中占较大比重，是降低物流费用、提高物流经济效益和社会效益的关键。因此，物流合理化在很大程度上取决于运输合理化，只有运输合理化，才能使物流系统更加合理，总体功能更优。
（三）运输是“第三利润源泉”的主要源泉
在物流构成中所需支付的费用主要有运输费、仓储费、包装费、装卸搬运费、流通加工费和物流过程中的损耗，其中运输费所占比重最高，是影响物流成本的重要因素。有关资料表明，我国运输费用占社会物流费用近50%的比例，甚至有些产品的运输费高于其生产成本，而且运输所需的时间长、距离长、消耗大。通过改革，采取合理化运输可以大大降低运输的消耗所需的时间和费用，对提高经济效益和社会效益均起着重要作用。所谓运输的物流“第三利润源泉”的主要源泉的意义也在于此。
二、通过优化运输环节进行物流分析的必要性和可行性
（一）必要性
1、运输服务是有效组织输入和输出物流的关键。企业的工厂、仓库与其他供货厂商和客户之间的地理分布直接影响着物流的运输费用。因此，运输条件是企业选择工厂、仓库、配送中心等物流设施配置地点需要考虑的主要因素之一。
2、运输影响着物流的其他构成因素。运输方式的选择决定着装运货物的包装要求；使用不同类型的运输工具决定其配套使用装卸搬运设备以及接受和发运站台的设计；企业库存储备量的大小，直接受运输状况的影响，发达的运输系统能够比较适量、快速和可靠地补充库存，以降低必要的储备水平。
3、运输费用在物流费用中占有很大的比重。运输费用是最大的物流成本之一。组织合理运输，以最小的费用、最快的时间，及时、准确、安全地将货物从其产地运到销地，是降低物流费用和提高经济效益的重要途径之一。运输费用关系整个物流费用，在物流费用中，运输费用所占的比重最高，一般来讲，在社会物流费用当中，运输费用占将近50%的比重。有些产品的运输费用甚至高于生产费用。因此，降低运输费用对于降低物流费用，提高物流经济效益，以及稳定商品价格，满足消费需求，提高社会经济效益都具有重要的意义。
4、运输还与物流的子系统包装、装卸、储存、配送有着不可分割的关系。运输、包装、储存、配送这些物流的子系统是一个密不可分的有机整体，它们相互衔接、相辅相成。整个物流活动是由包装、装卸、储存、配送、流通加工、运输等活动组成的，其中运输是物流活动的主要组成部分，是物流活动的核心环节，与其他物流活动息息相关，无论是企业的输入物流还是输出物流，或者流通领域的销售物流都必须依靠运输来实现商品的空间转移。
（二）可行性
1、物流理论已经基本成熟。物流学是一门综合性、应用性、系统性和拓展性很强的科学。它涉及自然科学、社会科学和工程技术科学；涉及到生产、流通和消费领域，国民经济的许多部门。随着经济的迅速发展，这些理论现在都已经比较成熟，因此，对物流的规划分析变得可行。
2、物流业已经形成一定规模。物流业是将运输、储存、装卸、搬运、包装、流通加工、配送、信息处理等基本功能根据实际需要实施有机结合的活动的集合。物流业是一个复合型产业，物流业是物流资源产业化而形成的一种复合型或聚合型产业。从某种程度上讲，对物流系统进行规划分析的主要目的之一就是要减少物流网络各个节点之间的费用消耗，因此物流行业的规模大小，将直接决定着物流规划结果的显著程度。目前，不管是国内还是国外，物流都具有相当大的规模，并在国民经济中发挥着重要作用，因此找到合适的突破点对物流系统中的各个子系统进行规划分析，将是非常可行的。
3、计算机技术的发展。自从进入21世纪之后，我国计算机技术得到广泛的应用，如今计算机技术已经涉及到大众生活的方方面面，计算机正成为进行规划研究不可或缺的工具。在对物流因素进行分析时，存在着众多影响因素，因此分析过程通常比较复杂，只有借助计算机技术才能较好地完成。
总之，运输过程对整个物流活动意义重大，所以在物流活动中必须采取科学合理的运输路线，有效地降低物流成本。Dijkstra算法就是通过一种方法，使运输的总路径最短、运费最少，尽可能地减少物流成本，提高产品的竞争力。
三、Dijkstra算法概述
迪杰斯特拉（Dijkstra）算法是一种典型的最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
（一）Dijkstra算法思想
Dijkstra算法思想为：设G=（V，E）是一个带权有向图（也可以是无向图，无向图是有向图的特例），把图中顶点集合V分成两组：第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径，就将其加入到集合S中，直到全部顶点都加入到S中，算法就结束了）；第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。
（二）Dijkstra算法具体步骤
第一，初始时，S只包含源点，即S＝{顶点}，v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或（若u不是v的出边邻接点）。
第二，从U中选取一个距离v最小的顶点k，把k加入S中（该选定的距离就是v到k的最短路径长度）。
第三，以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
第四，重复步骤第二步和第三步直到所有顶点都包含在S中。
四、Dijkstra算法在求运输最短路径上的应用
某企业要将一批产品由A地运往F地，从A到F有多条路线选择，怎样选择可以使运输线路最短（见图1）。
在A、F两地的交通图中的点B、C、D、E分别表示4个地名，点与点之间的连线表示两地之间的公路，边上所赋值代表两地间的长度（单位为公里）。
用Dijkstra算法求解运输最短路径，也就是要找出最短路径，使总距离最短，总运费最低具体步骤如下：
第一，在S集合中：进入A，此时S=，此时最短路径为A→A=0，以A为中间点，从A开始找。在U集合中：U=
第二，在S集合中：进入C，此时S=
第三，在S集合中：进入B，此时S=
第四，在S集合中：进入D，此时S=
第五，在S集合中：进入E，此时S=
第六，在S集合中：进入F，此时S=
第七，得到最短路径。从第六步可知，从A到F的最短路径为9公里，A到B的最短路径为A→C→B=5，A到C是最短路径为A→C=3，A到D的最短路径为A→C→D=6，A到E的最短路径为A→C→E=7，A到F的最短路径为A→C→D→F=9。
五、结束语
运输在整个物流活动中起着至关重要的作用，在运输过程中运输距离的长短将直接影响物流总成本的大小，因此在物流运输过程中必须确保运输路径最短，从而有效地降低运输成本，提高产品竞争力。本文通过Dijkstra算法求解出物流运输的最短路径，是一种简单有效的方法，可以很容易地找出运输的最短路径。
参考文献：
1、
