物流控制優(yōu)化方法分析：基于Dijkstra算法

浙江財經(jīng)學(xué)院 孫原

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

1 運(yùn)輸及其相關(guān)活動在物流產(chǎn)業(yè)中的重要性

在國民經(jīng)濟(jì)中，物流產(chǎn)業(yè)作為一個基礎(chǔ)產(chǎn)業(yè)，成為國民經(jīng)濟(jì)的重要組成部分，其主要作用就是將國民經(jīng)濟(jì)與其他產(chǎn)業(yè)之間進(jìn)行無縫對接，使它們緊密地聯(lián)系起來，物流產(chǎn)業(yè)對國民經(jīng)濟(jì)的發(fā)展起到積極的促進(jìn)作用，并有利于促進(jìn)社會再生產(chǎn)的擴(kuò)大。舉個恰當(dāng)?shù)睦?，物流業(yè)就像人體中的循環(huán)系統(tǒng)一樣，對整個國民經(jīng)濟(jì)起到促進(jìn)物資循環(huán)的作用。

運(yùn)輸及其相關(guān)活動在物流活動中毋庸置疑地起到了核心作用，運(yùn)輸直接對物品的作用為在空間各個環(huán)節(jié)的位置轉(zhuǎn)移，將供給者和需求者之間場所進(jìn)行形式上的合并，從而實現(xiàn)了“空間效應(yīng)”，具有以時間(速度)換取空間的特殊功能，物流及其相關(guān)活動的重要作用具體表現(xiàn)在以下兩個方面：

(1)物品運(yùn)輸是物流系統(tǒng)的重要組成部分，也是構(gòu)成物流業(yè)務(wù)的中心活動。 運(yùn)輸環(huán)節(jié)決定著一切物體的移動，移動的速度、移動的準(zhǔn)確性、移動的目標(biāo)性都與運(yùn)輸息息相關(guān)， 運(yùn)輸過程的合理與否直接影響著物流的發(fā)展。在經(jīng)濟(jì)發(fā)達(dá)國家，運(yùn)輸業(yè)和物流業(yè)是以聯(lián)營的形式出現(xiàn)在物流市場的。

(2)運(yùn)輸費(fèi)用在物流費(fèi)用中占有較大比例。物流費(fèi)用中直接費(fèi)用所占比例最大，包括運(yùn)輸費(fèi)、包裝費(fèi)、裝卸搬運(yùn)費(fèi)等，而其中運(yùn)輸費(fèi)所占的比重最大，是影響物流費(fèi)用的主要因素之一。 可見運(yùn)輸環(huán)節(jié)是實現(xiàn)物流企業(yè)基本利潤的最重要的一環(huán)。采取合理的路線安排，直接影響物流的效率，也直接影響到物流的費(fèi)用。

科學(xué)合理的運(yùn)輸路線與物流的成本的大小有著重要的關(guān)系。國際上很多物流管理公司都在使用Dijkstra算法來安排運(yùn)輸路線，保證路線最短，運(yùn)費(fèi)最少，做到降低公司成本，提高公司在行業(yè)的市場份額。

2 聚類分析算法及Djjkstra距離

2.1 聚類分析算法

聚類分析即數(shù)據(jù)分割，是指將大量的不確定的研究對象根據(jù)事先定義好的相似度度量方法分成不同的類，盡量減少同一個簇中的數(shù)據(jù)對象之間的差異，而簇間的數(shù)據(jù)對象的差異要做到較大。聚類分析源于數(shù)據(jù)挖掘、統(tǒng)計學(xué)等學(xué)科，現(xiàn)在已經(jīng)被多個需要運(yùn)用數(shù)據(jù)分析的領(lǐng)域所廣泛接受，如信息檢索、圖像處理、web信息處理、市場研究、數(shù)據(jù)分析、生物信息學(xué)、地理學(xué)以及數(shù)據(jù)庫技術(shù)等。聚類分析算法有如下經(jīng)典算法：劃分聚類方法、層次聚類方法、基于密度的聚類方法、基于網(wǎng)格的聚類方法、基于模型的聚類方法。除此之外，還有高維數(shù)據(jù)聚類方法、基于約束的聚類方法、子空間聚類方法、基于遺傳算法的聚類方法、數(shù)據(jù)流的聚類等算法，這些算法多是為了特定領(lǐng)域而提出的算法。

