Dijkstra算法在运输线路优化问题上的应用研究

颜保凡

(湖南铁路科技职业技术学院，湖南 株洲 412000)

0.引言

随着社会经济的快速发展，现代社会中物流也逐渐被提升到更重要的地位，在社会生活中也起着十分重要的作用，高效的运输过程是优质物流的重要保障。物流过程的所有业务也都是围绕运输这一中心环节展开的。在生产社会化程度日益加深的今天，运输也被提升到更重要的地位。物流活动的合理化归根结底就是运输的合理化。所以，在物流活动中，运输起着举足轻重的作用。对运输线路的优化是降低物流配送成本，提高服务质量的保证，同时也是增加经济效益的重要措施。本文通过对运输线路优化进行分析与研究，利用Dijkstra算法简单、便于实现的优点，对运输径路进行优化，以期找出最短路径，从而达到节约运输成本、节省运输资源的目的。

1.物流过程中的运输问题概述

1.1 运输与物流的关系

运输作为国民经济的命脉，在物流所有的功能中，运输是一个最基本的功能，是物流的核心。运输作为物流过程中最主要的增值活动，本身虽然不进行新的物质产品的生产，但却能实现物品在空间或时间上的转移，创造物品的“空间效用”及“时间效用”。

运输合理化是物流合理化的重要前提。运输合理化指的是一定产销条件下，货物的运量、运距、流向和中转环节满足全局最优。具体来说，就是要求将物资产品通过最合适的交通方式、最小的运输费用、最少的中转环节、最优的运输线路以及最快的运输速度从原产地转移到规定地点。运输合理化的内涵可以概括为两点。

1、合理分工、提升效率

运输合理化能够充分整合现有的运力以及资源，有效发挥中转环节中各种运输方式的优势，最终达到以最小的运输消耗满足相应的运输需求，从而提高效率。

2、降低成本、增长效益

运输合理化，能充分发挥运输工具的效能，节约运力和劳力，通过减少运输环节、优化运输路径、提高运输速度等手段实现运输效益最大化。

1.2 运输在物流中的地位和作用

1、运输是物流系统功能要素的核心

随着社会经济发展水平的不断提高以及全程物流的迅猛发展，运输的“空间效用”越发显著。而用户的消费只有借助于运输或配送的紧密配合才能得以最终实现，在物流系统的三大功能要素中，运输功能的主导地位和核心作用日益凸显，逐渐成为物流系统高效、优质功能发挥的关键要素之一。

2、运输是提升物流系统水平的关键

物流管理所追求的总目标就是使得物流合理化。它通过调整和改进物流设备配置、物流活动组织，使得物流系统达到整体优化的过程。最为直观的体现就是为以尽可能的物流成本，获得尽可能高的服务水平，或者说以最低成本为用户提供更多更好的物流服务。运输是物流的中心环节，任何物质产品的生产和消费都必须通过运输这一环节联系起来。因为运输不仅是物流系统中的动脉，而且是创造物流空间效用的主要功能要素，在物流系统整体功能起到了中心环节的重要作用。尽可能达到合理化运输，才能使物流系统结构更为完整，功能更加完善，进而到达系统总体的最优化。

3、运输是第三利润源的重要基础

在当今物流系统中，物流费用的一半以上用于完成运输。有些产品的运输费用甚至高于产品的生产费用。而在物流过程当中，运输是至关重要的一环。因此，优化运输组织能够大大降低物流的总体费用，进而提高物流系统的整体经济效益。物流成本的降低也成为物流系统的第三利润源。

2.最短路问题描述

在物流过程中，确定合理的运输路线非常重要。合理的运输路线不仅可以降低运输成本，提高车辆利用率，同时还可以提高服务水平。因此，如何确定运输路线就成为运输决策中的一个重要因素。运输合理化，除需要选择合理的运输方式外，还需要确定合理的调运和最佳运输路线，使运输量最大，运输成本最小，运输距离最短。在现实生活中，常常需要对一批货物从生产地运送到消费地，在运输过程中要经过不同的地点，如何使得运输路线最短或运输时间最短或运输费用最小，从而提高运输效率，增加运输收益就显得尤为重要。这就涉及到所谓的最短路问题。

在物流过程中，寻求配送路线的最短路问题是最常见的问题。最短路的概念是广义的，它既可以代表距离，又可以代表时间和费用。我们把与弧相联系的距离、时间、费用等称为弧的权，那么最短路问题一般可以描述为:

设VA和VB是图G={V，E}中的任意两点，各边上的权为Wij(［Vi，Vj］∈E)，最短路问题就是寻找从VA到VB的道路P，使该路的路权之和W(P)=∑［vivj］∈pWij为最小。

3.Dijkstra算法说明

当前被公认的求解最短路问题的一个经典算法就是Dijkstra算法，是由E.W.Dijkstra于1959年提出的在其满足前提条件为所有弧的权值必须非负的情况下，适用于最短路求解的算法。该算法在实际问题中有很广泛的应用。Dijkstra算法可以求得从某一给定的点到图中其他所有节点的最短路径，算法的时间复杂度为o(n2)，n为结点个数。具体的算法步骤如下:

