朱 顥

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

基于混合差分遺傳算法的聚類車輛路徑問題研究

朱 顥

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

針對所有客戶被預先分配給若干聚類的聚類車輛路徑問題，建立了相應的整數(shù)規(guī)劃模型，提出基于差分進化和遺傳算法的兩級混合算法。在聚類層，運用差分進化算法進行優(yōu)化，染色體基于聚類編號進行編碼，采用掃描算法初始化種群，結合聚類層的編碼特點，設計了基于升序排列的變異算子，在交叉環(huán)節(jié)考慮傳統(tǒng)差分進化算法的缺陷，設計了考慮聚類服務數(shù)和裝載率的混合交叉算子；在客戶層，運用遺傳算法進行優(yōu)化，染色體基于客戶編號進行編碼，交叉策略采用基因子段的整體交叉，變異時采用位置交換、逆序、插入等策略。最后，利用標準測試庫中的實例進行仿真，并與已知最優(yōu)值進行對比分析，結果表明，算法具有一定的可行性和有效性。

聚類車輛路徑；差分進化算法；遺傳算法；混合交叉算子；裝載率

1 引言

車輛路徑問題（VRP）屬于一類經典的組合優(yōu)化問題，也是NP難問題，自1959年被Dantzig和Ramser[1]首次提出以來，一直受到國內外研究者的廣泛關注。聚類車輛路徑問題（the Clustered Vehicle Routing Problem，CluVRP）作為有能力約束車輛路徑問題（CVRP）的一個變種，由Sevaux M和S?rensen K[2]于2008年首次提出，主要基于如下假設：所有的客戶根據其地理位置被預先分成若干個聚類；當某輛車訪問某個聚類時，必須連續(xù)不斷地訪問該聚類里的所有客戶，只有當其中的每一個客戶均被訪問完畢，車輛才能返回車場或者訪問下一個聚類。CluVRP也可以看作是廣義車輛路徑問題[3-4]（the Generalized Vehicle Routing Problem，GVRP）的擴展情況，其區(qū)別為：GVRP問題中，車輛只訪問每個聚類中的一個客戶，而CluVRP問題中，車輛需要訪問聚類中的每個客戶。當前，聚類車輛路徑問題在實際生活中的應用并不鮮見，如在快遞行業(yè)，快遞公司根據事先劃分的片區(qū)，安排若干輛快遞車負責多個社區(qū)（每個社區(qū)可對應一個問題中的聚類，其內部包括多個客戶），當某車輛前往某社區(qū)取送件時，必須將社區(qū)內的所有客戶全部服務完，才能離開該社區(qū)返回分撥中心或前往下一個社區(qū)。針對此類問題，需要解決的是在車輛裝載能力、車輛數(shù)量等約束條件下，合理地為每輛車分配聚類，確定聚類的訪問順序，以及每個聚類內的客戶服務順序，顯然，此類問題屬于一個典型的兩級優(yōu)化問題。

目前有關聚類車輛路徑問題的文獻中，Christof Defryn等[5-6]建立了相應的整數(shù)規(guī)劃模型，運用兩級變鄰域搜索算法進行求解；在聚類層，將問題轉化為一維的裝箱問題，利用最佳匹配遞減算法構造聚類層的初始解，并設計一種聚類間的交換操作，以修復聚類層的不可行解；在聚類層的鄰域結構上，設計了相應的交換、插入、2-Opt、Or-Opt算子；在客戶層，利用一種轉換算子生成每個聚類內的客戶順序，即客戶層的初始解，并設計了客戶的交換、插入、2-Opt、Or-Opt等操作。Battarra M等[7]采用分支切割算法和分支切割定價算法進行了求解。Barthélemy等[8]通過引入一個距離修改算子，在分屬不同聚類的客戶間加入一個較大的懲罰距離M，確保車輛必須連續(xù)服務完每一個聚類內的所有客戶，從而將CluVRP問題轉化為CVRP問題，最后用模擬退火算法進行了求解。Vidal T等[9]分別提出了基于迭代的鄰域搜索算法和混合遺傳算法來進行求解。Pop P和Chira C[10]等通過將問題中的每個聚類用一個虛擬的超級節(jié)點代替，將原問題轉化為一個全局圖，并利用遺傳算法進行了求解。Andrei Horvat Marc和Petric a C Pop等[11]也利用了超級節(jié)點這一思路，令超級節(jié)點位于該聚類的重心，用遺傳算法求解超級節(jié)點之間的最佳路線，并運用模擬退火算法求解每個聚類內的最短哈密頓路徑。Izquierdo E C等[12-13]將問題分解成兩層，每個聚類用一個虛擬中心代替，運用記錄更新法（Recordto-Record algorithm）優(yōu)化虛擬中心間的路徑，而每個虛擬中心內部構成一條哈密頓路徑，運用三類啟發(fā)式算法進行求解。

