基于ＧＩＳ優(yōu)化Ｄｉｊｋｓｔｒａ算法在物流中心選址中的研究

摘要：基于傳統(tǒng)的Dijkstra算法，提出了一種采用二叉堆結(jié)構(gòu)和網(wǎng)絡(luò)邊存儲模型的優(yōu)化Dijkstra算法。實驗結(jié)果表明：優(yōu)化后的算法是切實有效的，將其應(yīng)用到物流中心選址中得到了較滿意的選址方案。

關(guān)鍵詞：地理信息系統(tǒng)；最短路徑；迪克斯特拉算法；二叉堆；優(yōu)先級隊列；物流中心

中圖分類號：TP311．5文獻(xiàn)標(biāo)志碼：A

文章編號：1001－3695(2007)08－0289－03

0引言

現(xiàn)代物流是現(xiàn)代化生產(chǎn)的重要組成部分。物流中心在現(xiàn)代商品流通中的作用極大。它是作為商品周轉(zhuǎn)、分揀、配貨、保管和流通加工等活動的據(jù)點，克服在流通過程中所產(chǎn)生的時間和空間障礙，促進(jìn)商品按顧客要求順利轉(zhuǎn)移。物流中心的合理布局是物流系統(tǒng)中具有戰(zhàn)略意義的投資決策問題。物流中心布局是否合理，將對整個系統(tǒng)的物流合理化和商品流通的社會效益有著決定性的影響。

隨著計算機(jī)科學(xué)和信息科學(xué)的發(fā)展，地理信息系統(tǒng)(GIS)[1]在人們生產(chǎn)和生活中的應(yīng)用日益廣泛。而將地理信息系統(tǒng)等現(xiàn)代信息技術(shù)應(yīng)用于物流中心選址問題，可以更方便、更準(zhǔn)確地解決該問題。影響物流中心選址的因素非常多，本文只考慮路徑因素，路徑最短即為所求地址。目前，關(guān)于最短路徑搜索算法研究很多。其中1959年Dijkstra提出的單源問題算法是最適合拓?fù)渚W(wǎng)絡(luò)中兩節(jié)點最短路徑搜索的算法之一，本文將此算法稱為傳統(tǒng)算法。在傳統(tǒng)算法中，計算效率和存儲效率都很低。因此，本文在提高存儲效率方面將采用的是一種新型的網(wǎng)絡(luò)存儲模型——網(wǎng)絡(luò)邊存儲模型。這樣可使內(nèi)存的占用量大大減少。在提高計算效率方面將采用二叉堆數(shù)據(jù)結(jié)構(gòu)，這樣使得算法的效率得到很大的提高，系統(tǒng)的性能也有相應(yīng)的優(yōu)化。在物流中心選址系統(tǒng)中采用這種優(yōu)化算法，可以快速地得到物流中心選址方案，大大提高了物流系統(tǒng)的效率。

2優(yōu)化的Dijkstra算法

2．1優(yōu)先隊列及二叉堆數(shù)據(jù)結(jié)構(gòu)

上述算法描述式(2)的惟一目的，就是不斷從變化的V-S集合中找出下一條最短路徑。從中可以看出，由累計權(quán)值決定的最短路徑選擇具有優(yōu)先程度差異特征。考慮到這一特點，可以通過用各節(jié)點在算法中不斷被松弛的距起點的最短路徑值來構(gòu)造優(yōu)先級隊列[4]，以提高extractmin操作的效率。

優(yōu)先級隊列是一種用來維護(hù)由一組元素構(gòu)成集合S的數(shù)據(jù)結(jié)構(gòu)。作用于優(yōu)先級隊列上的操作主要有insert、minimum、extractmin、decreasekey 等。實現(xiàn)優(yōu)先級隊列的方法較多，本文則采用二叉堆這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。

二叉堆結(jié)構(gòu)[5]是一種數(shù)組對象，可以被視為一棵完全二叉樹。圖1即為一個二叉堆優(yōu)先級隊列及其所對應(yīng)的完全二叉樹。堆結(jié)構(gòu)必須滿足以下性質(zhì):對除了根節(jié)點以外的每個節(jié)點有A[parent(i)]≤A[i]或A[parent(i)]≥A[i]，即某個節(jié)點的值不小于(或不大于)其父節(jié)點的值。這樣，堆中的最小(最大)元素就存放在根節(jié)點中，且每一節(jié)點子樹中的節(jié)點值都不小于(或不大于)該節(jié)點的值。

