張 濤，謝金寶

（蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州730070）

突發(fā)事件會(huì)造成人民生命和財(cái)產(chǎn)的巨大損失，對(duì)應(yīng)急車輛路徑問題的研究就是在盡可能短的時(shí)間內(nèi)，更合理、科學(xué)地選擇最優(yōu)的車輛路徑，最大限度降低應(yīng)急成本，是救援工作中極為重要的研究?jī)?nèi)容。

我國(guó)學(xué)者更多是從理論方面出發(fā)，定性研究應(yīng)急物流的特點(diǎn)、保障機(jī)制和組織形式等問題；在定量方面，研究相對(duì)較少。我國(guó)是一個(gè)突發(fā)災(zāi)害頻發(fā)的國(guó)家，目前系統(tǒng)地、定量地對(duì)我國(guó)災(zāi)害救援應(yīng)急車輛路徑優(yōu)化模型和應(yīng)對(duì)遲緩、缺少科學(xué)依據(jù)的決策問題的研究，具有重要的現(xiàn)實(shí)意義。針對(duì)人工智能算法在求解優(yōu)化問題方面的優(yōu)勢(shì)，本文通過建立應(yīng)急車輛最優(yōu)路徑選擇模型，且在基本魚群算法的理論基礎(chǔ)上，提出一種改進(jìn)的人工魚群算法并將其應(yīng)用到應(yīng)急車輛路徑選擇問題上。

1 建立模型

1.1 問題描述

對(duì)應(yīng)急車輛路徑選擇問題的描述:選擇應(yīng)急總時(shí)間最短為目標(biāo)，在只有一個(gè)物資儲(chǔ)備中心，車載容量一定情況下，選擇車輛數(shù)盡可能少的為n個(gè)受災(zāi)點(diǎn)提供應(yīng)急物資，在完成對(duì)各受災(zāi)點(diǎn)的物資配送后，車輛又回到物資儲(chǔ)備中心。

假設(shè)條件:

1）物資儲(chǔ)備中心與受災(zāi)點(diǎn)的坐標(biāo)已知；

2）救援完成后車輛應(yīng)回到起始地點(diǎn)重新裝載貨物；

3）每個(gè)受災(zāi)點(diǎn)只被一輛車救援一次；

4）每輛車所運(yùn)輸救援物資不能超過車輛的負(fù)載能力。

1.2 模型建立

根據(jù)圖論方面的知識(shí)，設(shè)G＝（V，E）為應(yīng)急救援的路網(wǎng)，且該路網(wǎng)是一個(gè)完備圖。其中V為頂點(diǎn)集合，E為邊集合，頂點(diǎn)之間的距離權(quán)值為lij（lij＞0）。

定義變量:

建立應(yīng)急救援車輛路徑優(yōu)化模型:

式中:di為各受災(zāi)點(diǎn)物資需求數(shù)量；D為車輛的負(fù)載數(shù)量；lij為路網(wǎng)中任意兩點(diǎn)之間的距離；ˉv為車輛的平均速度；vmax為車輛的最大速度；qij為（i，j）弧的暢通度；pij為（i，j）弧上最大容量；vij為車輛經(jīng)過（i，j）路徑的實(shí)際速度，若pijqijˉv≤vmax時(shí)，vij＝pijqijˉv，否則vij＝vmax；tij為經(jīng)過（i，j）弧的時(shí)間，即tij＝lij／vij。

式（2）～式（6）是該模型的約束條件。

2 基本魚群算法

人工魚群算法的主要算子有魚群的覓食、聚群、追尾等行為。算法中涉及的參數(shù)定義為

N:魚群個(gè)體大?。?/p>

｛Xi｝:魚個(gè)體的狀態(tài)位置；

Yi＝f（Xi）:第i條魚當(dāng)前所在位置的食物濃度，Yi為目標(biāo)函數(shù)；

Visual:魚的視野范圍；

delta:魚群的擁擠度；

step:魚的移動(dòng)最大步長(zhǎng)；

n:當(dāng)前魚群覓食行為次數(shù)；

try＿number:覓食行為嘗試的最大次數(shù)；

MAXGEN:最大迭代次數(shù)。

魚群算法是一種高效的智能優(yōu)化算法，主要有魚群初始化、迷失行為、聚群行為、追尾行為、隨機(jī)行為和更新公告板。

1）魚群初始化。魚群中的每一個(gè)個(gè)體均為一組實(shí)數(shù)，是在給定范圍內(nèi)產(chǎn)生的隨機(jī)數(shù)組，即為原問題的初始解。

2）覓食行為。設(shè)人工魚當(dāng)前狀態(tài)為Xi，在其視野范圍內(nèi)隨機(jī)選擇一個(gè)狀態(tài)Xj，在求極大值問題中，Yi＜Yj（極小值問題可與極大值問題互換），則向該方向前進(jìn)一步；反之，重新隨機(jī)選擇狀態(tài)Xj，判斷是否滿足前進(jìn)條件。反復(fù)try＿number次后，若仍不滿足前進(jìn)條件，則隨機(jī)移動(dòng)一步。

