朱顥

（湖州職業(yè)技術(shù)學(xué)院，浙江 湖州 313000）

人工魚群算法在模糊VRP問題中的應(yīng)用

朱顥

（湖州職業(yè)技術(shù)學(xué)院，浙江 湖州 313000）

針對一類同時帶模糊旅行時間、卸貨時間和模糊需求的VRP問題，建立了以可信性測度為基礎(chǔ)的模糊機會約束規(guī)劃模型；然后設(shè)計了基于模糊模擬、神經(jīng)網(wǎng)絡(luò)和人工魚群算法的混合智能算法，在人工魚群算法尋優(yōu)過程中，針對問題設(shè)計了專門的人工魚修復(fù)策略、行為策略和尋優(yōu)策略；最后通過仿真實驗證明，該算法對解決此類模糊VRP問題是行之有效的。

模糊車輛路徑問題；人工魚群算法；模糊模擬；神經(jīng)網(wǎng)絡(luò)

1 引言

車輛路徑問題作為一類經(jīng)典的組合優(yōu)化問題，也是NP難問題，長期以來都是科學(xué)界的研究熱點。模糊車輛路徑問題作為其中的一個分支，其含義為：在外部環(huán)境（如交通狀況、客戶需求量、車輛旅行時間等）無法精確預(yù)測的情況下，如何合理地為每個客戶分配車輛，安排車輛的行駛路線和出發(fā)時間，以使得某些指標（如總費用、總行駛距離等）最優(yōu)。鑒于此類問題，Yanfang Ma等[1]討論了時間窗為模糊隨機變量的車輛路徑問題，提出了基于粒子群優(yōu)化的云理論。Lian Xue等[2]針對帶模糊需求的車輛路徑問題，提出了基于模糊模擬和差分進化算法的混合智能算法。Mehdi Adelzadeh[3]等考慮了一類帶模糊時間窗的多車型、多車場車輛路徑問題，并提出了一種啟發(fā)式算法。Ghannadpour等[4]針對一類帶模糊旅行時間和客戶滿意度的多目標動態(tài)車輛路徑問題，提出了基于遺傳算法的動態(tài)解決策略。Kuo,R.J等[5]以帶模糊需求的車輛路徑問題為對象，提出了一種基于粒子群算法和遺傳算法的混合算法，在粒子群算法中加入交叉和變異操作。Cao Erbao等[6]探討了一類帶模糊需求的開放式車輛路徑問題，運用隨機模擬和改進的差分進化算法進行了求解。Chang Shi Liu等[7]針對帶模糊需求的車輛路徑問題，提出了一種混合元啟發(fā)式算法。Lian Xue等[8]針對同樣的問題，利用模糊模擬和差分進化算法進行了求解。Peng Yang等[9]則運用粒子群算法進行了求解。

國內(nèi)文獻中，祝崇雋等[10]針對帶模糊需求的VRP問題，提出了基于可能性分布和基于需求上界的2-OPT算法。張建勇等則先后提出了一種Sweeping啟發(fā)式算法[11]和基于模糊模擬的混合遺傳算法[12]，針對具有模糊旅行時間的VRP問題，用模糊邏輯和遺傳算法相結(jié)合進行了求解[13]，并針對帶模糊預(yù)約時間的VRP問題，提出了基于“推一碰一擲”的改進遺傳算法[14]。曹二保等[15]針對帶模糊需求的車輛路徑問題，用基于隨機模擬的差分進化算法進行優(yōu)化。陳寶文等[16]針對帶模糊需求的車輛路徑問題，提出了基于多蟻群協(xié)作的改進蟻群算法。崔雪立等[17]針對具有模糊預(yù)約時間的車輛路徑問題，利用螞蟻算法進行求解。王君等[18]針對具有模糊需求的帶時間窗的車輛路徑問題，設(shè)計了嵌入模糊模擬的改進非支配排序混合遺傳算法。王連鋒等[19]考慮帶硬時間窗車輛路徑問題的多重模糊性質(zhì)，建立了多目標模糊期望值模型，提出了一種自適應(yīng)粒子群算法。

從有關(guān)模糊車輛路徑問題的文獻看，問題主要集中于帶模糊需求量和模糊時間窗、模糊預(yù)約時間等幾種類型上，對于帶模糊旅行時間的文獻較少，只有文獻[4]和文獻[13]涉及，同時具有模糊需求量、模糊旅行時間、模糊卸貨時間的研究文獻更少。優(yōu)化算法主要集中于各種啟發(fā)式算法[3,7，10,11]、蟻群算法[16，17]、粒子群算法[1，5，9，19]、遺傳算法[4,12,13,14，18]、差分進化算法[2,6,8,15]等幾類算法上。

