基于改進雙種群混合遺傳算法的車輛路徑問題研究

何國強 李斌成 王東先

摘?要：針對傳統遺傳算法求解帶容量約束的車輛路徑問題，存在早熟收斂、易陷入局部最優等問題，設計了雙種群混合遺傳算法。種群I在傳統遺傳算法中引入模擬退火思想及變鄰域搜索策略，增強算法局部搜索性能。種群II在迭代過程中，通過設定閾值判斷當種群達到早熟收斂狀態時，利用“移民策略”植入外部個體，達到增加種群多樣性、增強算法全局搜索和開發的能力。每次迭代完成后采用“移民算子”進行種群間的信息交流。最近鄰插入方法在算法迭代結束之后對求解所得最好解的各子路徑進行再優化。算例驗證分析可知，所提算法計算結果同算例給出的最好解之間的偏差均在-1.00%以內，求解質量優于所有對比的算法，表明所提算法能有效解決容量約束的車輛路徑問題，具有可靠的全局穩定性。

關?鍵?詞：容量車輛路徑問題;雙種群;混合遺傳算法;?移民策略;局部搜索/全局搜索

中圖分類號：TP301.6??文獻標志碼：?A?文章編號：2096-7934（2020）07-0108-11

一、?引言

車輛路徑問題（vehicle?routing?problem，?VRP）是典型的組合優化問題，經過不斷發展，在VRP問題的基礎上衍生出了很多其他問題，如：帶時間窗的VRP（vehicle?routing?problem?with?times?windows，?VRPTW）、多配送中心VRP（multiple?depot?vehicle?routing?problem，?m-VRP）、容量限制的VRP（capacitated?vehicle?routing?problem，?CVRP）等。其中，容量限制的VRP（capacitated?vehicle?routing?problem，?CVRP）實用性較為廣泛，因而吸引了眾多學者進行研究。目前，關于CVRP的計算方法主要分三類：精確算法、啟發式算法及智能優化算法。精確算法與啟發式算法對于較大規模CVRP問題求解比較困難，因而，目前對CVRP問題求解方法的研究主要集中在智能優化算法上，如遺傳算法（GA）[1]、模擬退火算法（SA）[2]、蟻群算法（ACO）[3]。石兆[4]通過對智能優化算法求解CVRP問題研究發現，禁忌搜索算法求解時間較短，但求解效果不穩定，禁忌規則也不易確定;模擬退火算法在犧牲時間的前提下可以計算得到相對滿意的結果，但存在易陷入局部最優的缺陷;蟻群算法存在求解效率低，容易產生早熟收斂現象的缺陷。考慮到以上智能優化算法的缺點和不足，近年來，有學者提出了這些算法的改進方法，如將多種智能算法融合以及設計新的算法。

采用多種智能優化算法混合來求解CVRP問題的研究主要有：劉萬鋒等[5]通過引入四種局部搜索算子進行了解的合法性評估，提出利用快速多鄰域迭代局部搜索算法（fast?multi-neighborhood?ILS，?FMNILS）求解車輛路徑問題，該算法在計算時間及解的滿意程度等方面都表現良好。王文蕊等[6]研究了帶諸多實際約束的大規模車輛路徑問題，按照地理區域的不同對客戶進行劃分，通過改進K均值聚類法對各區域配送線路進行聚類分析，從而將問題轉化為小規模的旅行商問題，但該方法對于多階段優化算法中的K均值聚類中心點的選擇方法仍需改進。姜婷[7]提出了混合差分蜂群算法，通過采用全局最優解指導鄰域搜索策略來增強人工蜂群開發能力不足的缺點，并通過差分算法的交叉更新策略對所提出的算法進行局部優化，該算法缺點是求解穩定性較弱。畢志升等[8]提出了基于Pareto支配接受準則的多目標模擬退火算法，但所設計的搜索策略對多目標搜索具有偏向性，因此仍需設計更好的局部搜索策略來避免搜索策略對多目標的偏向性問題。陳亮[9]通過對傳統蟻群算法計算結果質量差、收斂性弱等缺點的研究，提出了一種改進的蟻群算法來求解CVRP問題，通過引入基于DT策略的候選集來改進構建路徑質量，且在迭代過程中加入GIIM算子增強了局部搜索能力，但相比于其他類似算法，并不具有很大優勢，甚至很多結果都劣于類似算法的求解結果。

