最短路算法及其在物流管理中的應(yīng)用

余麗

（肇慶醫(yī)學(xué)高等專科，廣東肇慶526020）

最短路算法及其在物流管理中的應(yīng)用

余麗

（肇慶醫(yī)學(xué)高等?？?，廣東肇慶526020）

本文介紹了最短路的兩種算法，并介紹了它們?cè)谖锪鞴芾碇械娜舾蓱?yīng)用.將Dijkstra算法與Floyd算法用于解決物流管理中的配送路徑問題以及配送中心選址問題，并對(duì)這兩種算法進(jìn)行比較.

Dijkstra算法；Floyd算法；最短路

1 引言

最短路問題是交通網(wǎng)絡(luò)分析中的一個(gè)重要的問題，它是資源分配、路線設(shè)計(jì)及分析等優(yōu)化問題的基礎(chǔ).給定一個(gè)網(wǎng)絡(luò)，如何求它從某點(diǎn)到其它點(diǎn)的最短路，或者如何求任意兩點(diǎn)間的最短路?對(duì)此，已有很多好的算法.

最短路算法在物流管理中有廣泛的應(yīng)用.物流業(yè)被人們看作是世紀(jì)經(jīng)濟(jì)發(fā)展的新領(lǐng)域，在大力發(fā)展物流的同時(shí),人們面臨著一個(gè)共同的問題：即物流配送中心如何進(jìn)行合理的選址，如何選擇合適的配送路徑.物流中心選址及配送路徑的選擇是否合理直接關(guān)系到企業(yè)各項(xiàng)經(jīng)營(yíng)成本及其獲利程度.因此，合理選擇物流配送中心及配送路徑對(duì)于物流系統(tǒng)的規(guī)劃至關(guān)重要.而最短路算法正可以為物流配送中心選址及配送路徑選擇提供強(qiáng)有力的理論支持.

2 最短路算法

2.1 Dijkstra算法

Dijkstra算法是一種通過源結(jié)點(diǎn)出發(fā)到網(wǎng)絡(luò)當(dāng)中其他的地方各個(gè)點(diǎn)，從中尋找最佳的路徑和最短的通路的著名的算法.目前，Dijkstrs算法是大部分系統(tǒng)在解決最短路徑的問題時(shí)所應(yīng)用的理論基礎(chǔ)，不同的系統(tǒng)對(duì)這種算法采用的時(shí)候?qū)崿F(xiàn)的方式也是不同的.總的來說，該算法其主要的思想就是從源結(jié)點(diǎn)出發(fā)，按照路徑的長(zhǎng)度的遞增次序，每一次找一個(gè)結(jié)點(diǎn)跟源結(jié)點(diǎn)之間的最短通路，然后不斷繼續(xù)地尋找，直至把全部的結(jié)點(diǎn)找到為止，因此就產(chǎn)生了最短路徑.

Dijkstra算法的基本思想如下：

Dijkstra算法的基本思想是從圖G中的n-1個(gè)獨(dú)立割集中的每一個(gè)都選取一條最小的邊，從而構(gòu)成一個(gè)最小樹.現(xiàn)敘述如下：設(shè)圖G的點(diǎn)綜合為（x={1,2,3,…,n}），邊eij的權(quán)為wij.

第1步置u1=0，uj=w1j，j=2，3，…，n，P={1}，T={2,3,…, n}；

第2步在T中尋找一點(diǎn)k，使得

置P=PU{k}，T=T-{k}.若T=?，終止；否則，進(jìn)行第3步.

第3步對(duì)T中每一點(diǎn)j，置uj=min{uj，uk+wkj}，然后返回第1步.