截至目前，國內對聚類車輛路徑問題的研究幾乎處于空白，僅有部分文獻將聚類算法運用于各種車輛路徑問題中，如陳美軍等[14]針對多車場車輛路徑問題，提出了一種新的聚類蟻群算法；劉長石等[15]針對多輛車協(xié)作的隨機車輛路徑問題，設計了相應的模糊聚類和車輛協(xié)作策略；劉旺盛等[16]針對需求可拆分的車輛路徑問題,分析了客戶需求不可拆分的條件，提出了一種符合解的特征的聚類算法；向婷[17]等也針對需求可拆分車輛路徑問題,提出了一種先分組、后路徑的聚類算法。

綜上所述，目前有關聚類車輛路徑問題的研究主要是集中于精確算法（如分支定界算法、分支切割定價算法）、啟發(fā)式算法（如鄰域搜索算法）和部分智能優(yōu)化算法（如遺傳算法、模擬退火算法），差分進化算法作為一種具有較強全局搜索能力的智能優(yōu)化算法，在該問題中的應用尚未出現(xiàn)。本文針對此類問題，首先構建問題的模型，然后運用基于差分進化和遺傳算法的混合算法進行優(yōu)化，在聚類層運用差分進化算法尋優(yōu)，染色體直接采用基于聚類編號的編碼，而客戶層運用遺傳算法求解，染色體直接采用基于客戶編號的編碼。

2 問題描述

聚類車輛路徑問題可以描述為：在一個完全無向圖G=(V,E)中，V={ }0,1,2,...,n表示由車場0和客戶1,2,...,n構成的集合，E={(i,j)|i,j∈V,i≠j} 表示V中任意兩個頂點所構成的邊的集合；集合V={0 ,1,2,...,n}被預先按地理位置分成N+1個聚類V0,V1,V2,...,VN，其中聚類V0僅包含車場0，其他聚類V1,V2,...,VN均不含車場，無交集且至少包含一個客戶頂點，根據該問題的特征，有V=V0?V1?V2...?VN，對于任意l,p∈{0 ,1,2,...,N} 且l≠p，有Vl?Vp=?；對于任意兩個頂點i≠j，其距離為dij；每個客戶i∈{ }

1,2,...,n只能被一輛車提供服務，其貨物需求量為qi；車場共有m輛車，其額定載重量為Q，對于每個客戶i∈{ }

1,2,...,n，均有qi≤Q，且每輛車只能有一條運輸路線。

本節(jié)描述的聚類車輛路徑問題屬于一類典型的兩級優(yōu)化問題，其中第一級為聚類層，即先將各個聚類分配給車輛，并確定同一個路線中車輛訪問聚類的順序；第二級稱為客戶層，在聚類的分配和順序已安排的前提下，進一步安排每個聚類中車輛訪問客戶的順序。該問題的優(yōu)化目標為：在滿足如下三條約束的前提下，將聚類在車輛之間合理地分配，并尋求車輛訪問聚類的最優(yōu)順序和聚類內的客戶最優(yōu)順序，使得所有車輛的總行駛距離最短。

