摘要：車輛路徑問題主要研究物流配送中車輛線路優化以提高物流配送的效率。本系統實現基于百度地圖API及智能算法求解車輛路徑問題。首先通過百度地圖API獲取節點間實際道路的距離數據，然后將百度地圖API獲取的道路實際距離數據提交給改進的蟻群算法求解最短路徑模型，減少配送車輛的在途時間，采用電子地圖顯示最優的車輛路徑。

關鍵詞：蟻群算法 物流配送 路徑優化 空間信息

1 引言

應急物流是指為應對嚴重自然災害、突發性公共衛生事件、公共安全事件及軍事沖突等突發事件而對物質、人員、資金的需求進行緊急保障的一種特殊物流活動。

應急物流可以分為軍事應急物流和非軍事應急物流。非軍事應急物流可以細分為自然災害應急物流、人為災害應急物流和疫情應急物流。自然災害應急物流配送主要針對救災物資的收集、分類、包裝、運輸以及救災物資發放作業,整個救助物流的運輸與配送中，都是圍繞著災區的受災人員。

隨著環境災害對社會及國家財產造成的損失，如何提高應急物流配送水平成為亟待解決的問題。在車輛路徑問題的研究中，通常采用節點間直線距離之和作為最短路徑最優求解的數據基礎，而節點間直線距離和與道路實際距離通常相去甚遠，使得其最優路徑安排難于真正應用在實際需求中。

因此通過百度地圖獲取節點間實際道路的距離數據，通過增加約束條件、修改節點間距離的計算、更換選擇策略、調整信息揮發因子等方法改進基本蟻群算法，最后將百度地圖獲取的道路實際距離數據提交給改進蟻群算法求解。

面對城市各類突發公共事件發生頻繁的嚴峻形勢，面向城市建設中急需解決的應急物品運輸路徑問題，結合突發事件、地理信息技術、計算機技術、智能計算等領域的最新進展，通過對物品運輸路徑的分析和研究，利用理論與實踐相結合的方法，研究與救援車輛行駛時間密切相關的路網交通參數，建立路網狀態變化模型。

在此基礎上，建立基于蟻群算法的最短路徑模型并優化求解過程，減少物品配送車輛的在途時間，提升城市災害應急救災和減災水平，為保障城市人民生命財產以及區域可持續發展提供科學依據和技術支撐。

我國是一個自然災害多發的國家。災害威脅我國城市安全，造成了巨大的經濟損失和人員傷亡。應急物流是城市遇災處理系統中重要的組成部分，關于應急物流配送研究對于減小城市災害損失和擴大有著重要的指導意義。應急配送路徑選擇和車輛調度是物流配送中非常重要的一項活動。本研究搜集城市基礎地理數據資料，使用蟻群算法的最短路徑模型并優化求解過程，使得必要時為受災城市提供及時救援和合理幫助。

2、蟻群算法

蟻群算法（Ant Colony Optimization，ACO）是一種群智能算法，最早是由意大利學者Colorni A.,Dorigo M.等[1]在1991年提出。經過多年的發展，蟻群算法已經得到巨大的進步。

2.1 基本原理

蟻群算法是由自然界中螞蟻覓食的行為而啟發的。自然界中，在螞蟻尋找食物過程中，蟻群總能尋找到一條最優路徑去搬運食物。如圖顯示了這樣一個覓食的過程。

螞蟻覓食
如圖（a），假設A點蟻巢，E點為食物，螞蟻在運動過程中會釋放一種叫做信息素的物質，螞蟻會沿著信息素濃度最高的路徑運動，在沒有障礙物的時候，對于最開始的幾只螞蟻而言，沿直線運動的螞蟻搬運一次食物所需時間更短，則在相同的時間內，沿直線運動的螞蟻最多，假設每一只螞蟻在運動時所釋放信息素的量完全相同，則直線路徑所積累的信息素濃度最高，之后的螞蟻就會沿著信息素濃度最大的路徑運動，即直線路徑；