新設計算法求解CVRP問題的研究主要有：蔣海青等[10]提出通過化學優化算法求解CVRP問題，借鑒遺傳算法交叉和變異算子設計了分子的相撞、拆解、撞墻及局部優化的合成等四種反應來實現解的改進，并利用動態變化方式對相關參數進行控制，提高了算法的求解效率及全局搜索能力。顏騰威等[11]研究了和聲搜索算法在求解CVRP問題時存在搜索能力弱等缺陷，提出改進的和聲搜索算法，通過改進和聲音調生成策略及利用2-opt算子對新生成的和聲進行優化，既約束了不可行解的產生、壓縮搜索空間，又提升了搜索效率，但算例求解結果均劣于遺傳算法等經典算法。周和平等[12]針對傳統蟻群算法計算CVRP問題時的不足，提出了一種改進的蟻群算法，改進的算法在求解速度以及解的質量方面都有很好提升。李陽等[13]設計了一種變鄰域生物共棲算法，采用三種共棲搜索算子，提高了算法全局搜索能力，該算法具有較好的全局穩定性。夏茂庚等[14]通過研究節約里程算法和蒙特卡洛模擬方法，將二者特性相結合提出了Flag-MCS-CWS算法，為車輛路徑問題的求解提供了很有效的方法，該算法只對算例中30個點以內的問題進行了驗證。

上述文獻在求解CVRP問題時，其有效性和優越性均得到了驗證，但也存在因父代的不合法使得算法搜索范圍受限等問題，上述文獻中所采用的驗證算例多以小規模問題為主，對較大規模問題的求解是否有效還有待進一步考證。在求解CVRP問題的智能優化算法中，遺傳算法作為最傳統、最經典的優化算法，最適合CVRP問題的求解。因此，本文在程子安等[15]算法的基礎上設計了雙種群混合遺傳算法（double?population?hybrid?genetic?algorithm，?DPHGA?）來求解CVRP問題，期望在求解精度上有較大程度提升。

二、?車輛路徑問題數學模型

其中：（1）式表示目標函數;（2）式表示每輛車載重約束;（3）式表示每個客戶都被服務;（4）—（5）式表示保證每個客戶只被一輛車服務;（6）式表示消除子回路;（7）—（8）式表示二元變量取值范圍。

三、?雙種群混合遺傳算法

研究發現，傳統遺傳算法在求解CVRP問題時，隨著迭代次數的遞增，種群多樣性降低，初始種群產生的隨機性對解的影響巨大，造成了算法在尋優過程中存在早熟、收斂、陷入局部最優等問題。因此，文章考慮設計雙種群混合遺傳算法來提高算法的優化性能，種群I作為精英群體進行局部搜索，種群II作為劣勢群體進行全局開發。其中，種群I結合模擬退火算法思想及變鄰域搜索策略進行鄰域搜索，提高局部搜索性能;種群II采用傳統遺傳算法，對劣勢群體進行移民操作，增強全局開發能力，同時在進化過程中將種群I中最差個體同種群II中最優個體進行交換來實現兩個種群的協同優化，從而提高算法計算結果的穩定性，降低計算結果的波動性。

（一）算法設計

DPHGA算法求解車輛問題的流程如圖1所示，種群I著重算法的局部搜索能力，種群II著重算法的全局搜索能力。

（二）編碼

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

（三）種群初始化

根據上述編碼與解碼方案，種群的染色體為一組1～（N+K-1）之間的隨機數序列，通過隨機函數產生種群I、種群II的PopA和PopB個數量的染色體，此作為第一代種群。

（四）適應度值計算

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

（五）遺傳算子

1.?選擇算子

文中選擇算子采用沈斌等[16]提出的具有良好魯棒性的非線性排序輪盤賭策略，可以克服算法過早收斂。將兩種群的各自的染色體適應度值從小到大進行排序，并按式（10）分配概率。

