何國(guó)強(qiáng) 李斌成 王東先

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

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

中圖分類號(hào)：TP301.6??文獻(xiàn)標(biāo)志碼：?A?文章編號(hào)：2096-7934（2020）07-0108-11

一、?引言

車輛路徑問(wèn)題（vehicle?routing?problem，?VRP）是典型的組合優(yōu)化問(wèn)題，經(jīng)過(guò)不斷發(fā)展，在VRP問(wèn)題的基礎(chǔ)上衍生出了很多其他問(wèn)題，如：帶時(shí)間窗的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）實(shí)用性較為廣泛，因而吸引了眾多學(xué)者進(jìn)行研究。目前，關(guān)于CVRP的計(jì)算方法主要分三類：精確算法、啟發(fā)式算法及智能優(yōu)化算法。精確算法與啟發(fā)式算法對(duì)于較大規(guī)模CVRP問(wèn)題求解比較困難，因而，目前對(duì)CVRP問(wèn)題求解方法的研究主要集中在智能優(yōu)化算法上，如遺傳算法（GA）[1]、模擬退火算法（SA）[2]、蟻群算法（ACO）[3]。石兆[4]通過(guò)對(duì)智能優(yōu)化算法求解CVRP問(wèn)題研究發(fā)現(xiàn)，禁忌搜索算法求解時(shí)間較短，但求解效果不穩(wěn)定，禁忌規(guī)則也不易確定;模擬退火算法在犧牲時(shí)間的前提下可以計(jì)算得到相對(duì)滿意的結(jié)果，但存在易陷入局部最優(yōu)的缺陷;蟻群算法存在求解效率低，容易產(chǎn)生早熟收斂現(xiàn)象的缺陷?？紤]到以上智能優(yōu)化算法的缺點(diǎn)和不足，近年來(lái)，有學(xué)者提出了這些算法的改進(jìn)方法，如將多種智能算法融合以及設(shè)計(jì)新的算法。

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

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

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

二、?車輛路徑問(wèn)題數(shù)學(xué)模型

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

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

研究發(fā)現(xiàn)，傳統(tǒng)遺傳算法在求解CVRP問(wèn)題時(shí)，隨著迭代次數(shù)的遞增，種群多樣性降低，初始種群產(chǎn)生的隨機(jī)性對(duì)解的影響巨大，造成了算法在尋優(yōu)過(guò)程中存在早熟、收斂、陷入局部最優(yōu)等問(wèn)題。因此，文章考慮設(shè)計(jì)雙種群混合遺傳算法來(lái)提高算法的優(yōu)化性能，種群I作為精英群體進(jìn)行局部搜索，種群II作為劣勢(shì)群體進(jìn)行全局開發(fā)。其中，種群I結(jié)合模擬退火算法思想及變鄰域搜索策略進(jìn)行鄰域搜索，提高局部搜索性能;種群II采用傳統(tǒng)遺傳算法，對(duì)劣勢(shì)群體進(jìn)行移民操作，增強(qiáng)全局開發(fā)能力，同時(shí)在進(jìn)化過(guò)程中將種群I中最差個(gè)體同種群II中最優(yōu)個(gè)體進(jìn)行交換來(lái)實(shí)現(xiàn)兩個(gè)種群的協(xié)同優(yōu)化，從而提高算法計(jì)算結(jié)果的穩(wěn)定性，降低計(jì)算結(jié)果的波動(dòng)性。

（一）算法設(shè)計(jì)

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

（二）編碼

編碼：假設(shè)客戶點(diǎn)數(shù)目為N，配送車輛數(shù)為K，則該問(wèn)題的編碼可以表示為1～（N+K-1）的一個(gè)隨機(jī)排列。1～N表示客戶點(diǎn)數(shù)，N+1～（N+K-1）表示線路的分割點(diǎn)，利用分割點(diǎn)對(duì)線路進(jìn)行分割，即可得到K輛車各自的配送路徑。

（三）種群初始化

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

（四）適應(yīng)度值計(jì)算

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

（五）遺傳算子

1.?選擇算子

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

2.?交叉算子

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

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

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

3.?變異算子

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

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

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

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

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

1.?抖動(dòng)操作

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

Step1：對(duì)三種鄰域分別進(jìn)行k次搜索，找出在第t種鄰域下的個(gè)體最優(yōu)適應(yīng)度值f′（i，t），按照式（12），（13）計(jì)算第t種鄰域下的獎(jiǎng)勵(lì)值η（i，t）。

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

2.Metropolis?接受準(zhǔn)則

