浙江财经学院 孙原

全球经济已经步入飞速发展的阶段，这就客观地需要具有现代化特点的物流企业积极地发挥其优势。近几年物流业已经从新兴的行业逐渐成为社会的基础产业甚至是重要的产业，在一些发达国家物流行业已经成为推动经济可持续发展的主要支柱力量和经济增长点。对于物流企业而言，找到运送的最短路径，最大限度地节约运输费用，降低物流成本是企业最基本的运营手段之一。

1 运输及其相关活动在物流产业中的重要性

在国民经济中，物流产业作为一个基础产业，成为国民经济的重要组成部分，其主要作用就是将国民经济与其他产业之间进行无缝对接，使它们紧密地联系起来，物流产业对国民经济的发展起到积极的促进作用，并有利于促进社会再生产的扩大。举个恰当的例子，物流业就像人体中的循环系统一样，对整个国民经济起到促进物资循环的作用。

运输及其相关活动在物流活动中毋庸置疑地起到了核心作用，运输直接对物品的作用为在空间各个环节的位置转移，将供给者和需求者之间场所进行形式上的合并，从而实现了“空间效应”，具有以时间(速度)换取空间的特殊功能，物流及其相关活动的重要作用具体表现在以下两个方面：

(1)物品运输是物流系统的重要组成部分，也是构成物流业务的中心活动。 运输环节决定着一切物体的移动，移动的速度、移动的准确性、移动的目标性都与运输息息相关， 运输过程的合理与否直接影响着物流的发展。在经济发达国家，运输业和物流业是以联营的形式出现在物流市场的。

(2)运输费用在物流费用中占有较大比例。物流费用中直接费用所占比例最大，包括运输费、包装费、装卸搬运费等，而其中运输费所占的比重最大，是影响物流费用的主要因素之一。 可见运输环节是实现物流企业基本利润的最重要的一环。采取合理的路线安排，直接影响物流的效率，也直接影响到物流的费用。

科学合理的运输路线与物流的成本的大小有着重要的关系。国际上很多物流管理公司都在使用Dijkstra算法来安排运输路线，保证路线最短，运费最少，做到降低公司成本，提高公司在行业的市场份额。

2 聚类分析算法及Djjkstra距离

2.1 聚类分析算法

聚类分析即数据分割，是指将大量的不确定的研究对象根据事先定义好的相似度度量方法分成不同的类，尽量减少同一个簇中的数据对象之间的差异，而簇间的数据对象的差异要做到较大。聚类分析源于数据挖掘、统计学等学科，现在已经被多个需要运用数据分析的领域所广泛接受，如信息检索、图像处理、web信息处理、市场研究、数据分析、生物信息学、地理学以及数据库技术等。聚类分析算法有如下经典算法：划分聚类方法、层次聚类方法、基于密度的聚类方法、基于网格的聚类方法、基于模型的聚类方法。除此之外，还有高维数据聚类方法、基于约束的聚类方法、子空间聚类方法、基于遗传算法的聚类方法、数据流的聚类等算法，这些算法多是为了特定领域而提出的算法。

2.2 Djjkstra距离

Dijkstra距离求解的算法是1959年由计算机编程和科学先驱迪克斯特拉提出的，主要是解决在一个无向连通赋权图G=

Dijkstra算法最常用来求解一个有向图(也可以是无向图，无向图是有向图的一种特例)的一个点(称之为原点)到其余各点(称之为周边点)的最短路径问题。

3 Dijkstra算法在运输最短路径上的应用

某工厂要将产品从工厂所在地甲地运到使用地乙地， 从甲地到乙地有不同的路线可以选择，怎样选择可以使运输路线最短。如图 1 所示。

图1 甲地至乙地交通里程图

在甲乙两地的交通图中的点 V1，V2， …，V7 表示7 个运输地点，其中 V1 表示甲地 ，V7 表示乙地 ，所有点间的连线(边)表示两之间的公路，边所赋的全数表示两地间公路的长度(单位为公里)。

用 Dijkstra 算法求解运输最短路径， 也就是找出最短路径时总运费最低。

(1)给起始点 V1 标号为(0，S)。

(2)I={V1}；J={V2，V3，V4，V5，V6，V7}。

边的集合{[Vi，Vj]│Vi，Vj 两点中一点属于 I，而另一点属于J}={[V1，V2]，[V1，V3]}，并有：

S12=L1+C12=0+16=16；

S13=L1+C13=0+11=11；

Min(S12，S13)=S13=11。

给边[V1，V3]中的未标号的点 V3 标以(11，1)表示从 V1 到 V3的距离为 11， 并且在 V1 到 V3 的最短路径上 V3 的前面的点为V1。

(3)这时，I={V1，V3}；J={V2，V4，V5，V6，V7}。

边的集合{[Vi，Vj]│Vi，Vj 两点中一点属于 I，而另一点属于J}={[V1，V2]，[V3，V2]，[V3，V5]}，并有：

S32=L3+C32=11+4=15；

S35=L3+C35=11+5=16；

Min(S12，S32，S35)=S32=15。

给边[V3，V2]中未标号的点 V2 标以(15，3)。

(4)这时，I={V1，V3，V2}；J={V4，V5，V6，V7}。

边的集合{[Vi，Vj]│Vi，Vj 两点中一点属于 I，而另一点属于J}={[V3，V5]，[V2，V4]，[V2，V7]}，并有：

S24=L2+C24=15+7=22；