2.2 Djjkstra距離

Dijkstra距離求解的算法是1959年由計算機(jī)編程和科學(xué)先驅(qū)迪克斯特拉提出的，主要是解決在一個無向連通賦權(quán)圖G=

Dijkstra算法最常用來求解一個有向圖(也可以是無向圖，無向圖是有向圖的一種特例)的一個點(稱之為原點)到其余各點(稱之為周邊點)的最短路徑問題。

3 Dijkstra算法在運(yùn)輸最短路徑上的應(yīng)用

某工廠要將產(chǎn)品從工廠所在地甲地運(yùn)到使用地乙地， 從甲地到乙地有不同的路線可以選擇，怎樣選擇可以使運(yùn)輸路線最短。如圖 1 所示。

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

在甲乙兩地的交通圖中的點 V1，V2， …，V7 表示7 個運(yùn)輸?shù)攸c，其中 V1 表示甲地 ，V7 表示乙地 ，所有點間的連線(邊)表示兩之間的公路，邊所賦的全數(shù)表示兩地間公路的長度(單位為公里)。

用 Dijkstra 算法求解運(yùn)輸最短路徑， 也就是找出最短路徑時總運(yùn)費(fèi)最低。

(1)給起始點 V1 標(biāo)號為(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]中的未標(biāo)號的點 V3 標(biāo)以(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]中未標(biāo)號的點 V2 標(biāo)以(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]中未標(biāo)號的點 V5 標(biāo)以(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]中未標(biāo)號的點 V6 標(biāo)以(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]中未標(biāo)號的點 V4 標(biāo)以(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]中未標(biāo)號的點 V7 標(biāo)以(26，6)。

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

邊的集合{[Vi，Vj]│Vi，Vj 兩點中一點屬于I，而另一點屬于J}=Φ；計算結(jié)束。

(9)得到最短路徑。

從 V7 的標(biāo)號(26，6)，可知從 V1 到 V7 的最短距離為 26 公里，其最短路徑中 V7 的前一點為 V6，從 V6的標(biāo)號(19，5)可知V6 的前一點為 V5，從 V5 的標(biāo)號(16，3)可知 V5 的前一點為 V3，從 V3 的標(biāo)號 (11，1)可知 V3 的起一點為 V1， 即其最短路徑為V1→V3→V5→V6→V7，從甲地到乙地的最短距離為26。

由上述簡單算例可知，Dijkstra 算法很適合求解最短路徑問題，可以簡單而有效地找出最短路徑。

4 對Dijkstra算法中不足的優(yōu)化處理

4.1 原始Dijkstra算法的不足

(1)原始Dijkstra算法在進(jìn)行數(shù)據(jù)運(yùn)算時，必須按照其結(jié)點與距離之間的關(guān)系，建立關(guān)聯(lián)矩陣、鄰接矩陣與距離矩陣，進(jìn)而建立N×N的矩陣才能存儲數(shù)據(jù)， N為矩陣網(wǎng)絡(luò)的結(jié)點數(shù)，如結(jié)點較多，必將耗用大量計算機(jī)內(nèi)存。

