李斌成 何國強

摘 要：針對遺傳算法求解帶容量約束的車輛路徑問題時，存在早熟收斂和易陷入局部最優(yōu)的問題，提出了改進的遺傳算法。該算法結(jié)合掃描算法思想將種群初始化進行改進，使種群從迭代之初就處于一種最優(yōu)的狀態(tài)，并改進了選擇策略和交叉策略。通過標準測試算例驗證可知，該算法求解結(jié)果同測試算例給出的當前最優(yōu)值之間的偏差在-0.24%以內(nèi)，且求解結(jié)果和穩(wěn)定性均由于對比算法，為求解此類問題給出了更加有效的解決方案。

關(guān) 鍵 詞：容量約束車輛路徑問題;遺傳算法;掃描算法;相似度;移民策略

一、引言

1959年，Dantzig et al.[1]和Ralphs et al. [2]提出了帶容量約束的車輛路徑問題（capacitated vehicle routing problem，CVRP），在物流配送和車輛調(diào)度問題中得到了廣泛應(yīng)用。目前，關(guān)于容量約束車輛路徑的計算方法主要分三類：精確算法、啟發(fā)式算法及智能優(yōu)化算法。精確算法與啟發(fā)式算法對于較大規(guī)模容量約束車輛路徑問題求解比較困難，因此對容量約束車輛路徑問題求解方法的研究主要集中在智能優(yōu)化算法上，如遺傳算法（GA）[3]、模擬退火算法（SA）[4]、蟻群算法（ACO）[5]。石兆[6]通過對智能優(yōu)化算法求解容量約束車輛路徑問題研究發(fā)現(xiàn)，禁忌搜索算法求解時間較短，但求解效果不穩(wěn)定，禁忌規(guī)則也不易確定;模擬退火算法在犧牲時間的前提下可以計算得到相對滿意的結(jié)果，但存在易陷入局部最優(yōu)的缺陷;蟻群算法存在求解效率低，容易產(chǎn)生早熟收斂現(xiàn)象的問題。考慮到以上智能優(yōu)化算法的缺點和不足，近年來許多學(xué)者采用改進的智能優(yōu)化算法求解容量約束車輛路徑問題。劉萬峰、李霞通過引入四種局部搜索算子對求解結(jié)果進行可行性評估，提出利用快速多鄰域迭代局部搜索算法（fast multi-neighborhood ILS，F(xiàn)MNILS）求解車輛路徑問題，取得了很好的效果[7]。王文蕊、吳耀華針對車輛路徑問題實際應(yīng)用進行建模分析，按照地理區(qū)域的不同對客戶進行劃分，通過改進K均值聚類法對各區(qū)域配送線路進行聚類分析，從而將問題轉(zhuǎn)化為小規(guī)模的旅行商問題，但該方法對于多階段優(yōu)化算法中的K均值聚類中心點的選擇方法仍需改進[8]。姜婷提出了混合差分蜂群算法，通過采用全局最優(yōu)解來指導(dǎo)鄰域搜索策略來增強人工蜂群開發(fā)能力不足的缺點，并通過差分算法的交叉更新策略對所提出的算法進行了局部優(yōu)化[9]，該算法缺點是求解穩(wěn)定性較弱。

遺傳算法是求解此類非確定性多項式（non-deterministic polynomial，NP）完全問題的一種有效的全局搜索算法。趙燕偉等考慮將兩個采用不同遺傳算子的種群進行協(xié)同優(yōu)化來求解容量約束車輛路徑問題，避免算法在迭代過程中發(fā)生早熟收斂現(xiàn)象，取得了很好的效果，雙種群遺傳算法具有并行特點，利用兩個種群同時進行進化，采用交換種群間優(yōu)秀個體的遺傳信息來打破平衡狀態(tài)，利于跳出局部最優(yōu)[10]。Wang cand Lu通過對遺傳算法進行優(yōu)化操作，將掃描算法同遺傳算法相結(jié)合提出了混合遺傳算法，在增加種群多樣性的同時提高了算法尋優(yōu)能力[11]。Dorronsoro et al.將遺傳算法的全局搜索能力同2-opt局部搜索能力相結(jié)合，提出了混合遺傳算法來提高算法搜索性能[12]。本文在研究傳統(tǒng)遺傳算法求解車輛路徑問題時，存在早熟收斂、易陷入局部最優(yōu)及求解結(jié)果依賴初始種群等缺點，提出了改進遺傳算法（improved genetic algorithm，I-GA）求解容量約束車輛路徑問題。

