Dijkstra算法在運輸線路優(yōu)化問題上的應(yīng)用研究

顏保凡

(湖南鐵路科技職業(yè)技術(shù)學院，湖南 株洲 412000)

0.引言

隨著社會經(jīng)濟的快速發(fā)展，現(xiàn)代社會中物流也逐漸被提升到更重要的地位，在社會生活中也起著十分重要的作用，高效的運輸過程是優(yōu)質(zhì)物流的重要保障。物流過程的所有業(yè)務(wù)也都是圍繞運輸這一中心環(huán)節(jié)展開的。在生產(chǎn)社會化程度日益加深的今天，運輸也被提升到更重要的地位。物流活動的合理化歸根結(jié)底就是運輸?shù)暮侠砘?。所以，在物流活動中，運輸起著舉足輕重的作用。對運輸線路的優(yōu)化是降低物流配送成本，提高服務(wù)質(zhì)量的保證，同時也是增加經(jīng)濟效益的重要措施。本文通過對運輸線路優(yōu)化進行分析與研究，利用Dijkstra算法簡單、便于實現(xiàn)的優(yōu)點，對運輸徑路進行優(yōu)化，以期找出最短路徑，從而達到節(jié)約運輸成本、節(jié)省運輸資源的目的。

1.物流過程中的運輸問題概述

1.1 運輸與物流的關(guān)系

運輸作為國民經(jīng)濟的命脈，在物流所有的功能中，運輸是一個最基本的功能，是物流的核心。運輸作為物流過程中最主要的增值活動，本身雖然不進行新的物質(zhì)產(chǎn)品的生產(chǎn)，但卻能實現(xiàn)物品在空間或時間上的轉(zhuǎn)移，創(chuàng)造物品的“空間效用”及“時間效用”。

運輸合理化是物流合理化的重要前提。運輸合理化指的是一定產(chǎn)銷條件下，貨物的運量、運距、流向和中轉(zhuǎn)環(huán)節(jié)滿足全局最優(yōu)。具體來說，就是要求將物資產(chǎn)品通過最合適的交通方式、最小的運輸費用、最少的中轉(zhuǎn)環(huán)節(jié)、最優(yōu)的運輸線路以及最快的運輸速度從原產(chǎn)地轉(zhuǎn)移到規(guī)定地點。運輸合理化的內(nèi)涵可以概括為兩點。

1、合理分工、提升效率

運輸合理化能夠充分整合現(xiàn)有的運力以及資源，有效發(fā)揮中轉(zhuǎn)環(huán)節(jié)中各種運輸方式的優(yōu)勢，最終達到以最小的運輸消耗滿足相應(yīng)的運輸需求，從而提高效率。

2、降低成本、增長效益

運輸合理化，能充分發(fā)揮運輸工具的效能，節(jié)約運力和勞力，通過減少運輸環(huán)節(jié)、優(yōu)化運輸路徑、提高運輸速度等手段實現(xiàn)運輸效益最大化。

1.2 運輸在物流中的地位和作用

1、運輸是物流系統(tǒng)功能要素的核心

隨著社會經(jīng)濟發(fā)展水平的不斷提高以及全程物流的迅猛發(fā)展，運輸?shù)摹翱臻g效用”越發(fā)顯著。而用戶的消費只有借助于運輸或配送的緊密配合才能得以最終實現(xiàn)，在物流系統(tǒng)的三大功能要素中，運輸功能的主導(dǎo)地位和核心作用日益凸顯，逐漸成為物流系統(tǒng)高效、優(yōu)質(zhì)功能發(fā)揮的關(guān)鍵要素之一。

2、運輸是提升物流系統(tǒng)水平的關(guān)鍵

物流管理所追求的總目標就是使得物流合理化。它通過調(diào)整和改進物流設(shè)備配置、物流活動組織，使得物流系統(tǒng)達到整體優(yōu)化的過程。最為直觀的體現(xiàn)就是為以盡可能的物流成本，獲得盡可能高的服務(wù)水平，或者說以最低成本為用戶提供更多更好的物流服務(wù)。運輸是物流的中心環(huán)節(jié)，任何物質(zhì)產(chǎn)品的生產(chǎn)和消費都必須通過運輸這一環(huán)節(jié)聯(lián)系起來。因為運輸不僅是物流系統(tǒng)中的動脈，而且是創(chuàng)造物流空間效用的主要功能要素，在物流系統(tǒng)整體功能起到了中心環(huán)節(jié)的重要作用。盡可能達到合理化運輸，才能使物流系統(tǒng)結(jié)構(gòu)更為完整，功能更加完善，進而到達系統(tǒng)總體的最優(yōu)化。