人工魚群算法作為一種新型的智能優(yōu)化算法，由我國學(xué)者李曉磊[20]提出，該算法通過模擬魚群的覓食、聚群、追尾、隨機游動等行為，能有效地在問題的解空間進行搜索，尋找問題的最優(yōu)解。目前，人工魚群算法在車輛路徑問題中已有一定的應(yīng)用，如覃磊等[21]利用一種基于三維粒子編碼的改進人工魚群算法，對確定性VRP問題進行了研究。王培崇等[22]針對確定性的VRP問題，提出了將魚群算法和遺傳算法相混合的策略。柳毅等[23]對帶模糊需求的可回程車輛路徑問題，提出了改進的人工魚群算法。郭海湘等[24]針對煤礦物資行業(yè)中的配送車輛路徑問題，用人工魚群算法進行了求解。雖然人工魚群算法在車輛路徑問題中得到了一定的應(yīng)用，但是從相關(guān)文獻來看，主要基于確定性的車輛路徑問題，該算法在同時帶模糊需求和模糊時間的車輛路徑問題的應(yīng)用還不多見。

本文針對同時帶模糊需求量、模糊旅行時間、模糊卸貨時間的車輛路徑問題，建立相應(yīng)的模糊機會約束規(guī)劃模型；設(shè)計了基于模糊模擬、神經(jīng)網(wǎng)絡(luò)和人工魚群算法的混合智能算法：首先通過模糊模擬產(chǎn)生樣本數(shù)據(jù)，然后將樣本數(shù)據(jù)作為一個BP神經(jīng)網(wǎng)絡(luò)的輸入和期望輸出，對神經(jīng)網(wǎng)絡(luò)進行訓(xùn)練，使得該神經(jīng)網(wǎng)絡(luò)能逼近模型中的兩個可信性函數(shù)；最后利用訓(xùn)練好的神經(jīng)網(wǎng)絡(luò)計算任意一個問題解所對應(yīng)的兩個可信性函數(shù)的值，以此判斷該解是否滿足約束條件，并利用人工魚群算法進行尋優(yōu)，在此階段，設(shè)計了適合該問題的人工魚修復(fù)策略、移動策略和尋優(yōu)策略。

2 帶模糊時間和模糊需求量的VRP模型

帶模糊時間和模糊需求量的VRP問題可以被描述為：一個配送中心（用0表示，以下簡稱為“車場”）為n個客戶（i=1,2,...,n）提供送貨服務(wù)；車場共擁有m輛車（k=1,2,...,m），每輛車的額定載重量為Qk，從車場出發(fā)，完成一系列客戶的送貨后回到車場；每個客戶i只能由一輛車提供服務(wù)，其需求量qi為三角模糊數(shù)(qi1,qi2,qi3)；每個客戶i均有一個服務(wù)時間窗口[ai,bi]，送貨盡可能在此時間范圍內(nèi)進行；客戶i和 j的距離為Dij（i,j=0,1,2,...,n）；車輛從客戶i到客戶 j的旅行時間Tij不確定，用三角模糊數(shù)(Tij1,Tij2,Tij3)表示；車輛在客戶i處的卸貨時間Si不確定，用三角模糊數(shù)(Si1,Si2,Si3)表示；fi為車輛抵達客戶i的時間，若車輛在客戶i的時間窗口[ai,bi]之前抵達，則須等待至?xí)r間ai處才能開始卸貨，若在[ai,bi]之間到達，則立即卸貨。該問題的實質(zhì)是在滿足一系列約束（如車輛裝載能力約束、客戶需求時間窗口約束等）的條件下，為各輛車分配相應(yīng)的客戶及安排送貨順序，并確定各車輛從車場出發(fā)的時間，以使得某些指標最優(yōu)（如距離最短、成本最低等）。

問題的決策變量為x,y,t，其含義如下[25]：

x=(x1,x2,...,xn)，表示n個不同的客戶編號的一個排列，對于所有的 i≠j，有 1≤xi≤n，xi≠xj, i,j=1,2,...,n。

y=(y1,y2,...,ym-1)，表示m-1個位于區(qū)間[0,n]內(nèi)的整數(shù)，且 y0=0≤y1≤y2≤…≤ym-1≤n=ym，其含義如下：

對于每個k=1,2,...,m，yk-yk-1表示車輛k服務(wù)的客戶數(shù)量。若yk=yk-1，車輛k不運行；若yk>yk-1，則表明車輛k服務(wù)的客戶數(shù)為yk-yk-1，服務(wù)的客戶按順序從 xy(k-1)+1開始，到 xyk為止，其行駛路線為：車場0→客戶xy(k-1)+1→客戶 xy(k-1)+2→…→客戶 xyk-1→客戶 xyk→車場0 t=(t1,t2,...,tm)，tk代表車輛 k從車場出發(fā)的時間，k=1,2...,m。

對于每個x,y,t表示的送貨安排（問題解），可知：若車輛k已經(jīng)投入運行，則其到達第1個客戶的時間為：

車輛k運行的路程為：

綜上所述，可以建立如下的模糊機會約束模型：

模型中目標（4）表示最小化所有車輛的總行駛路程；約束（5）為車輛載重能力約束，表示每一輛車k所裝載貨運量不超過其額定載重量的可信性應(yīng)該不小于主觀給定值α；約束（6）為服務(wù)時間約束，表示車輛抵達每個客戶i的時間 fi處于時間窗口[ai,bi]內(nèi)的可信性應(yīng)該不小于主觀給定值 β；約束（7）、（8）和（9）分別能確保每個客戶只由一輛車提供服務(wù)，每輛車最多只被使用一次。