二、建立模型

本文所研究的是容量約束車輛路徑問題，這類問題是指存在一個配送中心且擁有多臺配送車輛，為多個客戶點進行貨物的配送工作，在滿足客戶點需求的基礎(chǔ)上對客戶配送次序及線路進行合理安排，使得總的配送里程或者配送費用最小。

設(shè)有向圖G=（V，E），V={0}∪V0表示所有節(jié)點的集合，0表示配送中心，V0={1，2，…，m}表示客戶點集合;E={（i，j）|i，j∈V}表示邊集合;cij表示客戶節(jié)點i和j之間的配送成本，由兩節(jié)點間的距離決定;k={1，2，…，K}表示配送中心可用車輛集合，為同類型車，最大載重為Q;di表示客戶i的需求量;xijk為二元決策變量，取值為1表示車輛k從節(jié)點i到節(jié)點j，否則取值為0;yik為二元決策變量，取值為1表示客戶點i由車輛k服務(wù)，否則取值為0。

式（1）表示總成本最小的目標函數(shù);式（2）表示配送車輛載重約束，配送車輛所服務(wù)的客戶需求不大于車輛載重約束;式（3）表示每個客戶有且僅有被一輛配送車輛所服務(wù);式（4）表示相同節(jié)點之間無連通路徑;式（5）表示一輛配送車輛僅服務(wù)一條路徑，從配送中心出發(fā)服務(wù)完客戶后，最后又返回配送中心;式（6）表示保證每個客戶都被服務(wù);式（7）和式（8）表示保證客戶被配送車輛服務(wù)時，一定存在與其相連的路徑;式（9）表示消除子回路;式（10）表示決策變量取值[13]。

三、改進遺傳算法

傳統(tǒng)遺傳算法在求解容量約束車輛路徑問題時，隨著迭代次數(shù)的遞增，種群多樣性急劇遞減，因為傳統(tǒng)遺傳算法隨機生成初始種群，這造成了算法在尋優(yōu)過程中存在早熟、收斂、陷入局部最優(yōu)等問題。因此，文章考慮設(shè)計改進遺傳算法來提高算法的尋優(yōu)性能，在研究車輛路徑問題特征基礎(chǔ)上，結(jié)合掃描算法思想，對種群初始化進行改進，使算法在迭代之初就處在一個較好的狀態(tài)。

（一）編碼

假設(shè)客戶點數(shù)目為N，配送車輛數(shù)為K，則該問題的編碼可以表示為1～（N+K-1）的一個自然數(shù)序列。1～N表示客戶點數(shù)，N+1～（N+K-1）表示線路的分割點，利用分割點對線路進行分割，即可得到K輛車各自的配送路徑。

（二）種群初始化

掃描法進行種群初始化的思想是利用配送中心和任意客戶點之間的一條射線對所有客戶點進行順時針或者逆時針掃描，通過車輛容量約束判定是否形成一條配送子路徑，并在該子路徑后加入分割符號，以此類推，直到所有客戶點都掃描結(jié)束，形成一套完整的配送方案，將其作為遺傳算法的一條染色體，重復(fù)這個過程，直到產(chǎn)生種群數(shù)量NP的染色體為止。為了使得初始種群在最初就保持一種最優(yōu)狀態(tài)，采用最近鄰插入法對每條染色體各子路徑進行順序調(diào)整，達到配送子路徑內(nèi)部有序的目的。

