李媛　解婷婷

摘 要：GIS技術(shù)其蘊含的巨大經(jīng)濟價值已經(jīng)被人們所廣泛認(rèn)知。GIS系統(tǒng)擁有強大的數(shù)據(jù)管理、分析能力，能夠有效處理大量復(fù)雜的地學(xué)問題，在地理信息系統(tǒng)的平臺上研究分析成品油二次配送路徑優(yōu)化問題問題概括來講主要有三個優(yōu)點：界面可視化、對空間數(shù)據(jù)的管理分析能力、分析功能。本文所以研究的內(nèi)容是在GIS環(huán)境下，對最優(yōu)路徑問題進行分析建模，進而求解出成品油二次配送的最優(yōu)化路徑，在對比分析多種不同算法后，選取Dijkstra算法作為求解最優(yōu)路徑問題的核心算法。

關(guān)鍵詞：GIS技術(shù)；路徑優(yōu)化；二次配送；Dijkstra算法

二戰(zhàn)后全球能源需求的大量增加，使得原油的供需矛盾逐步顯現(xiàn)，中國也從上世界九十年代起，由石油出口國轉(zhuǎn)為石油進口國，隨著中國經(jīng)濟的不斷發(fā)展，工業(yè)體系的不斷壯大，可以預(yù)期的是，在可替代能源尚無法大規(guī)模使用的大背景下，我國對石油資源的需求量在未來很長時期還將繼續(xù)保持較為快速的增長，對外依存度也在逐年增加。因此利用GIS技術(shù)來提升物流配送效率是當(dāng)前環(huán)境下的必然結(jié)果。

1 最優(yōu)化問題的相關(guān)算法

（1）Floyd算法

Floyd算法又被稱為插點法，是一種用于尋找給定的加權(quán)圖中頂點間最短路徑的算法[18]。該算法名稱以創(chuàng)始人斯坦福大學(xué)計算機科學(xué)系教授羅伯特·弗洛伊德命名。Floyd算法在求解最優(yōu)化路徑問題的是時候，是將區(qū)域道路網(wǎng)看做一個帶權(quán)矩陣，我們假設(shè)以A節(jié)點為起點，B點為目標(biāo)點，F(xiàn)loyd算法的解救過程就是遍歷所有由A通向B的路徑，然后從中選擇最優(yōu)路徑。在Floyd算法的運算過程中，對于弧的權(quán)值沒有限制，正負(fù)均可，其主要優(yōu)點是算法易于理解，代碼實現(xiàn)上不存在太大的技術(shù)障礙。但是Floyd算法時間復(fù)雜度是0（），在實際，不適合對大規(guī)模數(shù)據(jù)進行運算。

（2）蟻群算法

蟻群算法的誕生，最初來源于對螞蟻發(fā)現(xiàn)進食路徑的研究，關(guān)于蟻群算法的系統(tǒng)性研究最早出現(xiàn)在Marco Dorigo的博士論文中，這是一種仿生模擬進化算法[19]。我們可以重現(xiàn)螞蟻覓食的全部過程，螞蟻會在移動的過程中釋放生理激素，而這種激素會對其他螞蟻選擇移動方向產(chǎn)生影響。因為我們不難推測，最初的時候螞蟻的活動范圍就如同一張白紙，并不帶有任何的生理激素也就是路徑信息，而伴隨著螞蟻活動的增加，生理激素的濃度水平也會隨之逐步提升，不難發(fā)現(xiàn)信息素濃度越高的路徑，就是螞蟻活動越頻繁的路徑，反之路徑上生理激素的濃度越低，螞蟻的活動就越不活躍，伴隨著這種行為的不斷進行，生理激素濃度水平越高的道路就是螞蟻活動的最優(yōu)化路徑。蟻群算法的時間復(fù)雜度是0（**m）其中為模擬次數(shù)，n為節(jié)點數(shù)，m為螞蟻種群規(guī)模。

（3）Dijkstra算法

Dijkstra算法其本質(zhì)是將現(xiàn)實中的道路交通分解為節(jié)點和弧，并對弧進行賦值權(quán)值，可以表示道路的長度，路況等多種影響因素，通過建立一個帶權(quán)值的無向圖來模擬實際交通網(wǎng)絡(luò)中的實際道路情況，可以將無向圖看作樹，起始節(jié)點可以看作樹的根，從根到樹的各節(jié)點權(quán)值最小的路徑就是我們所需要的最優(yōu)路徑。Dijkstra算法適用于求解單源點到各個節(jié)點的最優(yōu)路徑問題。Dijkstra算法的時間復(fù)雜度為0（）， n表示中節(jié)點的個數(shù)。