3 算法介紹

3.1 問題的編碼及解碼

針對本模型，以(x,y,t)的形式進行整數(shù)和實數(shù)的混合編碼，該向量長度為n+2m-1，其中：x部分和y部分的含義如前所述，t部分為m個實數(shù)，代表m輛車的出發(fā)時間，可以限定在區(qū)間內(nèi)。采用此編碼方式肯定能滿足約束條件（7）-（9），按照如下方式進行解碼：先根據(jù)y部分的元素判斷每輛車是否執(zhí)行任務(wù)，對執(zhí)行任務(wù)的車輛，記錄每輛車服務(wù)的客戶數(shù)量number_custom和對應(yīng)的客戶編號code。

為更好地解釋解碼規(guī)則，給出一個由10個客戶，4輛車構(gòu)成的問題，其編碼長度為17：某一個解如下，[1,2, 4,3,6,5,7,8,9,10,1,4,8,8.004 9,8.069 4,8.101 4,8.099 4]。對此編碼，前10個整數(shù)元素代表10個客戶的重排；第11-13位的元素為1,4,8：表示第一輛車服務(wù)的客戶數(shù)量為1，對應(yīng)客戶編號為1，第二輛車服務(wù)的客戶數(shù)量為3，對應(yīng)客戶編號依次為2,4,3，第三輛車服務(wù)的客戶數(shù)量為4，對應(yīng)客戶編號依次為6,5,7,8；第四輛車服務(wù)的客戶數(shù)量為2，對應(yīng)客戶編號依次為9,10；第14-17位的元素分別表示四輛車從車場出發(fā)的時間。四輛車均執(zhí)行任務(wù)，每 輛 車 的客戶服務(wù)數(shù)量為 number_custom= [1 3 4 2]，對應(yīng)的客戶編號code由一個m×n的矩陣表示，如圖1所示。

圖1 客戶編號code矩陣

矩陣code具有如下特點：第一行表示第一輛車服務(wù)的客戶，第二行表示第二輛車服務(wù)的客戶，以此類推；所有非0的元素均表示客戶的編號，必須出現(xiàn)且只出現(xiàn)一次，且均排在0元素（稱為“偽元素”）之前；所有為0的元素?zé)o任何意義，表示此位置無任務(wù)安排，不同于前面所述的車場編號0；若某一行元素均為0，則表示該車輛沒有行駛。反過來，根據(jù)任意給定的符合上述條件的矩陣code，均可以通過倒推獲取(x,y,t)中x部分和y部分的值，在此稱為“逆映射”。

3.2 模糊變量的處理

由于本文中客戶的貨物需求量、車輛旅行時間、車輛卸貨時間均為三角模糊數(shù)，傳統(tǒng)的方法已經(jīng)無法解決約束條件（5）和（6），需要采用模糊模擬的方法。首先考慮隨機生成 sample_num個輸入樣本 solution[p]，p=1,2,...,sample_num，然后對樣本進行解碼，記錄每輛車服務(wù)的客戶數(shù)量number_custom和對應(yīng)的客戶編號code，得到該車輛的行駛路線。

對于每個輸入樣本solution[p]，采用如下方法進行模糊模擬：

Step1：對于每輛執(zhí)行任務(wù)的車輛k（1≤k≤m），首先判斷該車是否執(zhí)行任務(wù)，若未執(zhí)行任務(wù)，則跳過至下一輛車，否則，得到其行駛路線為：

g,其中Pos為模糊可能性測度。

Step2：重復(fù) Step1共 mod_ti mes次，可獲得mod_ti mes個的值和的值，g=1,2,...mod_ti mes。

Step3：計算d1和d2。

d1即為的估計值,d2即為Cr{ai≤fi(x,y,t)≤bi,i=1,2,…,n}的估計值。

3.3 用遺傳算法訓(xùn)練神經(jīng)網(wǎng)絡(luò)

針對前述車輛能力約束和需求時間窗口約束，將sample_num個輸入樣本solution[p]（p=1,2,..., sample_num）的編碼經(jīng)歸一化處理后，作為具有三層感知結(jié)構(gòu)的BP神經(jīng)網(wǎng)絡(luò)的輸入數(shù)據(jù)，3.2節(jié)模糊模擬得到的數(shù)據(jù)作為BP神經(jīng)網(wǎng)絡(luò)的期望輸出，利用遺傳算法訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)，使得該BP神經(jīng)網(wǎng)絡(luò)能逼近公式（5）和（6）中的兩個可信性函數(shù)。