S27=L2+C27=15+18=33；

Min(S35，S24，S27)=S35=16。

给边[V3，V5]中未标号的点 V5 标以(16，3)。

(5)这时，I={V1，V2，V3，V5}；J={V4，V6，V7}。

边的集合{[Vi，Vj]│Vi，Vj 两点中一点属于 I，而另一点属于J}={[V2，V4]，[V5，V4]，[V2，V7]，[V5，V6]}，并有：

S54=L5+C54=16+5=21；

S56=L5+C56=16+3=19；

Min(S24，S54，S27，S56)=S56=19。

给边[V5，V6]中未标号的点 V6 标以(19，5)。

(6)这时，I={V1，V2，V3，V5，V6}；J={V4，V7}。

边的集合{[Vi，Vj]│Vi，Vj 两点中一点属于 I，而另一点属于J}={[V2，V4]，[V5，V4]，[V2，V7]，[V6，V7]}，并有：

S67=L6+C67=19+7=26；

Min(S24，S54，S27，S67)=S54=21。

给边[V5，V4]中未标号的点 V4 标以(21，5)。

(7)这时，I={V1，V2，V3，V4，V5，V6}；J={V7}。

边的集合{[Vi，Vj]│Vi，Vj 两点中一点属于 I，而另一点属于J}={[V2，V7]，[V4，V7]，[V6，V7]}，并有：

S47=L4+C47=21+6=27；

Min(S27，S47，S67)=S67=26。

给边[V6，V7]中未标号的点 V7 标以(26，6)。

(8)这时，I={V1，V2，V3，V4，V5，V6，V7}；J=Φ。

边的集合{[Vi，Vj]│Vi，Vj 两点中一点属于I，而另一点属于J}=Φ；计算结束。

(9)得到最短路径。

从 V7 的标号(26，6)，可知从 V1 到 V7 的最短距离为 26 公里，其最短路径中 V7 的前一点为 V6，从 V6的标号(19，5)可知V6 的前一点为 V5，从 V5 的标号(16，3)可知 V5 的前一点为 V3，从 V3 的标号 (11，1)可知 V3 的起一点为 V1， 即其最短路径为V1→V3→V5→V6→V7，从甲地到乙地的最短距离为26。

由上述简单算例可知，Dijkstra 算法很适合求解最短路径问题，可以简单而有效地找出最短路径。

4 对Dijkstra算法中不足的优化处理

4.1 原始Dijkstra算法的不足

(1)原始Dijkstra算法在进行数据运算时，必须按照其结点与距离之间的关系，建立关联矩阵、邻接矩阵与距离矩阵，进而建立N×N的矩阵才能存储数据， N为矩阵网络的结点数，如结点较多，必将耗用大量计算机内存。

(2)原始Dijkstra算法在运行时按照结点的使用阶段，可分为未标记、临时标记和永久标记三类结点3种类型。计算时对所有结点初定为未标记结点，计算时与最短路径结点相关联的结点定义为临时标记结点，在计算中每一次循环都是从临时标记结点中搜索距源点路径长度最短的结点作为永久标记结点，并记录，直至找到目标结点或者所有结点都已成为永久标记结点才结束算法。根据算法的描述可知对临时标记结点的标定记录过程成为Dijkstra算法的瓶颈，增加了计算和记录的过程，但是大大影响了算法的计算时间和选择效率。

4.2 算法的优化

由于Dijkstra算法在寻找最短结点的过程中，可以利用将临时标记结点到源点的最短路径与本临时标记结点到目标结点的直线距离之和标记为此临时标记结点的一个属性值，这个临时标记的属性值将作为从临时标记结点集合中选取永久标记结点的依据，即选取此属性值最小的临时结点作为永久标记结点的方法来减少Dijkstra算法中成功搜索的搜索范围，以尽快到达目标结点。

运用合理的数据结构可以在很大程度上缩短算法的运行时间，所以根据GIS 中，结点、弧段的数据结构可以用来构成网络图，在网络图中，把道路交通图中的元素分解为点、弧等基本组成图形元素，把地图分解为结点和弧段的集合，对于弧段的表示，只需记录其起始结点编号、终止结点编号、弧段编号及弧段的权值(或其他属性信息)；对于每个属于结点集合的点，其数据项包括点的地理坐标、关联弧段数目、关联弧段的编号及结点的属性。利用结点—弧段联合结构，在算法运行过程中，可以减少大量低级的粗判断。在结点—弧段联合结构中，针对每个点进行遍历时，可以利用点的关联弧段数目来减少循环的次数，减少了大量无谓的循环运算，从而大大增加了搜索的效率。

5 结语

物流企业对运输过程进行判断时，考虑最多的是减少运输费用和缩短运输时间。在进行成本计算时，只有企业寻求“最短路”并且满足时间约束，这条“最短路”就是最佳路线；否则物流企业就必须对运输环节作出调整，遇到此种情况，就需要运用减少成本，缩短运输时间的方法来优化此环节，采用Dijkstra算法及优化算法就会解决上述问题，本文通过一个小案例来说明了Dijkstra算法及优化算法的可行性，希望本文可以对物流企业的相关管理工作有所帮助。

[1]巩艳芬,刘吟,于惠贤,丁海英.Dijkstra算法在企业物流运输网络中的应用[J].大庆石油学院院报,2005(4).

[2]王海晓.Dijkstra算法在求解物流运输最短路径中的应用[J].价值工程,2009(5).