1.構(gòu)建初始種群

種群初始化具體流程如下。

Step 1：計算所有客戶點與配送中心之間的正切值，并按照升序進行排列;

Step 2：從中隨機選擇一個正切值作為初始掃描射線，進行順時針掃描;

Step 3：累計扇形區(qū)域內(nèi)所覆蓋的客戶點需求之和，直到滿足配送車輛容量后停止掃描，形成一個配送的客戶群;

Step 4：以原射線末位置為起始位置重復(fù)上述過程，直到掃描完所有客戶點為止，將生成的各子路徑進行連接，中間采用分隔符進行分割，即形成一條染色體;

Step 5：將射線偏移一個角度后，重復(fù)Step 2～Step 5步驟產(chǎn)生其他染色體，直到生成種群規(guī)模NP的染色體時結(jié)束，如圖1所示。

2.最近鄰插入法

采用最近鄰插入法對每條染色體內(nèi)部各子路徑進行順序調(diào)整，基本流程如下。

Step 1：取配送中心0點為線路的起始點;

Step 2：依次選擇一條染色體中的子路徑，子路徑中尋找客戶點l，使得c0l值最小，從而構(gòu)成該子路徑中的一條局部線路0-l-0;

Step 3：從該子路徑客戶點中，尋找不屬于Step2中局部線路的客戶點并離該局部線路最近的k點;

Step 4：在局部線路上尋找使得cik+ckj-cij最小的弧線（i，j），將點k插入（i，j）之間;

Step 5：重復(fù)Step 2～Step 4，直到該子路徑上所有客戶都被訪問為止;

Step 6：進行該染色體下一子路徑各客戶點順序調(diào)整，直到所有子路徑均調(diào)整完成后，重復(fù)上述過程，選擇另一條染色體進行其子路徑順序調(diào)整。

（三）適應(yīng)度函數(shù)計算

在算法開始迭代前，對種群中每一條染色體Gej進行解碼操作，對解碼完成后的各子路徑進行車輛容量約束的判斷，若存在子路徑超出車輛容量約束，則該染色體Gej對應(yīng)的解為不可行解，對該染色體的目標函數(shù)賦值一個有限的整數(shù)M0作為懲罰值，降低該染色體遺傳到下一代的概率。根據(jù)式（1）計算目標函數(shù)值F（Gej），最后根據(jù)式（11）計算適應(yīng)度函數(shù)值。

（四）遺傳算子

周明在過往研究中給出了模式的定義，即它描述了在某些位置上具有相似結(jié)構(gòu)特征的個體編碼串的一個子集[14]。因此，通過改進種群初始化得到的種群中，對偏移一個正切值的相鄰染色體而言，兩分隔符之間具有相似的配送客戶群，亦即具有相似的模式?？紤]到初始化種群得到的個體已經(jīng)是滿足車輛容量約束的較優(yōu)狀態(tài)，為盡可能不破壞個體間的模式，文章設(shè)計了新的選擇和交叉策略進行局部搜索。

1.選擇策略

首先，利用非線性輪盤賭策略任意選擇一個個體abi;然后，通過個體相似度值來進行個體之間相似性的評價，選擇與個體abi相似性最大的個體abj進行后續(xù)的交叉操作。

（1）輪盤賭選擇

文中選擇算子采用沈斌、周瑩君、王家海過往研究中具有良好魯棒性的非線性排序輪盤賭策略，可以克服算法過早收斂[15]。將種群的染色體適應(yīng)度值從小到大進行排序，并按式（12）分配概率。為了加快收斂速度，采用精英保留策略，即種群中的最優(yōu)個體以概率1被復(fù)制到下一代。將分配給個體的選擇概率按從大到小排序，求出每個個體的累積概率即個體自身選擇概率與排在它之前個體的概率的累積和，然后產(chǎn)生一個隨機數(shù)，通過它落入那個累計選擇概率的區(qū)域而選擇相應(yīng)的個體，式（13）為累計概率公式。