具有n個元素的二叉堆是基于一棵完全二叉樹的，其高度為[log n]。對于二叉堆的操作，其作用時間至多與樹的高度成正比，為O(log n)。因此，若采用基于二叉堆實現(xiàn)的優(yōu)先級隊列來存儲Dijkstra算法中所擴(kuò)展出的D值及完成對D值的松弛操作[6]，則可大幅度降低算法的時間復(fù)雜度，提高算法效率。

2．2網(wǎng)絡(luò)路徑優(yōu)化模型

在網(wǎng)絡(luò)分析[7]過程中，實際上只需關(guān)心網(wǎng)絡(luò)邊的信息，如邊的權(quán)值、起點、終點。可采用只存儲邊的網(wǎng)絡(luò)拓?fù)湫畔ⅲ淮鎯嶋H網(wǎng)絡(luò)點的拓?fù)湫畔ⅲ瑴p少空間分析時所要檢索的數(shù)據(jù)量。基于該思想，采用圖2及表1的網(wǎng)絡(luò)邊存儲模型代替?zhèn)鹘y(tǒng)的矩陣或鄰接表的存儲模型，使內(nèi)存的占用量大大減少。

3優(yōu)化的Dijkstra算法在物流中心選址中的應(yīng)用

本文基于Windows 2000操作系統(tǒng)，采用ESRI公司的ArcView軟件，在Visual C++可視化環(huán)境下，實現(xiàn)了在給定地圖上提出一套最佳物流中心選址方案的功能。

本文只是從圖論的角度入手，運(yùn)用Dijkstra算法對物流中心配送網(wǎng)絡(luò)的節(jié)點(物流中心)和邊(運(yùn)輸線路)進(jìn)行了分析及優(yōu)化。實際應(yīng)用時，在此模型的基礎(chǔ)上可結(jié)合模糊評價法的有關(guān)理論與層次分析法等決策方法，對此基本模型作進(jìn)一步的完善和補(bǔ)充。 

4結(jié)束語

本文探討的最短路徑算法是基于網(wǎng)絡(luò)中邊(路段)與節(jié)點的地理相關(guān)性的拓?fù)涮卣鳌Ｔ趦?yōu)化算法中，構(gòu)造了一個包括最短路徑的二叉樹；而在存儲結(jié)構(gòu)中，則采用了一種網(wǎng)絡(luò)邊存儲模型。優(yōu)化后的Dijkstra算法減少了算法的內(nèi)存資源占用，大大提高了網(wǎng)絡(luò)分析的效率。但是，在物流中心的選址規(guī)劃中，影響其設(shè)置的因素很多，不僅涉及到如市場接近度、運(yùn)輸成本、勞動力成本以及與國家、省市規(guī)劃發(fā)展方針相適應(yīng)等因素，對于特殊性質(zhì)的物流中心還要考慮自然環(huán)境和經(jīng)營環(huán)境因素的影響。這不可能是簡單的、單一的技術(shù)方法所能解決的，它可能有多種方法的綜合，通過對多種因素的平衡，才能達(dá)到理想的效果。但最短路徑問題是物流中心選址的關(guān)鍵內(nèi)容，本文提出的優(yōu)化Dijkstra算法在解決最短路徑優(yōu)化方面取得了滿意的成果，為物流中心選址的綜合解決方案創(chuàng)造了有利條件。 

參考文獻(xiàn)：

［1］陳軍，鄔倫. 數(shù)字中國地理空間基礎(chǔ)框架[M].北京：科學(xué)出版社，2003：24－29. 

［2］NOTO M，SATO H.A method for the shortest path search by extended Dijkstra algorithm[C]//Proc of IEEE International Conference on Systems， Man， and Cybernetics.Nashville:[s.n.]，2000:2316－2320.

［3］BAO Peiming.A optimization algorithm based on Dijkstra’s algorithm in search of shortcut[J].Journal of Computer Research and Developmen，2001，38(3):307－311.

［4］BROWN M Z，BURSCHKA D，HANGER G D.Advances in computational stereo[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2003，25(8):9931009.

［5］EPPSTEIN D. Finding the k shortest paths[J].SIAM Journal on Computing，1999，28(2): 652－673.

［6］MILLER H J. Measuring spacetime accessibility benefits with in transportation networks: basic theory and computational procedures [J].Geographical Analysis，1999，31(1): 1－26.

［7］司連法，王文靜.快速Dijkstra最短路徑優(yōu)化算法的實現(xiàn)[J].測繪通報，2005(8):15－18.

［8］楊元法，莊明. 網(wǎng)絡(luò)中最短距離的遞歸算法[J].計算機(jī)工程，2005，31(13):93－98.



注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”