基于Dijkstra算法的物流運輸最短路徑的研究

　　摘要：運輸是物流活動的一個主要組成部分，是物流的核心環(huán)節(jié)。運輸?shù)穆窂絻?yōu)化是物流運輸中的一個重要問題，也是在實際應(yīng)用中的一個難以解決的問題。文章首先介紹了運輸在物流中的重要性以及優(yōu)化運輸環(huán)節(jié)進行物流分析的必要性和可行性，接著闡述了Dijkstra算法的基本思路以及求解運輸最短路徑的具體步驟，通過Dijkstra算法找出運輸中的最短路徑，進而減短運輸距離，降低物流成本，提高產(chǎn)品競爭力。
　　關(guān)鍵詞：運輸；最短路徑；Dijkstra算法
　　物質(zhì)運輸將生產(chǎn)和消費所處的不同空間聯(lián)結(jié)起來，為實現(xiàn)實物從生產(chǎn)到消費的移動起到了決定性的作用。在現(xiàn)代生產(chǎn)中，由于生產(chǎn)的專門化、集中化，生產(chǎn)與消費被分割的狀態(tài)越來越嚴(yán)重，被分隔的距離亦越來越大，進而運輸?shù)牡匚灰苍絹碓礁摺＿\輸在整個物流活動過程當(dāng)中起著舉足輕重的作用。
　　一、運輸在物流活動中的核心作用
　　（一）物流系統(tǒng)功能要素的核心是運輸
　　運輸功能創(chuàng)造了貨物的空間效用，儲存功能創(chuàng)造了貨物的時間效用，流通加工功能則改變了貨物的形質(zhì)效用，物流系統(tǒng)中的其他功能均圍繞該三大功能進行，這是物流系統(tǒng)運動中被公認(rèn)的規(guī)律。隨著經(jīng)濟的全球化、一體化的發(fā)展，通過運輸實現(xiàn)貨物的空間效用呈現(xiàn)出明顯的強化態(tài)勢，通過貨物的儲存保管實現(xiàn)起時間效用則呈現(xiàn)弱化趨勢，而通過流通加工實現(xiàn)改變貨物的形質(zhì)效用則需借助運輸或配送才能呈現(xiàn)出強化趨勢。其原因是在社會化大生產(chǎn)條件下，并不追求產(chǎn)品的生產(chǎn)和消費在空間位置上的一致性，且存在較大的地域位置上的差異，這種趨勢造成的直接影響就是對運輸?shù)囊蕾囆栽絹碓酱螅瑹o形中突出了運輸功能的主導(dǎo)作用。
　　（二）運輸是實現(xiàn)物流合理化的關(guān)鍵
　　以盡可能低的成本為用戶提供更多更好的服務(wù)是物流合理化的關(guān)鍵，它是以各物流子系統(tǒng)合理化為基礎(chǔ)的。但是，物流合理化并不是各子系統(tǒng)局部最優(yōu)的簡單疊加，而是根據(jù)系統(tǒng)原理，各子系統(tǒng)合理并相互協(xié)調(diào)產(chǎn)生結(jié)構(gòu)效用，才能使系統(tǒng)總體功能達到最優(yōu)。在當(dāng)代社會，一切物質(zhì)產(chǎn)品的生產(chǎn)和消費均離不開運輸，這不僅是因為運輸是物流系統(tǒng)的大動脈，其合理與否直接影響其他物流子系統(tǒng)的構(gòu)成，而且還因為運輸在物流系統(tǒng)的整體功能中發(fā)揮著中心環(huán)節(jié)的作用。除此以外，運輸費用在全部物流費用中占較大比重，是降低物流費用、提高物流經(jīng)濟效益和社會效益的關(guān)鍵。因此，物流合理化在很大程度上取決于運輸合理化，只有運輸合理化，才能使物流系統(tǒng)更加合理，總體功能更優(yōu)。
　　（三）運輸是“第三利潤源泉”的主要源泉
　　在物流構(gòu)成中所需支付的費用主要有運輸費、倉儲費、包裝費、裝卸搬運費、流通加工費和物流過程中的損耗，其中運輸費所占比重最高，是影響物流成本的重要因素。有關(guān)資料表明，我國運輸費用占社會物流費用近50%的比例，甚至有些產(chǎn)品的運輸費高于其生產(chǎn)成本，而且運輸所需的時間長、距離長、消耗大。通過改革，采取合理化運輸可以大大降低運輸?shù)南乃璧臅r間和費用，對提高經(jīng)濟效益和社會效益均起著重要作用。所謂運輸?shù)奈锪鳌暗谌麧櫾慈钡闹饕慈囊饬x也在于此。
　　二、通過優(yōu)化運輸環(huán)節(jié)進行物流分析的必要性和可行性
　　（一）必要性
　　1、運輸服務(wù)是有效組織輸入和輸出物流的關(guān)鍵。企業(yè)的工廠、倉庫與其他供貨廠商和客戶之間的地理分布直接影響著物流的運輸費用。因此，運輸條件是企業(yè)選擇工廠、倉庫、配送中心等物流設(shè)施配置地點需要考慮的主要因素之一。
　　2、運輸影響著物流的其他構(gòu)成因素。運輸方式的選擇決定著裝運貨物的包裝要求；使用不同類型的運輸工具決定其配套使用裝卸搬運設(shè)備以及接受和發(fā)運站臺的設(shè)計；企業(yè)庫存儲備量的大小，直接受運輸狀況的影響，發(fā)達的運輸系統(tǒng)能夠比較適量、快速和可靠地補充庫存，以降低必要的儲備水平。
　　3、運輸費用在物流費用中占有很大的比重。運輸費用是最大的物流成本之一。組織合理運輸，以最小的費用、最快的時間，及時、準(zhǔn)確、安全地將貨物從其產(chǎn)地運到銷地，是降低物流費用和提高經(jīng)濟效益的重要途徑之一。運輸費用關(guān)系整個物流費用，在物流費用中，運輸費用所占的比重最高，一般來講，在社會物流費用當(dāng)中，運輸費用占將近50%的比重。有些產(chǎn)品的運輸費用甚至高于生產(chǎn)費用。因此，降低運輸費用對于降低物流費用，提高物流經(jīng)濟效益，以及穩(wěn)定商品價格，滿足消費需求，提高社會經(jīng)濟效益都具有重要的意義。
　　4、運輸還與物流的子系統(tǒng)包裝、裝卸、儲存、配送有著不可分割的關(guān)系。運輸、包裝、儲存、配送這些物流的子系統(tǒng)是一個密不可分的有機整體，它們相互銜接、相輔相成。整個物流活動是由包裝、裝卸、儲存、配送、流通加工、運輸?shù)然顒咏M成的，其中運輸是物流活動的主要組成部分，是物流活動的核心環(huán)節(jié)，與其他物流活動息息相關(guān)，無論是企業(yè)的輸入物流還是輸出物流，或者流通領(lǐng)域的銷售物流都必須依靠運輸來實現(xiàn)商品的空間轉(zhuǎn)移。
　　（二）可行性
　　1、物流理論已經(jīng)基本成熟。物流學(xué)是一門綜合性、應(yīng)用性、系統(tǒng)性和拓展性很強的科學(xué)。它涉及自然科學(xué)、社會科學(xué)和工程技術(shù)科學(xué)；涉及到生產(chǎn)、流通和消費領(lǐng)域，國民經(jīng)濟的許多部門。隨著經(jīng)濟的迅速發(fā)展，這些理論現(xiàn)在都已經(jīng)比較成熟，因此，對物流的規(guī)劃分析變得可行。
　　2、物流業(yè)已經(jīng)形成一定規(guī)模。物流業(yè)是將運輸、儲存、裝卸、搬運、包裝、流通加工、配送、信息處理等基本功能根據(jù)實際需要實施有機結(jié)合的活動的集合。物流業(yè)是一個復(fù)合型產(chǎn)業(yè)，物流業(yè)是物流資源產(chǎn)業(yè)化而形成的一種復(fù)合型或聚合型產(chǎn)業(yè)。從某種程度上講，對物流系統(tǒng)進行規(guī)劃分析的主要目的之一就是要減少物流網(wǎng)絡(luò)各個節(jié)點之間的費用消耗，因此物流行業(yè)的規(guī)模大小，將直接決定著物流規(guī)劃結(jié)果的顯著程度。目前，不管是國內(nèi)還是國外，物流都具有相當(dāng)大的規(guī)模，并在國民經(jīng)濟中發(fā)揮著重要作用，因此找到合適的突破點對物流系統(tǒng)中的各個子系統(tǒng)進行規(guī)劃分析，將是非常可行的。
　　3、計算機技術(shù)的發(fā)展。自從進入21世紀(jì)之后，我國計算機技術(shù)得到廣泛的應(yīng)用，如今計算機技術(shù)已經(jīng)涉及到大眾生活的方方面面，計算機正成為進行規(guī)劃研究不可或缺的工具。在對物流因素進行分析時，存在著眾多影響因素，因此分析過程通常比較復(fù)雜，只有借助計算機技術(shù)才能較好地完成。
　　總之，運輸過程對整個物流活動意義重大，所以在物流活動中必須采取科學(xué)合理的運輸路線，有效地降低物流成本。Dijkstra算法就是通過一種方法，使運輸?shù)目偮窂阶疃獭⑦\費最少，盡可能地減少物流成本，提高產(chǎn)品的競爭力。
　　三、Dijkstra算法概述
　　迪杰斯特拉（Dijkstra）算法是一種典型的最短路算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。
　　（一）Dijkstra算法思想
　　Dijkstra算法思想為：設(shè)G=（V，E）是一個帶權(quán)有向圖（也可以是無向圖，無向圖是有向圖的特例），把圖中頂點集合V分成兩組：第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以后每求得一條最短路徑，就將其加入到集合S中，直到全部頂點都加入到S中，算法就結(jié)束了）；第二組為其余未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應(yīng)一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當(dāng)前最短路徑長度。
　　
　　（二）Dijkstra算法具體步驟
　　第一，初始時，S只包含源點，即S＝{頂點}，v的距離為0。U包含除v外的其他頂點，U中頂點u距離為邊上的權(quán)（若v與u有邊）或（若u不是v的出邊鄰接點）。
　　第二，從U中選取一個距離v最小的頂點k，把k加入S中（該選定的距離就是v到k的最短路徑長度）。
　　第三，以k為新考慮的中間點，修改U中各頂點的距離；若從源點v到頂點u的距離（經(jīng)過頂點k）比原來距離（不經(jīng)過頂點k）短，則修改頂點u的距離值，修改后的距離值的頂點k的距離加上邊上的權(quán)。
　　第四，重復(fù)步驟第二步和第三步直到所有頂點都包含在S中。
　　四、Dijkstra算法在求運輸最短路徑上的應(yīng)用
　　某企業(yè)要將一批產(chǎn)品由A地運往F地，從A到F有多條路線選擇，怎樣選擇可以使運輸線路最短（見圖1）。
　　
　　
　　在A、F兩地的交通圖中的點B、C、D、E分別表示4個地名，點與點之間的連線表示兩地之間的公路，邊上所賦值代表兩地間的長度（單位為公里）。
　　用Dijkstra算法求解運輸最短路徑，也就是要找出最短路徑，使總距離最短，總運費最低具體步驟如下：
　　第一，在S集合中：進入A，此時S=，此時最短路徑為A→A=0，以A為中間點，從A開始找。在U集合中：U=，A→B=6，A→C=3，A→其他U中的頂點=∞，發(fā)現(xiàn)A→C=3權(quán)值為最短。
　　第二，在S集合中：進入C，此時S=，此時最短路徑A→A=0，A→C=3，以C為中間點，從A→C=3這條最短路徑開始找。在U集合中：U=，A→C→B=5（比A→B=6要短），此時到B權(quán)值為A→C→B=5，A→C→D=6，A→C→E=7，A→C→其他U中的頂點=∞，發(fā)現(xiàn)A→C→B=5權(quán)值為最短。
　　第三，在S集合中：進入B，此時S=，此時最短路徑A→A=0，A→2661d13021fb8813ba6e8b3599023a2dC=3，A→C→B=5，以B為中間點，從A→C→B=5這條最短路徑開始找。在U集合中：U=，A→C→B→D=10（比第二步的A→C→D=6要長），此時到D權(quán)值改為A→C→D=6，A→C→B→其他U中的頂點=∞，發(fā)現(xiàn)A→C→D=6權(quán)值為最短。
　　第四，在S集合中：進入D，此時S=，此時最短路徑A→A=0，A→C=3，A→C→B=5，A→C→D=6，以D為中間點，從A→C→D=6這條最短路徑開始找。在U集合中，U=，A→C→D→E=8（比第二步的A→C→E=7要長），此時到E權(quán)值更改為A→C→E=7，A→C→D→F=9，發(fā)現(xiàn)A→C→E=7權(quán)值為最短。
　　第五，在S集合中：進入E，此時S=，此時最短路徑為A→A=0，A→C=3，A→C→B=5，A→C→D=6，A→C→E=7，以E為中間點，從A→C→E=7這條最短路徑開始找。在U集合中：U=，A→C→E→F=12（比第四步的A→C→D→F=9要長），此時到F權(quán)值更改為A→C→D→F=9，發(fā)現(xiàn)A→C→D→F=9權(quán)值為最短。
　　第六，在S集合中：進入F，此時S=，此時最短路徑為A→A=0，A→C=3，A→C→B=5，A→C→D=6，A→C→E=7，A→C→D→F=9。此時U集合已空，查找完畢。
　　第七，得到最短路徑。從第六步可知，從A到F的最短路徑為9公里，A到B的最短路徑為A→C→B=5，A到C是最短路徑為A→C=3，A到D的最短路徑為A→C→D=6，A到E的最短路徑為A→C→E=7，A到F的最短路徑為A→C→D→F=9。
　　五、結(jié)束語
　　運輸在整個物流活動中起著至關(guān)重要的作用，在運輸過程中運輸距離的長短將直接影響物流總成本的大小，因此在物流運輸過程中必須確保運輸路徑最短，從而有效地降低運輸成本，提高產(chǎn)品競爭力。本文通過Dijkstra算法求解出物流運輸?shù)淖疃搪窂剑且环N簡單有效的方法，可以很容易地找出運輸?shù)淖疃搪窂健?br/>　　參考文獻：
　　1、