基于ArcLogistics的油庫(kù)二次配送最優(yōu)路徑研究

李媛　解婷婷

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

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

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

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

（1）Floyd算法

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

（2）蟻群算法

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

（3）Dijkstra算法

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

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

（4）三種算法對(duì)比

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

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

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

3 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

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

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

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

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

作者簡(jiǎn)介

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