2.?交叉算子

所謂交叉運算，是指對兩個相互配對的染色體根據交叉概率按某種規則相互交換其部分基因，從而形成兩個新的個體。交叉運算在遺傳算法中起關鍵作用，是產生新個體的主要方法，在一定程度上影響著種群的多樣性，為了提高搜索性能，對雙種群采用不同的交叉策略，記兩個種群分別為種群I和種群II。

（1）種群I交叉算子：采用部分匹配交叉算子（PMX），該交叉操作的對象是連續基因片段，基本思想源于一維線性結構的基因位置順序，PMX操作生成新的子代個體，這些子代個體繼承父代或生成新的連續優良基因的可能性較高。

（2）種群II交叉算子：采用順序交叉策略（OX），同部分匹配交叉策略基本相同，唯一不同點是以父代中選擇的基因片段為操作對象進行。

3.?變異算子

變異是指根據變異概率將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。遺傳算法中的變異運算是產生新個體的輔助方法，它決定了遺傳算法的局部搜索能力，同時保持種群的多樣性遺傳算法中的變異運算是產生新個體的輔助方法，它決定了遺傳算法的局部搜索能力，同時保持種群的多樣性。

（1）種群I變異算子：采用兩點交換變異策略，通過隨機的方式，在個體任意相鄰兩分隔符之間選擇兩個不同位置的基因，將它們的基因進行交換。

（2）種群II變異算子：采用逆序變異策略，通過隨機的方式，在染色體的編碼序列中選擇兩個不同基因座之間的基因，將其逆序排列，生成一個新的編碼序列。

（六）種群I局部搜索策略

種群I完成變異操作之后，對其進行變鄰域搜索策略，來提高種群在進化過程中的多樣性，增強算法局部探索能力，進一步提高算法搜索到滿意解的概率。

1.?抖動操作

“抖動”是鄰域生成的主要方法，通常采用以下三種策略進行：互換操作（swap），隨機交換染色體某兩個基因的位置;逆序操作（reversion），將染色體某兩個基因位置之間的基因序列逆序;?插值操作（insertion），隨機選擇一個基因位置將其插入染色體其他位置。為了使算法能夠對這三種鄰域進行合理搜索，避免不必要的計算，采用易軍等[17]提出的概率策略進行選擇，定義在開始鄰域搜索之前種群I中每個個體i適應度值為f（i）。

Step1：對三種鄰域分別進行k次搜索，找出在第t種鄰域下的個體最優適應度值f′（i，t），按照式（12），（13）計算第t種鄰域下的獎勵值η（i，t）。

Step2：按照式（14）計算各鄰域的概率，利用輪盤賭選擇需要搜索的鄰域，一次搜索完成后即更新獎勵值。

2.Metropolis?接受準則

對種群I中染色體產生的新鄰域進行判斷，具體步驟如下。

Step6：若滿足終止條件，則更新當前最優解，結束程序;否則按照衰減函數衰減T后返回Step2。以Metropolis鏈長L為終止條件。

Step7：種群I所有個體完成鄰域選擇操作以后，更新當前最優解，并將變異完成后產生的種群與經過局部搜索策略產生的新的種群進行合并，按照目標函數值從小到大進行排序，從中選出種群I中染色體數目的個體作為下一次進化的種群。

（七）種群II移民策略

隨著遺傳算法迭代次數的增加，種群逐漸收斂于最適應環境的個體，種群多樣性隨之降低，種群群體結構趨于相似，從而降低了搜索效率，算法也會隨之產生早熟收斂現象，可見改善種群多樣性是解決早熟收斂問題的主要方法。因此，在算法進化的過程中，通過采用張義長等[18]“移民策略”對種群II引入外部個體，替換部分適應度值較小的個體，以此打亂群體結構來增加種群多樣性，從而進一步增強種群II的全局開發以及搜索能力。

