基于Dijkstra算法的物流配送最短路徑算法研究

1、總第257期2011年第3期計(jì)算機(jī)與數(shù)字工程Computer&D ig ital Eng ineer ing48基于Dijkstra算法的物流配送最短路徑算法研究*王 華(陜西交通職業(yè)技術(shù)學(xué)院 西安 710021摘 要 根據(jù)城市交通網(wǎng)絡(luò)的特點(diǎn),運(yùn)用結(jié)點(diǎn) 弧段 有向線結(jié)構(gòu)描述交通網(wǎng)絡(luò),利用動(dòng)態(tài)分段技術(shù)建立了基于AR C G IS的配貨網(wǎng)絡(luò)數(shù)據(jù)庫,充分考慮了配貨路線短、用時(shí)少、費(fèi)用低的特點(diǎn),運(yùn)用Dijkst ra算法實(shí)現(xiàn)物流配送最短路徑算法,提高了城市物流配送的便利性和高效性。關(guān)鍵詞 交通網(wǎng)絡(luò);A r cG IS;數(shù)據(jù)庫;Dijkstr a;最短路徑中圖分類號(hào) F719;P208Logis

2、tics Distribution Shortest Path Based on Dijkstra A lgorithmWa ng Hua(ShaanX i Colleg e o f Communication T echno log y,Xi an 710021A bstract Establish a log istics distr ibution database based on A rcGIS acco rding to the character istics o f urban tr affic netw or k,using node a rc description of

3、transport,achieve log istics distributio n shor test path based o n dijkstr a considering of less rount/t ime/cost,improv e the co nv enience of ueban lo gist ics distr ibut ion efficiency.Key Words tr affic netw o rk,A rcG IS,database,D ijkstra,sho rtest pathClass Nu mber F719;P2081 引言物流是指一切旨在創(chuàng)造空間效

4、用、時(shí)間效用和形質(zhì)效用的物資物質(zhì)實(shí)體的流動(dòng)1。它將運(yùn)輸、倉儲(chǔ)、裝卸、加工、整理、配送、信息等方面有機(jī)結(jié)合,形成完整的供應(yīng)鏈,為用戶提供多功能、一體化的綜合性服務(wù)。配送是物流中一種特殊的、綜合的活動(dòng)形式,是物流系統(tǒng)中非常重要的一個(gè)環(huán)節(jié),它的運(yùn)作狀況對(duì)整個(gè)物流系統(tǒng)起著至關(guān)重要的作用。配送中心作為物流活動(dòng)中專職從事配送工作的組織者,具有規(guī)模大、配送能力強(qiáng)的特點(diǎn),從而使得由配送中心對(duì)用戶進(jìn)行需求物品配送成為物流配送的主要形式。而其中配送車輛的路徑合理與否,對(duì)于配送速度、配送費(fèi)用、運(yùn)力配備以及配送成本與效益的影響均很大,采用科學(xué)合理的方法來確定車輛路徑便成為配送中心進(jìn)行配送活動(dòng)的一項(xiàng)重要工作2。而現(xiàn)實(shí)中

5、客戶眾多且分散、城市道路復(fù)雜等客觀條件的制約,使得配送車輛的調(diào)度存在空置率和空駛率非常大的問題,降低了物流企業(yè)的工作效率和經(jīng)濟(jì)效益。在圖論中有很多種算法可以實(shí)現(xiàn)最短路徑的搜索,最典型、最常用的算法為Dijkstar算法34。本文針對(duì)GIS的應(yīng)用特點(diǎn),闡述了從GIS數(shù)據(jù)分析入手,構(gòu)建用于實(shí)現(xiàn)算法的邏輯網(wǎng)絡(luò),并在數(shù)據(jù)分析的基礎(chǔ)上,實(shí)現(xiàn)基于Dijkstra算法的物流配送最短路徑。2 建立模型及屬性數(shù)據(jù)庫城市交通主要由眾多的街道相交、相連而構(gòu)成,并組成縱橫交錯(cuò)、錯(cuò)綜復(fù)雜的城市交通網(wǎng)絡(luò)圖。本文以交叉路口點(diǎn)把道路進(jìn)行分割,這樣整個(gè)交通網(wǎng)將由交叉路口點(diǎn)和路段組成,并定義交叉路口點(diǎn)為網(wǎng)絡(luò)的節(jié)點(diǎn),路段為網(wǎng)絡(luò)的邊

6、,建立模型過程就是把現(xiàn)實(shí)中的城市道路網(wǎng)絡(luò)實(shí)體抽象為網(wǎng)絡(luò)圖論理論中的網(wǎng)絡(luò)圖,這就要理解它們二者的不同之*收稿日期:2010年9月7日,修回日期:2010年10月10日作者簡(jiǎn)介:王華,女,碩士,講師,研究方向:電子商務(wù)與物流。2011年第3期計(jì)算機(jī)與數(shù)字工程49處,然后通過一定的綜合變換把它們有機(jī)地對(duì)應(yīng)起來,城市網(wǎng)絡(luò)圖最大特點(diǎn)有以下幾個(gè)方面:1城市交通特征的空間分布存在顯著的方向性差異,同一道路路段的不同方向。因此,由城市道路網(wǎng)系統(tǒng)抽象出來的網(wǎng)絡(luò)應(yīng)該是有向帶權(quán)圖,道路網(wǎng)絡(luò)系統(tǒng)中的交叉口被抽象為網(wǎng)絡(luò)圖中的節(jié)點(diǎn),而交叉口之間的路段被抽象為網(wǎng)絡(luò)圖中帶權(quán)弧。2在公路路網(wǎng)分析規(guī)劃或交通規(guī)劃研究中,交叉口僅作

7、為路的交叉點(diǎn)或控制段的節(jié)點(diǎn)來考慮,其長(zhǎng)度等幾何要素也要記入里程。3拓?fù)潢P(guān)系的表達(dá),在傳統(tǒng)平面模型中道路之間的拓?fù)潢P(guān)系通過弧段節(jié)點(diǎn)屬性表的方式隱式表達(dá),交叉的道路在交叉口分享節(jié)點(diǎn),這是一種典型幾何拓?fù)浔磉_(dá)。針對(duì)以上城市交通網(wǎng)絡(luò)特點(diǎn),把城市道路網(wǎng)絡(luò)實(shí)體抽象為網(wǎng)絡(luò)圖論理論中的網(wǎng)絡(luò)圖,然后在此模型基礎(chǔ)上建立相應(yīng)的屬性數(shù)據(jù)庫,本文中空間數(shù)據(jù)庫共分2個(gè)圖層:節(jié)點(diǎn)圖層及道路圖層,每個(gè)圖層有其對(duì)應(yīng)的屬性表結(jié)構(gòu),屬性表結(jié)構(gòu)文件定義了空間對(duì)象的屬性數(shù)據(jù)的表結(jié)構(gòu)。因此,在節(jié)點(diǎn)圖層和道路圖層的屬性表結(jié)構(gòu)文件中定義的節(jié)點(diǎn)和道路信息如表1、表2所示。表1 路段結(jié)點(diǎn)屬性表節(jié)點(diǎn)代碼節(jié)點(diǎn)名稱關(guān)聯(lián)道路關(guān)聯(lián)道路數(shù)N odeID N