該Dijktra算法其實(shí)就是在保證局部距離的最短來更好地獲得整體距離最短，是一種以局部來計(jì)算總體的貪心的策略的算法.如果從源點(diǎn)到其中任意點(diǎn)的路徑不存在，那么可以假設(shè)該點(diǎn)的最短路徑是一條長(zhǎng)度為無窮大的虛擬路徑.通過這個(gè)的分析，我們可以知道Dijkstra算法過程是由沒有被確定為最短路徑頂點(diǎn)的全部頂點(diǎn)中選擇出一個(gè)權(quán)值最小的弧段，直至對(duì)比得到這一點(diǎn)頂點(diǎn)為止，然后仍舊不斷地繼續(xù)前面相同的工作，不斷地反復(fù)循環(huán).

Dijkstra算法在計(jì)算任意一個(gè)點(diǎn)到其他的點(diǎn)的最短路徑的時(shí)候一共需要兩次的循環(huán)，其時(shí)間的復(fù)雜度是O(n2).因此在計(jì)算一對(duì)頂點(diǎn)之間的最短路徑的時(shí)候，需要以每一個(gè)頂點(diǎn)作為源點(diǎn).如果執(zhí)行算法n次，那么總的執(zhí)行的時(shí)間的復(fù)雜度是為O(n3)，所以要選擇一個(gè)弧段是權(quán)值是最小的話，就必須把全部還沒確定的頂點(diǎn)都來掃描一次，如果數(shù)據(jù)量比較大的話，就會(huì)對(duì)計(jì)算機(jī)的速度產(chǎn)生較大的影響.

2.2 Floyd算法

Floyd算法又稱為弗洛伊德算法，插點(diǎn)法，是一種動(dòng)態(tài)規(guī)劃的算法，用于尋找給定的加權(quán)圖中頂點(diǎn)間最短路徑的一種算法.Floyd算法在所以頂點(diǎn)之間的最短路徑的算法中是很具有代表性的，其核心的思想是通過一個(gè)圖的權(quán)值矩陣求出它的每?jī)牲c(diǎn)間的最短路徑矩陣.每次迭代求出的是只經(jīng)過點(diǎn)集的某個(gè)子集的最短路徑（一般來說初始矩陣就是鄰接矩陣），這個(gè)子集在每次迭代中都加多一個(gè)點(diǎn)，當(dāng)全部的頂點(diǎn)都作為中間頂點(diǎn)的時(shí)候，就可以求出最后的權(quán)矩陣，這時(shí)就反映出全部的頂點(diǎn)之間的最短的距離.