(2)原始Dijkstra算法在運(yùn)行時按照結(jié)點的使用階段，可分為未標(biāo)記、臨時標(biāo)記和永久標(biāo)記三類結(jié)點3種類型。計算時對所有結(jié)點初定為未標(biāo)記結(jié)點，計算時與最短路徑結(jié)點相關(guān)聯(lián)的結(jié)點定義為臨時標(biāo)記結(jié)點，在計算中每一次循環(huán)都是從臨時標(biāo)記結(jié)點中搜索距源點路徑長度最短的結(jié)點作為永久標(biāo)記結(jié)點，并記錄，直至找到目標(biāo)結(jié)點或者所有結(jié)點都已成為永久標(biāo)記結(jié)點才結(jié)束算法。根據(jù)算法的描述可知對臨時標(biāo)記結(jié)點的標(biāo)定記錄過程成為Dijkstra算法的瓶頸，增加了計算和記錄的過程，但是大大影響了算法的計算時間和選擇效率。

4.2 算法的優(yōu)化

由于Dijkstra算法在尋找最短結(jié)點的過程中，可以利用將臨時標(biāo)記結(jié)點到源點的最短路徑與本臨時標(biāo)記結(jié)點到目標(biāo)結(jié)點的直線距離之和標(biāo)記為此臨時標(biāo)記結(jié)點的一個屬性值，這個臨時標(biāo)記的屬性值將作為從臨時標(biāo)記結(jié)點集合中選取永久標(biāo)記結(jié)點的依據(jù)，即選取此屬性值最小的臨時結(jié)點作為永久標(biāo)記結(jié)點的方法來減少Dijkstra算法中成功搜索的搜索范圍，以盡快到達(dá)目標(biāo)結(jié)點。

運(yùn)用合理的數(shù)據(jù)結(jié)構(gòu)可以在很大程度上縮短算法的運(yùn)行時間，所以根據(jù)GIS 中，結(jié)點、弧段的數(shù)據(jù)結(jié)構(gòu)可以用來構(gòu)成網(wǎng)絡(luò)圖，在網(wǎng)絡(luò)圖中，把道路交通圖中的元素分解為點、弧等基本組成圖形元素，把地圖分解為結(jié)點和弧段的集合，對于弧段的表示，只需記錄其起始結(jié)點編號、終止結(jié)點編號、弧段編號及弧段的權(quán)值(或其他屬性信息)；對于每個屬于結(jié)點集合的點，其數(shù)據(jù)項包括點的地理坐標(biāo)、關(guān)聯(lián)弧段數(shù)目、關(guān)聯(lián)弧段的編號及結(jié)點的屬性。利用結(jié)點—弧段聯(lián)合結(jié)構(gòu)，在算法運(yùn)行過程中，可以減少大量低級的粗判斷。在結(jié)點—弧段聯(lián)合結(jié)構(gòu)中，針對每個點進(jìn)行遍歷時，可以利用點的關(guān)聯(lián)弧段數(shù)目來減少循環(huán)的次數(shù)，減少了大量無謂的循環(huán)運(yùn)算，從而大大增加了搜索的效率。

5 結(jié)語

物流企業(yè)對運(yùn)輸過程進(jìn)行判斷時，考慮最多的是減少運(yùn)輸費(fèi)用和縮短運(yùn)輸時間。在進(jìn)行成本計算時，只有企業(yè)尋求“最短路”并且滿足時間約束，這條“最短路”就是最佳路線；否則物流企業(yè)就必須對運(yùn)輸環(huán)節(jié)作出調(diào)整，遇到此種情況，就需要運(yùn)用減少成本，縮短運(yùn)輸時間的方法來優(yōu)化此環(huán)節(jié)，采用Dijkstra算法及優(yōu)化算法就會解決上述問題，本文通過一個小案例來說明了Dijkstra算法及優(yōu)化算法的可行性，希望本文可以對物流企業(yè)的相關(guān)管理工作有所幫助。

[1]鞏艷芬,劉吟,于惠賢,丁海英.Dijkstra算法在企業(yè)物流運(yùn)輸網(wǎng)絡(luò)中的應(yīng)用[J].大慶石油學(xué)院院報,2005(4).

[2]王海曉.Dijkstra算法在求解物流運(yùn)輸最短路徑中的應(yīng)用[J].價值工程,2009(5).