基于蟻群算法的“層輻式”應急配送路徑規劃研究

米志強

?

基于蟻群算法的“層輻式”應急配送路徑規劃研究

米志強

（湖南現代物流職業技術學院，湖南 長沙 410131)

每當國家遇到重大災害、疫情時，為了挽救更多人的生命，需要在第一時間啟動救援應急預案，文章把傳統“點輻式”應急調度模型改造成“層輻式”應急調度模型，利用蟻群算法對“層輻式”應急配送路徑中實際應用問題進行了研究，并提供一些實際解決方案。

應急配送；蟻群算法；層輻式；路徑規劃

引　言

大規模突發性自然災害發生后，對于災區（應急點）來說，本地區的應急救援物資會出現短缺的現象，此時需要從其他地區（出救點）調撥，對于“出救點”來說，調用應急救援物資進行緊急救援時，它的供給量和供給速度往往是不能滿足應急點的消耗，這就產生了應急救援物資調度問題。

應急救援物資調度中的路徑規劃技術是應急物流的關鍵技術之一，對其調研算法的研究有利于推進路徑優化，滿足實際災害救援應用需要。其主要涉及的問題包括：理論模型的建立，再用某種算法尋找一條從出救點到應急點的最優路徑，從而得到相對更優的行為決策。

1　“層輻式”應急配送模型抽象

當發生災害時，往往是“一方有難，四方支援”，它的救援模型如圖1，我們可以簡稱為“點輻式”救援應急配送調度網絡模型。它以“災區（應急點）”中心，眾多“出救點”由此點為“軸點”向“應急點”實施救援。目前，“點輻式”調度已取得了很大的進展，但是當發生大規模自然災害時，往往不是單點受災，而是多受災點同時出現，這種“多點災害、多點救援”應急救援調度網絡模型，我們稱之為“層輻式”如圖2所示，這種模型中的起步較早，其模型也更加復雜。

圖1.“點輻式”救援模型

圖2.“層輻式”救援模型

2　相關配送路徑優化的研究回顧

傳統路徑規劃方法一般是基于圖形進行模擬試驗，該方法一般是建立在全局路徑規劃的基礎上。目前國內外普遍存在的方法包括柵格法、拓撲法、可視圖法、Voronoi圖法、人工勢場法、A*算法等。

近年來，隨著應急配送的復雜性增加及現代計算技術的迅速發展，傳統路徑規劃已經難以滿足移動應急配送路徑規劃的要求，因此智能路徑算法不斷被研究并應用。人工智能路徑規劃算法的提出大大提高了路徑規劃的優化，加快規劃速度,滿足實際應用的需要。智能路徑規劃算法主要包括遺傳算法、粒子群算法、模糊邏輯、神經網絡、人工免疫算法以及多種混合算法。以上算法在障礙物環境已知或未知情況下均已取得一定的研究成果。

何建敏等提出了在有限制期約束的情況下，邊權（或者時間）為區間數的賦權圖最小風險路徑的選取算法。王軍等研究了基于應急資源多點分布條件下的資源調度優化問題，提出了送達及時性、運輸路線可靠性組合計算模型。

3　蟻群算法原理及特點

蟻群算法(Ant Algorithm簡稱AA)是意大利學者Dorigo和Colorni在1991年提出的一種仿生優化算法。他們模擬和借鑒了現實世界中螞蟻種群的行為特征，用來解決各種分布環境下的組合優化問題，螞蟻算法主要是通過螞蟻群體之間的信息傳遞而達到尋優的目的，最初又稱蟻群優化方法(Ant Colony Optimization簡稱ACO)，蟻群搜索食物的過程與求解旅行售貨員問題(Traveling Salesman Problem ,簡稱TSP)非常相性。

蟻群算法主要特點是：正反饋、分布式計算、能夠較好地與其他啟發式算法相融合。正反饋過程使得該方法能很快發現較好解；分布式計算使得該方法易于并行實現;與其他啟發式算法相結合,使得該方法易于發現較好解。

4　“層輻式”路徑優化問題的提出

