基于最大最小螞蟻系統的一種應急物流路徑規劃方法

金保華，張 亮，和振遠

（鄭州輕工業學院，鄭州450002）

基于最大最小螞蟻系統的一種應急物流路徑規劃方法

金保華，張 亮，和振遠

（鄭州輕工業學院，鄭州450002）

根據應急物流中存在的一些問題，利用最大最小螞蟻系統收斂速度快和避免局部最優的優勢，提出了一種基于最大最小螞蟻系統的應急物流路徑規劃方法．該方法通過最大最小螞蟻系統將信息素限制在一個適當的范圍之內，克服了傳統算法收斂速度慢和易陷于局部最優的缺點．對應用最大最小螞蟻系統的應急物流系統進行仿真實驗，結果表明：該方法能快速實現應急物流配送，滿足了實際需要，減少了物流成本．

蟻群優化；最大最小螞蟻系統；旅行商問題；應急物流

應急物流是指為突發事件提供緊急物資、資金、職員的一種特別活動．本文就應急物流選擇最佳配送路線問題提出解決方法，即將最大最小螞蟻系統（MMAS）應用到物流配送系統中，從而快速找到最優路徑，完成配送．

蟻群算法是最近幾年才提出的一種新型的模擬進化算法．螞蟻系統（AS）是第一個蟻群算法，它最早是由意大利學者Dorigo Maniezzo等人在20世紀90年代初提出來，并用該方法求解旅行商問題（Traveling Salesman Problem，TSP）［1］、二次分配問題（Quadratic Assignment Problem，QAP）、job－shop調度問題等，取得了一系列較好的實驗結果．但螞蟻系統容易出現搜索停滯現象．針對AS算法的不足，許多學者對其進行深入研究，最后在AS基礎上提出了最大最小螞蟻系統［2］．

最大最小螞蟻系統通過只允許在最好的解方法中增加信息素來實現最優路徑搜索．它使用簡單的機制限制了信息素的增強，有效避免了搜索的過早收斂．MMAS算法是當前解決TSP和QAP問題性能最好的方法之一．本文主要是將最大最小螞蟻系統應用到應急物流路徑選擇中，并得到了較好的結果．

1 最大最小螞蟻系統的原理

提升蟻群優化算法性能的關鍵是避免過早陷入搜索停滯現象．為了解決這個問題，MMAS在螞蟻系統的基礎上作了以下4個方面的改進：

（1）在算法運行期間，只允許單只螞蟻增加信息素．這只螞蟻可能在當前迭代中找到最優解，或者在線索開始時就找到最優解．

（2）為了避免出現搜索停滯現象，信息素范圍限制在

（3）將弧段信息素初始化為τmax．

（4）當系統達到停滯狀態，或者在一定次數的迭代過程中不再有更優的路徑出現時，則所有的信息素值都會被重新初始化．之間．

1．1 信息素更新

在MMAS中，每次循環結束后只有一只螞蟻更新信息素．信息素更新規則如下：

式中：△Tijbest＝1／f（sbest），f（sbest）代表了循環最優解或者全局最優解的值．MMAS主要使用迭代最優解．只用循環最優解或者全局最優解中的一個解進行信息素更新是MMAS中搜索過程最重要的方法．當僅用全局最優解時，搜索可能很快集中到這個解周圍，而限制了搜索其他可能更好的解．如果只用循環最優解，可能導致大量的解元素得到偶然加強．當然，也可以用混合策略，如用循環最優解為更新信息素的默認值，而全局最優解僅僅在循環固定次數后使用．

1．2 信息素最大最小值的設置

如果信息素更新只選擇循環最優或全局最優中的一種時，更容易發生搜索停滯現象，最終出現其中一個選擇點的信息素值明顯比他點的信息素值高．螞蟻依據公式（2）選擇下一個節點：

隨著信息素的增加，螞蟻更愿意選擇這個解．結果是螞蟻重復地建立同一個解，于是便產生了停滯現象．

為了避免進入停滯狀態，MMAS增加了τmax和τmin的限制，對所有信息素值τij（t），有τmin≤τij（t）≤τmax．如果τij（t）＞τmax，則重新設置為τij（t）＝τmax；類似地，如果τij（t）＜τmin，則重新設置為τij（t）＝τmin．同時也要強調τmin＞0和τmax＜∞．

通過公式（3）重新定義收斂概念：

式中：f（sopt）是某個具體問題的最優解．

在MMAS中，最大信息素τmax設置為漸進的最大估計值．在公式（3）中用全局最優解f（sgb）代替f（sopt）來實現．每找到一個新的方法，τmax就更新一次，其動態變化值為τmax（t）．

為了給τmin確定合理值，先假設如下：

（1）在停滯發生之前很快找到最優解．在這種情況下，在一次算法迭代中構造全局最優解的概率明顯高于0，并且在這個最優解附近可能找到更好的解．