3）聚群行為。設(shè)人工魚當(dāng)前狀態(tài)為Xi，探索當(dāng)前領(lǐng)域內(nèi)（即dij＜Visual）的伙伴數(shù)目nf及中心位置Xc，如果有Yc／nf＞deltaYi，表明伙伴中心有較多的食物并且不太擁擠，則朝著伙伴的中心位置方向前進(jìn)一步；否則執(zhí)行覓食行為。

4）追尾行為。設(shè)人工魚當(dāng)前狀態(tài)為Xi，探索當(dāng)前領(lǐng)域內(nèi)（即dij＜Visual）的伙伴數(shù)目nf及伙伴中Yj為最大的伙伴Xj，如果Yj／nf＞deltaYi，表明伙伴Xj的狀態(tài)具有較高的食物濃度并且其周圍不太擁擠，則朝著伙伴Xj的方向前進(jìn)一步；否則執(zhí)行覓食行為。

5）隨機(jī)行為。在視野中隨機(jī)選擇一個(gè)狀態(tài)，然后向該方向移動(dòng)，即Xi的下一個(gè)位置Xi／next為Xi／next＝Xi＋r·Visual，其中，r是［－1，1］區(qū)間的隨機(jī)數(shù)；Visual是人工魚的視野范圍。

6）更新公告板。設(shè)置一個(gè)公告板，用于記錄魚群內(nèi)歷史最佳魚的狀態(tài)Xgbest。各人工魚每迭代一次都檢查自身狀態(tài)，如果f（Xi）＜f（Xgbest）成立，將Xgbest變?yōu)閄i。

3 改進(jìn)的魚群算法

基本魚群算法在解決實(shí)際問題時(shí)還存在不足，如視野范圍的選擇是隨機(jī)的，移動(dòng)步長(zhǎng)也是隨機(jī)的，雖然能在一定程度上擴(kuò)大尋優(yōu)的范圍，但會(huì)使得算法的收斂速度減慢。

3.1 改進(jìn)策略

1）改變尺度步長(zhǎng)。變步長(zhǎng)策略有兩種方法:指數(shù)式衰減變化策略和分段變化策略。指數(shù)式衰減變化策略為step＝step·α，α∈（0，1）為衰減因子，隨迭代進(jìn)程增加減小步長(zhǎng)；分段變化策略是依據(jù)迭代過程，在不同階段設(shè)置不同的步長(zhǎng)，即在算法運(yùn)行初期，設(shè)置較大步長(zhǎng)進(jìn)行計(jì)算，增強(qiáng)全局搜索能力，減少計(jì)算時(shí)間，在算法運(yùn)行后期，設(shè)置較小步長(zhǎng)，增強(qiáng)局部搜索能力和提高解的精度，尋找全局最優(yōu)解。

2）視野范圍的自適應(yīng)變化。采用Visual＝Visual0·n／MAXGEN，其中，n為迭代次數(shù)，MAXGEN為迭代總次數(shù)，該式是視野隨著迭代次數(shù)的增加而逐漸變小。在算法運(yùn)行前期，增大視野范圍，增強(qiáng)算法的全局搜索能力，減少計(jì)算時(shí)間；在算法運(yùn)行后期，視野范圍隨公式計(jì)算減小，覓食行為和隨機(jī)行為增強(qiáng)，則更有利于局部搜索，且提高了解的搜索精度，尋找到全局最優(yōu)解。

3.2 算法步驟

根據(jù)上述模型，文中給出改進(jìn)后的魚群算法流程如圖1所示。

圖1 改進(jìn)魚群算法流程

具體算法如下:

Step 1:初始化。初始化魚群數(shù)目、步長(zhǎng)、視野范圍、擁擠度和試探次數(shù)；

Step 2:計(jì)算目標(biāo)函數(shù)值，找出最小值及其對(duì)應(yīng)的人工魚個(gè)體，并賦給公告板；

Step 3:執(zhí)行魚群的追尾行為和聚群行為算子，得到兩個(gè)不同的解，比較二者的大小，選擇較小者；

Step 4:將追尾行為和聚群行為得到的解與公告板比較，若優(yōu)于公告板的解，則用當(dāng)前的狀態(tài)取代公告板的狀態(tài)；否則轉(zhuǎn)step5；

Step 5:判斷是否達(dá)到最大的迭代次數(shù):是，則輸出最優(yōu)解；否，則進(jìn)行視野范圍、步長(zhǎng)的自適應(yīng)變化操作，轉(zhuǎn)step3。

4 算例分析

