物流配送系統(tǒng)中大規(guī)模最短路徑算法的研究

1、CHINA MANAGEMENT INFORMATIONIZATION/收稿日期2007-09-10作者簡介忻瑞嬋,上海立信會計學(xué)院講師。!物流配送系統(tǒng)中大規(guī)模最短路徑算法的研究忻瑞嬋(上海立信會計學(xué)院,上海201620摘要在物流配送管理系統(tǒng)中,車輛路徑優(yōu)化是一個典型的難題,而最短路徑算法是其基礎(chǔ)。傳統(tǒng)的最短路徑算法,如Dijkstra 最短路徑算法因性能問題無法適應(yīng)大規(guī)模的拓?fù)渚W(wǎng)絡(luò)和實(shí)時計算。本文在Dijkstra 最短路徑算法的基礎(chǔ)上,在方向優(yōu)先等改進(jìn)算法的啟發(fā)下,設(shè)計和開發(fā)了基于GIS 的大規(guī)模最短路徑算法。實(shí)驗(yàn)表明,該算法受拓?fù)渚W(wǎng)絡(luò)規(guī)模的影響極小,能夠快速完成實(shí)時最短路徑計算。關(guān)鍵詞最

2、短路徑;車輛路徑優(yōu)化;GIS ;物流配送;Dijkstra 最短路徑算法中圖分類號F270.7文獻(xiàn)標(biāo)識碼A文章編號1673-0194(200805-0067-03中國管理信息化China Management Informationization2008年3月第11卷第5期Mar.,2008Vol.11,No.5提前期和時間裕度,加強(qiáng)運(yùn)輸過程實(shí)時跟蹤控制和及時信息反饋,通過這些方式保證物流的安全和高效運(yùn)行。如此即可減少不確定性,降低信息風(fēng)險。五、結(jié)論供應(yīng)鏈中充滿了信息風(fēng)險,但是企業(yè)由于競爭等多方面的壓力,又不得不選擇合作伙伴,因而研究對供應(yīng)鏈中的信息風(fēng)險如何進(jìn)行規(guī)避就顯得極為必要。本文主要從以

3、下幾個方面進(jìn)行探討:充分利用現(xiàn)代信息技術(shù)改善信息流的傳遞;建立信息共享的激勵協(xié)調(diào)約束機(jī)制;實(shí)行VMI 庫存控制;建立新型客戶關(guān)系;改變傳統(tǒng)的單向信息傳遞模式;在信息共享過程中,實(shí)行風(fēng)險防范機(jī)制;消除冗余環(huán)節(jié),簡化供應(yīng)鏈。通過以上幾種方法,就可以在很大程度上降低供應(yīng)鏈中的信息風(fēng)險,從而為企業(yè)創(chuàng)造更大的合作空間,提高企業(yè)的競爭力。主要參考文獻(xiàn)1楊紅芬.供應(yīng)鏈管理中的信息風(fēng)險及對策分析J .商業(yè)經(jīng)濟(jì)與管理,2004,(5:6-9.2馬士華,林勇.供應(yīng)鏈管理M .第2版.北京:機(jī)械工業(yè)出版社,2005.3劉寶成.供應(yīng)鏈中的信息扭曲及修正J .中國物資流通,2006,(8:5-7.4李愛琴.牛鞭效應(yīng)的治

4、理J .國際財務(wù)與會計,2003,(1:16-18.5葉翠玉,王濤.我國企業(yè)的供應(yīng)鏈管理現(xiàn)狀及未來發(fā)展意義J .新材料產(chǎn)業(yè),2001,(12:74-75.6丁青.供應(yīng)鏈管理中的信息問題及對策分析J .工程設(shè)計與建設(shè),2002,(6:47-49.7韓東東,施國洪,馬漢武.供應(yīng)鏈管理中的風(fēng)險防范J .工業(yè)工程,2002,5(3:37-41.8李杰,朱倩.從風(fēng)險角度看供應(yīng)鏈企業(yè)合作伙伴關(guān)系J .現(xiàn)代管理科學(xué),2002,(12:20-21.9呂安洪.供應(yīng)鏈管理研究J .特區(qū)經(jīng)濟(jì),2004,(5:22-25.10劉靜,唐國卿.基于供應(yīng)鏈的企業(yè)績效評價體系J .企業(yè)天地,2006,(8:18-21.11張

5、棟.供應(yīng)鏈中牛鞭效應(yīng)的治理J .知識經(jīng)濟(jì),2007,(9:17-19.12王金風(fēng).供應(yīng)鏈管理中的不確定性J .知識經(jīng)濟(jì),2005,(3:21-24.13趙鎮(zhèn).基于供應(yīng)鏈的企業(yè)競爭優(yōu)勢研究J .北方經(jīng)貿(mào),2006,(8:13-16.14劉建峰,鐘勝.供應(yīng)鏈中的信息風(fēng)險管理J .特區(qū)經(jīng)濟(jì),2004,(10:5-9.15張家敏.供應(yīng)鏈管理M .北京:中國人民大學(xué)出版社,2003.16桂良軍,趙志民,田志瑩.基于第三方參與的供應(yīng)鏈?zhǔn)找娣峙錂C(jī)制研究J .會計研究,2006,(10:51-54.17王清.基于供應(yīng)鏈的企業(yè)競爭優(yōu)勢研究J .管理科學(xué)文摘,2005,(4:17-19.18王國文,趙海然.供應(yīng)鏈

6、中的信息風(fēng)險管理M .北京:企業(yè)管理出版社,2005.19潘成云.解讀產(chǎn)業(yè)供應(yīng)鏈兼析我國新興產(chǎn)業(yè)供應(yīng)鏈基本特征J .當(dāng)代財經(jīng),2002,(9:4-7.20馬永生.供應(yīng)鏈管理中信息共享風(fēng)險及其弱化J .煤炭經(jīng)濟(jì)研究,2006,(8:14-16.21余偉萍.經(jīng)濟(jì)全球化基于企業(yè)能力的供應(yīng)鏈條優(yōu)化分析J .中國工業(yè)經(jīng)濟(jì),2004,(5:5-8.一、物流配送路徑優(yōu)化隨著物流技術(shù)和應(yīng)用的發(fā)展,物流配送過程中的車輛路徑優(yōu)化問題(Vehicle Routing Problem ,VRP 1成為一個研究的熱點(diǎn)。它是一個NP 難題,不能得到解析解,通常只能通過各種啟發(fā)式算法得到近似解。物流配送路徑優(yōu)化問題涉及因素

7、眾多,各種因素之間關(guān)系十分復(fù)雜。車輛路徑優(yōu)化問題的定義依約束和目標(biāo)的不同而有不同深度的定義。一般是指從一個配送中心用多輛車向多個需求網(wǎng)點(diǎn)送貨。配送中心和網(wǎng)點(diǎn)之間的位置和距離一67企業(yè)管理信息化定,網(wǎng)點(diǎn)的需求配貨量和車輛的容量一定,要求合理安排運(yùn)輸路線,使得總運(yùn)程最低,即總路徑最短,費(fèi)用最少。通過調(diào)整約束和優(yōu)化目標(biāo),問題的難度可以進(jìn)一步提高。但無論如何,優(yōu)化算法最終都基于網(wǎng)點(diǎn)(包括配送中心之間的最短路徑。圖1是一個典型的物流配送路徑優(yōu)化系統(tǒng)的流程圖。從圖1可以看出,配送路徑優(yōu)化系統(tǒng)區(qū)分為兩部分。左邊流程完成的任務(wù)包括:(1根據(jù)GIS地圖數(shù)據(jù)提取道路、對相交道路進(jìn)行分割、生成路段拓?fù)渚W(wǎng)絡(luò),網(wǎng)絡(luò)的節(jié)

8、點(diǎn)是路口,弧是節(jié)點(diǎn)之間的路段;(2根據(jù)道路拓?fù)渚W(wǎng)絡(luò)計算任意兩個節(jié)點(diǎn)之間的最短路徑。將最短路徑生成過程預(yù)先執(zhí)行的理由是最短路徑算法時空復(fù)雜度高,并且通常道路信息變更并不頻繁。右邊是配送路徑優(yōu)化的流程。通常, VRP優(yōu)化算法都含兩個過程:(1生成滿足約束的多條路線;(2對每條路線采用TSP優(yōu)化算法繼續(xù)優(yōu)化。這兩個過程都以節(jié)點(diǎn)之間的最短路徑作為基礎(chǔ)。因此,最短路徑算法在VRP問題中占有非常重要的地位。但圖1描述的是一個理想的配送優(yōu)化系統(tǒng)的流程,即假定路徑的屬性和最短路徑都不更新或更新不頻繁。而實(shí)際情況并非如此。如路況數(shù)據(jù)的變化,包括修路導(dǎo)致的道路不通、雨雪等導(dǎo)致的部分道路行駛難度系數(shù)變化以及臨時堵車

9、等情況都將導(dǎo)致預(yù)先計算的最短路徑失效。另一方面,對于大規(guī)模的拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu),預(yù)存所有最短路徑需要非常大的空間,導(dǎo)致配送優(yōu)化性能下降。本文在研究各種用于VRP最短路徑算法的基礎(chǔ)上,綜合前人的研究成果,提出可行的基于GIS的大規(guī)模最短路徑算法。二、最短路徑優(yōu)化算法最短路徑算法在1959年就已經(jīng)提出,因其應(yīng)用廣泛,是TSP、中國郵路問題等問題的子問題,成為運(yùn)籌學(xué)和組合優(yōu)化領(lǐng)域的熱點(diǎn)問題。目前該算法在國內(nèi)外已經(jīng)被廣泛深入研究。最短路徑算法也是VRP優(yōu)化的基礎(chǔ),因此,最短路徑算法的最新研究中也包括其在VRP優(yōu)化中的改進(jìn)。1.傳統(tǒng)最短路徑算法通常,傳統(tǒng)的最短路徑優(yōu)化算法是指Dijkstra和Floyd提出的

10、兩個算法2。他們都采用圖作為路網(wǎng)拓?fù)涞拇鎯Y(jié)構(gòu)。Dijkstra提出的算法按路徑長度遞增的次序產(chǎn)生最短路徑,實(shí)現(xiàn)從某個源點(diǎn)到其余各個節(jié)點(diǎn)的最短路徑,時間復(fù)雜度是O(n2。Floyd提出的算法按路徑搜索試探產(chǎn)生最短路徑,時間復(fù)雜度也是O(n2,但該算法計算每一對頂點(diǎn)之間的最短路徑。如果需要得到任意兩個節(jié)點(diǎn)之間的最短路徑,Floyd算法更合適。國內(nèi)外對于這兩個算法已經(jīng)有很多的改進(jìn)版本1,3,4。2.面向VRP的最短路徑算法Dijkstra和Floyd提出的最短路徑優(yōu)化算法考慮的拓?fù)渚W(wǎng)絡(luò)是抽象網(wǎng)絡(luò),對于網(wǎng)絡(luò)節(jié)點(diǎn)和弧并沒有額外的限制。而在VRP問題中,拓?fù)渚W(wǎng)絡(luò)是路網(wǎng),因此是平面網(wǎng)絡(luò),且節(jié)點(diǎn)和弧都有各種

11、可以用于進(jìn)一步優(yōu)化的屬性。人類在這種平面網(wǎng)絡(luò)的路由問題上,積累了很多經(jīng)驗(yàn)和知識,可以作為啟發(fā)式規(guī)則用于優(yōu)化。另一方面,物流配送優(yōu)化系統(tǒng)一般都是構(gòu)建在GIS之上,路網(wǎng)在地圖上有直觀的體現(xiàn)。GIS提供的各種特性也都可以用于最短路徑優(yōu)化。這些考慮利于減少最短路徑搜索過程中的搜索范圍,從而提高算法性能。文獻(xiàn)3提出一種直線化的改進(jìn)Dijkstra算法,通過對臨時標(biāo)記節(jié)點(diǎn)的堆排序使得搜索向目標(biāo)節(jié)點(diǎn)快速逼近。雖然每次搜索的節(jié)點(diǎn)集合減少了,但每次計算時拓?fù)渚W(wǎng)絡(luò)的規(guī)模并沒有減少。Dijkstra的搜索策略是廣度優(yōu)先,文獻(xiàn)4提出的算法采用方向優(yōu)先的方式求兩點(diǎn)之間的最短距離,根據(jù)源點(diǎn)到終點(diǎn)的方向可以顯著減少搜索的中

12、間節(jié)點(diǎn),并且這種方式對VRP問題是可行的,因?yàn)榫W(wǎng)點(diǎn)集合構(gòu)成的僅僅是龐大的路網(wǎng)拓?fù)渚W(wǎng)路的一個很小的子網(wǎng)。三、基于GIS的大規(guī)模最短路徑優(yōu)化算法在Dijkstra算法及其改進(jìn)算法的啟發(fā)下,本文設(shè)計了一種基于GIS的大規(guī)模最短路徑優(yōu)化算法,以適應(yīng)物流配送優(yōu)化系統(tǒng)大規(guī)模路徑優(yōu)化的需要。圖2是該算法的流程圖。由圖2可以看出,算法分為兩部分,但明顯不同于圖1中的算法,生成道路拓?fù)渚W(wǎng)絡(luò)后并不預(yù)先生成最短路徑。而右邊的最短路徑算法是求兩個輸入節(jié)點(diǎn)A0和A n之間的最短路徑L。以下是算法步驟的說明。圖1物流配送路徑優(yōu)化系統(tǒng)流程圖圖2基于GIS 的大規(guī)模最短路徑優(yōu)化算法68/CHINA MANAGEMENT IN

13、FORMATIONIZATIONCHINA MANAGEMENT INFORMATIONIZATION/收稿日期2007-08-13作者簡介劉勇(1975-,男,四川綿竹人,成都理工大學(xué)信息管理學(xué)院管理綜合實(shí)驗(yàn)室副主任,實(shí)驗(yàn)師,主要從事電子商務(wù)、ERP 實(shí)踐教學(xué)與研究。!基于MATLAB 的回歸分析模型在經(jīng)濟(jì)預(yù)測分析中的應(yīng)用劉勇,白林(成都理工大學(xué)信息管理學(xué)院,成都610059摘要經(jīng)濟(jì)預(yù)測是企業(yè)決策的前提與基礎(chǔ),MATLAB 具有強(qiáng)大的數(shù)據(jù)處理和分析功能,可以方便、快捷、準(zhǔn)確、直觀地進(jìn)行回歸數(shù)學(xué)建模和預(yù)測分析。本文通過案例分析,運(yùn)用MATLAB 統(tǒng)計工具箱中提供的命令regress 建立回歸分

14、析數(shù)學(xué)模型,并進(jìn)行回歸預(yù)測分析,取得很好的效果。關(guān)鍵詞MATLAB ;經(jīng)濟(jì)預(yù)測;回歸分析中圖分類號F270.7文獻(xiàn)標(biāo)識碼A文章編號1673-0194(200805-0069-03中國管理信息化China Management Informationization2008年3月第11卷第5期Mar.,2008Vol.11,No.5步驟1:根據(jù)輸入節(jié)點(diǎn)A 0和A n 的經(jīng)緯度坐標(biāo),通過GIS 引擎進(jìn)行直線分割,將直線段A 1A n 等分為n 段。設(shè)等分點(diǎn)依次是a 1,a 2,a n -1。步驟2:對a i (i=1,2,n-1,在拓?fù)渚W(wǎng)絡(luò)數(shù)據(jù)庫中選擇最近的節(jié)點(diǎn),設(shè)為A i 。步驟3:對(A i ,

15、A i+1(i=0,2,n-1,在其外接圓包圍的節(jié)點(diǎn)集合內(nèi)應(yīng)用Dijkstra 算法求最短路徑,設(shè)為L i 。(A i ,A i +1的外接圓定義為:圓心C=(A i +A i+1/2,即A i 和A i +1的中點(diǎn);半徑r =m A i A i +1,其中m 為使得最短路徑存在的最小正整數(shù)。外接圓以及外接圓內(nèi)節(jié)點(diǎn)的計算通過GIS 引擎可以實(shí)現(xiàn)。步驟4:拼接L i (i=0,2,n-1,作為A 0和A n 之間的最短路徑L 。顯然,n 和外接圓半徑r 的選擇直接影響每次應(yīng)用Di-jkstra 算法求最短路徑的復(fù)雜度。當(dāng)n=1,r =+時,即等價于原Dijkstra 算法。雖然本文采用外接圓,但

16、理論上可以采用其他形式的外接形,只要包圍兩個端點(diǎn),并以大概率保證兩個端點(diǎn)之間最短路徑歷經(jīng)的節(jié)點(diǎn)都在其范圍內(nèi)。雖然,本文算法也使用了直線化和方向的概念,但明顯不同于文獻(xiàn)3和4提出的算法:(1每次計算的拓?fù)渚W(wǎng)絡(luò)規(guī)模本身顯著減少;(2對拓?fù)渚W(wǎng)絡(luò)的直線分割利于并行快速實(shí)現(xiàn)最短路徑;(3平面圖和GIS 的功能得到充分體現(xiàn)。四、結(jié)束語本文在傳統(tǒng)Dijkstra 算法的基礎(chǔ)上,在方向優(yōu)先等改進(jìn)算法的啟發(fā)下,提出了基于GIS 的大規(guī)模最短路徑近似算法,以適應(yīng)物流配送路徑實(shí)時優(yōu)化的需要。該算法體現(xiàn)以下思想和特性:(1大規(guī)模的拓?fù)渚W(wǎng)絡(luò)通過節(jié)點(diǎn)之間的直線分割,每次計算的拓?fù)渚W(wǎng)絡(luò)規(guī)模被顯著減少;(2分割將拓?fù)渚W(wǎng)絡(luò)規(guī)模對最短路徑計算性能的影響降低到足夠低的程度;(3Dijkstra 算法之外的計算可以通過現(xiàn)有的GIS 引擎(如Mapinfo ,ArcGIS 等實(shí)現(xiàn)。算法分析表明該方法能夠降低大規(guī)模最短路徑計算的復(fù)雜性,使得最短路徑的實(shí)時計算成為可能。主要參考文獻(xiàn)1李軍,郭耀煌.物流配送車輛優(yōu)化調(diào)度理論與方法M .北京:中國物資出版社,2001.2嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(C 語言版M .北京:清華大學(xué)出版社,1997.3王開義,趙春江,胥桂仙等.GIS 領(lǐng)域最短路徑搜索問題的一種高效實(shí)現(xiàn)J .中國圖像圖形學(xué)報:A 版,2003,8(8:951-956.4張連蓬,劉國林,江濤,等.G