（2）信息素值的上限和下限之間的差異而不是啟發式信息影響了最終的解結構．

第一個假設的有效性依賴于問題的搜索空間特征．它意思是在較優解周圍可能找到最優解，比如TSP問題．第二個假設是在設置τmin的對稱方式的推導中，忽略啟發式信息對概率的影響．

鑒于這些假設，通過限制算法線索最小值的收斂得到τmin的最佳值．當MMAS收斂時，找到的最佳方法的概率為Pbest，Pbest明顯高于0．事實上，在選擇點選擇相應解元素的概率Pdec直接依賴于τmin和τmax．為了簡單起見，算法中假設Pdec在所有決策點都不變．然后，螞蟻做n次“正確”選擇，并且用概率Pndec建立了最好的方法．通過設置Pndec＝Pbest，即

因此，給定一個Pbest，能夠確定τmin的大概值．綜合起來，在每個選擇點上螞蟻需在avg＝n／2的各個解元素中進行選擇．根據公式（2）能夠計算出概率Pdec，即

從上式中解出τmin的值為：

式中：Pbest＝1，τmin＝0．如果Pbest太小，公式（4）中可能會有τmin＞τmax．在這種情況下，設置τmin＝τmax，這相當于在解結構中僅使用了啟發式信息．根據公式（4），可以由給定的Pbest確定τmin．因此，在 MMAS中，Pbest提供了一個調查限制較低線索的好方法．

1．3 信息素的初始化

在算法開始時，所有邊上的信息素初試值都設定為τmax的一個估計值．隨著算法的執行，默認路徑被選擇的概率很小．為了增加探索這些路徑的可能性，在MMAS中，當算法接近停滯狀態時，或者在指定次數的迭代中未能得到一條更優的路徑時，就會觸發信息素的重新初始化［4］．

2 MMAS在應急物流配送中的應用

2．1 最佳路徑的描述

配送是應急物流系統中的主要過程．車輛調度及路線安排是配送中心作出決策的重要內容，它直接影響到配送成本和服務質量．即時配送以某天的任務為目標，在充分掌握了這一天的配送地點、需求量、種類及要求到達時間的前提下，及時安排最優的配送路線并安排相應的配送車輛實行配送．因此一個好的物流配送算法對于應急配送系統是非常關鍵的，如果不對算法進行任何約束，那么將很難在合理的時間內得到滿意解．將最大最小螞蟻系統的思想應用到物流配送算法中，實現了對所選路線的合理安排，在成本和服務質量上達到了最佳．

應急物流配送系統是非常復雜的，在搜索最優路徑過程中，有以下2個約束條件：

（1）所有車輛的行車速度相同；

（2）在各節點處理貨物的時間也相同．

2．2 應急物流配送中的最大最小螞蟻系統

在一趟應急配送過程中，將所有的配送點視作一個連通圖上的點，車輛從一個配送中心出發，利用最短時間將貨物送到各節點，最后到達另一配送中心．始發點對應于MMAS中的蟻穴，終點對應于食物源，根據MMAS尋找最優路徑．

選擇最佳路徑問題與螞蟻進行覓食的過程類似［5］．給定一個有n個節點的路線圖，螞蟻從起點出發尋找到達終點的最短路徑．根據MMAS，設螞蟻的數量為m；n表示一趟配送中的配送節點數；N表示實驗中總的循環周期數；d ij表示節點i與節點j之間的距離；ηij為能見度因子；τij表示t時刻邊（i，j）上的信息素濃度；初始時刻，所有的m只螞蟻都集中在配送中心起點處，且賦予每條邊上相等的信息素值τij（0）＝τmax．螞蟻在運動過程中，根據各條路徑上的信息素量決定其轉移方向，轉移概率Pijk（t）由公式（2）計算得到，它表示t時刻第k只螞蟻（k＝0，1，2，3…）由節點i轉移到節點j的概率．

2．3 應急物流系統中 MMAS算法描述

算法開始時，設NC為實驗中螞蟻當前的循環次數，初始值設為0，Tabuk（s）用于記錄第k只螞蟻經過的節點，Tabu1用于記錄每次循環結束后找到的最短路徑，q為Tabu1表索引的序號，初始值為0．算法步驟如下：

（1）N表示循環周期數，邊（i，j）上信息素初始值設置為τij（0）＝τmax，再根據公式（4）計算τmin的值．t＝0時刻，m只螞蟻位于起始點．假設單只螞蟻完成一個節點的旅行時間為1．

（2）設s的初始值為1（s為Tabu表索引的序號），Tabuk（1）為初始點．

（3）循環開始，NC從0開始，當NC大于N時，循環結束．

（4）從k＝1只螞蟻開始搜索路徑，如果Tabuk（s）不是終點，由公式（2）計算下一個節點的概率Pijk（t），在t時刻，第k只螞蟻在Tabuk（s－k）中選擇要經過的節點．設第k只螞蟻選擇節點j，則將j插入Tabuk（s）中．一直循環，直到所有螞蟻都達到終點．