交叉運算是指通過選擇策略選出的兩個配對個體按照某種方式互相交換其部分基因，從而形成兩個新個體的過程?？紤]到改進種群初始化個體之間的相似性，設(shè)計了改進的均勻交叉算子。改進均勻交叉算子（improved uniform crossover）是指兩個配對個體的每一個基因座上的基因都以相同的概率進行交叉，然后對個體中重復(fù)的基因進行沖突檢測和替換，從而產(chǎn)生兩個新的個體。具體操作過程如下。

Step 1：通過選擇策略得到兩個個體A和B作為父代個體，如圖2所示。

Step 2：隨機生成一個同個體編碼同維的屏蔽字段W=w1，w2，w3，…，wi，…，wl，其中l(wèi)表示個體的維數(shù)，如圖3所示。

Step 3：若wi=0，則新個體A′的第i個基因座上的基因值繼承A對應(yīng)的基因值，新個體B′的第i個基因座上的基因值繼承B對應(yīng)的基因值;若wi=1，則新個體A′的第i個基因座上的基因值繼承B對應(yīng)的基因值，新個體B′的第i個基因座上的基因值繼承A對應(yīng)的基因值，交叉后個體如圖4所示。

Step 4：檢測沖突基因，根據(jù)交換的兩組基因建立一個映射關(guān)系，如圖4所示，以1-6-3這一映射關(guān)系為例，從Step 2中能夠發(fā)現(xiàn)交換后的預(yù)子代1中存在兩個基因1，這時將預(yù)子代1中被選中部分的基因1通過映射關(guān)系轉(zhuǎn)換為基因3，依次類推，將預(yù)子代中的所有沖突基因進行轉(zhuǎn)換。

最后形成一對新的無沖突子代染色體A″和B″，結(jié)果如圖6所示。

3.變異策略

變異運算是產(chǎn)生新個體的輔助方法，這也是遺傳算法運算過程中不可或缺的，可以改善遺傳算法局部搜索能力及維持種群的多樣性。文中采用兩點交換變異策略，通過隨機的方式，在染色體中選擇兩個不同位置的基因，將它們的基因進行交換。

（五）移民策略

遺傳算法在進化過程中，種群中的個體會趨于相似，種群的多樣性會急劇下降，產(chǎn)生了遺傳算法早熟收斂現(xiàn)象，算法過早地收斂于局部最優(yōu)解，此時，交叉和變異操作很難使得算法跳出局部最優(yōu)解。為了改變算法的早熟收斂現(xiàn)象，通過設(shè)定閾值判定當算法達到早熟收斂狀態(tài)時，采用“移民策略”引入外部個體，替換部分適應(yīng)度值較大的個體，以此打亂群體結(jié)構(gòu)來增加種群多樣性，從而進一步增強種群搜索能力。由于種群多樣性的減少主要體現(xiàn)在群體間個體適應(yīng)度值的接近程度上，即種群適應(yīng)度值方差的降低，為了簡化計算，利用公式（15）計算適應(yīng)度方差，當E小于某一閾值時，可認為算法存在早熟收斂現(xiàn)象，可對其進行“移民策略”操作，閾值的取值通過算例測算后獲得。

四、算例驗證及結(jié)果分析

本文選取容量約束車輛路徑問題算例集中的SetA、SetB、SetE、SetP部分算例對改進遺傳算法（I-GA）進行測試。實驗環(huán)境為CPU∶2.50GHz;開發(fā)環(huán)境：MATLAB R2015b;在Intel（R） Core（TM） i5-2450M CPU@2.5GHZ、4GB RAM計算機和Windows7平臺上運行。算例參數(shù)設(shè)置為：種群規(guī)模NP等于所求算例的規(guī)模數(shù);迭代次數(shù)為MaxGen=1000;種群交叉概率PcA=0.9;種群變異概率PmB=0.1;早熟收斂判斷閾值經(jīng)測算，取值為E=1.0e-14，不滿足約束個體的適應(yīng)度函數(shù)懲罰值M0=50。圖7給出了改進遺傳算法求解算例E-n22-k4和A-n32-k5的配送線路圖以及進化迭代曲線。

