人工魚群算法在模糊VRP問題中的應用

朱顥

（湖州職業技術學院，浙江 湖州 313000）

人工魚群算法在模糊VRP問題中的應用

朱顥

（湖州職業技術學院，浙江 湖州 313000）

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

模糊車輛路徑問題；人工魚群算法；模糊模擬；神經網絡

1 引言

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

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

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

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

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

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

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

問題的決策變量為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個位于區間[0,n]內的整數，且 y0=0≤y1≤y2≤…≤ym-1≤n=ym，其含義如下：

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

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

車輛k運行的路程為：

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

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

3 算法介紹

3.1 問題的編碼及解碼

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

為更好地解釋解碼規則，給出一個由10個客戶，4輛車構成的問題，其編碼長度為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個整數元素代表10個客戶的重排；第11-13位的元素為1,4,8：表示第一輛車服務的客戶數量為1，對應客戶編號為1，第二輛車服務的客戶數量為3，對應客戶編號依次為2,4,3，第三輛車服務的客戶數量為4，對應客戶編號依次為6,5,7,8；第四輛車服務的客戶數量為2，對應客戶編號依次為9,10；第14-17位的元素分別表示四輛車從車場出發的時間。四輛車均執行任務，每 輛 車 的客戶服務數量為 number_custom= [1 3 4 2]，對應的客戶編號code由一個m×n的矩陣表示，如圖1所示。

圖1 客戶編號code矩陣

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

3.2 模糊變量的處理

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

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

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

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

Step2：重復 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 用遺傳算法訓練神經網絡

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

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

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

輸出層節點閾值設為：

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

圖2 BP網絡權值結構

3.3.3 遺傳算法的適應度。神經網絡的訓練目標為極小化所有訓練樣本的總誤差Error，本文采用基于序的評價函數，見式（14）：

其中a'為一較小的參數。

3.4 人工魚群算法優化

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

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

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

圖3 客戶編號codep子線路間調整

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

圖4 客戶編號codep子線路內調整

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

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

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

3.4.4 人工魚的步長step。根據人工魚群算法的原理，當前人工魚 fi sh在執行聚群行為和追尾行為時，若發現中心魚或最優伙伴魚較自身狀態更優（食物更濃），且周圍不太擁擠時，fi sh朝中心魚或最優伙伴魚的方向前進一步達到狀態 fi shnext。以聚群行為為例，應同時滿足式（17）和（18）。

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

3.4.5 人工魚的聚群行為

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

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

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

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

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

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

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

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

式（19）中Fcenter為 fi shcenter的適應度，n_f為伙伴群內人工魚數量，δ為擁擠度因子，Fp為 fi sh[p]的適應度。

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

式（20）中Fbest_parter為伙伴群內最優人工魚的適應度，其他符號同上。

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

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

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

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

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

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

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

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

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

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

圖5 人工魚群算法尋優策略

4 仿真實例

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

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

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

經過Matlab 7.0編程，得到問題的最優解為：

該最優解滿足車輛能力約束和需求時間窗口約束條件，經過解碼分析，共有三輛車執行任務（分別為第1、2、4輛車），其出發時間為8.332 6時、8.222 4時和8.248 3時。

對應的客戶編號如下：

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

圖6為經過模糊模擬5 000次，訓練神經網絡2 000次，人工魚群算法500次迭代后總行駛里程的迭代示意圖。

圖6 總行駛里程迭代結果

（2）人工魚群算法與其他算法的比較。針對同樣的仿真數據，基于同樣的種群編碼格式，以同樣的神經網絡最優權值，在種群規模均為50，總迭代次數均為500的情況下，以本文所提算法為基礎隨機運行10次，與傳統的遺傳算法和模擬退火算法運行的結果進行比較，結果見表2。

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

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

5 結束語

本文考慮了一類車輛行駛時間、卸貨時間和客戶的需求量均為模糊變量的VRP問題，針對該問題建立了基于可信性測度的模糊機會約束規劃模型，然后針對該問題提出了基于人工魚群算法的智能優化算法，通過仿真實驗證明，該算法對于解決帶模糊車輛行駛時間、模糊卸貨時間和模糊需求量的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].電子學報,2001,(8):1-3.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[26]朱顥,唐萬生.加工時間為連續隨機變量的JobShop調度問題[J].系統工程與電子技術,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

湖州市自然科學基金（2015YZ07）

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