（1）每輛車均從車場出發(fā)，為客戶提供服務后，需返回車場；（2）當車輛進入某個聚類后，必須連續(xù)不斷地為該聚類內的所有客戶提供服務，直至完畢，才能進入下一個聚類或返回車場；（3）車輛所在路線中客戶需求量之和不得超過車輛額定載重量Q。

如圖1為一個車場、15個客戶構成的完全無向圖，其中15個客戶被分成5個聚類。存在兩條運輸路線，車輛訪問聚類的順序分別為：V0-V1-V2-V3-V0，V0-V5-V4-V0，稱為聚類層子路徑；車輛訪問客戶的順序分別為：0-1-2-3-4-5-6-0，0-15-14-13-12-11-10-9-8-7-0，稱為客戶層子路徑。

3 問題模型

定義問題的變量為yik、xijk，其含義分別為：

圖1 聚類車輛路徑問題示意圖

該問題的模型如下：

該模型中：式（1）表示該模型的目標函數(shù)為極小化所有車輛的總行駛距離；式（2）表示每個客戶由且僅由一輛車提供服務；式（3）、（4）表示yik和xijk之間的關系，且每個客戶只能被服務一次；式（5）表示車輛的載重能力約束；式（6）表示消去子回路約束，其中|R|表示集合R中的客戶個數(shù)；式（7）表示每個聚類僅被一輛車服務；式（8）表示車輛從車場出發(fā)，服務完客戶后需要返回車場；式（9）表示聚類Vp中的客戶需連續(xù)被服務，|Vp|為聚類Vp中的客戶個數(shù)。

4 算法介紹

4.1 運用差分進化算法優(yōu)化聚類層

差分進化算法是Rainer Storn在1996年IEEE會議上首次提出的一種智能優(yōu)化算法[18]，該算法的結構與遺傳算法類似，通過變異、交叉、選擇等操作算子進行尋優(yōu)，具有魯棒性強、易執(zhí)行、易理解等特點。

4.1.1 掃描算法初始化種群。聚類層染色體采用聚類編號1,2,...,N的一個重排表示，車場所在聚類0不計入其中，如圖1中聚類層的編碼結構可以表示為[1,2,3,5,4]。為提高聚類層初始種群的質量，借鑒文獻[19]中的掃描算法進行初始化，具體方法如下：

首先對每個聚類，依次比較其中各客戶與車場的連線和車場所在橫坐標軸正向之間的夾角（0-360o），令最小的夾角為該聚類的X軸正向角度值；然后對各個聚類按X軸正向角度值升序排列；最后隨機選擇一個聚類作為起始點，按照逆時針方向，依次將后面的聚類安排在染色體中；重復前面步驟可得到種群規(guī)模為popsize_clu的聚類層染色體種群pop_clu。每條聚類層染色體均可按照下述步驟Step1-Step4生成可行的聚類層子路徑：

Step1:選擇第1輛車執(zhí)行任務。

Step2:選擇排列中最左邊的聚類，計算該聚類中所有客戶的總需求量，按公式（5）判斷該聚類加入車輛所在路線后是否超載，若不超載，則將聚類安排給當前車輛；否則，新開一輛車，將聚類安排給新開的車。

Step3:將該聚類從排列中刪除。

Step4:重復Step2和Step3，若所有的聚類均安排完畢，則獲得可行的聚類層子路徑，即將聚類在車輛間分配完畢，并獲得車輛訪問聚類的順序。

4.1.2 基于升序排列的變異操作。差分進化算法與遺傳算法的主要區(qū)別在于，其變異后的中間染色體v通過三個隨機的父代染色體pop_clu(a,:)、pop_clu(b,:)、pop_clu(c,:)的基因值差分計算產生，即v=pop_clu(c,:)+F[pop_clu(a,:)-pop_clu(b,:)]，其中F為縮放因子，為區(qū)間[0,1]內的常數(shù)。由于變異后的中間染色體v的基因值會包含實數(shù)甚至負數(shù)，不再符合前述編碼為{1,2,...,N}的重排的特點，因此需要對中間染色體v的基因按照基于升序的排序規(guī)則重新調整：設生成的中間染色體v的基因值為(min,max)內的實數(shù)，min是其最小基因值，max是其最大基因值，先對其每個位置的基因值按照升序進行排列，然后將基因值min對應的位置用“1”代替，第2小基因值對應的位置用“2”代替,依次類推，基因值max對應位置用“N”代替。