3.3.1 神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)和參數(shù)的確定。假設(shè)該BP網(wǎng)絡(luò)的輸入層節(jié)點數(shù)為M，隱層節(jié)點數(shù)為N，輸出層節(jié)點數(shù)為L，則對于每個solution[p]，將其每個基因作為輸入層節(jié)點，節(jié)點數(shù)M為solution[p]的編碼長度；輸出層節(jié)點數(shù)L=2，分別對應(yīng)公式（5）和（6）中的兩個可信性函數(shù)；隱層節(jié)點數(shù)N經(jīng)過多次實驗后確定，節(jié)點數(shù)太少會使BP神經(jīng)網(wǎng)絡(luò)的逼近能力不夠，而太多會增加網(wǎng)絡(luò)訓(xùn)練的時間。

由于神經(jīng)網(wǎng)絡(luò)的輸入層節(jié)點為solution[p]中的基因(x,y,t)，隱層節(jié)點閾值可考慮為x、y、t三部分基因之和的一半，由于x部分各基因之和始終不變，y、t部分的基因始終在變化，根據(jù)隨機生成的輸入樣本中y、t部分的情況，考慮取平均值。因此可將隱層節(jié)點閾值初步設(shè)為：

輸出層節(jié)點閾值設(shè)為：

3.3.2 遺傳算法的編碼及解碼。設(shè)染色體種群集合為title_pop，種群規(guī)模為popsize。本節(jié)中染色體為神經(jīng)網(wǎng)絡(luò)的權(quán)值，如圖2所示：染色體總長度為M×N+2×N，前M×N個基因為輸入層節(jié)點i和隱層節(jié)點j之間的權(quán)值，表示為wij∈[0,1]；后2×N個基因為隱層節(jié)點 j和輸出層2個節(jié)點之間的權(quán)值，表示為。對于每個權(quán)值染色體，采用文獻[26]的方法計算所有輸入樣本訓(xùn)練后的總誤差Error。

圖2 BP網(wǎng)絡(luò)權(quán)值結(jié)構(gòu)

3.3.3 遺傳算法的適應(yīng)度。神經(jīng)網(wǎng)絡(luò)的訓(xùn)練目標為極小化所有訓(xùn)練樣本的總誤差Error，本文采用基于序的評價函數(shù)，見式（14）：

其中a'為一較小的參數(shù)。

3.4 人工魚群算法優(yōu)化

隨機產(chǎn)生以 (x,y,t)表示的人工魚種群fi sh[p]，p=1,2,...,popsize_fi sh，種群規(guī)模為popsize_fi sh，然后利用訓(xùn)練好的神經(jīng)網(wǎng)絡(luò)計算出Qk,k=1,2,...,m}和Cr{ai≤fi(x,y,t)≤bi,i=1,2,…,n}的值，判斷該人工魚是否可行，若不滿足約束條件（5）和（6），則采用如下3.4.1的方式進行修復(fù)。

3.4.1 人工魚的修復(fù)策略。首先需要對不可行的人工魚 fi sh[p]進行解碼，得到其對應(yīng)的矩陣codep，然后針對兩個能力約束進行修正：

（1）若不滿足車輛載重能力約束，表明有車輛服務(wù)的客戶過多，先從矩陣codep中選擇服務(wù)客戶數(shù)最多的那輛車（如圖3為第3輛車）開始調(diào)整，選擇最末尾的客戶（圖中客戶編號為8），將其分配給已執(zhí)行任務(wù)且服務(wù)客戶數(shù)最少的那輛車（圖中為第1輛車），該客戶編號插入已有客戶最后面（客戶1后面），此方法表示在幾條子路徑之間進行客戶數(shù)量的增減，然后逆映射操作，判斷是否滿足該約束，否則重復(fù)該步驟直到滿足約束條件為止。

圖3 客戶編號codep子線路間調(diào)整

（2）若滿足車輛載重能力約束但不滿足服務(wù)時間窗口約束，則表明每輛車裝載能力滿足要求，各條子路徑客戶分配沒有問題，但是子路徑內(nèi)的客戶順序以及車輛的出發(fā)時間需要調(diào)整。由此，可以依照客戶數(shù)量多少依次在每條子路徑中隨機交換兩個子路徑內(nèi)的客戶位置（如圖4中將第3輛車所構(gòu)成的子線路內(nèi)客戶7和8交換位置），然后逆映射操作，判斷是否滿足該約束，若所有的子路徑均交換完畢，還不能滿足約束條件，則對車輛出發(fā)時間t進行變異，隨機生成一個t'替換t直至滿足約束條件。

圖4 客戶編號codep子線路內(nèi)調(diào)整

3.4.2 人工魚的距離。人工魚對外界的感知靠視覺來實現(xiàn)，只有視覺范圍內(nèi)的環(huán)境信息才能被人工魚所接收，因此如何設(shè)計兩條人工魚的距離對算法來說就顯得尤為重要，本文擬借鑒文獻[24]所述的方法來定義兩條人工魚之間的距離及中心魚。

不失一般性，任意兩條由(x1,y1,t1)和(x2,y2,t2)表示的人工魚 fi sh[1]和 fi sh[2]，均可以經(jīng)過解碼得到矩陣code1和code2，用符號eki表示兩個矩陣第k行和第i列位置客戶編號的相似度，如果相同，則eki=0，否則eki=1，則兩條人工魚的距離表示為公式（15）。

