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

朱顥

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

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

朱顥

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

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

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

1 引言

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

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

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

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

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

2 帶模糊時(shí)間和模糊需求量的VRP模型

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

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

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

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

對(duì)于每個(gè)k=1,2,...,m，yk-yk-1表示車輛k服務(wù)的客戶數(shù)量。若yk=yk-1，車輛k不運(yùn)行；若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ā)的時(shí)間，k=1,2...,m。

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

車輛k運(yùn)行的路程為：

綜上所述，可以建立如下的模糊機(jī)會(huì)約束模型：

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

3 算法介紹

3.1 問題的編碼及解碼

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

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

圖1 客戶編號(hào)code矩陣

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

3.2 模糊變量的處理

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

對(duì)于每個(gè)輸入樣本solution[p]，采用如下方法進(jìn)行模糊模擬：

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

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

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

Step3：計(jì)算d1和d2。

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

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

針對(duì)前述車輛能力約束和需求時(shí)間窗口約束，將sample_num個(gè)輸入樣本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）中的兩個(gè)可信性函數(shù)。

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

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

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

3.3.2 遺傳算法的編碼及解碼。設(shè)染色體種群集合為title_pop，種群規(guī)模為popsize。本節(jié)中染色體為神經(jīng)網(wǎng)絡(luò)的權(quán)值，如圖2所示：染色體總長度為M×N+2×N，前M×N個(gè)基因?yàn)檩斎雽庸?jié)點(diǎn)i和隱層節(jié)點(diǎn)j之間的權(quán)值，表示為wij∈[0,1]；后2×N個(gè)基因?yàn)殡[層節(jié)點(diǎn) j和輸出層2個(gè)節(jié)點(diǎn)之間的權(quán)值，表示為。對(duì)于每個(gè)權(quán)值染色體，采用文獻(xiàn)[26]的方法計(jì)算所有輸入樣本訓(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)練目標(biāo)為極小化所有訓(xùn)練樣本的總誤差Error，本文采用基于序的評(píng)價(jià)函數(shù)，見式（14）：

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

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

隨機(jī)產(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ò)計(jì)算出Qk,k=1,2,...,m}和Cr{ai≤fi(x,y,t)≤bi,i=1,2,…,n}的值，判斷該人工魚是否可行，若不滿足約束條件（5）和（6），則采用如下3.4.1的方式進(jìn)行修復(fù)。

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

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

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

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

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

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

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

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

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

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

3.4.5 人工魚的聚群行為

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

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

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

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

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

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

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

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

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

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

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

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

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

（4）檢驗(yàn)人工魚 fi shnew是否可行，若該人工魚不可行，需要進(jìn)行修復(fù)，修復(fù)時(shí)優(yōu)先考慮在集合identifier_no中的元素間進(jìn)行位置的交換以及對(duì)tnew部分的取值重新隨機(jī)生成，以保證 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)之一儲(chǔ)存）；若 fi shnew的狀態(tài)較 fi sh[p]差，則重新嘗試，反復(fù)嘗試tr y_number后，仍不能獲得一個(gè)更好的狀態(tài)，則放棄覓食行為。

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

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

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

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

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

4 仿真實(shí)例

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

（1）實(shí)驗(yàn)結(jié)果。針對(duì)本文提出的VRP問題，利用Matlab進(jìn)行仿真實(shí)驗(yàn)，仿真參數(shù)如下：模糊模擬輸入樣本 個(gè) 數(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 各客戶的模糊需求、模糊卸貨時(shí)間

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

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

對(duì)應(yīng)的客戶編號(hào)如下：

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

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

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

5 結(jié)束語

本文考慮了一類車輛行駛時(shí)間、卸貨時(shí)間和客戶的需求量均為模糊變量的VRP問題，針對(duì)該問題建立了基于可信性測度的模糊機(jī)會(huì)約束規(guī)劃模型，然后針對(duì)該問題提出了基于人工魚群算法的智能優(yōu)化算法，通過仿真實(shí)驗(yàn)證明，該算法對(duì)于解決帶模糊車輛行駛時(shí)間、模糊卸貨時(shí)間和模糊需求量的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]祝崇雋,劉民,吳澄,等.針對(duì)模糊需求的VRP的兩種2—OPT算法[J].電子學(xué)報(bào),2001,(8):1-3.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[26]朱顥,唐萬生.加工時(shí)間為連續(xù)隨機(jī)變量的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-），男，講師，碩士，研究方向：車輛路徑問題。