物流運(yùn)輸系統(tǒng)中最短路徑算法及應(yīng)用物流運(yùn)輸系統(tǒng)中最短路徑算法及應(yīng)用物流運(yùn)輸系統(tǒng)中最短路徑算法及應(yīng)用V:1.0精細(xì)整理，僅供參考物流運(yùn)輸系統(tǒng)中最短路徑算法及應(yīng)用日期：20xx年X月物流運(yùn)輸系統(tǒng)中最短路徑算法及應(yīng)用摘要：根據(jù)GIS中網(wǎng)絡(luò)計(jì)算的實(shí)際情況，根據(jù)A*算法和Dijkstra算法中快速搜索技術(shù)的實(shí)現(xiàn)入手，采用最短路徑算法結(jié)合GIS的方法，提出了一種解決物流運(yùn)輸中車輛路徑問題的高效率實(shí)現(xiàn)的方法。引言：在競(jìng)爭(zhēng)日益激烈的現(xiàn)代商業(yè)社會(huì)，企業(yè)只有以市場(chǎng)為核心去適應(yīng)不斷變化的環(huán)境并及時(shí)對(duì)市場(chǎng)做出發(fā)應(yīng)，才能在競(jìng)爭(zhēng)中立于不敗之地。物流管理正是以實(shí)現(xiàn)上述要求為目標(biāo)的。而物流配送是現(xiàn)代化物流管理中的一個(gè)重要環(huán)節(jié)。它是指按用戶的定貨要求，在配送中心進(jìn)行分貨、配貨，并將配好的貨物及時(shí)送交收貨人的活動(dòng)。在物流配送業(yè)務(wù)中，存在許多優(yōu)化決策的問題。本文只討論物流配送路徑優(yōu)化問題。合理選擇配送路徑，對(duì)加快配送速度、提高服務(wù)質(zhì)量、降低配送成本以及增加經(jīng)濟(jì)效益都有很大影響。所謂的車輛路徑問題（VehicleRoutingProblem）VRP。它也是目前在物流系統(tǒng)中較受關(guān)注的一個(gè)方面。它是指在客戶需求位置已知的情況下，確定車輛在各個(gè)客戶間的行程路線，使得運(yùn)輸路線最短或運(yùn)輸成本最低。一、系統(tǒng)介紹求解物流配送路徑優(yōu)化問題的方法有很多是路徑引導(dǎo)的功能。本設(shè)計(jì)主要功能是從給定的車輛位置和多個(gè)目標(biāo)點(diǎn)位置，計(jì)算車輛遍歷所有目標(biāo)點(diǎn)的代價(jià)最優(yōu)值，并給出代價(jià)值和路徑描述，并在地圖上進(jìn)行路徑顯示。路徑引導(dǎo)模塊的主要過程：初始化路網(wǎng)->得到車輛信息和目標(biāo)點(diǎn)信息->求車輛遍歷所有目標(biāo)點(diǎn)的代價(jià)最優(yōu)值和遍歷次序（僅求遍歷次序，而不需求走什么道路）->求每個(gè)目標(biāo)點(diǎn)遍歷的最優(yōu)路徑（求具體的道路）->輸出遍歷次序和路徑描述二、車輛遍歷所有目標(biāo)點(diǎn)的代價(jià)最優(yōu)值算法本設(shè)計(jì)中的遍歷次序的算法采用的是等代價(jià)搜索法，它是A＊算法的一種簡(jiǎn)化版本。等代價(jià)搜索法也是基于寬度優(yōu)先搜索上進(jìn)行了部分優(yōu)化的一種算法,它與A＊算法的相似之處都是每次只展開某一個(gè)結(jié)點(diǎn)（不是展開所有結(jié)點(diǎn)）,不同之處在于：它不需要去另找專門的估價(jià)函數(shù),而是以該結(jié)點(diǎn)到A點(diǎn)的距離作為估價(jià)值。例如圖1，從A點(diǎn)出發(fā)，要遍歷C,B,D,E四個(gè)目標(biāo)點(diǎn)。具體算法過程如下：圖1起點(diǎn)和遍歷目標(biāo)點(diǎn)圖1、從A點(diǎn)開始依次展開得到AB（7）、AC（3）、AD（10）、AE（15）四個(gè)新結(jié)點(diǎn),把第一層結(jié)點(diǎn)A標(biāo)記為已展開,并且每個(gè)新結(jié)點(diǎn)要Record下其距離（括號(hào)中的數(shù)字）;2、把未展開過的AB、AC、AD、AE四個(gè)結(jié)點(diǎn)中距離最小的一個(gè)展開,即展開AC（3）結(jié)點(diǎn),得到ACB（8）、ACD（16）、ACE（13）三個(gè)結(jié)點(diǎn),并把結(jié)點(diǎn)AC標(biāo)記為已展開;3、再?gòu)奈凑归_的所有結(jié)點(diǎn)中找出距離最小的一個(gè)展開,即展開AB（7）結(jié)點(diǎn),得到ABC（12）、ABD（20）、ABE（19）三個(gè)結(jié)點(diǎn),并把結(jié)點(diǎn)AB標(biāo)記為已展開;4、再次從未展開的所有結(jié)點(diǎn)中找出距離最小的一個(gè)展開,即展開ACB（8）結(jié)點(diǎn)……（不再展開AD、AE）;5、每次展開所有未展開的結(jié)點(diǎn)中距離最小的那個(gè)結(jié)點(diǎn),直到展開的新結(jié)點(diǎn)中出現(xiàn)目標(biāo)Case（結(jié)點(diǎn)含有5個(gè)字母）時(shí),即得到了Result.由上可見,A＊算法和等代價(jià)搜索法并沒有象寬度優(yōu)先搜索一樣展開所有結(jié)點(diǎn),只是根據(jù)某一原則（或某一估價(jià)函數(shù)值）每次展開距離A點(diǎn)最近的那個(gè)結(jié)點(diǎn)（或是估價(jià)函數(shù)計(jì)算出的最可能的那個(gè)結(jié)點(diǎn)）,反復(fù)下去即可最終得到答案.雖然中途有時(shí)也展開了一些并不是答案的結(jié)點(diǎn),但這種展開并不是大規(guī)模的,不是全部展開,因而耗時(shí)要比寬度優(yōu)先搜索小得多.三、目標(biāo)點(diǎn)遍歷的最優(yōu)路徑（求具體的道路迪杰斯特拉算法在計(jì)算兩個(gè)具體目標(biāo)點(diǎn)間的具體道路時(shí)，本設(shè)計(jì)采用了迪杰斯特拉算法。在設(shè)計(jì)中又對(duì)迪杰斯特拉算法進(jìn)行優(yōu)化，以實(shí)現(xiàn)高速公路優(yōu)先。Dijkstra算法的基本思路是：假設(shè)每個(gè)點(diǎn)都有一對(duì)標(biāo)號(hào)(dj,pj)，其中dj是從起源點(diǎn)s到點(diǎn)j的最短路徑的長(zhǎng)度(從頂點(diǎn)到其本身的最短路徑是零路(沒有弧的路)，其長(zhǎng)度等于零)；pj則是從s到j(luò)的最短路徑中j點(diǎn)的前一點(diǎn)。求解從起源點(diǎn)s到點(diǎn)j的最短路徑算法的基本過程如下：1)初始化。起源點(diǎn)設(shè)置為：①ds=0,ps為空;②所有其他點(diǎn):di=∞,pi=;