3.4.3 人工魚的適應(yīng)度函數(shù)。由于該模型需要將目標函數(shù)極小化，對人工魚進行解碼后，根據(jù)式（4）求得目標函數(shù)值Z，令人工魚的適應(yīng)度函數(shù)為：

3.4.4 人工魚的步長step。根據(jù)人工魚群算法的原理，當(dāng)前人工魚 fi sh在執(zhí)行聚群行為和追尾行為時，若發(fā)現(xiàn)中心魚或最優(yōu)伙伴魚較自身狀態(tài)更優(yōu)（食物更濃），且周圍不太擁擠時，fi sh朝中心魚或最優(yōu)伙伴魚的方向前進一步達到狀態(tài) fi shnext。以聚群行為為例，應(yīng)同時滿足式（17）和（18）。

且應(yīng)該保證 fi shnext較 fi sh更優(yōu)，否則聚群行為沒有意義，這一思想在連續(xù)空間中容易實現(xiàn)。在VRP這一類的組合優(yōu)化問題中，解的空間是離散的，不一定存在一個合適的狀態(tài) fi shnext滿足以上特征，即使搜尋到了符合這樣特征的一個狀態(tài) fi shnext，該人工魚不一定是可行的，還需要按照3.4.1的方式再次進行修復(fù)，而修復(fù)的過程還會再次改變它們的距離，導(dǎo)致新狀態(tài) fi shnext有可能處于當(dāng)前人工魚 fi sh的視野之外。因此，對于本文的人工魚群算法，若符合聚群行為和追尾行為的條件，則讓當(dāng)前人工魚直接跳躍到中心魚或最優(yōu)伙伴魚上，一方面節(jié)省了算法尋優(yōu)的時間，另一方面避免了過多的修復(fù)，此時，其步長step其實是根據(jù)自身情況決定的，在執(zhí)行覓食行為時同樣如此。

3.4.5 人工魚的聚群行為

（1）確定人工魚視野內(nèi)伙伴群的中心魚位置。對于中心魚的確立，本部分采用逆向的方式，先確定可能的中心魚 fi shcenter所對應(yīng)的矩陣codecenter，然后“逆映射”可得到中心魚 fi shcenter編碼方式(xcenter,ycenter,tcenter)中 xcenter部分和ycenter部分的值。

Step1：對伙伴群 partner內(nèi)的每條人工魚 fi sh[j]，先通過解碼分別獲得矩陣codej；

Step2：令k=1,2,...,m和i=1,2,...,n，統(tǒng)計客戶編號1,2,…,n及偽元素0在每個矩陣code的第k行和第i列位置上出現(xiàn)的次數(shù)，取出出現(xiàn)次數(shù)最多的那個客戶編號（包括偽元素0）填入 codecenter[k][i]，并用另一個矩陣max_numcenter[k][i]記錄該客戶編號（包括偽元素0）在該位置出現(xiàn)的次數(shù)。

通過Step1和Step2可以初步得到一個矩陣codecenter，但該矩陣可能不符合3.1節(jié)中所描述的特征：①某個客戶編號出現(xiàn)2次及以上；②某個客戶編號未曾出現(xiàn)；③某個客戶編號前面存在偽元素0。對于以上可能出現(xiàn)的情況，采用如下方式進行修正：

首先設(shè)置存儲器storage={1,2,…,n}，并將已經(jīng)安排在codecenter中的客戶編號清除。對于codecenter中出現(xiàn)的情況①，先比較相應(yīng)位置上該編號分別出現(xiàn)的次數(shù)，保留max_numcenter[k][i]取值大的位置（最大限度地保留了伙伴魚群的共性），若出現(xiàn)的次數(shù)一樣，則優(yōu)先保留最左邊的位置（這樣減少了矩陣codecenter中偽元素0在客戶編號1,2,…,n前出現(xiàn)的可能性），其余位置的編號暫時用偽元素0代替,并記錄其橫坐標k和縱坐標i，此方法解決了問題①；然后重新掃描codecenter，查找排在客戶編號前面的偽元素0，從存儲器中隨機安排一個尚未插入的客戶編號，重復(fù)操作直到問題③解決，若所有客戶均安排完畢，仍然存在問題③的現(xiàn)象，則將本行后面的非0客戶編號依次前移。若上述問題①和③解決，但是還有剩余客戶編號未安排，則隨機安排在某一行最后非0的客戶編號后，此方法解決了問題②。

Step3：在得到矩陣codecenter后進行逆映射操作，可得到中心魚 fi shcenter編碼方式(xcenter,ycenter,tcenter)中 xcenter部分和 ycenter部分的值。至于 tcenter的值，可以取伙伴群partner內(nèi)的每條人工魚 fi sh[j]中t部分的平均值。

Step4：檢驗該中心魚 fi shcenter是否可行，將訓(xùn)練好的神經(jīng)網(wǎng)絡(luò)嵌入，計算該VRP模型中兩個可信性函數(shù)的值，若不滿足約束條件（5）和（6），則采用3.4.1策略進行修復(fù)，否則說明可行。