對(duì)種群I中染色體產(chǎn)生的新鄰域進(jìn)行判斷，具體步驟如下。

Step6：若滿足終止條件，則更新當(dāng)前最優(yōu)解，結(jié)束程序;否則按照衰減函數(shù)衰減T后返回Step2。以Metropolis鏈長(zhǎng)L為終止條件。

Step7：種群I所有個(gè)體完成鄰域選擇操作以后，更新當(dāng)前最優(yōu)解，并將變異完成后產(chǎn)生的種群與經(jīng)過(guò)局部搜索策略產(chǎn)生的新的種群進(jìn)行合并，按照目標(biāo)函數(shù)值從小到大進(jìn)行排序，從中選出種群I中染色體數(shù)目的個(gè)體作為下一次進(jìn)化的種群。

（七）種群II移民策略

隨著遺傳算法迭代次數(shù)的增加，種群逐漸收斂于最適應(yīng)環(huán)境的個(gè)體，種群多樣性隨之降低，種群群體結(jié)構(gòu)趨于相似，從而降低了搜索效率，算法也會(huì)隨之產(chǎn)生早熟收斂現(xiàn)象，可見改善種群多樣性是解決早熟收斂問(wèn)題的主要方法。因此，在算法進(jìn)化的過(guò)程中，通過(guò)采用張義長(zhǎng)等[18]“移民策略”對(duì)種群II引入外部個(gè)體，替換部分適應(yīng)度值較小的個(gè)體，以此打亂群體結(jié)構(gòu)來(lái)增加種群多樣性，從而進(jìn)一步增強(qiáng)種群II的全局開發(fā)以及搜索能力。

由于種群多樣性的減少主要體現(xiàn)在群體間個(gè)體適應(yīng)度值的接近程度上，即種群適應(yīng)度值方差的減小，為了簡(jiǎn)化計(jì)算，利用公式（15）計(jì)算適應(yīng)度方差，當(dāng)E小于某一閾值時(shí)，可認(rèn)為算法存在早熟收斂現(xiàn)象，可對(duì)其進(jìn)行“移民策略”操作，閾值的取值通過(guò)算例測(cè)算后獲得。

（八）種群間信息交換

雙種群遺傳算法，在進(jìn)化過(guò)程中，各種群之間是相互獨(dú)立的，不同種群之間通過(guò)“移民算子”[19]實(shí)現(xiàn)信息交流。移民算子將兩個(gè)種群在進(jìn)化過(guò)程中求得的特定個(gè)體定期引入到對(duì)方的種群中，保證種群I中精英群體進(jìn)行局部搜索，種群II中劣勢(shì)群體進(jìn)行全局開發(fā)，從而實(shí)現(xiàn)種群間的信息交流和協(xié)同進(jìn)化。具體流程為：用種群II中的最優(yōu)個(gè)體同種群I中的最差個(gè)體進(jìn)行交換。

（九）局部再優(yōu)化

通常，求解CVRP問(wèn)題所得結(jié)果均須采取其他措施進(jìn)一步優(yōu)化。文中采用最近鄰插入方法[20]對(duì)求解所得最好解的各個(gè)子路徑進(jìn)行再優(yōu)化，以此尋找比當(dāng)前更優(yōu)的解。最近鄰插入方法是一種改進(jìn)的局部搜索算法，通過(guò)反轉(zhuǎn)每條子路徑來(lái)實(shí)現(xiàn)結(jié)果的優(yōu)化，對(duì)進(jìn)化完成后生成的最好解對(duì)應(yīng)的各子路徑進(jìn)行順序調(diào)整。

最近鄰插入法流程如下。

Step1：取配送中心0點(diǎn)為線路的起始點(diǎn);

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

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

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

Step5：重復(fù)Step2～Step4，直到該子路徑上所有客戶都被訪問(wèn)為止;

Step6：重復(fù)Step1-Step5，直到所有子路徑均優(yōu)化完成為止。

四、?算例驗(yàn)證及結(jié)果分析

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

實(shí)驗(yàn)1?選取CVRP算例集Set-B、Set-E、Set-P中16個(gè)算例，表1給出了張曉楠等[21]提出得HSSA和本文DPHGA的計(jì)算結(jié)果，*表示最優(yōu)值。每個(gè)算例重復(fù)計(jì)算20次，其中BKR表示算例給出的當(dāng)前最優(yōu)值，Best、Worst、Average分別表示算法計(jì)算所得最好值、最差值和均值，Dev表示計(jì)算結(jié)果同最優(yōu)值的偏差（Dev=（BKR-Best）/BKR×100%）。

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

