基于Dijkstra算法的物流運(yùn)輸最短路徑的研究

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