8、 o deN ame linkr oad linkro adnum表2 路段信息屬性表路段代碼路段名稱路段長(zhǎng)度行車方向起始站點(diǎn)終止站點(diǎn)RoadID RoadNam RoadLeg RoadDir RoadF RoadE 在文件中主要包含了空間數(shù)據(jù),指明了地圖的坐標(biāo)系、屬性表結(jié)構(gòu)、地圖對(duì)象的類型和地理坐標(biāo)信息等。對(duì)圖層中每一路段,均記錄了該路段的起點(diǎn)和終點(diǎn)經(jīng)緯度坐標(biāo);因此,可以直接對(duì)文件進(jìn)行操作,從中提取各節(jié)點(diǎn)的坐標(biāo)信息,表2中有路段起點(diǎn)、終點(diǎn),這樣表1、表2的屬性表就建立了聯(lián)系。3 Dijkstra算法過程城市道路網(wǎng)模型表示為G=(V,E,這里V表示站點(diǎn)綜合后產(chǎn)生的節(jié)點(diǎn)集合,E為相鄰兩節(jié)點(diǎn)的距

9、離即弧段距離它是一個(gè)非負(fù)實(shí)數(shù)。E=d a b|d a b=F(X1,X2,X3, (1式中,X1為簡(jiǎn)單距離因子表示道路幾何距離;X2為路面等級(jí)因子;X3為擁擠程度因子。路面等級(jí)因子X2和擁擠程度因子X3表示路面等級(jí)和人、車流量等因素對(duì)通行能力的影響,可以使用阻抗值來表示這種影響程度,而阻抗值的大小就需對(duì)整個(gè)交通區(qū)內(nèi)路段等級(jí)和擁擠程度進(jìn)行分類,然后依次對(duì)每一類賦予阻抗值,這樣阻抗值的大小表示路段等級(jí)和擁擠程度等對(duì)通行能力的影響,雖然這種影響只是定性的并不能如實(shí)表示影響的大小,但卻具有橫向的比較性。Dijkstra算法的基本思路是:假如每一點(diǎn)都有一對(duì)標(biāo)號(hào)(d j,p j,其中d j是從起源點(diǎn)s到點(diǎn)

10、j的最短路徑的長(zhǎng)度(從一個(gè)點(diǎn)到其本身的長(zhǎng)度為0,兩個(gè)互不相通的點(diǎn)的距離為無窮大,p j則是從s 到j(luò)的最短路徑中j點(diǎn)的前一點(diǎn),求解從起源點(diǎn)s 到j(luò)的最短路徑算法基本過程如下:1初始化,起始點(diǎn)設(shè)置為:d s=0,p s為空; !所有其它點(diǎn):d t=,對(duì)不同的點(diǎn)尋找最短路徑時(shí),p t不同;#標(biāo)記起源點(diǎn)s,記k=s,其它所有點(diǎn)設(shè)置為未標(biāo)記的。2檢查從所有已標(biāo)記的點(diǎn)k到其直接連接的未標(biāo)記的點(diǎn)j的距離,并設(shè)置d j=m ind j,d k+l kj(2式中,l kj為從k到j(luò)的直接連接距離。3選取下一個(gè)點(diǎn),從所有未標(biāo)記的結(jié)點(diǎn)中,選取d j中最小的一個(gè)i值d i=mind j,所有未標(biāo)記的點(diǎn)j對(duì)應(yīng)點(diǎn)i最短

11、路徑中的一點(diǎn),并設(shè)為已標(biāo)定的4找到點(diǎn)i的前一點(diǎn),從已標(biāo)記的點(diǎn)中找到直接連接點(diǎn)i的點(diǎn)u作為前一點(diǎn),設(shè)置i=u5標(biāo)記點(diǎn)i,如果所有點(diǎn)已標(biāo)記,則算法退出,否則記k=i,轉(zhuǎn)到2再繼續(xù)。由上可知,頂點(diǎn)越多,循環(huán)次數(shù)越多,計(jì)算時(shí)間將成倍增長(zhǎng)。Dijkstra算法所采用的圖遍歷是以頂點(diǎn)數(shù)為基數(shù)作二次循環(huán)6,每重循環(huán)的次數(shù)均為節(jié)點(diǎn)數(shù)n,它的執(zhí)行過程產(chǎn)生了以s為節(jié)點(diǎn)的一棵樹,隨著算法的進(jìn)一步執(zhí)行該樹向四面八方延伸,直至到達(dá)終點(diǎn)為止,其算法執(zhí)行的時(shí)間復(fù)雜度為O(n2,它可以尋找出從源點(diǎn)s到所有節(jié)點(diǎn)的最短路徑。4 算法實(shí)現(xiàn)在ARCGIS環(huán)境下對(duì)地圖進(jìn)行矢量化,然后再在VB環(huán)境下通過Arco bject二次開發(fā),實(shí)現(xiàn)

12、了最短路徑的快速搜索,圖中共有交叉路口138個(gè),該機(jī)算是在計(jì)算機(jī)配置為Pentium550,內(nèi)存為128M,硬盤為10G,用Dijkstr a時(shí)間為0.23t,圖中黑粗線即為起始站點(diǎn)到終點(diǎn)的最優(yōu)路徑(大雁塔 小雁塔,列表框內(nèi)顯示的是該線路所經(jīng)過的站點(diǎn)。50王 華:基于D ijkstra算法的物流配送最短路徑算法研究第39 卷圖1 Dijkstra算法查詢最短路徑Dijkstra算法所采用的圖遍歷是以頂點(diǎn)數(shù)為基數(shù)作二次循環(huán)5,78,每重循環(huán)的次數(shù)均為節(jié)點(diǎn)數(shù)n,其算法執(zhí)行的時(shí)間復(fù)雜度為O(n2,它可以尋找出從一個(gè)源點(diǎn)到所有節(jié)點(diǎn)的最短路徑。Dijkstra 在他的算法中,從上一步到下一步,利用節(jié)點(diǎn)標(biāo)

13、號(hào)方法存儲(chǔ)計(jì)算信息來避免那些重復(fù)的加法和比較,路徑信息通過記錄每個(gè)節(jié)點(diǎn)的前繼弧獲得,而不是記錄路徑的所有歷弧。5 結(jié)語采用ArcGIS的集成開發(fā)方式,設(shè)計(jì)了城市物流配送最短路徑查詢系統(tǒng)。本系統(tǒng)主要面向配貨公司、物流企業(yè)和客戶,為不同需求的用戶提供全面、準(zhǔn)確的物流配送信息,該系統(tǒng)采用Dijkstra算法可以尋找出從一個(gè)源點(diǎn)到所有節(jié)點(diǎn)的最短路徑。Dijkstra在它的算法中,從上一步到下一步,利用節(jié)點(diǎn)標(biāo)號(hào)方法存儲(chǔ)計(jì)算信息來避免那些重復(fù)的加法和比較,路徑信息通過記錄每個(gè)節(jié)點(diǎn)的前弧段獲得,而不是記錄路徑的所有弧段,幫助客戶選擇最優(yōu)配貨路線,以提高城市物流配送的便利性和高效性。參考文獻(xiàn)1王槐林,劉明菲.

14、物流管理學(xué)M.武漢:武漢大學(xué)出版社,20022鄭峰峻.改進(jìn)的蟻群算法在物流配送路徑問題中的實(shí)現(xiàn)J.物流科技,2010(2:21243章淑君,曹建成.基于DijK st ra算法的最短路徑功能的實(shí)現(xiàn)方法J.測(cè)繪標(biāo)準(zhǔn)化,2005,66(21:30364趙學(xué)峰.一種求解T SP的混合蟻群算法J.西北師范大學(xué)學(xué)報(bào),2003,39(4:31345劉云忠,宣慧玉.螞蟻算法在車輛路徑問題中的研究J.信息與控制,2004,33(2:2492526鄒智軍.T JT S仿真系統(tǒng)的應(yīng)用J.中國(guó)公路學(xué)報(bào),2000,14(增刊:92967宣登殿,胡大偉,藺宏良.基于GIS的城市物流配送系統(tǒng)規(guī)劃方法J.長(zhǎng)安大學(xué)學(xué)報(bào)(自然

15、科學(xué)版,2006,26(2:84878葛志偉,李怡,滕春賢.基于G IS的物流配送系統(tǒng)的分析與設(shè)計(jì)研究J.哈爾濱理工大學(xué)學(xué)報(bào),2005,10(6:7073(上接第8頁5 結(jié)語本文提出了一種的局部對(duì)比度增強(qiáng)算法,該算法吸取了基于直方圖修正的對(duì)比度增強(qiáng)算法的優(yōu)點(diǎn),將其與局部直方圖均衡算法POSHE相結(jié)合,并解決了POSHE算法的子塊自適應(yīng)問題。實(shí)驗(yàn)結(jié)果表明本文算法具有噪聲魯棒性、可調(diào)節(jié)動(dòng)態(tài)范圍、增強(qiáng)等級(jí)可控制、局部對(duì)比度強(qiáng)的優(yōu)點(diǎn),增強(qiáng)后的圖像具有較好的視覺效果。為使算法能應(yīng)用到實(shí)際,后續(xù)的工作中,應(yīng)該找到該算法的快速算法,提高效率,同時(shí)使其中的一些參數(shù)更加優(yōu)化,使該算法的自適應(yīng)性更強(qiáng)。參考文獻(xiàn)1岡

16、薩雷斯,等.數(shù)字圖像處理M.北京:電子工業(yè)出版社,2007:72742H yunsup Y oo n,Y oung jo on Han,Her nsoo H ahn.Image Contrast Enhancement based Sub histog r am Equali zation T echnique witho ut Over equalization N oiseJ.Internatio nal Journal of Comput er Science and Eng i neer ing,2009,3(2:8187bi histog ram equalizat ionJ.IEE

17、E T r ansactio ns o nCo nsumer Electr onics,1997,43(1:18Enhancement Based o n Weig hted T hresholded H istog ram EqualizationJ.IEEE T r ansactio n on ConsumerElectro nics,2007,53(2:7577645T arik A rici,Salih D ikbas,Y ucel A ltunbasak.A H istog ram M odificatio n F ramew or k and Its A pplication fo

18、 rImage Contrast EnhancementJ.IEEE T r ansactions on Image P rocessing,2009,18(9:192119356Joung Y oun K im,L ee Sup K im,Seung Ho H wang.An A dv anced Contrast Enhancement U sing Part ially O v erlapped Sub Blo ck H isto gr am Equalizatio nJ.I EEE T ransactions on Circuits And Sy st ems Fo r V ideo T ech nolog y,2001,11(4:475484g ram equalization approach to imag e enhancementJ.Dig ital Signal Pro cessing,2004(14:1581708S D Chen,A R Ramli.Contr ast enhancement using recursiv e