Dijkstra算法在運輸線路優化問題上的應用研究

顏保凡

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

0.引言

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

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

1.1 運輸與物流的關系

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

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

1、合理分工、提升效率

運輸合理化能夠充分整合現有的運力以及資源，有效發揮中轉環節中各種運輸方式的優勢，最終達到以最小的運輸消耗滿足相應的運輸需求，從而提高效率。

2、降低成本、增長效益

運輸合理化，能充分發揮運輸工具的效能，節約運力和勞力，通過減少運輸環節、優化運輸路徑、提高運輸速度等手段實現運輸效益最大化。

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

1、運輸是物流系統功能要素的核心

隨著社會經濟發展水平的不斷提高以及全程物流的迅猛發展，運輸的“空間效用”越發顯著。而用戶的消費只有借助于運輸或配送的緊密配合才能得以最終實現，在物流系統的三大功能要素中，運輸功能的主導地位和核心作用日益凸顯，逐漸成為物流系統高效、優質功能發揮的關鍵要素之一。

2、運輸是提升物流系統水平的關鍵

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

3、運輸是第三利潤源的重要基礎

在當今物流系統中，物流費用的一半以上用于完成運輸。有些產品的運輸費用甚至高于產品的生產費用。而在物流過程當中，運輸是至關重要的一環。因此，優化運輸組織能夠大大降低物流的總體費用，進而提高物流系統的整體經濟效益。物流成本的降低也成為物流系統的第三利潤源。

2.最短路問題描述

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

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

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

3.Dijkstra算法說明

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

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

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

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

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

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

4.Dijkstra算法在最短路問題上的應用分析

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

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

圖4 .1 8個頂點帶權有向圖

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

圖4 .2 Dijkstra算法求解圖

5.結論

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

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

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

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

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

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