（5）計算第k只螞蟻的長度L k．選擇L k最短時的值，將第k只螞蟻經過的路徑按照τij（t＋1）＝ρ·τij（t）＋△τijk進行更新．其中ρ是一個系數，（1－ρ）為信息素的蒸發率．然后將該路徑復制到Tabu1（i＋＋）中，根據公式（3）計算出τmax（t），如果τij（t）＞τmax（t），則τmax（t）＝τij（t），否則τmax（t）不變．根據公式（4）計算τmin（t）的值，如果τmin（t）＞τmax（t），設置τmin（t）＝τmax（t）．

（6）循環次數NC自動加1，回到步驟（3）繼續執行．

（7）得到記錄每次循環中最短路徑的Tabu1表，比較Tabu1中的各路徑長度，選出最佳的路徑．

3 實驗分析

本文選取12個節點進行實驗．各節點坐標如表1所示．

表1 12個節點的坐標

表2 參數設置

其中：α為信息量τij（t）對螞蟻選擇該路徑的影響因子，它反映了螞蟻在運動過程中所積累的信息量，α越大，螞蟻選擇以前走過的路徑的可能性就越大，α越小，搜索過程越早陷入局部最優；β為期望度ηij（t）的影響因子，它反映了蟻群搜索過程中先驗性因素的作用大小，β值越大，算法收斂速度越快；ρ為信息素揮發因子，由于信息素ρ的存在，當問題的規模較大時，會使從未被搜索到的路徑上的信息素減小到接近于0．

為了便于比較，分別選取6、12、20只螞蟻進行實驗，最后的最優路徑如圖1所示．

圖1 6、12、20只螞蟻的路徑長度對比圖

循環過程中，信息素值的動態變化如圖2所示．

實驗最后，運用MMAS搜索到的最優路徑如圖3所示．

由上述實驗結果可看出，通過MMAS能在很短時間內找到最短路徑，在應急配送系統中起到很大的作用．實驗過程中，當螞蟻數量與問題中的節點數量相同時，搜索到的路徑最短．

應急物流最關鍵的因素是突出物流配送的時效性．當突發事件發生時，如何選擇一條最短配送路徑是至關重要的．很多算法被用在求解應急物流路徑選擇問題上，并得到較好的效果，常用的算法有模擬退火算法、螞蟻系統等．模擬退火算法能較好地求解較具體的問題，但其難以知道什么時候最優解已經被求得．相對而言，最大最小螞蟻系統在應急物流路徑選擇中比模擬退火算法和螞蟻系統有更好的效果．

4 結 語

應急物流在我國出現較晚，尚屬一個新概念．我國應急物流體系還很不完善，需要加強這方面的理論和實踐研究．本文將最小最大螞蟻系統應用到應急物流路徑選擇中，并得到了較好的結果．但最大最小螞蟻系統雖然克服了易出現搜索停滯現象等不足，但還沒有形成系統的分析方法，其數學基礎較薄弱，實驗中參數的選擇基本上都是基于經驗的．

［1］Barbarosoglu，Ozgur．ATabuSearchAlgorithmfortheVehicleRoutingProblem［J］．Computers＆OperationsResearch，1999，26：255－270．

［2］StutzleT，HoosHH．Max－MinantSystem［J］．FutureGenerationComputerSystem，2000，16（8）：889－914．

［3］李士勇．蟻群算法及其應用［M］．哈爾濱：哈爾濱工業大學出版社，2004，24－27．

［4］張學敏，張航．基于改進蟻群算法的最短路徑問題研究［J］．控制理論與應用，2009，28（6）：4－6．

［5］劉祥．基于蟻群算法的物流配送算法［J］．科技情報開發與經濟，2009，19（10）：89－91．

A Method of Contingency Logistics Path Planning Based on Max－Min Ant System

JIN Bao－hua，ZHANG Liang，HE Zhen－yuan
（Zhengzhou University of Light Industry，Zhengzhou 450002，China）

According to the problems in Contingency Logistics，using the advantage of fast convergence and avoiding local optimum of Max－Min ant system，the Contingency Logistics path planning method based on the Max－Min ant system is proposed in this paper．This method overcomes the slow convergence and easy－trapped local optimum of conventional algorithms through that the Max－Min ant system limits the pheromone in an appropriate range．Finally，simulation experiments are executed for contingency logistics system which using the Max－Min ant system，experiments show that the method fast achieves the contingency logistics and distribution，which not only meets the actual needs，but reduces the cost of logistics．

ant colony optimization；Max－Min ant system；traveling salesman problem；contingency logistics

TP18

A

10．3969／j．issn．1671－6906．2011．02．004

1671－6906（2011）02－0014－04

2011－03－13

河南省重點科技攻關項目（072102210007）

金保華（1966－），男，河南鄭州人，副教授．