Dijkstra算法在物流配送運(yùn)輸中的最短路徑優(yōu)化研究

摘 要：傳統(tǒng)的Dijkstra算法一般用于計(jì)算一個(gè)源節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最小代價(jià)路徑，它能夠適應(yīng)網(wǎng)絡(luò)拓?fù)涞淖兓?，因而可以?yīng)用在物流中的配送線(xiàn)路規(guī)劃上。原始的Dijkstra算法在實(shí)現(xiàn)時(shí)不僅占用大量計(jì)算機(jī)內(nèi)存，而且執(zhí)行效率也不高。針對(duì)這一問(wèn)題，本文基于傳統(tǒng)的Dijkstra算法，對(duì)其數(shù)據(jù)存儲(chǔ)和算法思路進(jìn)行了優(yōu)化。最終通過(guò)實(shí)驗(yàn)證明優(yōu)化后的Dijkstra比原始的Dijkstra算法在執(zhí)行效率上有了較大的提高。

關(guān)鍵詞：Dijkstra算法；最短路徑；物流配送；優(yōu)化算法

中圖分類(lèi)號(hào)：TP301.6

物流業(yè)的發(fā)展已成為國(guó)民經(jīng)濟(jì)的一個(gè)新的增長(zhǎng)點(diǎn)，科學(xué)合理的物流業(yè)是經(jīng)濟(jì)可持續(xù)發(fā)展的重要部分，其發(fā)展程度已經(jīng)成為衡量一個(gè)國(guó)家現(xiàn)代化程度和綜合國(guó)力的重要標(biāo)志之一，被喻為促進(jìn)經(jīng)濟(jì)增長(zhǎng)的“第三利潤(rùn)源泉”。在物流配送活動(dòng)中，主要是把一批貨物從配送中心運(yùn)送到一個(gè)或多個(gè)非固定客戶(hù)的接貨處。通常配送中心與客戶(hù)之間有多條運(yùn)輸路線(xiàn)可以選擇。如果配送中心不進(jìn)行運(yùn)輸路線(xiàn)的合理規(guī)劃，往往會(huì)出現(xiàn)不合理的運(yùn)輸現(xiàn)象，如迂回運(yùn)輸、重復(fù)運(yùn)輸?shù)?。不合理運(yùn)輸會(huì)造成運(yùn)輸成本上升。因此確定合理的配送路線(xiàn)，從而使運(yùn)輸成本降低的同時(shí)又使服務(wù)水平得到改善是物流配送管理工作的一項(xiàng)重要內(nèi)容。

本論文是筆者在湖北某軟件公司實(shí)習(xí)期間，參與的一個(gè)物資綜合管理系統(tǒng)，其中有一個(gè)模塊是關(guān)于車(chē)輛調(diào)配和物流運(yùn)輸?shù)?，然后在此基礎(chǔ)上實(shí)現(xiàn)基于Dijkstra算法并對(duì)其進(jìn)行優(yōu)化的物流配送最短路徑選擇算法。通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，不僅節(jié)約了物流成本，而且提高了運(yùn)輸?shù)男省?/p>

1 Dijkstra算法介紹

1.1 Dijkstra算法思想及步驟

Dijkstra算法用于計(jì)算一個(gè)源節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最短代價(jià)路徑，它是按路徑長(zhǎng)度遞增的次序來(lái)產(chǎn)生最短路徑的算法。該算法的輸入包含一個(gè)有權(quán)重的有向圖G以及G中的一個(gè)頂點(diǎn)s，用V表示G中所有頂點(diǎn)的集合，S表示已求得最短路徑的值頂點(diǎn)，w（u，v）表示從頂點(diǎn)u到頂點(diǎn)v的權(quán)重（設(shè)定權(quán)重均為非負(fù)值），（u，v）表示從頂點(diǎn)u到頂點(diǎn)v有路徑相連，d（v）表示從頂點(diǎn)s到頂點(diǎn)v的最小權(quán)重。步驟如下：