由于種群多樣性的減少主要體現在群體間個體適應度值的接近程度上，即種群適應度值方差的減小，為了簡化計算，利用公式（15）計算適應度方差，當E小于某一閾值時，可認為算法存在早熟收斂現象，可對其進行“移民策略”操作，閾值的取值通過算例測算后獲得。

（八）種群間信息交換

雙種群遺傳算法，在進化過程中，各種群之間是相互獨立的，不同種群之間通過“移民算子”[19]實現信息交流。移民算子將兩個種群在進化過程中求得的特定個體定期引入到對方的種群中，保證種群I中精英群體進行局部搜索，種群II中劣勢群體進行全局開發，從而實現種群間的信息交流和協同進化。具體流程為：用種群II中的最優個體同種群I中的最差個體進行交換。

（九）局部再優化

通常，求解CVRP問題所得結果均須采取其他措施進一步優化。文中采用最近鄰插入方法[20]對求解所得最好解的各個子路徑進行再優化，以此尋找比當前更優的解。最近鄰插入方法是一種改進的局部搜索算法，通過反轉每條子路徑來實現結果的優化，對進化完成后生成的最好解對應的各子路徑進行順序調整。

最近鄰插入法流程如下。

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

Step2：在所求得的子路徑中尋找客戶點l，使得c0l值最小，從而構成該子路徑中的一條局部線路0-l-0;

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

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

Step5：重復Step2～Step4，直到該子路徑上所有客戶都被訪問為止;

Step6：重復Step1-Step5，直到所有子路徑均優化完成為止。

四、?算例驗證及結果分析

本文選取CVRP問題測試集中的SetA、SetB、SetP部分算例對DPHGA進行測試。實驗環境為CPU：2.50GHz;開發環境：Matlab?R2015b;在Intel（R）?Core（TM）?i5-2450M?CPU@2.5GHZ、4GB?RAM計算機和windows7平臺上運行。算例參數設置為：種群I、種群II的規模NP根據所求算例規模進行動態調整;客戶規模在30～50之間時，種群NP=50，迭代次數為MaxGen=1000，客戶規模在51～80之間時，種群NP=80，迭代次數為MaxGen=2000;種群I交叉概率PcA=0.9，種群I變異概率PmA=0.1;種群II交叉概率PcB=0.9，種群II變異概率PmB=0.1;模擬退火變鄰域選擇策略初始溫度t0=10，溫度退化率ρ=0.99，Metropolis鏈長L=10;早熟收斂判斷閾值經測算，取值為E=1.0e-14，不滿足約束個體的適應度函數懲罰值M0=50。

實驗1?選取CVRP算例集Set-B、Set-E、Set-P中16個算例，表1給出了張曉楠等[21]提出得HSSA和本文DPHGA的計算結果，*表示最優值。每個算例重復計算20次，其中BKR表示算例給出的當前最優值，Best、Worst、Average分別表示算法計算所得最好值、最差值和均值，Dev表示計算結果同最優值的偏差（Dev=（BKR-Best）/BKR×100%）。

由表1對比結果可知：HSSA可求解出所給算例集中的4個最優值，與最優值的平均偏差為-1.18%;本文DPHGA能夠求出8最優解，與最優解平均偏差為-0.50%。在求解精度方面，本文DPHGA求解結果與最優值得偏差明顯小于對比HSSA所計算結果，并且DPHGA能夠求解到最優解的比例更高，求解穩定，優于所對比的算法。

實驗2?選取CVRP算例集Set-A中24個算例，表2給出了對比Sener[22]和Ng[23]提出的LNS-ACO和EBMC-ABC同本文DPHGA的計算結果。每個算例重復計算20次，表2中的符號含義同表1。

由表2對比結果可知：LNS-ACO求解出所給出算例集中的17個最優值，與最優值的平均偏差為-0.44%;EBMC-ABC求解出所給出算例集中的17個最優值，與最優值的平均偏差為-0.17%;本文DPHGA能夠求出16個最優值，與最優解平均偏差為-0.19%。在求解精度方面，本文DPHGA求解結果與最優值的偏差明顯小于對比LNS-ACO所計算結果，并且與EBMC-ABC計算結果基本一致，本文算法能夠求解到最優解的比例更高，求解穩定，優于所對比算法。

