物流運(yùn)輸系統(tǒng)中最短路徑算法及應(yīng)用

1、物流運(yùn)輸系統(tǒng)中最短路徑算法及應(yīng)用摘要：根據(jù)GIS中網(wǎng)絡(luò)計(jì)算的實(shí)際情況，根據(jù)A*算法和Dijkstra算法中快速 搜索技術(shù)的實(shí)現(xiàn)入手，采用最短路徑算法結(jié)合 GIS的方法，提出了一種解決物流運(yùn)輸中 車(chē)輛路徑問(wè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)化決策的問(wèn)題。本文只討論物流配送 路徑優(yōu)化問(wèn)題。

2、合理選擇配送路徑，對(duì)加快配送速度、提高服務(wù)質(zhì)量、降低配送 成本以及增加經(jīng)濟(jì)效益都有很大影響。 所謂的車(chē)輛路徑問(wèn)題（ Vehicle RoutingProblem）VRP。它也是目前在物流系統(tǒng)中較受關(guān)注的一個(gè)方面。它是指在客戶需求 位置已知的情況下，確定車(chē)輛在各個(gè)客戶間的行程路線，使得運(yùn)輸路線最短或運(yùn)輸 成本最低。一、系統(tǒng)介紹 求解物流配送路徑優(yōu)化問(wèn)題的方法有很多是路徑引導(dǎo)的功能。本設(shè)計(jì)主要功能 是從給定的車(chē)輛位置和多個(gè)目標(biāo)點(diǎn)位置，計(jì)算車(chē)輛遍歷所有目標(biāo)點(diǎn)的代價(jià)最優(yōu)值， 并給出代價(jià)值和路徑描述，并在地圖上進(jìn)行路徑顯示。路徑引導(dǎo)模塊的主要過(guò)程： 初始化路網(wǎng) -得到車(chē)輛信息和目標(biāo)點(diǎn)信息 -求車(chē)輛遍歷所

3、有目標(biāo)點(diǎn)的代價(jià)最優(yōu)值和 遍歷次序（僅求遍歷次序，而不需求走什么道路） -求每個(gè)目標(biāo)點(diǎn)遍歷的最優(yōu)路徑 （求具體的道路） -輸出遍歷次序和路徑描述二、車(chē)輛遍歷所有目標(biāo)點(diǎn)的代價(jià)最優(yōu)值算法本設(shè)計(jì)中的遍歷次序的算法采用的是等代價(jià)搜索法，它是A *算法的一種簡(jiǎn)化版本。等代價(jià)搜索法也是基于寬度優(yōu)先搜索上進(jìn)行了部分優(yōu)化的一種算法,它與 A算法的 相似之處都是每次只展開(kāi)某一個(gè)結(jié)點(diǎn) （不是展開(kāi)所有結(jié)點(diǎn)） , 不同之處在于： 它不需要去另找專(zhuān)門(mén)的估價(jià)函數(shù)，而是以該結(jié)點(diǎn)到A點(diǎn)的距離作為估價(jià)值。例如圖1, 從A點(diǎn)出發(fā)，要遍歷C,B,D,E四個(gè)目標(biāo)點(diǎn)。具體算法過(guò)程如下：AD圖1起點(diǎn)和遍歷目標(biāo)點(diǎn)圖1、 從A點(diǎn)開(kāi)始依次展開(kāi)得