第一步 若采用带权的邻接矩阵，arcs表示带权有向图，其中arcs［i］［j］是弧＜Vi，Vj＞上的权值。若顶点Vi和顶点Vj不是直接连通的，则arcs［i］ ［j］ 的值为MAX(极大值)。S表示从顶点V出发的最短路径的终点的集合，它的初始状态为空集。则从顶点V出发到图上其余各顶点 (终点)Vi可能存在的路径的并不仅仅只是一条，因此我们将可能存在的路径的初始值记为 D［i］ =arcs［LocateVex(G，V)［i］ Vi∈V］。

第二步 寻找选择Vj，如果满足式子D［j］ =min{D［i］Vi∈V·S}。则有顶点Vj即为当前求得的一条从顶点V出发的最短路径的终点，记为S=S∪ {j}。

第三步 更新从顶点V出发到集合V·S上任意一顶点Vk可能存在的最短路径的值，如果满足表达式D［j］ +arcs［j］［k］ ＜D［k］Vk，则对 D［k］ 进行修改，具体表达式为D［k］ =D ［j］ +arcs［j］［k］。

第四步重复步骤二和步骤三，循环就可求得顶点V到图上其余各个顶点最终的最短路径及最短路径的值。

由此可知，Dijkstra算法具有思路清晰，程序实现虽然简单的特点。但是如果顶点数越多的话，这也就意味着循环的次数也就会越多，同样计算时间也会急剧增加。这样算法执行的时间复杂度为O(n2)。本文提出一种改进算法策略，其核心思想是将整个带有权值的有向图分区划分成各个子图，这样的做法基本符合现代物流企业分区配送的方法。因此在此基础上只需对各子图进行划分计算各顶点的最短路径，然后综合决策进行处理划分。遵循以下原则:两点之间直线距离是最短几何距离，因此在物流多个配送点中，最短路径一般是配送起点和终点连接的直线周围，所以应该沿着连接起点和终点的直线进行划分。除此之外，系统具有开辟存储结构功能，将已经算好的顶点之间的最短路径存储在数据库中，这样就避免了计算工作的重复性。

4.Dijkstra算法在最短路问题上的应用分析

假设某个城市有一个配送中心，拥有足够的载重量为q的车辆。需要给n个需求点送货，设配送中心编号为1，其他需求点编号为i(i=2，……，n)，设每个需求点的需求量为gi(i=2，……，n)，配送中心有K辆车 (载重量均为q)，且每辆车的位置和需求点位置都是已知的，同时要求每个需求点只能由一辆车为其服务，以dij表示需求点i到j的运送距离，D表示车辆一次配送的最大里程限制，目标是配送的总里程最短。

如图4.1所示，图V1→V8代表从配送中心V1出发向需求点V2，V3，……，V8进行依次访问，要求我们找出从V1出发到其余各点的最短距离及达到最短距离所通过的最短路径。

图4 .1 8个顶点带权有向图

基于运筹学的原理利用传统表上作业方法求解上述问题的话，虽然结果准确，但计算过程却需要花费太多时间，而且步骤冗长繁琐，由此不难想象当有向图中点的个数相当多时，计算工程量将达到怎样的程度。当将这一问题采用Dijkstra算法进行计算时，计算机则可在很短的时间内计算出精确的结果并找出准确的路线，从而可以大大的节省进行计算的工作量和时间。论文就上述问题通过VisualC++编写程序可得出该问题的最短路径为:1－2－4－7－8，最短路径的值为10。结果如图4.2所示。

图4 .2 Dijkstra算法求解图

5.结论

在物流配送中经常要设计最佳的配送路线以便提高配送效率，降低配送成本，因此通过计算两个配送点的最短路线最后去综合决策多个配送点之间的较优的配送路径。运输作为物流系统的核心功能要素，随着现代物流业的飞速发展以及小体积、多品类、小批量、高附加值和季节性商贸流通产品的运输逐年增加，运输作为货物流通中的必不可少的环节，其重要性日益突出。运输线路的最优化直接影响到一个企业的物流成本、送货时间，同时也对社会经济效益产生巨大影响。本文通过利用Dijkstra算法对最短路问题进行分析求解，找出满足约束条件的最优解，对Dijkstra算法是求解最短路问题的经典算法进行了验证。

［1］余群英.运输组织与管理［M］.北京 机械工业出版社，2009，5

［2］宁宣熙等.管理运筹学教程 ［M］.北京 清华大学出版社，2007，8

［3］田晟.基于Dijkstra算法的物流配送系统最短路径程序设计［J］.交通标准化.2009(NO.200):89－92

［4］张念.用Dijkstra算法实现对整车配送线路的优化［J］.中国水运.2007(5):141－142

［5］周程.物流配送路径优化策略研究 ［J］.武汉理工大学学报 (交通科学与工程版).2005(5):797－800.