（1）初始時(shí)，集合S只包含頂點(diǎn)s，s的路徑長(zhǎng)度值被賦為0（即d（s）=0），選擇頂點(diǎn)m，若存在能直接到達(dá)的邊（s，m），則d（m）=min{w（s，m）}，并將頂點(diǎn)m加入集合S，對(duì)于所（1）Dijkstra算法的效率與頂點(diǎn)數(shù)N密切相關(guān)。

（2）在存儲(chǔ)圖形數(shù)據(jù)和運(yùn)算時(shí)，需要定義N*N的數(shù)組，其中N為網(wǎng)絡(luò)的結(jié)點(diǎn)數(shù)，當(dāng)網(wǎng)絡(luò)的結(jié)點(diǎn)數(shù)較大時(shí)，將占用大量的計(jì)算機(jī)內(nèi)存。

（3）當(dāng)從未標(biāo)記節(jié)點(diǎn)集合（V-S）選定下一個(gè)頂點(diǎn)m作中間節(jié)點(diǎn)后，在更新最短路徑的過(guò)程中，需要掃描所有的未標(biāo)記節(jié)點(diǎn)并進(jìn)行比較更新。而未標(biāo)記節(jié)點(diǎn)集合（V-S）中往往包含大量與中間點(diǎn)m不直接相連的節(jié)點(diǎn)，即Cost[j，k]=∞。因而很多操作無(wú)效而導(dǎo)致執(zhí)行效率降低。

2 Dijkstra算法優(yōu)化

2.1 數(shù)據(jù)存儲(chǔ)的優(yōu)化

通常在一個(gè)城市交通圖模擬出來(lái)的網(wǎng)絡(luò)圖中，存在很多頂點(diǎn)（物流運(yùn)輸?shù)牡攸c(diǎn)）和邊（道路），而且錯(cuò)綜復(fù)雜，但真正與某一頂點(diǎn)相關(guān)的邊和頂點(diǎn)是有限的。以鄰接矩陣或關(guān)聯(lián)矩陣為基礎(chǔ)的算法中，存在著很多權(quán)值為∞的元素，這些無(wú)效的元素占用了大量的計(jì)算機(jī)內(nèi)存。如果在表示網(wǎng)絡(luò)結(jié)構(gòu)圖的關(guān)系時(shí)，只是記錄與某一頂點(diǎn)相關(guān)的邊和頂點(diǎn)，這樣就可以減少很多無(wú)效的權(quán)值為∞的頂點(diǎn)，從而起到節(jié)約內(nèi)存的作用。具體步驟如下：

（1）依據(jù)最大相鄰頂點(diǎn)數(shù)的概念，計(jì)算出網(wǎng)絡(luò)圖中的最大相鄰頂點(diǎn)數(shù)m；

（2）根據(jù)網(wǎng)絡(luò)圖構(gòu)造鄰接矩陣。以網(wǎng)絡(luò)圖中的頂點(diǎn)為行，以該頂點(diǎn)相鄰的點(diǎn)為列，矩陣的行數(shù)為網(wǎng)絡(luò)圖中的實(shí)際頂點(diǎn)數(shù)，列數(shù)為網(wǎng)絡(luò)圖中的最大相鄰頂點(diǎn)數(shù)m，改鄰接矩陣中的值為與行頂點(diǎn)相連的頂點(diǎn)值。如果該頂點(diǎn)的相鄰頂點(diǎn)數(shù)少于最大相鄰頂點(diǎn)數(shù)m，則用0代替。

（3）根據(jù)網(wǎng)絡(luò)圖構(gòu)造判斷矩陣。對(duì)照上一步構(gòu)造出來(lái)的鄰接矩陣，用鄰接矩陣?yán)锏母鱾€(gè)元素對(duì)應(yīng)邊號(hào)的權(quán)值代替同一位置的頂點(diǎn)值就構(gòu)成了判斷矩陣；