（2）執(zhí)行聚群行為準則。當(dāng)中心魚 fi shcenter優(yōu)于當(dāng)前人工魚 fi sh[p]，且 fi shcenter的周圍不太擁擠時（判斷準則見式（23）），則讓 fi sh[p]直接跳向 fi shcenter（當(dāng)然，此處不是直接改變 fi sh[p]的值，而是將 fi shcenter先作為fi sh[p]的下一代候選狀態(tài)之一儲存起來，以備和其他行為執(zhí)行結(jié)果進行比較，再來決定下一代迭代時fi sh[p]的狀態(tài)），否則不執(zhí)行聚群行為。

式（19）中Fcenter為 fi shcenter的適應(yīng)度，n_f為伙伴群內(nèi)人工魚數(shù)量，δ為擁擠度因子，F(xiàn)p為 fi sh[p]的適應(yīng)度。

3.4.6 人工魚的追尾行為。在 fi sh[p]視野范圍visual內(nèi)，搜尋適應(yīng)度最大的其他伙伴魚，令其為 fi shbest_parter，若其位置較 fi sh[p]更優(yōu)，且周圍不太擁擠（判斷準則見式（20）），則讓 fi sh[p]直接跳向 fi shbest_parter（同樣將fi shbest_parter作為 fi sh[p]的下一代候選狀態(tài)之一儲存），否則不執(zhí)行追尾行為。

式（20）中Fbest_parter為伙伴群內(nèi)最優(yōu)人工魚的適應(yīng)度，其他符號同上。

3.4.7 人工魚的覓食行為。在 fi sh[p]視野范圍visual內(nèi)，隨機產(chǎn)生一條新的人工魚 fi shnew（假設(shè)其對應(yīng)的矩陣為codenew），方法如下：

（1）以 fi sh[p]對應(yīng)的矩陣codep為基礎(chǔ)，從該矩陣編號1,2,…,n中隨機選擇至少n-visual個編號（其余編號組成集合identifier_no），將其插入另一個矩陣codenew相同的位置，這樣可以保證 fi shnew與 fi sh[p]距離在visual內(nèi)，其他位置暫時用偽元素0代替。

（2）對codenew進行掃描，若某客戶的前面有偽元素0，從identifier_no中隨機選擇客戶編號，替代該偽元素0，直至無此現(xiàn)象；若codenew中已有的客戶前面已經(jīng)無偽元素0，而identifier_no中仍然有客戶未安排，則將identifier_no中客戶隨機安排在一輛車的末尾。

（3）逆映射操作，得到 fi shnew編碼結(jié)構(gòu)中的xnew部分和ynew部分，tnew部分的取值可以隨機生成。

（4）檢驗人工魚 fi shnew是否可行，若該人工魚不可行，需要進行修復(fù)，修復(fù)時優(yōu)先考慮在集合identifier_no中的元素間進行位置的交換以及對tnew部分的取值重新隨機生成，以保證 fi shnew依然在 fi sh[p]視野范圍visual內(nèi)。

（5）若 fi shnew優(yōu)于 fi sh[p]，則讓 fi sh[p]直接跳向fi shnew（將 fi shnew作為 fi sh[p]的下一代候選狀態(tài)之一儲存）；若 fi shnew的狀態(tài)較 fi sh[p]差，則重新嘗試，反復(fù)嘗試tr y_number后，仍不能獲得一個更好的狀態(tài)，則放棄覓食行為。

3.4.8 人工魚的隨機移動行為。隨機移動行為是覓食行為的缺省行為。在人工魚 fi sh[p]視野范圍visual內(nèi)，隨機產(chǎn)生一條新的人工魚 fi shrandom（同3.4.7所述的方法），并檢驗對該人工魚是否可行，若可行則直接讓fi sh[p]跳向 fi shrandom。

3.4.9 人工魚的行為策略。人工魚的行為包括聚群、追尾、覓食、隨機移動四種，每條人工魚究竟采取何種策略，關(guān)系到算法的搜索空間和收斂速度。本文擬采用并行的搜索策略，先判斷聚群、追尾、覓食能否執(zhí)行，若能執(zhí)行，選擇最優(yōu)的行為，若三種均不能執(zhí)行，則執(zhí)行隨機移動行為。具體如下：

對每條人工魚 fi sh[p]，首先判斷是否滿足執(zhí)行聚群、追尾、覓食的判斷準則，若滿足則先分別嘗試執(zhí)行聚群行為、追尾行為、覓食行為，并比較三種行為執(zhí)行后得到的新的人工魚fi shcenter、fi shbest_parter、fi shnew的適應(yīng)度，取適應(yīng)度最高的狀態(tài)作為 fi sh[p]的下一代。若三種行為均不滿足判斷準則，則執(zhí)行隨機移動行為，將 fi shrandom作為 fi sh[p]的下一代。

