金保華，張 亮，和振遠(yuǎn)

（鄭州輕工業(yè)學(xué)院，鄭州450002）

基于最大最小螞蟻系統(tǒng)的一種應(yīng)急物流路徑規(guī)劃方法

金保華，張 亮，和振遠(yuǎn)

（鄭州輕工業(yè)學(xué)院，鄭州450002）

根據(jù)應(yīng)急物流中存在的一些問題，利用最大最小螞蟻系統(tǒng)收斂速度快和避免局部最優(yōu)的優(yōu)勢(shì)，提出了一種基于最大最小螞蟻系統(tǒng)的應(yīng)急物流路徑規(guī)劃方法．該方法通過最大最小螞蟻系統(tǒng)將信息素限制在一個(gè)適當(dāng)?shù)姆秶畠?nèi)，克服了傳統(tǒng)算法收斂速度慢和易陷于局部最優(yōu)的缺點(diǎn)．對(duì)應(yīng)用最大最小螞蟻系統(tǒng)的應(yīng)急物流系統(tǒng)進(jìn)行仿真實(shí)驗(yàn)，結(jié)果表明：該方法能快速實(shí)現(xiàn)應(yīng)急物流配送，滿足了實(shí)際需要，減少了物流成本．

蟻群優(yōu)化；最大最小螞蟻系統(tǒng)；旅行商問題；應(yīng)急物流

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

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

最大最小螞蟻系統(tǒng)通過只允許在最好的解方法中增加信息素來實(shí)現(xiàn)最優(yōu)路徑搜索．它使用簡(jiǎn)單的機(jī)制限制了信息素的增強(qiáng)，有效避免了搜索的過早收斂．MMAS算法是當(dāng)前解決TSP和QAP問題性能最好的方法之一．本文主要是將最大最小螞蟻系統(tǒng)應(yīng)用到應(yīng)急物流路徑選擇中，并得到了較好的結(jié)果．

1 最大最小螞蟻系統(tǒng)的原理

提升蟻群優(yōu)化算法性能的關(guān)鍵是避免過早陷入搜索停滯現(xiàn)象．為了解決這個(gè)問題，MMAS在螞蟻系統(tǒng)的基礎(chǔ)上作了以下4個(gè)方面的改進(jìn)：

（1）在算法運(yùn)行期間，只允許單只螞蟻增加信息素．這只螞蟻可能在當(dāng)前迭代中找到最優(yōu)解，或者在線索開始時(shí)就找到最優(yōu)解．

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

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

（4）當(dāng)系統(tǒng)達(dá)到停滯狀態(tài)，或者在一定次數(shù)的迭代過程中不再有更優(yōu)的路徑出現(xiàn)時(shí)，則所有的信息素值都會(huì)被重新初始化．之間．

1．1 信息素更新

在MMAS中，每次循環(huán)結(jié)束后只有一只螞蟻更新信息素．信息素更新規(guī)則如下：

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

1．2 信息素最大最小值的設(shè)置

如果信息素更新只選擇循環(huán)最優(yōu)或全局最優(yōu)中的一種時(shí)，更容易發(fā)生搜索停滯現(xiàn)象，最終出現(xiàn)其中一個(gè)選擇點(diǎn)的信息素值明顯比他點(diǎn)的信息素值高．螞蟻依據(jù)公式（2）選擇下一個(gè)節(jié)點(diǎn)：

隨著信息素的增加，螞蟻更愿意選擇這個(gè)解．結(jié)果是螞蟻重復(fù)地建立同一個(gè)解，于是便產(chǎn)生了停滯現(xiàn)象．

為了避免進(jìn)入停滯狀態(tài)，MMAS增加了τmax和τmin的限制，對(duì)所有信息素值τij（t），有τmin≤τij（t）≤τmax．如果τij（t）＞τmax，則重新設(shè)置為τij（t）＝τmax；類似地，如果τij（t）＜τmin，則重新設(shè)置為τij（t）＝τmin．同時(shí)也要強(qiáng)調(diào)τmin＞0和τmax＜∞．

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

式中：f（sopt）是某個(gè)具體問題的最優(yōu)解．

在MMAS中，最大信息素τmax設(shè)置為漸進(jìn)的最大估計(jì)值．在公式（3）中用全局最優(yōu)解f（sgb）代替f（sopt）來實(shí)現(xiàn)．每找到一個(gè)新的方法，τmax就更新一次，其動(dòng)態(tài)變化值為τmax（t）．

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

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

（2）信息素值的上限和下限之間的差異而不是啟發(fā)式信息影響了最終的解結(jié)構(gòu)．

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

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

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

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

式中：Pbest＝1，τmin＝0．如果Pbest太小，公式（4）中可能會(huì)有τmin＞τmax．在這種情況下，設(shè)置τmin＝τmax，這相當(dāng)于在解結(jié)構(gòu)中僅使用了啟發(fā)式信息．根據(jù)公式（4），可以由給定的Pbest確定τmin．因此，在 MMAS中，Pbest提供了一個(gè)調(diào)查限制較低線索的好方法．