3、運輸是第三利潤源的重要基礎(chǔ)

在當今物流系統(tǒng)中，物流費用的一半以上用于完成運輸。有些產(chǎn)品的運輸費用甚至高于產(chǎn)品的生產(chǎn)費用。而在物流過程當中，運輸是至關(guān)重要的一環(huán)。因此，優(yōu)化運輸組織能夠大大降低物流的總體費用，進而提高物流系統(tǒng)的整體經(jīng)濟效益。物流成本的降低也成為物流系統(tǒng)的第三利潤源。

2.最短路問題描述

在物流過程中，確定合理的運輸路線非常重要。合理的運輸路線不僅可以降低運輸成本，提高車輛利用率，同時還可以提高服務(wù)水平。因此，如何確定運輸路線就成為運輸決策中的一個重要因素。運輸合理化，除需要選擇合理的運輸方式外，還需要確定合理的調(diào)運和最佳運輸路線，使運輸量最大，運輸成本最小，運輸距離最短。在現(xiàn)實生活中，常常需要對一批貨物從生產(chǎn)地運送到消費地，在運輸過程中要經(jīng)過不同的地點，如何使得運輸路線最短或運輸時間最短或運輸費用最小，從而提高運輸效率，增加運輸收益就顯得尤為重要。這就涉及到所謂的最短路問題。

在物流過程中，尋求配送路線的最短路問題是最常見的問題。最短路的概念是廣義的，它既可以代表距離，又可以代表時間和費用。我們把與弧相聯(lián)系的距離、時間、費用等稱為弧的權(quán)，那么最短路問題一般可以描述為:

設(shè)VA和VB是圖G={V，E}中的任意兩點，各邊上的權(quán)為Wij(［Vi，Vj］∈E)，最短路問題就是尋找從VA到VB的道路P，使該路的路權(quán)之和W(P)=∑［vivj］∈pWij為最小。

3.Dijkstra算法說明

當前被公認的求解最短路問題的一個經(jīng)典算法就是Dijkstra算法，是由E.W.Dijkstra于1959年提出的在其滿足前提條件為所有弧的權(quán)值必須非負的情況下，適用于最短路求解的算法。該算法在實際問題中有很廣泛的應(yīng)用。Dijkstra算法可以求得從某一給定的點到圖中其他所有節(jié)點的最短路徑，算法的時間復(fù)雜度為o(n2)，n為結(jié)點個數(shù)。具體的算法步驟如下:

第一步 若采用帶權(quán)的鄰接矩陣，arcs表示帶權(quán)有向圖，其中arcs［i］［j］是?。糣i，Vj＞上的權(quán)值。若頂點Vi和頂點Vj不是直接連通的，則arcs［i］ ［j］ 的值為MAX(極大值)。S表示從頂點V出發(fā)的最短路徑的終點的集合，它的初始狀態(tài)為空集。則從頂點V出發(fā)到圖上其余各頂點 (終點)Vi可能存在的路徑的并不僅僅只是一條，因此我們將可能存在的路徑的初始值記為 D［i］ =arcs［LocateVex(G，V)［i］ Vi∈V］。

第二步 尋找選擇Vj，如果滿足式子D［j］ =min{D［i］Vi∈V·S}。則有頂點Vj即為當前求得的一條從頂點V出發(fā)的最短路徑的終點，記為S=S∪ {j}。

第三步 更新從頂點V出發(fā)到集合V·S上任意一頂點Vk可能存在的最短路徑的值，如果滿足表達式D［j］ +arcs［j］［k］ ＜D［k］Vk，則對 D［k］ 進行修改，具體表達式為D［k］ =D ［j］ +arcs［j］［k］。

第四步重復(fù)步驟二和步驟三，循環(huán)就可求得頂點V到圖上其余各個頂點最終的最短路徑及最短路徑的值。