③標(biāo)記起源點(diǎn)s，記k=s,其他所有點(diǎn)設(shè)為未標(biāo)記的。2)檢驗(yàn)從所有已標(biāo)記的點(diǎn)k到其直接連接的未標(biāo)記的點(diǎn)j的距離，并設(shè)置：dj=min［dj,dk+lkj］式中，lkj是從點(diǎn)k到j(luò)的直接連接距離。3)選取下一個(gè)點(diǎn)。從所有未標(biāo)記的結(jié)點(diǎn)中，選取dj中最小的一個(gè)i：di=min［dj,所有未標(biāo)記的點(diǎn)j］點(diǎn)i就被選為最短路徑中的一點(diǎn)，并設(shè)為已標(biāo)記的。4)找到點(diǎn)i的前一點(diǎn)。從已標(biāo)記的點(diǎn)中找到直接連接到點(diǎn)i的點(diǎn)j*，作為前一點(diǎn),設(shè)置：i=j*5)標(biāo)記點(diǎn)i。如果，則算法完全推出，否則，記k=i，轉(zhuǎn)到2)再繼續(xù)。直到所有點(diǎn)已標(biāo)記。本文提出的Dijkstra算法實(shí)現(xiàn)GIS中的網(wǎng)絡(luò)一般為各種道路、管網(wǎng)、管線等，這些網(wǎng)絡(luò)在具有圖理論中的基本特征的同時(shí)，更具有自己在實(shí)際中的一些特點(diǎn)。首先，在GIS中大多數(shù)網(wǎng)絡(luò)都是有向帶權(quán)圖，如道路有單雙向問題，電流、水流都有方向（如果是無向圖也可歸為有向圖的特例），且不同的方向可能有不同的權(quán)值。更重要的一點(diǎn)是，根據(jù)最短路徑算法的特性可以知道，頂點(diǎn)的出度是個(gè)重要指標(biāo)，但是其入度在算法里則不必考慮。在具體實(shí)現(xiàn)時(shí)為了能實(shí)現(xiàn)高速優(yōu)先，如果是高速，在標(biāo)記兩點(diǎn)間距離是按實(shí)際距離的1/2或1/3來標(biāo)記，以實(shí)現(xiàn)高速優(yōu)先考慮。在最后算總路程時(shí)把它乘上縮小的倍數(shù)。即保證總路程不變。本系統(tǒng)利用GPS定位系統(tǒng)實(shí)現(xiàn)對(duì)物流系統(tǒng)的相關(guān)車輛進(jìn)行監(jiān)控、調(diào)度、指揮、管理，以提高物流業(yè)務(wù)的效率，有效的控制物流成本，保障司機(jī)和貨物的安全，提高管理水平