（4）然后根據(jù)鄰接矩陣和判斷矩陣求網(wǎng)絡(luò)圖上某一頂點(diǎn)到其他頂點(diǎn)間的最短路徑。

2.2 算法思路的優(yōu)化

傳統(tǒng)的Dijkstra算法能求出網(wǎng)絡(luò)圖中的最短路徑，但是在頂點(diǎn)和邊很多的情況下，該算法需要遍歷很多節(jié)點(diǎn)，而且很多是無(wú)效的頂點(diǎn)，所以執(zhí)行效率比較低。其主要表現(xiàn)在：更新新加入的頂點(diǎn)m到集合V—S中所有頂點(diǎn)的最短路徑時(shí)，需要大量比較d[m] + w[m，v]和d[v]的大小，而此時(shí)很多頂點(diǎn)并不與m相鄰（即w[m，v]=∞），這樣就增加了額外的運(yùn)算量。由于Dijkstra算法是計(jì)算從起點(diǎn)到某一頂點(diǎn)的最短路徑，我們也可以將其表述為計(jì)算從某一頂點(diǎn)到起點(diǎn)的最短路徑。因此求最短路徑問(wèn)題可以分解兩個(gè)子問(wèn)題，即計(jì)算由起點(diǎn)到終點(diǎn)的最短路徑和由終點(diǎn)到起點(diǎn)的最短路徑，這樣就大大降低了求解最短路徑問(wèn)題的復(fù)雜度。

傳統(tǒng) Dijkstra算法在提取最短路徑節(jié)點(diǎn)時(shí)需要遍歷所有的在集合V—S中的頂點(diǎn)，并更新最短路徑值，所以算法的實(shí)踐復(fù)雜度為O（N2）。而本文改進(jìn)的算法將此問(wèn)題分解為兩個(gè)子問(wèn)題進(jìn)行求解，而且符合并行處理思想。這樣對(duì)執(zhí)行速度有了較大的提高，特別是對(duì)于網(wǎng)絡(luò)圖中頂點(diǎn)數(shù)和邊較多的情況下。

3 結(jié)束語(yǔ)

在物流配送中，合理的配送路線(xiàn)規(guī)劃不僅能夠及時(shí)地滿(mǎn)足客戶(hù)的需求，而且可以節(jié)約配送中心的運(yùn)輸成本，所以求出最短配送路徑算法的效率具有重要的作用。本文結(jié)合配送路線(xiàn)規(guī)劃的實(shí)際情況，選擇Dijkstra算法作為物流配送路線(xiàn)規(guī)劃的核心算法，并對(duì)它的不足提出了優(yōu)化方法，在數(shù)據(jù)存儲(chǔ)和算法思路兩個(gè)方面進(jìn)行了優(yōu)化，使優(yōu)化后的算法能夠提高配送路線(xiàn)規(guī)劃的效率。最后經(jīng)實(shí)驗(yàn)證明，優(yōu)化后的Dijkstra算法不僅節(jié)約了物流成本，而且提高了運(yùn)輸效率。

參考文獻(xiàn)：

[1]嚴(yán)蔚敏，吳偉明.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，2009.

[2]李臣波.一種基于Dijkstra的最短路徑算法[J].哈爾濱理工大學(xué)學(xué)報(bào)，2008.

[3]李怡，張鐵柱，滕春賢.基于GIS的配送車(chē)輛路線(xiàn)規(guī)劃的研究[J].哈爾濱理工大學(xué)學(xué)報(bào)，2006，11

作者簡(jiǎn)介：鐘寶榮（1963-），通信作者，教授，1992年華中理工大學(xué)計(jì)算機(jī)軟件專(zhuān)業(yè)碩士畢業(yè)，主要研究方向?yàn)椋壕W(wǎng)絡(luò)數(shù)據(jù)庫(kù)技術(shù)、圖形圖象處理技術(shù)、多媒體數(shù)據(jù)通信技術(shù)等。

作者單位：長(zhǎng)江大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，湖北荊州 434023