其算法思路如下：?jiǎn)为?dú)一條邊的路徑也不一定是最佳路徑.從任意一條單邊路徑開始.所有兩點(diǎn)之間的距離是邊的權(quán)的和，(如果兩點(diǎn)之間沒有邊相連,則為無窮大）.對(duì)于每一對(duì)頂點(diǎn)u和v，看看是否存在一個(gè)頂點(diǎn)w使得從u到w再到v比己知的路徑更短.如果是更新它.不可思議的是，只要按排適當(dāng)，就能得到結(jié)果.dmij為從節(jié)點(diǎn)i到節(jié)點(diǎn)j的最短距離.

3 最短路算法在物流管理中的應(yīng)用

隨著經(jīng)濟(jì)的全球化迅速發(fā)展和信息科技技術(shù)的突飛猛進(jìn)，物流的配送技術(shù)也隨著迅速提升.物流配送與我們先進(jìn)的信息科技技術(shù)以及數(shù)學(xué)模型的工具也是息息相關(guān)，緊密地結(jié)合在一起，通過應(yīng)用各種優(yōu)化的方法對(duì)物流配送當(dāng)中的各個(gè)環(huán)節(jié)進(jìn)行管理，甚至進(jìn)行決策，從而實(shí)現(xiàn)了最佳的配合.同時(shí)，最短路算法在物流配送中能夠適應(yīng)現(xiàn)代物流的特點(diǎn)，可以達(dá)到減少成本和提高經(jīng)濟(jì)效益和物流效益的效果.

3.1 最短路算法中物流配送路徑的選取中的應(yīng)用及算法比較

例1現(xiàn)有一批食品，打算由v1汽車站配送到v5大型超市，尋找一條最短的路線.經(jīng)過實(shí)際測(cè)量，得到以下路線網(wǎng)絡(luò)圖，如圖1所示.

圖1

3.1.1 用Dijkstra算法計(jì)算

（1）求出v1到v2的最短距離為1千米，v1到v2的最短距離為2千米，v1到v4的的最短距離為∞千米，v1到v5的最短距離為∞千米.由于v1到其他各距離最小為1，所以保留邊e12.

（2）仍用Dijkstra算法計(jì)算v2到v3、v4、v5的距離；取(ui,u2+w2i)，保留該點(diǎn)以及之前的點(diǎn)和邊.

（3）重復(fù)進(jìn)行之前一步，直到找出最短路徑為止.迭代過程如下：

根據(jù)上面的步驟，可以得到從v1汽車站配送到v5大型超市的最短路徑長(zhǎng)度為6，即走v1v2v5.

3.1.2 用Floyd算法計(jì)算

Floyd算法主要用距離矩陣來求解，所以先要構(gòu)造n個(gè)矩陣D0，D1，…Dn.本例中n=5，從D5矩陣中可以直接讀出到相互之間的最短距離.

根據(jù)Floyd算法來解題,如下：

第一步:確定矩陣D0.如果頂i和j之間有邊相連等于該邊長(zhǎng)度，如果沒有.由圖2可知

第三步：采用類似的辦法可得D2,D3,D4,D(5)矩陣為:

D5的各元素值就是相應(yīng)頂點(diǎn)間的最短路徑.D5矩陣中對(duì)應(yīng)的就是v1到v5相互之間的最短距離，顯然可以看出兩地之間的最短路徑長(zhǎng)度為6.

通過上面的例子可以了解到：Dijkstra算法通常用在計(jì)算一個(gè)點(diǎn)到其他的點(diǎn)之間的最小的路徑，它在搜索的過程中，剛好與物流系統(tǒng)當(dāng)中由一個(gè)中心點(diǎn)到其他點(diǎn)從近到遠(yuǎn)的配送方式一致：雖然Flody算法是求出每?jī)蓚€(gè)點(diǎn)間的最短的路徑，可是它僅僅是求出兩點(diǎn)間的最短路徑的長(zhǎng)度，卻未能對(duì)整個(gè)路徑的結(jié)點(diǎn)作標(biāo)示，這對(duì)物流配送查詢途徑路徑造成困難.兩者相比之下，Dijkstra算法的性能較為穩(wěn)定，同時(shí)也比較適合網(wǎng)絡(luò)的拓展變化，因?yàn)檫x擇Dijkstra算法為物流配送運(yùn)輸路線的基礎(chǔ)算法.

3.2 基于最短路算法的物流中心選址方法

本文中最短路算法包含Dijkstra算法和Flody算法，也就是頂點(diǎn)對(duì)間的最短路的算法和全部頂點(diǎn)之間的最短路算法.Dijkstra算法在物流的配送運(yùn)輸中能夠合理的進(jìn)行決策和分析，而Flody算法比較適合選擇合理的物流中心，從而使物流的總費(fèi)用達(dá)到最少的效果，但是在選擇物流中心時(shí)，由于一些約束的條件限制，導(dǎo)致選擇物流位置只能在特定的一些區(qū)域，同時(shí)，物流運(yùn)輸?shù)馁M(fèi)用與物流運(yùn)輸?shù)木嚯x呈非線性的關(guān)系.

下面結(jié)合實(shí)例來說明最短路徑說法在物流配送中心選址中的應(yīng)用.

例2已知定點(diǎn)①、②、③、④,各點(diǎn)間的費(fèi)用如圖2所示，在四個(gè)點(diǎn)中選定一個(gè)點(diǎn)為物流的中心，使得該點(diǎn)到其他每個(gè)點(diǎn)的費(fèi)用是最小的.