在該算法尋優(yōu)的過程中，為了避免算法陷入局部最優(yōu)，令變量no_update=0，用來對公告板的更新情況進行記錄，若某一次迭代完后公告板進行了更新，則令no_update=0，否則令no_update自動加1，若公告板連續(xù)若干代（用no_update_ti mes表示）無法更新，即 no_update=no_update_ ti mes，則將人工魚種群中適應(yīng)度最差的10%個體進行替換，用隨機產(chǎn)生的人工魚替代，以擴大問題的搜索空間，希望有所發(fā)現(xiàn)，具體的尋優(yōu)策略如圖5所示。

圖5 人工魚群算法尋優(yōu)策略

4 仿真實例

本文擬以包含20個客戶、4輛車的VRP問題為例進行仿真，部分數(shù)據(jù)如車場與客戶及客戶之間的行駛距離、行駛時間、各客戶的需求時間窗口、各車輛的運載能力均來源于文獻[25]，由于篇幅所限，在此不一一列出，其他數(shù)據(jù)如客戶對貨物的模糊需求量、車輛在客戶處的模糊卸貨時間基于假設(shè)，具體數(shù)據(jù)見表1。實例中的置信水平α和β均為0.6。

（1）實驗結(jié)果。針對本文提出的VRP問題，利用Matlab進行仿真實驗，仿真參數(shù)如下：模糊模擬輸入樣本 個 數(shù) sample_num=400，模 糊 模 擬 次 數(shù)mod_ti mes=5 000；神經(jīng)網(wǎng)絡(luò)權(quán)值染色體種群數(shù)量popsize=100，迭代次數(shù) AG_iter=2 000，交叉概率pos_cross=0.8，變異概率 pos_mu=0.5；人工魚群規(guī)模popsize_fi sh=50，人工魚視野范圍visual=16，擁擠度因子δ=0.1，覓食行為反復(fù)嘗試次數(shù)tr y_number=10，最優(yōu)解無更新允許次數(shù)no_update_ti mes=10，人工魚群最大迭代次數(shù)max_iter=500。

表1 各客戶的模糊需求、模糊卸貨時間

經(jīng)過Matlab 7.0編程，得到問題的最優(yōu)解為：

該最優(yōu)解滿足車輛能力約束和需求時間窗口約束條件，經(jīng)過解碼分析，共有三輛車執(zhí)行任務(wù)（分別為第1、2、4輛車），其出發(fā)時間為8.332 6時、8.222 4時和8.248 3時。

對應(yīng)的客戶編號如下：

每輛車的客戶服務(wù)數(shù)量為 number_custom= [7 7 0 6]，總行駛里程為740。

圖6為經(jīng)過模糊模擬5 000次，訓(xùn)練神經(jīng)網(wǎng)絡(luò)2 000次，人工魚群算法500次迭代后總行駛里程的迭代示意圖。

圖6 總行駛里程迭代結(jié)果

（2）人工魚群算法與其他算法的比較。針對同樣的仿真數(shù)據(jù)，基于同樣的種群編碼格式，以同樣的神經(jīng)網(wǎng)絡(luò)最優(yōu)權(quán)值，在種群規(guī)模均為50，總迭代次數(shù)均為500的情況下，以本文所提算法為基礎(chǔ)隨機運行10次，與傳統(tǒng)的遺傳算法和模擬退火算法運行的結(jié)果進行比較，結(jié)果見表2。

表2 本文算法和遺傳算法、模擬退火算法的比較

實驗結(jié)果表明，在種群規(guī)模相同且總迭代次數(shù)一樣的情況下，本文算法的最優(yōu)值、平均值和均方差均要優(yōu)于遺傳算法和模擬退火算法，算法較遺傳算法和模擬退火算法更穩(wěn)定，且獲得最優(yōu)值所需的迭代次數(shù)較少。

5 結(jié)束語

本文考慮了一類車輛行駛時間、卸貨時間和客戶的需求量均為模糊變量的VRP問題，針對該問題建立了基于可信性測度的模糊機會約束規(guī)劃模型，然后針對該問題提出了基于人工魚群算法的智能優(yōu)化算法，通過仿真實驗證明，該算法對于解決帶模糊車輛行駛時間、模糊卸貨時間和模糊需求量的VRP問題是行之有效的。

[1]Yan fang Ma,Jiu ping Xu.A cloud theory-based particle swarm optimization for multiple decision maker vehicle routing problems with fuzzy random time windows[J].Engineering optimization,2015,47(6):825-842.

[2]Lian Xue.Fuzzy simulation on the vehicle routing problem[J]. Information technology journal,2013,12(21):6 098-6 102.

[3]Mehdi Adelzadeh,Vahid Mahdavi Asl,Mehdi Koosha.A mathematical model and a solving procedure for multi-depot vehicle routing problem with fuzzy time window and heterogeneous vehicle[J].The international journal of advanced manufacturing technology,2014,5(8):793-802.

[4]Ghannadpour S F,Noori S,Tavakkoli-Moghaddam R.Multiobjective dynamic vehicle routing problem with fuzzy travel times and customers’satisfaction in supply chain management[J]. IEEE transactions on engineering management,2013,60(4): 777-790.