由此可知，Dijkstra算法具有思路清晰，程序?qū)崿F(xiàn)雖然簡單的特點。但是如果頂點數(shù)越多的話，這也就意味著循環(huán)的次數(shù)也就會越多，同樣計算時間也會急劇增加。這樣算法執(zhí)行的時間復(fù)雜度為O(n2)。本文提出一種改進算法策略，其核心思想是將整個帶有權(quán)值的有向圖分區(qū)劃分成各個子圖，這樣的做法基本符合現(xiàn)代物流企業(yè)分區(qū)配送的方法。因此在此基礎(chǔ)上只需對各子圖進行劃分計算各頂點的最短路徑，然后綜合決策進行處理劃分。遵循以下原則:兩點之間直線距離是最短幾何距離，因此在物流多個配送點中，最短路徑一般是配送起點和終點連接的直線周圍，所以應(yīng)該沿著連接起點和終點的直線進行劃分。除此之外，系統(tǒng)具有開辟存儲結(jié)構(gòu)功能，將已經(jīng)算好的頂點之間的最短路徑存儲在數(shù)據(jù)庫中，這樣就避免了計算工作的重復(fù)性。

4.Dijkstra算法在最短路問題上的應(yīng)用分析

假設(shè)某個城市有一個配送中心，擁有足夠的載重量為q的車輛。需要給n個需求點送貨，設(shè)配送中心編號為1，其他需求點編號為i(i=2，……，n)，設(shè)每個需求點的需求量為gi(i=2，……，n)，配送中心有K輛車 (載重量均為q)，且每輛車的位置和需求點位置都是已知的，同時要求每個需求點只能由一輛車為其服務(wù)，以dij表示需求點i到j(luò)的運送距離，D表示車輛一次配送的最大里程限制，目標是配送的總里程最短。

如圖4.1所示，圖V1→V8代表從配送中心V1出發(fā)向需求點V2，V3，……，V8進行依次訪問，要求我們找出從V1出發(fā)到其余各點的最短距離及達到最短距離所通過的最短路徑。

圖4 .1 8個頂點帶權(quán)有向圖

基于運籌學的原理利用傳統(tǒng)表上作業(yè)方法求解上述問題的話，雖然結(jié)果準確，但計算過程卻需要花費太多時間，而且步驟冗長繁瑣，由此不難想象當有向圖中點的個數(shù)相當多時，計算工程量將達到怎樣的程度。當將這一問題采用Dijkstra算法進行計算時，計算機則可在很短的時間內(nèi)計算出精確的結(jié)果并找出準確的路線，從而可以大大的節(jié)省進行計算的工作量和時間。論文就上述問題通過VisualC++編寫程序可得出該問題的最短路徑為:1－2－4－7－8，最短路徑的值為10。結(jié)果如圖4.2所示。

圖4 .2 Dijkstra算法求解圖

5.結(jié)論

在物流配送中經(jīng)常要設(shè)計最佳的配送路線以便提高配送效率，降低配送成本，因此通過計算兩個配送點的最短路線最后去綜合決策多個配送點之間的較優(yōu)的配送路徑。運輸作為物流系統(tǒng)的核心功能要素，隨著現(xiàn)代物流業(yè)的飛速發(fā)展以及小體積、多品類、小批量、高附加值和季節(jié)性商貿(mào)流通產(chǎn)品的運輸逐年增加，運輸作為貨物流通中的必不可少的環(huán)節(jié)，其重要性日益突出。運輸線路的最優(yōu)化直接影響到一個企業(yè)的物流成本、送貨時間，同時也對社會經(jīng)濟效益產(chǎn)生巨大影響。本文通過利用Dijkstra算法對最短路問題進行分析求解，找出滿足約束條件的最優(yōu)解，對Dijkstra算法是求解最短路問題的經(jīng)典算法進行了驗證。

［1］余群英.運輸組織與管理［M］.北京 機械工業(yè)出版社，2009，5

［2］寧宣熙等.管理運籌學教程 ［M］.北京 清華大學出版社，2007，8

［3］田晟.基于Dijkstra算法的物流配送系統(tǒng)最短路徑程序設(shè)計［J］.交通標準化.2009(NO.200):89－92

［4］張念.用Dijkstra算法實現(xiàn)對整車配送線路的優(yōu)化［J］.中國水運.2007(5):141－142

［5］周程.物流配送路徑優(yōu)化策略研究 ［J］.武漢理工大學學報 (交通科學與工程版).2005(5):797－800.