從結(jié)點 A 到結(jié)點 J 的最短路徑是 A1→B2→E5→F6→H8→J10，權(quán)值求和為10.8。不難發(fā)現(xiàn)，利用Dijkstra算法所需的求解步驟為45.使用 Dijkstra算法求解最優(yōu)化路徑問題時，為了使算法能夠正常運行會占用一定的內(nèi)存空間。在實際應(yīng)用中，數(shù)據(jù)的處理量往往很大，對于系統(tǒng)也要求實時性，所以實際使用中，對于服務(wù)器和客戶端性能會有一定的要求，因此，如果能夠?qū)ijkstra 算法進行結(jié)構(gòu)優(yōu)化，可以很大程度上縮小計算步驟，但是隨著處理器技術(shù)的不斷發(fā)展進步，處理器的計算能力不斷提升，在實際求解最優(yōu)化路徑問題的過程中，Dijkstra算法的缺陷，其實并不會成為最首要的障礙

（4）三種算法對比

Dijkstra算法復(fù)雜度較低，可以解決單元點問題算法，但是適應(yīng)性差；Floyd算法易于理解，但是時間復(fù)雜度較高不適合大規(guī)模計算；蟻群算法適應(yīng)性強，正反饋性好缺點是收斂速度慢。綜合考慮，本文采用Dijkstra算法，并對其進行適當(dāng)優(yōu)化從而求解最短路徑問題

2 最優(yōu)化路徑分析模型的構(gòu)建

從本質(zhì)上來講，Dijkstra算法最終的到的結(jié)果其實是道路網(wǎng)絡(luò)模型的權(quán)值，因此如果要使Dijkstra算法能夠用于解決實際問題，其關(guān)鍵在對于權(quán)值的處理。文本對于權(quán)值的處理考慮以下幾個因素：距離、路況。以此構(gòu)建出來的優(yōu)化模型為： ，其中為道路的長度，為道路的通行狀況。影響通行狀況的因素很多，包括車流量、道路寬度、路面養(yǎng)護情況等。對于這些影響因素目前尚沒有高效的評價分析模型，如果一一探討，工作量大，且沒有任何意義。在這里我們可以用平均通行速度來表示道路的通行狀況，因為無論車流量、路面養(yǎng)護情況如何影響道路的通行狀況，其最終的影響形式就是影響車輛的通行速度。我們因此可以構(gòu)建道路的通行狀況模型=，其中 為車輛經(jīng)過該路段的平均速度， 為我們所設(shè)定的標(biāo)準(zhǔn)速度。所以權(quán)值的計算結(jié)果為，在系統(tǒng)的實際使用過程中，我們會在GIS系統(tǒng)里面對道路屬性進行直接賦值，避免在運算過程中重復(fù)計算，進而有效減少系統(tǒng)的計算量。

3 結(jié)語

在GIS平臺的基礎(chǔ)之上在算法的選取上采用Dijkstra算法，在分析物流配送體系的基礎(chǔ)之上，建立了最優(yōu)化路徑的算法模型，本系統(tǒng)的功能模塊包括地圖數(shù)據(jù)的導(dǎo)出、地圖標(biāo)注、屬性查詢以及最優(yōu)化路徑查詢模塊，系統(tǒng)采用Visual Studio 2008+AE組件的方式，實現(xiàn)了所需要的系統(tǒng)功能。具有較高的實際應(yīng)用價值。

參考文獻

[1] 徐洪勇.基于GIS的最短路徑算法改進對比研究：（碩士學(xué)位論文）.北京：中國地質(zhì)大學(xué)，2008.

[2] 陳琥.交通網(wǎng)絡(luò)最優(yōu)路徑分析研究[D].北京：解放軍信息工程大學(xué)，2007.

[3] 阮潔，鐘寶榮. Dijkstra算法在物流配送運輸中的最短路徑優(yōu)化研究[J].產(chǎn)業(yè)聚焦，2007， 第16卷（第8期 ）：42-44.

[4] 黃貴玲. 基于蟻群算法的最短路徑問題的研究與應(yīng)用[J]. 計算機工程與應(yīng)用， 2007，43（13）..

[5張學(xué)敏.GIS環(huán)境下的動態(tài)交通最優(yōu)路徑算法研究：（碩士學(xué)位論文）.長沙：中南大學(xué).2009.

作者簡介

李媛 （1992—），女，碩士，最優(yōu)化理論與應(yīng)用。