基于ArcLogistics的油庫二次配送最優路徑研究

李媛　解婷婷

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

關鍵詞：GIS技術；路徑優化；二次配送；Dijkstra算法

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

1 最優化問題的相關算法

（1）Floyd算法

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

（2）蟻群算法

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

（3）Dijkstra算法

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

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

（4）三種算法對比

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

2 最優化路徑分析模型的構建

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

3 結語

在GIS平臺的基礎之上在算法的選取上采用Dijkstra算法，在分析物流配送體系的基礎之上，建立了最優化路徑的算法模型，本系統的功能模塊包括地圖數據的導出、地圖標注、屬性查詢以及最優化路徑查詢模塊，系統采用Visual Studio 2008+AE組件的方式，實現了所需要的系統功能。具有較高的實際應用價值。

參考文獻

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

[2] 陳琥.交通網絡最優路徑分析研究[D].北京：解放軍信息工程大學，2007.

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

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

[5張學敏.GIS環境下的動態交通最優路徑算法研究：（碩士學位論文）.長沙：中南大學.2009.

作者簡介

李媛 （1992—），女，碩士，最優化理論與應用。