如圖 (b)，出現障礙物時，螞蟻會以相同的概率從障礙物的兩側繞過，從H點或者C點繞過障礙物，由圖可知從C點繞過障礙物的路徑最短，則該路徑所積累的信息素濃度高，則會有更多的螞蟻從C點繞過障礙物，如圖(c)所示。

2.2 實現過程

假如蟻群中所有螞蟻的數量為antcount，節點數量為citycount（其中配送中心的數量為1，配送點的數量為citycount-1），所有節點之間的距離矩陣用distance表示，信息素矩陣用tao表示，最佳路徑為besttour。每只螞蟻都有自己的內存，內存中用一個禁忌表（unvisitedcity）來存儲該螞蟻已經訪問過的節點，當值為0時表示未訪問過，值為1時，表示訪問過，意味著其在以后的搜索中將不能訪問這些節點；

在每次迭代和選擇過程中，用tour表示當前路線，容量為citycount+1，其中第一個值與最后一個值相同，保證螞蟻最后回到起點；還有另外一些數據，例如一些控制參數 (alpha=1.0，beta=2.0，rou=0.5)，該螞蟻行走玩全程的總距離（bestlength），等等。假定算法的迭代次數為maxgen，運行時間為runtimes。

蟻群算法計算過程如下：

（1）初始化。

設runtimes=0，初始化bestlength為一個無窮大的數，bestTour為空。初始化所有的螞蟻的tao矩陣所有元素初始化為0.1，unvisitedcity表中的值全部設為0。同時，通過函數SelectFirstCity()選定配送中心為螞蟻的起始位置，將其在unvisitedcity矩陣中對應的值變為1，并將其加入到tour表中。

（2）為每只螞蟻選擇下一個節點。

用函數SelectNextCity()為每只螞蟻選擇下一個節點，該節點只能從unvisitedcity矩陣中值為0的節點中選擇，其中每個節點以某種概率搜索到，每搜到一個，便將其在unvisitedcity矩陣中對應的值變為1，并將其加入到tour表中。該過程重復citycount-1次，直到所有的節點都遍歷一次。遍歷完所有節點后，將起始節點再次加入到tour中，即tour的第一個元素和隨后一個元素均為配送中心節點，此時tour表元素數量為citycount+1。

最后通過函數CalTourLength()計算總的路徑距離，比較每個螞蟻的路徑距離，然后和bestlength比較，若它的路徑距離比bestlength小，則將該值賦予bestlength，并且將其tour賦予besttour。

（3）用函數UpdateTao()更新信息素矩陣。

（4）檢查終止條件

當達迭代次數達到maxgen時，算法停止，轉到第（5）步；否則，重新初始化所有的螞蟻的tao矩陣所有元素初始化為0.1，unvisitedcity表中的值全部設為0。同時，通過函數SelectFirstCity()選定配送中心為螞蟻的起始位置，將其在unvisitedcity矩陣中對應的值變為1，并將其加入到tour表中。重復執行（2），（3）,(4)步。

（5）輸出最優值。

算法流程圖如圖所示：

蟻群算法流程圖
3、系統實現

為達到總運行時間最短的目標，采用改進的蟻群算法優化導航路線，用以優化配送路徑，并顯示優化結果，從而為應急配送系統的構建提供行之有效的信息化手段。

通過將蟻群算法與百度地圖結合起來實現配送，為將蟻群算法與百度地圖的結合更直觀的顯示出來，該模塊的設計采用了frame框架，將該模塊分為左右兩個部分，左側為物流節點選擇區，右側為百度地圖。配送員可以在左側欄中選擇一個配送中心（出發點）、多個配送點（目標場所），由蟻群算法計算出最優路徑，最終可得到路徑規劃結果。

圖1地圖查詢模塊界面
4、結論

本文是基于百度地圖API、javascript和JSP編寫的一個路徑優化系統。系統將所有的地理數據存放到數據庫中，可查詢所服務點的詳細位置，顯示各配送點之間的導航路線。為達到總運行時間最短的目標，采用改進的蟻群算法優化導航路線，用以優化配送路徑，并將最佳路徑用百度地圖呈現出來，從而為配送系統的構建提供行之有效的信息化手段。