關(guān)注掌鏈公眾號(hào)
洞悉物流供應(yīng)鏈
關(guān)注掌鏈公眾號(hào)
洞悉物流供應(yīng)鏈
摘要：車(chē)輛路徑問(wèn)題主要研究物流配送中車(chē)輛線路優(yōu)化以提高物流配送的效率。本系統(tǒng)實(shí)現(xiàn)基于百度地圖API及智能算法求解車(chē)輛路徑問(wèn)題。首先通過(guò)百度地圖API獲取節(jié)點(diǎn)間實(shí)際道路的距離數(shù)據(jù)，然后將百度地圖API獲取的道路實(shí)際距離數(shù)據(jù)提交給改進(jìn)的蟻群算法求解最短路徑模型，減少配送車(chē)輛的在途時(shí)間，采用電子地圖顯示最優(yōu)的車(chē)輛路徑。
關(guān)鍵詞：蟻群算法 物流配送 路徑優(yōu)化 空間信息
1 引言
應(yīng)急物流是指為應(yīng)對(duì)嚴(yán)重自然災(zāi)害、突發(fā)性公共衛(wèi)生事件、公共安全事件及軍事沖突等突發(fā)事件而對(duì)物質(zhì)、人員、資金的需求進(jìn)行緊急保障的一種特殊物流活動(dòng)。
應(yīng)急物流可以分為軍事應(yīng)急物流和非軍事應(yīng)急物流。非軍事應(yīng)急物流可以細(xì)分為自然災(zāi)害應(yīng)急物流、人為災(zāi)害應(yīng)急物流和疫情應(yīng)急物流。自然災(zāi)害應(yīng)急物流配送主要針對(duì)救災(zāi)物資的收集、分類(lèi)、包裝、運(yùn)輸以及救災(zāi)物資發(fā)放作業(yè),整個(gè)救助物流的運(yùn)輸與配送中，都是圍繞著災(zāi)區(qū)的受災(zāi)人員。
隨著環(huán)境災(zāi)害對(duì)社會(huì)及國(guó)家財(cái)產(chǎn)造成的損失，如何提高應(yīng)急物流配送水平成為亟待解決的問(wèn)題。在車(chē)輛路徑問(wèn)題的研究中，通常采用節(jié)點(diǎn)間直線距離之和作為最短路徑最優(yōu)求解的數(shù)據(jù)基礎(chǔ)，而節(jié)點(diǎn)間直線距離和與道路實(shí)際距離通常相去甚遠(yuǎn)，使得其最優(yōu)路徑安排難于真正應(yīng)用在實(shí)際需求中。
因此通過(guò)百度地圖獲取節(jié)點(diǎn)間實(shí)際道路的距離數(shù)據(jù)，通過(guò)增加約束條件、修改節(jié)點(diǎn)間距離的計(jì)算、更換選擇策略、調(diào)整信息揮發(fā)因子等方法改進(jìn)基本蟻群算法，最后將百度地圖獲取的道路實(shí)際距離數(shù)據(jù)提交給改進(jìn)蟻群算法求解。
面對(duì)城市各類(lèi)突發(fā)公共事件發(fā)生頻繁的嚴(yán)峻形勢(shì)，面向城市建設(shè)中急需解決的應(yīng)急物品運(yùn)輸路徑問(wèn)題，結(jié)合突發(fā)事件、地理信息技術(shù)、計(jì)算機(jī)技術(shù)、智能計(jì)算等領(lǐng)域的最新進(jìn)展，通過(guò)對(duì)物品運(yùn)輸路徑的分析和研究，利用理論與實(shí)踐相結(jié)合的方法，研究與救援車(chē)輛行駛時(shí)間密切相關(guān)的路網(wǎng)交通參數(shù)，建立路網(wǎng)狀態(tài)變化模型。
在此基礎(chǔ)上，建立基于蟻群算法的最短路徑模型并優(yōu)化求解過(guò)程，減少物品配送車(chē)輛的在途時(shí)間，提升城市災(zāi)害應(yīng)急救災(zāi)和減災(zāi)水平，為保障城市人民生命財(cái)產(chǎn)以及區(qū)域可持續(xù)發(fā)展提供科學(xué)依據(jù)和技術(shù)支撐。
我國(guó)是一個(gè)自然災(zāi)害多發(fā)的國(guó)家。災(zāi)害威脅我國(guó)城市安全，造成了巨大的經(jīng)濟(jì)損失和人員傷亡。應(yīng)急物流是城市遇災(zāi)處理系統(tǒng)中重要的組成部分，關(guān)于應(yīng)急物流配送研究對(duì)于減小城市災(zāi)害損失和擴(kuò)大有著重要的指導(dǎo)意義。應(yīng)急配送路徑選擇和車(chē)輛調(diào)度是物流配送中非常重要的一項(xiàng)活動(dòng)。本研究搜集城市基礎(chǔ)地理數(shù)據(jù)資料，使用蟻群算法的最短路徑模型并優(yōu)化求解過(guò)程，使得必要時(shí)為受災(zāi)城市提供及時(shí)救援和合理幫助。
2、蟻群算法
蟻群算法（Ant Colony Optimization，ACO）是一種群智能算法，最早是由意大利學(xué)者Colorni A.,Dorigo M.等[1]在1991年提出。經(jīng)過(guò)多年的發(fā)展，蟻群算法已經(jīng)得到巨大的進(jìn)步。
2.1 基本原理
蟻群算法是由自然界中螞蟻覓食的行為而啟發(fā)的。自然界中，在螞蟻尋找食物過(guò)程中，蟻群總能尋找到一條最優(yōu)路徑去搬運(yùn)食物。如圖顯示了這樣一個(gè)覓食的過(guò)程。
如圖（a），假設(shè)A點(diǎn)蟻巢，E點(diǎn)為食物，螞蟻在運(yùn)動(dòng)過(guò)程中會(huì)釋放一種叫做信息素的物質(zhì)，螞蟻會(huì)沿著信息素濃度最高的路徑運(yùn)動(dòng)，在沒(méi)有障礙物的時(shí)候，對(duì)于最開(kāi)始的幾只螞蟻而言，沿直線運(yùn)動(dòng)的螞蟻搬運(yùn)一次食物所需時(shí)間更短，則在相同的時(shí)間內(nèi)，沿直線運(yùn)動(dòng)的螞蟻?zhàn)疃?，假設(shè)每一只螞蟻在運(yùn)動(dòng)時(shí)所釋放信息素的量完全相同，則直線路徑所積累的信息素濃度最高，之后的螞蟻就會(huì)沿著信息素濃度最大的路徑運(yùn)動(dòng)，即直線路徑；
如圖 (b)，出現(xiàn)障礙物時(shí)，螞蟻會(huì)以相同的概率從障礙物的兩側(cè)繞過(guò)，從H點(diǎn)或者C點(diǎn)繞過(guò)障礙物，由圖可知從C點(diǎn)繞過(guò)障礙物的路徑最短，則該路徑所積累的信息素濃度高，則會(huì)有更多的螞蟻從C點(diǎn)繞過(guò)障礙物，如圖(c)所示。
2.2 實(shí)現(xiàn)過(guò)程
假如蟻群中所有螞蟻的數(shù)量為antcount，節(jié)點(diǎn)數(shù)量為citycount（其中配送中心的數(shù)量為1，配送點(diǎn)的數(shù)量為citycount-1），所有節(jié)點(diǎn)之間的距離矩陣用distance表示，信息素矩陣用tao表示，最佳路徑為besttour。每只螞蟻都有自己的內(nèi)存，內(nèi)存中用一個(gè)禁忌表（unvisitedcity）來(lái)存儲(chǔ)該螞蟻已經(jīng)訪問(wèn)過(guò)的節(jié)點(diǎn)，當(dāng)值為0時(shí)表示未訪問(wèn)過(guò)，值為1時(shí)，表示訪問(wèn)過(guò)，意味著其在以后的搜索中將不能訪問(wèn)這些節(jié)點(diǎn)；
在每次迭代和選擇過(guò)程中，用tour表示當(dāng)前路線，容量為citycount+1，其中第一個(gè)值與最后一個(gè)值相同，保證螞蟻?zhàn)詈蠡氐狡瘘c(diǎn)；還有另外一些數(shù)據(jù)，例如一些控制參數(shù) (alpha=1.0，beta=2.0，rou=0.5)，該螞蟻行走玩全程的總距離（bestlength），等等。假定算法的迭代次數(shù)為maxgen，運(yùn)行時(shí)間為runtimes。
蟻群算法計(jì)算過(guò)程如下：
（1）初始化。
設(shè)runtimes=0，初始化bestlength為一個(gè)無(wú)窮大的數(shù)，bestTour為空。初始化所有的螞蟻的tao矩陣所有元素初始化為0.1，unvisitedcity表中的值全部設(shè)為0。同時(shí)，通過(guò)函數(shù)SelectFirstCity()選定配送中心為螞蟻的起始位置，將其在unvisitedcity矩陣中對(duì)應(yīng)的值變?yōu)?，并將其加入到tour表中。
（2）為每只螞蟻選擇下一個(gè)節(jié)點(diǎn)。
用函數(shù)SelectNextCity()為每只螞蟻選擇下一個(gè)節(jié)點(diǎn)，該節(jié)點(diǎn)只能從unvisitedcity矩陣中值為0的節(jié)點(diǎn)中選擇，其中每個(gè)節(jié)點(diǎn)以某種概率搜索到，每搜到一個(gè)，便將其在unvisitedcity矩陣中對(duì)應(yīng)的值變?yōu)?，并將其加入到tour表中。該過(guò)程重復(fù)citycount-1次，直到所有的節(jié)點(diǎn)都遍歷一次。遍歷完所有節(jié)點(diǎn)后，將起始節(jié)點(diǎn)再次加入到tour中，即tour的第一個(gè)元素和隨后一個(gè)元素均為配送中心節(jié)點(diǎn)，此時(shí)tour表元素?cái)?shù)量為citycount+1。
最后通過(guò)函數(shù)CalTourLength()計(jì)算總的路徑距離，比較每個(gè)螞蟻的路徑距離，然后和bestlength比較，若它的路徑距離比bestlength小，則將該值賦予bestlength，并且將其tour賦予besttour。
（3）用函數(shù)UpdateTao()更新信息素矩陣。
（4）檢查終止條件
當(dāng)達(dá)迭代次數(shù)達(dá)到maxgen時(shí)，算法停止，轉(zhuǎn)到第（5）步；否則，重新初始化所有的螞蟻的tao矩陣所有元素初始化為0.1，unvisitedcity表中的值全部設(shè)為0。同時(shí)，通過(guò)函數(shù)SelectFirstCity()選定配送中心為螞蟻的起始位置，將其在unvisitedcity矩陣中對(duì)應(yīng)的值變?yōu)?，并將其加入到tour表中。重復(fù)執(zhí)行（2），（3）,(4)步。
（5）輸出最優(yōu)值。
算法流程圖如圖所示：
3、系統(tǒng)實(shí)現(xiàn)
為達(dá)到總運(yùn)行時(shí)間最短的目標(biāo)，采用改進(jìn)的蟻群算法優(yōu)化導(dǎo)航路線，用以優(yōu)化配送路徑，并顯示優(yōu)化結(jié)果，從而為應(yīng)急配送系統(tǒng)的構(gòu)建提供行之有效的信息化手段。
通過(guò)將蟻群算法與百度地圖結(jié)合起來(lái)實(shí)現(xiàn)配送，為將蟻群算法與百度地圖的結(jié)合更直觀的顯示出來(lái)，該模塊的設(shè)計(jì)采用了frame框架，將該模塊分為左右兩個(gè)部分，左側(cè)為物流節(jié)點(diǎn)選擇區(qū)，右側(cè)為百度地圖。配送員可以在左側(cè)欄中選擇一個(gè)配送中心（出發(fā)點(diǎn)）、多個(gè)配送點(diǎn)（目標(biāo)場(chǎng)所），由蟻群算法計(jì)算出最優(yōu)路徑，最終可得到路徑規(guī)劃結(jié)果。
4、結(jié)論
本文是基于百度地圖API、javascript和JSP編寫(xiě)的一個(gè)路徑優(yōu)化系統(tǒng)。系統(tǒng)將所有的地理數(shù)據(jù)存放到數(shù)據(jù)庫(kù)中，可查詢所服務(wù)點(diǎn)的詳細(xì)位置，顯示各配送點(diǎn)之間的導(dǎo)航路線。為達(dá)到總運(yùn)行時(shí)間最短的目標(biāo)，采用改進(jìn)的蟻群算法優(yōu)化導(dǎo)航路線，用以優(yōu)化配送路徑，并將最佳路徑用百度地圖呈現(xiàn)出來(lái)，從而為配送系統(tǒng)的構(gòu)建提供行之有效的信息化手段。
參考文獻(xiàn)
[1] Colorni, A., M. Dorigo and V. Mariiezzo., 1991. Distributed Optimization by Ant Colonies, in: Proc. Eearop. Conf. Arti?cial Life, ed. F. Varela and P. Bourgine.
（本文作者：張子寒 朱海佳 郭騰飛 亓呈明 來(lái)源：北京聯(lián)合大學(xué)城市軌道交通與物流學(xué)院 本文得到北京聯(lián)合大學(xué)“啟明星”大學(xué)生科技創(chuàng)新項(xiàng)目201911417XJ146支持。）
