改進遺傳算法在容量約束車輛路徑問題中的應用研究

李斌成 何國強

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

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

一、引言

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

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

二、建立模型

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

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

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

三、改進遺傳算法

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

（一）編碼

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

（二）種群初始化

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

1.構建初始種群

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

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

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

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

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

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

2.最近鄰插入法

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

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

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

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

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

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

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

（三）適應度函數計算

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

（四）遺傳算子

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

1.選擇策略

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

（1）輪盤賭選擇

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

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

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

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

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

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

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

3.變異策略

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

（五）移民策略

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

四、算例驗證及結果分析

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

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

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

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

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

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

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

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

五、結論

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

參考文獻：

[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]石兆.物流配送選址——運輸路徑優化問題研究[D].長沙：中南大學，2014.

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

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

[9]姜婷.混合差分蜂群算法求解帶容量約束車輛路徑問題[J].宜賓學院學報，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]周明.遺傳算法原理及應用[M].北京：國防工業出版社，1999.

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

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

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

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