4.1問題設計

在“多點災害、多點救援”的“層輻式”應急救援實際過程中，特別是地質災害發生之后，由于災害的破壞性，導致道路、橋梁及其他交通受到不同程度的破壞，這需要智能的路徑優化設計。

設定“層輻式”災害救援輻度(即災害范圍)為x、y，“層級深度”（即應急物資中轉層次數）為n。那么我可以把“層輻式”抽象表達為（x,y,n）一個三維關系。假定在救援輻度為一個800×800的平面場景圖，在原點O(0, 0)點為“出救點”，它只能在該平面場景范圍內活動。圖中有12個不同形狀的區域是配送過程不能與之發生碰撞的障礙點，障礙點的數學描述如表1：

表1

編號障礙點名稱障礙問題假設左下頂點坐標其它特性描述處理辦法 1正方形水壩開裂障礙(300, 400)邊長200繞行，層級深度+1 2圓形大面積塌方，必須繞行圓心坐標(550, 450)，半徑70繞行，層級深度+1 3平行四邊形遇到無法直行，必須交其它工具轉運(360, 240)底邊長140，左上頂點坐標(400, 330)，繞行，層級深度+1 4三角形遇道路雜物堵塞障礙(280, 100)上頂點坐標(345, 210)，右下頂點坐標(410, 100)時間加倍 5正方形水壩開裂障礙(80, 60)邊長150繞行，層級深度+1 6三角形遇道路雜物堵塞障礙(60, 300)上頂點坐標(150, 435)，右下頂點坐標(235, 300)時間加倍 7長方形橋梁斷落障礙(0, 470)長220，寬60繞行，層級深度+1 8平行四邊形遇到無法直行，必須交其它工具轉運(150, 600)底邊長90，左上頂點坐標(180, 680)層級深度+1 9長方形橋梁斷落障礙(370, 680)長60，寬120繞行，層級深度+1 10正方形水壩開裂障礙(540, 600)邊長130繞行，層級深度+1 11正方形水壩開裂障礙(640, 520)邊長80繞行，層級深度+1 12長方形橋梁斷落障礙(500, 140)長300，寬60繞行，層級深度+1

設定“層輻式”場景圖中4個點O(0，0)，A(300，300)，B(100，700)，C(700，640)。

圖3.800×800平面場景圖

4.2 問題分析

5　模型的建立與求解

5.1 模型假設與符號說明

由4.2得出如下假設：

（1）假設應急配送工具寬度忽略不計。這樣，它的運動可以看成是一個點的移動。

（2）假設應急配送直線行走和轉彎時均以最大速度運行。

（3）假設障礙物始終是題目所給的12個不同形狀的區域，且位置，大小等性質一直不變。

表2.符號說明

符號說明 無障礙時最大速度 轉彎半徑 的最短路徑中第i個分段的長度 的最短路徑中第i個分段的長度 的最短路徑中第i個分段的長度 的最短時間 表示的弧長 表示的直線長度

圖4.路徑示意圖

圖5.最短路徑圖

Min（2）

綜上，構造如下優化模型：

Min（3）

求解上述模型，得到結果如下：

表2.的最短路徑

分段起點終點線段類型長度 1（0，0）(70.50596,213.1406)直線224.4994 2(70.50596,213.1406)(70.6064,219.4066)以（80，210）為圓心的弧線9.1105 3(70.6064,219.4066)（300，300）直線237.4273 總長度471.0372

在本文中，我們將路線圖簡化為一個賦權網絡圖，并利用蟻群算法，找出最短路徑的大致路線。構造賦權網絡圖如下：

我們把平面上的一些點編號，并將它們之間的距離關系簡化為網絡圖（如圖6）。如果節點直接可以直線到達而不遇到障礙物，則它們之間的邊的權重為直線距離，否則它們之間沒有邊。如圖7：

圖6.節點編號圖

圖7.賦權網絡圖

（1）蟻群算法模型

（2）執行步驟

第一步初始化N只螞蟻。實際上就是N條道路，并計算當前的螞蟻位置。