[5]Kuo R J,Zulvia F E,Suryadi K.Hybrid particle swarm optimization with genetic algorithm for solving capacitated vehicle routing problem with fuzzy demand-A case study on garbage collection system[J].Applied mathematics and computation,2012,219(5):2 574-2 588.

[6]Cao Erbao.The open vehicle routing problem with fuzzy demands[J].Expert systems with application,2010,37(3):2 405-2 411.

[7]Chang Shi Liu,Shu Jin Zhu.Hybrid meta-heuristic approaches for vehicle routing Problem with fuzzy demands[J].Key engineering materials,2010,(439):241-246. [8]Lian Xue,Xiaoxia Dai.Research on the vehicle routing problem with fuzzy demands[A].International conference on computer-aided material and engineering[C].2011.

[9]Peng Yang,Qian Ye-mei.Vehicle routing problem with fuzzy demands and the particle swarm optimization solution[A].International conference on management and service science[C].2010.

[10]祝崇雋,劉民,吳澄,等.針對模糊需求的VRP的兩種2—OPT算法[J].電子學(xué)報,2001,(8):1-3.

[11]張建勇,李軍.模糊需求VRP的一種Sweeping啟發(fā)式算法[J].中國管理科學(xué),2007,15(10):71-75.

[12]張建勇,李軍.模糊車輛路徑問題的一種混合遺傳算法[J].管理工程學(xué)報,2005,19(2):23-26.

[13]張建勇,李軍.具有模糊旅行時間的VRP的一種混合遺傳算法[J].管理工程學(xué)報,2006,20(4):13-16.

[14]張建勇，李軍，郭耀煌.具有模糊預(yù)約時間的VRP混合遺傳算法[J].管理科學(xué)學(xué)報,2005,8(6):64-70.

[15]曹二保,賴明勇,李董輝.基于混合差分進化算法的模糊需求車輛路徑問題[J].系統(tǒng)工程理論與實踐,2009,29(2):106-113.

[16]陳寶文,宋申民,陳興林.模糊需求車輛路徑問題及其啟發(fā)式蟻群算法[J].計算機應(yīng)用,2006,26(11):2 639-2 642.

[17]崔雪立,朱道利,馬良.模糊約定時間車輛路徑問題及其螞蟻算法求解[J].系統(tǒng)工程學(xué)報,2009,24(8):489-493.

[18]王君,李波.基于多目標優(yōu)化的模糊需求VRPTW動態(tài)管理[J].管理學(xué)報,2013,(2):238-243.

[19]王連鋒,宋建社,曹繼平等.帶硬時間窗模糊車輛路徑問題的多目標優(yōu)化[J].計算機工程,2013,(4)9-13.

[20]李曉磊.一種新型的智能優(yōu)化方法—人工魚群算法[D].杭州:浙江大學(xué),2003.

[21]覃磊,周康.基于改進的人工魚群算法的車輛優(yōu)化調(diào)度[J].微電子學(xué)與計算機,2015,32(6):50-53.

[22]王培崇,錢旭,周玉.求解VRP問題的混合魚群遺傳優(yōu)化算法[J].計算機工程與應(yīng)用,2009,45(24):201-203.

[23]柳毅.求解模糊需求可回程取貨車輛路徑問題的改進人工魚群算法[J].模式識別與人工智能,2010,23(8):560-564.

[24]郭海湘,劉嫣然,等.煤礦物資配送車輛路徑問題的人工魚群算法[J].系統(tǒng)管理學(xué)報，2012,21(5):341-351.

[25]劉寶碇,趙瑞清,王綱.不確定規(guī)劃及應(yīng)用[M].北京:清華大學(xué)出版社,2003.

[26]朱顥,唐萬生.加工時間為連續(xù)隨機變量的JobShop調(diào)度問題[J].系統(tǒng)工程與電子技術(shù),2007,29(5):759-763.

App lication of Artificial Fish Swarm A lgorithm in Fuzzy VRP

Zhu Hao
(Huzhou Vocational&TechnicalCollege,Huzhou 313000,China)

In this paper,in view of a type of VRP simultaneously with fuzzy traveling time,fuzzy discharging time and fuzzy demand,we built a fuzzy chance-constrained programming model based on credibility measurement and designed the hybrid intelligent algorithm based on fuzzy simulation,neural network and artificial fish swarm algorithm for its solution.Then we developed specifically the artificial fish recovery strategy,behavior strategy and optimization strategy for the optimization process using the artificial fish swarming algorithm.At the end,throughasimulationexperiment,wedemonstrated thevalidityof thealgorithm in solving this typeof fuzzy VRPs.

fuzzy VRP;artificial fish swarm algorithm;fuzzysimulation;neuralnetwork

F224.0;F252.14

A

1005-152X(2017)05-0064-08

10.3969/j.issn.1005-152X.2017.05.017

2017-03-31

湖州市自然科學(xué)基金（2015YZ07）

朱顥（1980-），男，講師，碩士，研究方向：車輛路徑問題。