假設(shè)某地發(fā)生突發(fā)事件，現(xiàn)要求從物資儲(chǔ)備中心向16個(gè)受災(zāi)地點(diǎn)緊急運(yùn)送救援物資，已知物資儲(chǔ)備中心有200個(gè)單位的應(yīng)急救援物資，每輛車的裝載負(fù)荷為40個(gè)單位，車載速度為50km／h，物資儲(chǔ)備中心和16個(gè)受災(zāi)地點(diǎn)的坐標(biāo)以及各受災(zāi)點(diǎn)的物資需求量數(shù)據(jù)見表1，其中，0代表物資儲(chǔ)備中心，1～16代表16個(gè)受災(zāi)點(diǎn)。

表1 儲(chǔ)備中心和受災(zāi)點(diǎn)坐標(biāo)及物資需求量

根據(jù)模型和算法，設(shè)定魚群最大循環(huán)次數(shù)Cnumber＝200，可視范圍visual＝3，魚群種群數(shù)量為20，擁護(hù)因子為5。利用Matlab軟件，對(duì)算法編程計(jì)算，經(jīng)過200代迭代計(jì)算，得最優(yōu)結(jié)果為:車輛數(shù)為4，總的配送時(shí)間最短且為1.728h以及最優(yōu)選擇路徑如表2所示。

表2 最優(yōu)結(jié)果

最優(yōu)選擇路徑如圖2所示。從圖2可看出，4輛應(yīng)急車輛在應(yīng)急物資儲(chǔ)備中心0點(diǎn)滿載應(yīng)急物資，分別從0點(diǎn)出發(fā)，選擇四條最優(yōu)路徑0－7－11－16－6－0、0－3－4－5－0、0－14－13－2－12－0和0－10－9－8－15－1－0將應(yīng)急救援物資配送到受災(zāi)點(diǎn)，最后4輛車都再次回到0點(diǎn)；并且利用改進(jìn)的人工魚群算法得到總的配送時(shí)間最短且為1.728h，這無(wú)疑對(duì)應(yīng)急救援工作能否順利展開具有重大的實(shí)際意義。

圖2 應(yīng)急車輛路徑選擇

5 結(jié)束語(yǔ)

由于應(yīng)急救援過程中的不確定性因素很多，基于傳統(tǒng)方法的應(yīng)急車輛路徑選擇已不能得到令人滿意的結(jié)果。因此，文中提出一種改進(jìn)的魚群算法來求解應(yīng)急車輛路徑，其結(jié)果能達(dá)到優(yōu)化的目的，并為決策者提供選擇。由于應(yīng)急救援環(huán)境的復(fù)雜性，如何建立更加符合真實(shí)環(huán)境下的應(yīng)急車輛最優(yōu)路徑選擇模型將是下一步研究的內(nèi)容。

［1］范玉軍，王冬冬，孫明明.改進(jìn)的人工魚群算法［J］.重慶師范大學(xué)學(xué)報(bào):自然科學(xué)版，2007，24（3）:23－26.

［2］李妍峰，高自友，李軍.基于實(shí)時(shí)交通信息的城市動(dòng)態(tài)網(wǎng)絡(luò)車輛路徑優(yōu)化問題［J］.系統(tǒng)工程理論與實(shí)踐，2013（7）:1813－1819.

［3］肖力.物流配送車輛路徑優(yōu)化問題的仿真研究［J］.鄂州大學(xué)學(xué)報(bào)，2012（2）:5－8.

［4］柳毅，余福茂，俞武揚(yáng).同時(shí)取送貨車輛路徑問題的改進(jìn)人工魚群算法［J］.杭州電子科技大學(xué)學(xué)報(bào)，2014（3）:34－37.

［5］Dethloff J.Vehicle routing and reverse logistics:the vehicle routing problem with simultaneous delivery and pick up［J］.OR－Spektrum，2001，23（1）:79－96.

［6］Tien J H，Levin S A，Rubenstein D I.Dynamics of fish shoals:identifying key decision rules［J］.Evolutionary E－cology Research，2004，6（4）:555－565.

［7］陳剛，彭永濤.災(zāi)難救援應(yīng)急物資配送問題的研究現(xiàn)狀及發(fā)展方向［J］.鐵道運(yùn)輸與經(jīng)濟(jì)，2012（4）:62－66.

［8］馬繼紅，陳浩如.基于改進(jìn)魚群算法在管道最優(yōu)搶修路徑的研究［J］.管道技術(shù)與設(shè)備，2014（1）:4－6.

［9］王培崇，雷鳳君，錢旭.改進(jìn)人工魚群算法及其收斂性分析［J］.科學(xué)技術(shù)與工程，2013（3）:616－620.

［10］Yazdani D，Toosi A N，MEYVODJ M R.Fuzzy adaptive artificial fish swarm algorithm.Proc of the 23rd Australasian Joint conference on Artificial Intelligence，2010:334－343.