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

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

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

4、理J .國(guó)際財(cái)務(wù)與會(huì)計(jì),2003,(1:16-18.5葉翠玉,王濤.我國(guó)企業(yè)的供應(yīng)鏈管理現(xiàn)狀及未來(lái)發(fā)展意義J .新材料產(chǎn)業(yè),2001,(12:74-75.6丁青.供應(yīng)鏈管理中的信息問(wèn)題及對(duì)策分析J .工程設(shè)計(jì)與建設(shè),2002,(6:47-49.7韓東東,施國(guó)洪,馬漢武.供應(yīng)鏈管理中的風(fēng)險(xiǎn)防范J .工業(yè)工程,2002,5(3:37-41.8李杰,朱倩.從風(fēng)險(xiǎn)角度看供應(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劉靜,唐國(guó)卿.基于供應(yīng)鏈的企業(yè)績(jī)效評(píng)價(jià)體系J .企業(yè)天地,2006,(8:18-21.11張

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

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

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

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

9、等情況都將導(dǎo)致預(yù)先計(jì)算的最短路徑失效。另一方面,對(duì)于大規(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、中國(guó)郵路問(wèn)題等問(wèn)題的子問(wèn)題,成為運(yùn)籌學(xué)和組合優(yōu)化領(lǐng)域的熱點(diǎn)問(wèn)題。目前該算法在國(guó)內(nèi)外已經(jīng)被廣泛深入研究。最短路徑算法也是VRP優(yōu)化的基礎(chǔ),因此,最短路徑算法的最新研究中也包括其在VRP優(yōu)化中的改進(jìn)。1.傳統(tǒng)最短路徑算法通常,傳統(tǒng)的最短路徑優(yōu)化算法是指Dijkstra和Floyd提出的

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

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

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

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

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

15、A i+1(i=0,2,n-1,在其外接圓包圍的節(jié)點(diǎn)集合內(nèi)應(yīng)用Dijkstra 算法求最短路徑,設(shè)為L(zhǎng) 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)的計(jì)算通過(guò)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 =+時(shí),即等價(jià)于原Dijkstra 算法。雖然本文采用外接圓,但

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