例如，經過變異后得到的中間染色體v為[-0.8,3.4,2.5,6.7,-5.4,9.7,4.8]，則利用前述規(guī)則進行調整后，該中間染色體v調整為[2,4,3,6,1,7,5]。

4.1.3 混合交叉操作。傳統(tǒng)差分進化算法的交叉操作是基于當前染色體pop_clu(i,:)和變異后得到的中間染色體v的交叉，通常是隨機選擇一個位置，其基因來自于v，其余位置由交叉概率因子決定其基因來自pop_clu(i,:)或v，經驗證，傳統(tǒng)的交叉機制不再適用于具有上述編碼結構的聚類層染色體，因為會導致交叉后的染色體中兩個位置的基因完全一樣，破壞原來的編碼規(guī)則，因此，本文采用如下混合交叉策略：先對父代染色體pop_clu(i,:)和中間染色體v分別進行解碼，得到各條聚類層子路徑，然后計算各聚類層子路徑的H值，將H值最大的子路徑交換至對方染色體首部，并消去后面相同的元素，得到兩個新的染色體pop_clu(i,:)new和vnew。H值的定義如下：

式（10）中N'為該聚類層子路徑中包含的聚類個數(shù)。N'越大，表示車輛服務的聚類越多，則H值越大，在交叉時該段基因應優(yōu)先被保留；Di為第i個聚類的需求量，車輛服務的所有聚類總需求量越大，則車輛的剩余載重能力越小，車輛利用率越高，在交叉時同樣該段基因應優(yōu)先被保留。

如圖2表示父代染色體pop_clu(i,:)為[3,2,5,4,7,1,8,6]，經過解碼后其H值最大的子路徑對應的基因段為4-7-1-8，圖2中上部分虛線框所示；中間染色體v為[5,6,1,8,3,2,7,4]，經過解碼后其H值最大的子路徑對應的基因段為1-8-3-2。經過交叉后消去后面相同的元素，如圖2中陰影部分所示，得到新的染色體pop_clu(i,:)new和vnew。

圖2 聚類層染色體交叉算子示意圖

4.1.4 選擇操作。差分進化算法的選擇操作采用貪婪策略，將交叉操作得到的染色體pop_clu(i,:)new和vnew與父代染色體pop_clu(i,:)進行比較，選擇最優(yōu)的聚類層染色體作為子代，具體而言：針對每條聚類層染色體，先調用客戶層的遺傳算法，尋找所對應的最優(yōu)客戶層染色體和目標值，其目的是在聚類層子路徑確定后，搜尋能使得總行駛距離最短的客戶層子路徑，并將最短的總行駛距離返回給對應的聚類層染色體，作為其差分進化算法選擇操作時計算適應度的依據。

4.2 運用遺傳算法優(yōu)化客戶層

4.2.1 掃描算法初始化種群?？蛻魧尤旧w采用基于客戶編號的方式。由于車輛進入聚類后，需連續(xù)不斷地訪問聚類中的所有客戶，因此客戶層染色體以聚類層染色體為依據，按車輛訪問聚類的先后順序，將每個聚類所屬的客戶組成一個基因子段依次排列。如4.1節(jié)中當聚類層染色體表示為[1,2,3,5,4]時，其對應的客戶層染色體包含5個基因子段，根據圖1所示，編碼[1‖2 3‖4 5 6‖15 14 13 12 11‖10 9 8 7]和[1‖3 2‖4 6 5‖14 15 13 11 12‖7 8 9 10]均為該聚類層染色體對應的客戶層染色體。借鑒4.1節(jié)中的思路，同樣可利用掃描算法生成種群規(guī)模為popsize_custom的客戶層染色體種群pop_custom，只是需在每個聚類的空間范圍內進行掃描生成相應的基因子段。