4、到 AB( 7)、AC( 3)、AD( 10)、AE (15)四個(gè)新結(jié)點(diǎn)， 把第一層結(jié)點(diǎn)A標(biāo)記為已展開(kāi),并且每個(gè)新結(jié)點(diǎn)要Record下其距離(括號(hào)中的 數(shù)字)；2、 把未展開(kāi)過(guò)的AB AC AD AE四個(gè)結(jié)點(diǎn)中距離最小的一個(gè)展開(kāi)，即展開(kāi)AC(3) 結(jié)點(diǎn),得到ACB( 8)、ACD( 16)、ACE( 13)三個(gè)結(jié)點(diǎn)，并把結(jié)點(diǎn)AC標(biāo)記為已 展開(kāi)；3、 再?gòu)奈凑归_(kāi)的所有結(jié)點(diǎn)中找出距離最小的一個(gè)展開(kāi) ，即展開(kāi)AB ( 7)結(jié)點(diǎn)，得到 ABC( 12)、ABD(20)、ABE( 19)三個(gè)結(jié)點(diǎn)，并把結(jié)點(diǎn)AB標(biāo)記為已展開(kāi)；4、 再次從未展開(kāi)的所有結(jié)點(diǎn)中找出距離最小的一個(gè)展開(kāi),即展開(kāi)ACB8)結(jié)點(diǎn)(不再展

5、開(kāi)AD AE);5、每次展開(kāi)所有未展開(kāi)的結(jié)點(diǎn)中距離最小的那個(gè)結(jié)點(diǎn) ，直到展開(kāi)的新結(jié)點(diǎn)中出現(xiàn)目標(biāo)Case (結(jié)點(diǎn)含有5個(gè)字母)時(shí),即得到了 Result.由上可見(jiàn),A *算法和等代價(jià)搜索法并沒(méi)有象寬度優(yōu)先搜索一樣展開(kāi)所有結(jié)點(diǎn)，只是根據(jù)某一原則(或某一估價(jià)函數(shù)值)每次展開(kāi)距離 A點(diǎn)最近的那個(gè)結(jié)點(diǎn)(或是估價(jià)函 數(shù)計(jì)算出的最可能的那個(gè)結(jié)點(diǎn))，反復(fù)下去即可最終得到答案雖然中途有時(shí)也展開(kāi)了 一些并不是答案的結(jié)點(diǎn)，但這種展開(kāi)并不是大規(guī)模的，不是全部展開(kāi)，因而耗時(shí)要比寬 度優(yōu)先搜索小得多.三、目標(biāo)點(diǎn)遍歷的最優(yōu)路徑(求具體的道路3.1迪杰斯特拉算法在計(jì)算兩個(gè)具體目標(biāo)點(diǎn)間的具體道路時(shí)，本設(shè)計(jì)采用了迪杰斯特拉算法。

6、在設(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)到其本身的最短路徑是零路 (沒(méi)有弧的路 ) ，其長(zhǎng)度等于 零)；pj則是從s到j(luò)的最短路徑中j點(diǎn)的前一點(diǎn)。求解從起源點(diǎn)s到點(diǎn)j的 最短路徑算法的基本過(guò)程如下：1) 初始化。起源點(diǎn)設(shè)置為：ds=O, ps為空； 所有其他點(diǎn)：di= s, 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

7、 dj, dk+lkj 式中, lkj 是從點(diǎn) k 到 j 的直接連接距離。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)記。3.2 本文提出的 Dijkstra 算法實(shí)現(xiàn)GIS 中的網(wǎng)絡(luò)一般為各種道路、管網(wǎng)、管線等,這些網(wǎng)絡(luò)在具有圖理論中的基 本特征的同時(shí),更具有自己在

8、實(shí)際中的一些特點(diǎn)。首先,在 GIS 中大多數(shù)網(wǎng)絡(luò)都是 有向帶權(quán)圖,如道路有單雙向問(wèn)題,電流、水流都有方向(如果是無(wú)向圖也可歸為 有向圖的特例),且不同的方向可能有不同的權(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來(lái)標(biāo)記，以實(shí)現(xiàn)高速優(yōu)先考慮。在最后算總路程時(shí)把它乘上縮小 的倍數(shù)。即保證總路程不變。本系統(tǒng)利用GPS定位系統(tǒng)實(shí)現(xiàn)對(duì)物流系統(tǒng)的相關(guān)車(chē)輛進(jìn)行監(jiān)控、 調(diào)度、指揮、管理, 以提高物流業(yè)務(wù)的效率，有效的控制物流成本，保障司機(jī)和貨物的安全，提高管理 水平和服務(wù)質(zhì)量。系