實驗1 分別選取容量約束車輛路徑問題測試集SetA三個算例及SetP中的6個算例，表1給出了對比算法CRO [16]和本文的設(shè)計算法。每個算例重復(fù)計算20次，其中BKR表示標準測試算例給出的當前最優(yōu)解，Best、Worst、Average分別表示對應(yīng)算法計算得到的最好值、最差值和均值，Dev表示計算結(jié)果同最優(yōu)值的偏差（Dev=（BKR-Best）/BKR×100%）。

由表1對比結(jié)果分析可知：CRO可以求出Set-A和Set-P中9個算例中的4個最優(yōu)值，與最優(yōu)值的平均偏差為-1.44%;本文設(shè)計的改進遺傳算法能夠求出9個算例中的7個最優(yōu)解，與最優(yōu)解平均偏差為-0.24%。在求解精度方面，本文改進遺傳算法求解結(jié)果同最優(yōu)值BKR的偏差明顯小于對比算法CRO所計算結(jié)果，并且改進遺傳算法能夠求解到最優(yōu)解的比例更高，求解穩(wěn)定，優(yōu)于所對比的算法。

實驗2 選取容量約束車輛路徑的Set-A算例集中的5個算例，表2給出了對比算法CO-HS [17]和本文設(shè)計算法I-GA的計算結(jié)果，每個算例重復(fù)計算20次，表2中符號含義同表1。

由表2對比結(jié)果可知：CO-HS沒有求解出Set-A算例集中5個算例的最優(yōu)值，與最優(yōu)值的平均偏差為-2.57%;本文改進遺傳算法能夠求出5個算例中的5個最優(yōu)解，與最優(yōu)解平均偏差為0.00%。在求解精度方面，本文改進遺傳算法求解結(jié)果與最優(yōu)值的偏差明顯小于對比CO-HS所計算結(jié)果，并且改進遺傳算法能夠求解到最優(yōu)解的比例更高，求解穩(wěn)定，優(yōu)于所對比的算法。

實驗3 選取容量約束車輛路徑的Set算例集中的9個算例，表3給出了對比算法Flag-MCS-CWS [18]和本文設(shè)計改進遺傳算法的計算結(jié)果，每個算例重復(fù)計算20次，表3中符號含義同表1。

由表3對比結(jié)果可知：Flag-MCS-CWS求解出Set算例集中9個算例中的2個最優(yōu)值，與最優(yōu)值的平均偏差為-0.27%;本文改進遺傳算法能夠求出9個算例中的8個最優(yōu)解，與最優(yōu)解平均偏差為-0.05%。在求解精度方面，本文改進遺傳算法求解結(jié)果與最優(yōu)值的偏差明顯小于對比Flag-MCS-CWS所計算結(jié)果，并且改進遺傳算法能夠求解到最優(yōu)解的比例更高，求解穩(wěn)定，優(yōu)于所對比的算法。

以上計算結(jié)果表明，改進遺傳算法不僅可以有效求解容量約束車輛路徑問題，相比于對比算法而言，具有良好的魯棒性。由此可見，本文提出的改進遺傳算法為求解容量約束車輛路徑問題提供了一個很好的思路。

五、結(jié)論