4.2.2 選擇操作。采用賭輪選擇。

4.2.3 基于基因子段的整體交叉。由于同一個聚類中的客戶必須被連續(xù)訪問，因此，在以一定的交叉概率pos_cross進行客戶層染色體之間的交叉操作時，必須將某一個聚類中的客戶整體交叉，如圖3所示為同時將兩個客戶層染色體中的第2個基因子段和第5個基因子段交換。

圖3 客戶層染色體交叉算子示意圖

4.2.4 變異操作。在以一定的變異概率pos_mutation對客戶層染色體進行變異時，采用位置交換、逆序、插入等操作，具體操作時隨機選擇一種上述操作方式，必須保證原客戶所屬的基因子段不變。如圖4分別為對客戶層染色體第4個基因子段進行三種變異操作：將客戶15和客戶11進行位置交換、將客戶11插入到客戶15前面、將客戶15至客戶11之間的5個基因整體逆序。

5 算法步驟

本文算法的總體步驟如下：

Step1：參數(shù)初始化。設置聚類層染色體種群規(guī)模popsize_clu、差分進化算法最大迭代次數(shù)max_iter_clu、縮放因子F、客戶層染色體種群規(guī)模popsize_custom、遺傳算法最大迭代次數(shù)max_iter_custom、遺傳算法交叉概率pos_cross和變異概率pos_mutation等。

圖4 客戶層染色體三種變異操作算子示意圖

Step2：利用掃描算法生成聚類層染色體種群pop_clu。對每個聚類染色體，調用函數(shù)GA_custom()搜尋其對應的最優(yōu)客戶層染色體best_custom和目標值Z。更新最優(yōu)聚類層染色體best_clu及其對應的最優(yōu)客戶層染色體best_custom?和最優(yōu)目標值Z?。

Step3：令iter←1。

Step4：令i←1，對聚類染色體pop_clu(i,:)執(zhí)行差分進化算法變異操作，并利用基于升序的排序規(guī)則調整中間染色體v。

Step5：對染色體pop_clu(i,:)和染色體v進行交叉操作，得到兩個新的染色體pop_clu(i,:)new和vnew。

Step6：對染色體pop_clu(i,:)new和vnew，分別調用函數(shù)GA_custom()，搜尋其對應的最優(yōu)客戶層染色體best_custom和目標值Z，并和pop_clu(i,:)的目標值進行比較，執(zhí)行差分進化算法選擇操作，選擇三者中最優(yōu)個體進入下一代，并更新最優(yōu)聚類染色體best_clu、最優(yōu)客戶層染色體best_custom?和最優(yōu)目標值Z?。令i=i+1，返回Step4，直至i＞popsize_clu。

Step7：令iter=iter+1 ，返 回 Step4，直 至iter＞max_iter_clu。

Step8：輸出最優(yōu)聚類染色體best_clu、最優(yōu)客戶層染色體best_custom?和最優(yōu)目標值Z?。

其中，函數(shù)GA_custom()的步驟如下：

Step1.1：根據聚類染色體中的車輛聚類分配和聚類訪問順序，結合掃描算法生成對應的客戶層染色體種群pop_custom。

Step1.2：計算每個客戶層染色體對應的目標值Zcustom，更新最優(yōu)客戶層染色體best_custom和其目標值

Step1.3：令t←1

Step1.4：執(zhí)行客戶層染色體選擇操作。

Step1.5：按照交叉概率pos_cross執(zhí)行交叉操作。

Step1.6：按照變異概率pos_mutation執(zhí)行變異操作，并計算變異后染色體的目標值Zcustom，更新best_custom和其目標值

Step1.7：令t=t+1 ，返 回 Step1.4，直 至t＞max_iter_custom。

Step1.8：返回best_custom和，將賦給Z。

6 仿真實驗分析