1．3 信息素的初始化

在算法開始時(shí)，所有邊上的信息素初試值都設(shè)定為τmax的一個(gè)估計(jì)值．隨著算法的執(zhí)行，默認(rèn)路徑被選擇的概率很小．為了增加探索這些路徑的可能性，在MMAS中，當(dāng)算法接近停滯狀態(tài)時(shí)，或者在指定次數(shù)的迭代中未能得到一條更優(yōu)的路徑時(shí)，就會(huì)觸發(fā)信息素的重新初始化［4］．

2 MMAS在應(yīng)急物流配送中的應(yīng)用

2．1 最佳路徑的描述

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

應(yīng)急物流配送系統(tǒng)是非常復(fù)雜的，在搜索最優(yōu)路徑過程中，有以下2個(gè)約束條件：

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

（2）在各節(jié)點(diǎn)處理貨物的時(shí)間也相同．

2．2 應(yīng)急物流配送中的最大最小螞蟻系統(tǒng)

在一趟應(yīng)急配送過程中，將所有的配送點(diǎn)視作一個(gè)連通圖上的點(diǎn)，車輛從一個(gè)配送中心出發(fā)，利用最短時(shí)間將貨物送到各節(jié)點(diǎn)，最后到達(dá)另一配送中心．始發(fā)點(diǎn)對(duì)應(yīng)于MMAS中的蟻穴，終點(diǎn)對(duì)應(yīng)于食物源，根據(jù)MMAS尋找最優(yōu)路徑．

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

2．3 應(yīng)急物流系統(tǒng)中 MMAS算法描述

算法開始時(shí)，設(shè)NC為實(shí)驗(yàn)中螞蟻當(dāng)前的循環(huán)次數(shù)，初始值設(shè)為0，Tabuk（s）用于記錄第k只螞蟻經(jīng)過的節(jié)點(diǎn)，Tabu1用于記錄每次循環(huán)結(jié)束后找到的最短路徑，q為Tabu1表索引的序號(hào)，初始值為0．算法步驟如下：

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

（2）設(shè)s的初始值為1（s為Tabu表索引的序號(hào)），Tabuk（1）為初始點(diǎn)．

（3）循環(huán)開始，NC從0開始，當(dāng)NC大于N時(shí)，循環(huán)結(jié)束．

（4）從k＝1只螞蟻開始搜索路徑，如果Tabuk（s）不是終點(diǎn)，由公式（2）計(jì)算下一個(gè)節(jié)點(diǎn)的概率Pijk（t），在t時(shí)刻，第k只螞蟻在Tabuk（s－k）中選擇要經(jīng)過的節(jié)點(diǎn)．設(shè)第k只螞蟻選擇節(jié)點(diǎn)j，則將j插入Tabuk（s）中．一直循環(huán)，直到所有螞蟻都達(dá)到終點(diǎn)．

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

（6）循環(huán)次數(shù)NC自動(dòng)加1，回到步驟（3）繼續(xù)執(zhí)行．

（7）得到記錄每次循環(huán)中最短路徑的Tabu1表，比較Tabu1中的各路徑長(zhǎng)度，選出最佳的路徑．

3 實(shí)驗(yàn)分析

本文選取12個(gè)節(jié)點(diǎn)進(jìn)行實(shí)驗(yàn)．各節(jié)點(diǎn)坐標(biāo)如表1所示．

表1 12個(gè)節(jié)點(diǎn)的坐標(biāo)

表2 參數(shù)設(shè)置

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

為了便于比較，分別選取6、12、20只螞蟻進(jìn)行實(shí)驗(yàn)，最后的最優(yōu)路徑如圖1所示．

圖1 6、12、20只螞蟻的路徑長(zhǎng)度對(duì)比圖

循環(huán)過程中，信息素值的動(dòng)態(tài)變化如圖2所示．

實(shí)驗(yàn)最后，運(yùn)用MMAS搜索到的最優(yōu)路徑如圖3所示．

由上述實(shí)驗(yàn)結(jié)果可看出，通過MMAS能在很短時(shí)間內(nèi)找到最短路徑，在應(yīng)急配送系統(tǒng)中起到很大的作用．實(shí)驗(yàn)過程中，當(dāng)螞蟻數(shù)量與問題中的節(jié)點(diǎn)數(shù)量相同時(shí)，搜索到的路徑最短．

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

4 結(jié) 語

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

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

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

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

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

［5］劉祥．基于蟻群算法的物流配送算法［J］．科技情報(bào)開發(fā)與經(jīng)濟(jì)，2009，19（10）：89－91．

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

JIN Bao－h(huán)ua，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

河南省重點(diǎn)科技攻關(guān)項(xiàng)目（072102210007）

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