實(shí)驗(yàn)2?選取CVRP算例集Set-A中24個(gè)算例，表2給出了對(duì)比Sener[22]和Ng[23]提出的LNS-ACO和EBMC-ABC同本文DPHGA的計(jì)算結(jié)果。每個(gè)算例重復(fù)計(jì)算20次，表2中的符號(hào)含義同表1。

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

如圖2所示，標(biāo)準(zhǔn)遺傳算法（GA）、模擬退火算法（SA）和DPHGA計(jì)算算例A-n37-k5、P-n45-k5、B-n39-k5的收斂曲線對(duì)比。可知SA單獨(dú)計(jì)算CVRP算例時(shí)，在求解到算例的次優(yōu)解之后會(huì)陷入局部最優(yōu)，收斂效果較差;相比于SA，GA收斂速度較快，經(jīng)過(guò)大量迭代計(jì)算后可以逐步提升解的質(zhì)量，但在20次重復(fù)計(jì)算中，很難求解到最優(yōu)值;相對(duì)于SA、GA單獨(dú)計(jì)算而言，?DPHGA收斂曲線平緩，無(wú)早熟及陷入局部最優(yōu)情況出現(xiàn)，三個(gè)案例均在DPHGA迭代700次左右就逼近算例已知全局最優(yōu)解?？梢?，改進(jìn)雙種群混合遺

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

綜上所述，?DPHGA在求解精度、算法穩(wěn)定性等方面均優(yōu)于所對(duì)比的5中算法，是求解CVRP問(wèn)題的有效方法。

五、?結(jié)論

本文提出基于改進(jìn)雙種群混合遺傳算法求解CVRP問(wèn)題。算法采用兩個(gè)種群協(xié)同進(jìn)化的思想，種群II結(jié)合遺傳算法全局搜索性能及移民策略思想進(jìn)行算法的全局搜索及開發(fā)，擴(kuò)大解方案的搜索空間，維持種群的高多樣性;種群I在傳統(tǒng)遺傳算法迭代基礎(chǔ)上，引入模擬退火思想及變鄰域搜索策略，增強(qiáng)算法的局部探索能力。劣勢(shì)種群進(jìn)行全局搜索開發(fā)，精英種群進(jìn)行局部探索，然后兩種群通過(guò)協(xié)同進(jìn)化的機(jī)制極大提高了算法搜索到全局最優(yōu)解的概率。算例驗(yàn)證及分析表明，DPHGA可有效求解CVRP，尋優(yōu)質(zhì)量?jī)?yōu)于對(duì)比算法，今后可進(jìn)一步改進(jìn)該算法，增強(qiáng)算法求解大規(guī)?？蛻羲憷男阅堋?/p>

參考文獻(xiàn)：

[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]?石兆.?物流配送選址—運(yùn)輸路徑優(yōu)化問(wèn)題研究[D].?長(zhǎng)沙：中南大學(xué)，?2014：30-33.

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

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

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

[8]?畢志升，蔡茗芊.?基于多目標(biāo)模擬退火的帶容量限制車輛路徑問(wèn)題[J].?計(jì)算機(jī)與數(shù)字工程，?2017，?45（8）：?1513-1518.

[9]?陳亮，周晶晶.?求解CVRP的改進(jìn)蟻群系統(tǒng)算法[J].?軍事交通學(xué)院學(xué)報(bào)，?2014，?16（5）：?92-95.

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

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

[12]?周和平，陳亮.?求解CVRP問(wèn)題的一種改進(jìn)啟發(fā)式蟻群算法[J].?后勤工程學(xué)院學(xué)報(bào)，?2015，?31（4）：?80-84，89.

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

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

[15]?程子安，童鷹，申麗娟，等.?雙種群混合遺傳算法求解柔性作業(yè)車間調(diào)度問(wèn)題[J].?計(jì)算機(jī)工程與設(shè)計(jì)，?2016，?37（6）：?1636-1642.

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

[17]?易軍，李太福.?求解作業(yè)車間調(diào)度的變鄰域細(xì)菌覓食優(yōu)化算法[J].?機(jī)械工程學(xué)報(bào)，?2012，?48（12）：?178-183.

[18]?張義長(zhǎng)，楊加明，魯宇明.?結(jié)合保優(yōu)策略和移民策略的自適應(yīng)遺傳算法[J].?計(jì)算機(jī)工程與應(yīng)用，?2010，?46（31）：?36-38.

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

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

[21]?張曉楠，范厚明.?混合分散搜索算法求解帶容量約束車輛路徑問(wèn)題[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.