本文提出改進遺傳算法求解容量約束車輛路徑問題。針對容量約束車輛路徑問題的相關(guān)特性，改進遺傳算法采用掃描法思想改進初始化種群，并結(jié)合種群初始化改進了遺傳算法的選擇策略和交叉策略，在算法迭代后期判斷其早熟收斂現(xiàn)象，據(jù)此引入外部種群來增強種群的多樣性。實驗結(jié)果表明，改進遺傳算法求解容量約束車輛路徑問題時具有良好的求解精度和收斂速度，為遺傳算法求解此類問題提供了一定的參考。同傳統(tǒng)遺傳算法相比，由于對初始種群進行設(shè)定緣故，改進遺傳算法在算例求解過程中結(jié)果更加穩(wěn)定，后續(xù)研究還需在求解精度及時間復(fù)雜度方面做進一步改進。

參考文獻：

[1]DANTZIG G B，RAMSER J H.The truck dispatching problem[J].Management science，1959，6（1）：80-91.

[2]RALPHS T K，KOPMAN L，PULLEYBLANK W R，et al.On the capacitated vehicle routing problem[J].Mathematical programming，2003，94（2-3）：343-359.

[3]VIDAL T，CRAINIC T G，GENDREAU M，et al.Implicit depot assignments and rotations in vehicle routing heuristics[J].European journal of operational research，2014，237（1）：15-28.

[4]PRADHANANGA R，TANIGUCHI E，YAMADA T，et al.Environmental analysis of pareto optimal routes in hazardous material transportation[J].Procedia-social and behavioral sciences，2014，125（1）：506-517.

[5]NARASIMHA K V，KIVELEVITCH E，SHARMA B，et al.An ant colony optimization technique for solving min–max multi-depot vehicle routing problem[J].Swarm & evolutionary computation，2013，13（complete）：63-73.

[6]石兆.物流配送選址——運輸路徑優(yōu)化問題研究[D].長沙：中南大學(xué)，2014.

[7]劉萬峰，李霞.車輛路徑問題的快速多鄰域迭代局部搜索算法[J].深圳大學(xué)學(xué)報（理工版），2015，32（2）：196-204.

[8]王文蕊，吳耀華.帶實際約束的大規(guī)模車輛路徑問題建模及求解[J].控制與決策，2013，28（12）：1799-1804.

[9]姜婷.混合差分蜂群算法求解帶容量約束車輛路徑問題[J].宜賓學(xué)院學(xué)報，2017，17（12）：52-56.

[10]趙燕偉，吳斌，蔣麗，等.車輛路徑問題的雙種群遺傳算法求解方法[J].計算機集成制造，2004，10（3）：303-306.

[11]WANG C H，LU J Z.A hybrid genetic algorithm that optimizes capacitated vehicle routing problem[J].Expert systems with applications，2009，36（2）：2921-2936.

[12]DORRONSORO B，ARIAS D，LUAN F.A grid-based hybrid cellular genetic algorithm for large scale instances of the CVRP[C]// 2017 International Conference on High Performance Computing & Simulation.Genoa：Institute of Electronics Engineers，2007：759-765.

[13]李陽，范厚明.求解帶容量約束車輛路徑問題的混合變鄰域生物共棲搜索算法[J].控制與決策，2018，33（7）：1190-1198.

[14]周明.遺傳算法原理及應(yīng)用[M].北京：國防工業(yè)出版社，1999.

[15]沈斌，周瑩君，王家海.基于自適應(yīng)遺傳算法的Job-Shop調(diào)度問題研究[J].計算機應(yīng)用，2009，29（S2）：161-164，188.

[16]蔣海青，趙燕偉，冷龍龍.基于化學(xué)反應(yīng)優(yōu)化算法的車輛路徑問題[J].計算機集成制造系統(tǒng)，2018，24（8）：2012-2022.

[17]顏騰威，王麗俠，周杰，等.求解CVRP問題的改進和聲算法[J].計算機技術(shù)與發(fā)展，2016，26（9）：187-191.

[18]夏茂庚，鄭陽光，蘭延濤，等.有容量約束車輛路徑問題的蒙特卡洛模擬算法[J].科學(xué)技術(shù)與工程，2012，12（26）：6849-6852.