物流控制優化方法分析：基于Dijkstra算法

浙江財經學院 孫原

全球經濟已經步入飛速發展的階段，這就客觀地需要具有現代化特點的物流企業積極地發揮其優勢。近幾年物流業已經從新興的行業逐漸成為社會的基礎產業甚至是重要的產業，在一些發達國家物流行業已經成為推動經濟可持續發展的主要支柱力量和經濟增長點。對于物流企業而言，找到運送的最短路徑，最大限度地節約運輸費用，降低物流成本是企業最基本的運營手段之一。

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).