以文獻[5]中所介紹的A、B、P、G、M類標準測試庫為例進行仿真實驗，該測試庫仿真實例以X-n-kc-v的結構表示，不同于本文前面正文中部分符號所代表的含義，此處X代表測試庫類型（如A、B、P、G、M類）、n代表頂點數(shù)（包括客戶和車場）、k代表相應CVRP問題中的車輛數(shù)、c代表聚類數(shù)、v代表CluVRP問題中的車輛數(shù)。相關參數(shù)設置見表1。

表1 算法參數(shù)設置

6.1 仿真結果

利用Matlab R2016進行編程，運行環(huán)境為Intel i5-5200U、CPU2.2GHZ，4G內存。以A-n33-k5-C11-V2為例，經過仿真，得到最優(yōu)目標值為472，共包含2條子路徑，如圖5所示，聚類層和客戶層的子路徑分別為：

聚類層子路徑1：0-9-1-5-3-10-8-0，對應的客戶層子路徑為：0-21-33-14-9-8-27-5-13-6-28-26-31-11-18-10-4-17-16-23-0；聚類層子路徑2：0-4-6-2-7-11-0，對應的客戶層子路徑為：0-3-25-7-20-15-22-2-30-32-19-29-12-24-0。

圖5 實例A-n33-k5-C11-V2的路徑

其迭代示意圖如圖6所示。

圖6 實例A-n33-k5-C11-V2迭代示意圖

另以M-n200-K16-c67-v6為例，通過仿真，得到如圖7所示的六條子路徑，其對應的總行駛距離為929。

圖7 實例M-n200-K16-c67-v6路徑

6.2 實驗結果對比分析

運用本文所提算法，選取A、B、P、G、M類型測試庫共20個實例進行仿真，每個測試實例隨機運行10次，將10次運行結果的最優(yōu)值、平均值與已知最優(yōu)值[5]進行比較，見表2。

表2 本文算法結果與已知最優(yōu)值對比分析

通過比較可知，本文所提算法在解決客戶數(shù)100以內的中小規(guī)模問題時，基本能搜索到問題的最優(yōu)解，這得益于算法在初始化聚類層染色體種群時，采用掃描算法，在一定程度上提高了初始種群的質量；在進行聚類層染色體交叉操作時，充分考慮了服務聚類數(shù)和裝載率等因素，優(yōu)先保留H值大的基因子段，同時，即使兩個完全相同的染色體進行交叉，也能產生新的子代染色體，這使得算法能一定程度上跳出局部最優(yōu)；在客戶層染色體遺傳算法中，通過基因子段的整體操作，擴大了遺傳算法的搜索空間，同時運用逆序、插入、交換等變異算子，盡可能地保證了一定的局部搜索能力。

當然，本文所提算法還存在一定不足，在解決大規(guī)模CluVRP問題時，得到的解還不甚滿意，與已知最優(yōu)值尚有一定偏差，隨著問題規(guī)模的增加，算法尋優(yōu)時間不斷增加，如何進一步優(yōu)化算法的性能，以加強針對大規(guī)模CluVRP問題的尋優(yōu)能力，是今后進一步研究的方向。

7 結論

本文針對客戶被預先劃分給聚類的聚類車輛路徑問題，構建了相應的數(shù)學模型，通過基于差分進化算法和遺傳算法的兩級混合算法來進行優(yōu)化，在算法的設計方面，聚類層染色體和客戶層染色體的編碼結構簡單，運用掃描算法初始化兩層染色體種群，通過在聚類層采用基于升序排列的變異操作和考慮聚類服務數(shù)、車輛載重率的混合交叉算子，以及在客戶層采用基于基因子段的整體交叉和多種變異算子等多種策略，較好地對該類問題進行了求解。

[1]Dantzig G B,Ramser J H.The Truck Dispatching Problem[M].INFORMS,1959.

[2]Sevaux M,S?rensen K.Hamiltonian paths in large clustered routing problems[A].Proceedings of the EU/MEeting 2008 workshop on Metaheuristics for Logistics and Vehicle Routing[C].2008.

[3]李大衛(wèi),王夢光.廣義車輛路徑問題—模型及算法[A].1997中國控制與決策學術年會論文集[C].1997

