基于百度地圖的應急避難場所物品運輸路徑優(yōu)化*

□ 宋文倩，陽喬欣，郭子祎，梁明明，亓呈明

(北京聯(lián)合大學 城市軌道交通與物流學院，北京 100101)

自然災害和突發(fā)性公共安全事故使得應急物流越來越重要。應急物流配送是應急物流中的重要環(huán)節(jié)，應急物資在從物資儲備中心到災區(qū)民眾手中的大部分時間都是在配送運輸上[1]，最優(yōu)的配送方案對應急物流保障系統(tǒng)意義重大。

對于北京市各類自然災害發(fā)生頻繁的嚴峻形勢，面向北京市應急避難場所應用中急需解決的應急物品運輸問題，本文結合災害事件性質(zhì)、地理信息技術、計算機技術、智能計算等領域的最新進展，通過對物品運輸路徑的分析和研究，利用蟻群算法和百度地圖API構建適合于北京市避難場所應急物品運輸?shù)穆窂絻?yōu)化方案。

在最短路徑研究中，最常見的方法是用兩點間直線距離之和作為最優(yōu)解的數(shù)據(jù)基礎，而兩個地點間的直線距離與道路實際距離往往相差較大，使得計算的最優(yōu)路徑往往不能夠應用到實際道路中，而現(xiàn)在百度地圖開放編輯，所以用百度地圖 API 獲取兩地間實際道路的距離數(shù)據(jù)，利用百度地圖動態(tài)管理所顯示的區(qū)域內(nèi)應急避難場所、物品配送中心的所有元素，及時應對不斷變化的路況。系統(tǒng)將所有的地理數(shù)據(jù)存放到數(shù)據(jù)庫中，可查詢所服務點的詳細位置，顯示周邊主要重要場所與各避難場所之間的導航路線。然后通過增加約束條件、修改節(jié)點間距離的計算等方法改進基本蟻群算法，利用改進蟻群算法對道路實際距離數(shù)據(jù)求解，將最優(yōu)路徑在百度地圖上顯示出來。實驗表明，該方法具有可行性與實用性，完善了最短路徑問題從理論研究過渡到實際應用。

十幾年來，我國一直重視應急物流的發(fā)展。應急物流配送路徑的研究，是保證應急物流系統(tǒng)的重要工作之一。張立毅[2]在混沌系統(tǒng)及模擬退火機制上引入基本蟻群算法，研究物流配送路徑的優(yōu)化問題。百度地圖API是一套由JavaScript語言編寫的應用程序接口，包含了構建地圖基本功能的各種接口，有助于在網(wǎng)站中構建功能豐富交互性強的地圖應用。Deddy[3]將谷歌地圖應用在送餐領域；鄭軼民[4]將百度地圖API中的道路信息與MMAS算法相結合，提升了垃圾車路徑規(guī)劃系統(tǒng)的實用性。

1 改進的蟻群算法

蟻群算法(Ant Colony Algorithm,ACA)是由意大利學者M.Dorigo等人[5]于20世紀90年代初期通過模擬自然界中螞蟻集體尋徑的行為而提出的一種基于種群的啟發(fā)式仿生進化算法；在螞蟻爬行的過程中會在道路上留下信息素，通過同一條路徑的螞蟻越多，信息素的濃度就越高，而后續(xù)的螞蟻會在選擇時傾向于信息素濃度高的路徑。

設有m個螞蟻，τij(t)為t時刻邊e(i，j)上信息素的強度，pijk表示在t時刻螞蟻k由位置i轉移到位置j的概率[6]，如公式(1)：

(1)

其中，allowedk={0，1，…，n-1}-tabuk表示螞蟻k可抵達的地點集合，ηij表示邊弧(i，j)的能見度，dij表示城市i與城市j之間的距離。α為信息啟發(fā)式因子，其值越大說明螞蟻對信息素越敏感，β為期望啟發(fā)式因子，其值越大說明螞蟻對線路的長短越敏感，ρ為信息素揮發(fā)因子，1-ρ表示信息素殘留因子。經(jīng)過n時刻后的一次循環(huán)，各路徑上信息量要根據(jù)公式(2)調(diào)整:

(2)

用百度地圖API返回的JSON包封裝得到任意兩個節(jié)點間的實際距離矩陣替代勾股定理，可提高系統(tǒng)的計算精度。主要涉及到百度地圖Route Matrix API的使用，獲取線路距離和時間，無需獲取詳細線路信息。這里得到的任意兩節(jié)點間的距離是實際道路有向距離，而非傳統(tǒng)理論研究中使用勾股定理計算兩點間的直線距離。

在基本蟻群算法中，螞蟻通常會將通過式(1)計算的最大概率訪問到同一個點，使算法陷入停滯。為此，本文提出了一種采用隨機模式調(diào)整信息素的方法，信息素更新式描述如下：產(chǎn)生0-m之間的隨機數(shù)k，計算過程中保存k個適應度較好的解的相應分量作候選組，將m段路徑長度排序，將路徑中長度最短的k條邊和m-k條邊按下式更新信息素：

(3)

Lgb為最優(yōu)螞蟻所走路徑長度。由于信息素同時得到更新，可加快收斂的速度，增強了全局搜索的能力。

2 系統(tǒng)實現(xiàn)

百度地圖API是一套由JavaScript語言編寫的將復雜的GIS底層邏輯封裝起來的應用接口，可方便的調(diào)用百度搜集的龐大的地圖數(shù)據(jù)庫，為地圖應用開發(fā)提供基本地圖本地搜索路線規(guī)劃定位等服務，它的使用為直觀掌握用戶地理位置提供了有力支撐。百度地圖API可標記避難場點的地址信息，將避難場點標記到地圖的具體位置，然后進行地址的經(jīng)緯度轉換。本文選用北京市應急避難場所網(wǎng)絡數(shù)據(jù)和避難場所附近的大型超市網(wǎng)絡數(shù)據(jù)進行實驗分析。該路網(wǎng)包含大量的交叉口、通路，具有典型復雜網(wǎng)絡的特征。在該路網(wǎng)上任選一個大型超市作為起點和選一個應急避難場所作為終點，計算最短時間路徑，最后在客戶端輸出顯示求解結果[7]，結果見圖1。

在傳統(tǒng)的路徑規(guī)劃問題中，兩地點之間的距離通常是通過勾股定理來獲得，然而在實踐中，車輛的行駛路徑，需要結合當?shù)氐木唧w路況基于以上分析，本文將結合百度地圖API中的批量算路服務(RouteMatrix)來獲得配送車輛在城市中可選擇的行車路線。

為了驗證路徑規(guī)劃系統(tǒng)的運行效果，本文選定20個應急避難場點進行了仿真驗證。在仿真過程中，首先通過百度地圖API中的Route Matrix獲得任兩個地點之間的相互路程及行駛時間，采用改進蟻群算法進行求解，最終得到如圖1中的路徑規(guī)劃結果。

圖1 蟻群優(yōu)化后的配送場所

3 結論

本文利用理論與實踐相結合的方法，研究了與配送車輛行駛時間密切相關的行駛路線問題。為盡快地將盡可能多的應急物資運往災區(qū)，通過對物品運輸路徑的分析和研究，運用改進蟻群算法，通過借助互聯(lián)網(wǎng)、地圖平臺，通過百度地圖API進行二次開發(fā)，構建了適合于北京市避難場所應急物品運輸?shù)穆窂絻?yōu)化方案，而后選用了北京市應急避難場所網(wǎng)絡數(shù)據(jù)和避難場所附近的大型超市網(wǎng)絡數(shù)據(jù)進行實例分析。實驗結果證明，本方法具有一定的理論意義和實踐價值。