第二步初始化運行參數，開始迭代。

第三步在迭代補數范圍內，計算轉移概率，如果小于全局轉移概率就進行小范圍的搜索，否則進行大范圍的搜索。

第四步更新信息素，記錄狀態，準備進行下一次迭代。

第五步轉第三步

第六步輸出結果

（3）結果分析

50只螞蟻的初始狀態是無序分布的，優化后螞蟻移動后的最終位置實現了兩級分化，這樣我們就得到了最優解。

圖8分別是平均和最優的變化曲線，從中可以知道，算法收斂速度很快，效果很快，效果較好。

圖8.信息素濃度的平均值和最優值

圖9.最短路線示意圖

在上一部分中，我們已經確定了最短路的運行路線是按照圖3中的節點，但是這個簡化圖中距離只考慮了直線，而沒有考慮實際行走中的圓弧長度。因此，我們將這條路線進行分段，使得每段路線只繞開一個障礙物。

圖10.最短路徑圖

Min（5）

求解上述模型，得到結果如下：

兩個圓弧切點坐標：

同理我們可以計算出其他分段路線的最短路徑。

表3.的最短路徑

分段起點終點線段類型長度 1(0,0)(50.1353,301.6396)直線305.7777 2(50.1353,301.6396)(51.6795,305.547)以（60，300）為圓心的弧線5.88 3(51.6795,305.547)(141.6795,440.547)直線162.2498 4(141.6795,440.547)(147.9621,444.79.0)以（150，435）為圓心的弧線7.7756 5(147.9621,444.79.0)(222.0379,460.2099)直線75.6637 6(222.0379,460.2099)(230,470)以（220，470）為圓心的弧線13.6557 7(230,470)(230,530)直線60 8(230,530)(225.5026,538.3538)以（220，530）為圓心的弧線9.8883 9(225.5026,538.3538)(144.5033,591.6462)直線96.9536 10(144.5033,591.6462)(140.6892,596.3523)以（150，600）為圓心的弧線6.1545 11(140.6892,596.3523)(100,700)直線110.377 總長854.3759

[1]李大衛,王莉.物流系統選址調度——模型與算法[M].北京:科學出版社,2014:30-31.

[2]邵舉平.不確定環境下供應鏈一體化物流計劃模型與算法[M].北京:經濟科學出版社,2010:89-90

[3]梁毓明,徐立鴻.動機器人路徑規劃技術的研究現狀與發展趨勢[C].學術論文,2009,(3):36-39

[4]魯慶.基于柵格法的移動機器人路徑規劃研究[J].電腦與信息技術,2007,(12):24-27.

[5]TAKAHASHI.O.And SCHILLING R.J.Motion planning in a plane-using generalized voronoi digrams[J].IEEE Xplore.1989.

[6]范玉娥.基于多目標的震后應急物資車輛路徑問題研究[D].沈陽大學,2014:77-78.

[7]鄭斌,馬祖軍,李雙琳等.基于雙層規劃的震后初期應急物流系統優化[J].系統工程學報,2014,(1):113-125.

[8]金雷澤,杜振軍,賈凱.基于勢場法的移動機器人路徑規劃仿真研究[J].計算機工程與應用,2007,(24):43.

[9]Koren Y,And Borenstein J.Potential field methods and their inherent limitations for mobile robot navigation[C].IEEE,1991: 1398-1404.

[10]LEROY’G,LALLY A M,et al.The use of dynamic contexts to improve casual Internet searching[J].ACM Transactions on Information System,2003,(3):229-253.

[11]陳衛東,朱奇光.基于模糊算法的移動機器人路徑規劃[J].電子學報,2011,(4):971-974.

[12]計國君.突發事件應急物流資源配送優化問題研究.中國流通經濟,2007,(3):18-21.

（責任編校：何俊華）

2016－03－20

米志強（1972－），男，湖南辰溪人，副教授，國家系統分析師，研究方向為物流信息技術。

U652.1+2

A

1673-2219（2016）10-0080-07