圖2

3.2.1 根據(jù)Dijkstra算法來解題,如下：

反復(fù)應(yīng)用Dijkstra算法，求出每一個(gè)候選地到其它各點(diǎn)的最短路徑，由于過程較多，只給出如下結(jié)果：

利用Dijkstra算法，得到上面的結(jié)果，通過觀察可以得出①到②的最短距離為1，①到③的最短距離為2，①到④的最短距離為3，由此，①到②、③、④各點(diǎn)最短距離和為6同理，②到其它處最短距離和為11，③到其它處的最短距離和為9，④到其它處的最短距離和為6.比較各處到其它各處費(fèi)用和的大小，可知①和④處到其它各點(diǎn)的費(fèi)用最小.因此，①和④處就經(jīng)濟(jì)要素而言是最優(yōu)的.

3.2.2 根據(jù)Floyd算法來解題，如下：

第一步：確定矩陣D0.如果頂i和j之間有邊相連等于該邊長(zhǎng)度，如果沒有，而.由圖4可知

由此可知

第三步：采用類似的辦法可得D2，D3，D4矩陣為

D4的各元素值就是相應(yīng)頂點(diǎn)間的最短路徑.第一行值之和即為①處到其它三處的物流費(fèi)用的和，可知①到其它的費(fèi)用和為6，②到其它處費(fèi)用和為11，③到其它處的費(fèi)用和為9，④到其它處的費(fèi)用和為6.比較各處到其它各處費(fèi)用和的大小，可知①和④處到其它各點(diǎn)的費(fèi)用最小.因此，①和④處就經(jīng)濟(jì)要素而言是最優(yōu)的.

Dijkstra算法是求最短路徑最常用也是最有效的方法，但是它只能求從某一頂點(diǎn)到其余各頂點(diǎn)的最短路徑.若是用于配送中心的選址問題的情況，對(duì)于這種情況，就得重復(fù)多次用Dijkstra算法，計(jì)算起來比較復(fù)雜.而1962年Floyd提出了求任意兩點(diǎn)間最短距離的算法，就能更好的用于這種情況的解決.Dijkstra算法主要是用來標(biāo)記路徑，而Floyd算法則能在矩陣中直觀的看出結(jié)果來.但是，當(dāng)配送中心候選地較多時(shí)Floyd算法也會(huì)顯得相當(dāng)累贅.

4 結(jié)語

本文對(duì)最短路算法在物流配送中選用的方法進(jìn)行了分析，同時(shí)，最短路算法對(duì)物流配送也起到重要的作用，不僅能夠規(guī)劃調(diào)整物流配送的路線，而且有效地節(jié)約物流配送成本.本文將Dijkstra算法與Floyd算法分別應(yīng)用于物流管理中的配送路徑問題以及配送中心選址問題，并對(duì)這兩種算法進(jìn)行比較.認(rèn)為Dijkstra算法在物流配送路線規(guī)劃方面比較適合，而配送中心選址問題用Floyd算法求解則更簡(jiǎn)潔.

〔1〕甘應(yīng)愛,田豐,李維錚,等.運(yùn)籌學(xué)[M].北京：清華大學(xué)出版社，2005.

〔2〕傅彥.離散數(shù)學(xué)及其應(yīng)用[M].北京：高等教育出版社，2007.

〔3〕王燕,蔣笑梅.配送中心全程規(guī)劃[M]北京:機(jī)械工業(yè)出版社，2004.

〔4〕刁在筠,等.運(yùn)籌學(xué)(第二版)[M].北京:高等教育出版社，2005.

〔5〕耿娟.工業(yè)企業(yè)物流網(wǎng)絡(luò)規(guī)劃[M].西安:西安建筑科技大學(xué)，2007.

TP301.6

A

1673-260X（2013）11-0020-03