如圖2所示，標準遺傳算法（GA）、模擬退火算法（SA）和DPHGA計算算例A-n37-k5、P-n45-k5、B-n39-k5的收斂曲線對比。可知SA單獨計算CVRP算例時，在求解到算例的次優解之后會陷入局部最優，收斂效果較差;相比于SA，GA收斂速度較快，經過大量迭代計算后可以逐步提升解的質量，但在20次重復計算中，很難求解到最優值;相對于SA、GA單獨計算而言，?DPHGA收斂曲線平緩，無早熟及陷入局部最優情況出現，三個案例均在DPHGA迭代700次左右就逼近算例已知全局最優解。可見，改進雙種群混合遺

傳算法在求解精度、算法收斂性等方面均得到很大提高，尋優質量較高。

綜上所述，?DPHGA在求解精度、算法穩定性等方面均優于所對比的5中算法，是求解CVRP問題的有效方法。

五、?結論

本文提出基于改進雙種群混合遺傳算法求解CVRP問題。算法采用兩個種群協同進化的思想，種群II結合遺傳算法全局搜索性能及移民策略思想進行算法的全局搜索及開發，擴大解方案的搜索空間，維持種群的高多樣性;種群I在傳統遺傳算法迭代基礎上，引入模擬退火思想及變鄰域搜索策略，增強算法的局部探索能力。劣勢種群進行全局搜索開發，精英種群進行局部探索，然后兩種群通過協同進化的機制極大提高了算法搜索到全局最優解的概率。算例驗證及分析表明，DPHGA可有效求解CVRP，尋優質量優于對比算法，今后可進一步改進該算法，增強算法求解大規模客戶算例的性能。

參考文獻：

[1]??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.

[2]?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.

[3]?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（C）：?63-73.

[4]?石兆.?物流配送選址—運輸路徑優化問題研究[D].?長沙：中南大學，?2014：30-33.

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

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

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

[8]?畢志升，蔡茗芊.?基于多目標模擬退火的帶容量限制車輛路徑問題[J].?計算機與數字工程，?2017，?45（8）：?1513-1518.

[9]?陳亮，周晶晶.?求解CVRP的改進蟻群系統算法[J].?軍事交通學院學報，?2014，?16（5）：?92-95.

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

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

[12]?周和平，陳亮.?求解CVRP問題的一種改進啟發式蟻群算法[J].?后勤工程學院學報，?2015，?31（4）：?80-84，89.

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

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

[15]?程子安，童鷹，申麗娟，等.?雙種群混合遺傳算法求解柔性作業車間調度問題[J].?計算機工程與設計，?2016，?37（6）：?1636-1642.

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

[17]?易軍，李太福.?求解作業車間調度的變鄰域細菌覓食優化算法[J].?機械工程學報，?2012，?48（12）：?178-183.

[18]?張義長，楊加明，魯宇明.?結合保優策略和移民策略的自適應遺傳算法[J].?計算機工程與應用，?2010，?46（31）：?36-38.

[19]?史峰.?MATLAB?智能算法—30個案例分析[M].?北京：北京航天航空大學出版社，2011：69-79.

[20]?CROES?G?A.?A?method?for?solving?traveling-salesman?problems[J].?Operations?research，?1958，?6（6）：?791-812.

[21]?張曉楠，范厚明.?混合分散搜索算法求解帶容量約束車輛路徑問題[J].?控制與決策，?2015，?30（11）：?1937-1944.

[22]?AKPINAR?S.?Hybrid?large?neighbourhood?search?algorithm?for?capacitated?vehicle?routing?problem[J].?Expert?systems?with?applications，?2016，?61：28-38.

[23]NG?K?K?H，LEE?C?K?M，ZHANG?S?Z.?A?multiple?colonies?artificial?bee?colony?algorithm?for?a?capacitated?vehicle?routing?problem?and?re-routing?strategies?under?time-dependent?traffic?congestion[J].?Computers?&?industrial?engineering，?2017，?109：?151-168.