[4]Ghiani G,Improta G.An efficient transformation of the generalized vehicle routing problem[J].European Journal of Operational Research,2000,122(1):11-17.

[5]Defryn C,S?rensen K.A fast two-level variable neighborhood search for the clustered vehicle routing problem[J].Computers&Operations Research,2017,83:78-94.

[6]Defryn C,S?rensen K.A two-level variable neighbourhood search for the euclidean clustered vehicle routing problem[R].2015.

[7]Battarra M,Erdogan G,Vigo D.Exact Algorithms for the Clustered Vehicle Routing Problem[J].Operations Research,2014,62(1):58-71.

[8]Barthélémy T,Rossi A,Sevaux M,et al.Metaheuristic approach for the clustered VRP[A].EU/ME 2010[C].2010.

[9]Vidal T,Battarra M,Subramanian A,et al.Hybrid metaheuristics for the Clustered Vehicle Routing Problem[J].Computers&Operations Research,2015,58:87-99.

[10]Pop P,Chira C.A hybrid approach based on genetic algorithms for solving the Clustered Vehicle Routing Problem[A].Evolutionary Computation[C].2014.

[11]Marc A H,Fuksz L,Pop P C,et al.A Novel Hybrid Algorithm for Solving the Clustered Vehicle Routing Problem[M].Springer International Publishing,2015.

[12]Izquierdo E C,Rossi A,Sevaux M.Modeling and Solving the Clustered Capacitated Vehicle Routing Problem[A].Proceeding of the 14thEU/ME workshop[C].2013.

[13]Expósito-Izquierdo C,Rossi A,Sevaux M.A Two-Level solution approach to solve the Clustered Capacitated Vehicle Routing Problem[J].Computers& IndustrialEngineering,2016,91:274-289.

[14]陳美軍,張志勝,陳春詠,等.多車場車輛路徑問題的新型聚類蟻群算法[J].中國制造業(yè)信息化,2008,37(6):1-5.

[15]劉長石,賴明勇.基于模糊聚類與車輛協(xié)作策略的隨機車輛路徑問題[J].管理工程學報,2010,24(2):75-78.

[16]劉旺盛,楊帆,李茂青,等.需求可拆分車輛路徑問題的聚類求解算法[J].控制與決策,2012,27(4):535-541.

[17]向婷,潘大志.求解需求可拆分車輛路徑問題的聚類算法[J].計算機應用,2016,36(11):3 141-3 145.

[18]Storn R.Differential evolution design of an IIR-filter[A].IEEE International Conference on Evolutionary Computation[C].1996.

[19]吳天羿,許繼恒.基于混合遺傳算法的模糊需求車輛路徑問題[J].解放軍理工大學學報(自然科學版),2014,(5):475-481.

Study on Clustered VRP Based on Hybrid Differential Genetic Algorithm

Zhu Hao
(Huzhou Vocational&Technical College,Huzhou 313000,China)

In this paper,in view of the routing problem of all the customer vehicles assigned to certain clusters in advance,we built the corresponding integer programming model,and proposed the bi-level hybrid algorithm based on the differential evolution and GA,according to which,at the cluster level,the differential evolution algorithm was used for optimization purpose,the mutation operator was designed based on ascending sort and considering the inadequacy of the traditional differential evolutionary algorithm in the crossover link,the hybrid crossover operator was designed to account for the quantity of clustering service and loading rate;at the customer level,the GA was used for optimization purpose,the chromosomes encoded based on customer numbering and different strategies adopted during the mutation.At the end,we had a simulation study regarding an empirical case from the standard test library and compared the result with the established optimal value to show the feasibility and validity of the algorithm of this paper.

clustered vehicle routing;differential evolutionary algorithm;genetic algorithm;hybrid crossover operator;loading rate

F224.0;F252.14

A

1005-152X(2017)10-0075-08

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

2017-09-10

湖州市自然科學基金（2015YZ07）；浙江省高等教育課堂教學改革項目（kg2015786）

朱顥，講師，碩士，主要研究方向：車輛路徑問題、物流工程。