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

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

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

一、引言

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

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

二、建立模型

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

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

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

三、改進(jìn)遺傳算法

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

（一）編碼

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

（二）種群初始化

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

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

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

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

Step 2：從中隨機(jī)選擇一個(gè)正切值作為初始掃描射線，進(jìn)行順時(shí)針掃描;

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

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

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

2.最近鄰插入法

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

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

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

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

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

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

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

（三）適應(yīng)度函數(shù)計(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ù)式（11）計(jì)算適應(yīng)度函數(shù)值。

（四）遺傳算子

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

1.選擇策略

首先，利用非線性輪盤賭策略任意選擇一個(gè)個(gè)體abi;然后，通過(guò)個(gè)體相似度值來(lái)進(jìn)行個(gè)體之間相似性的評(píng)價(jià)，選擇與個(gè)體abi相似性最大的個(gè)體abj進(jìn)行后續(xù)的交叉操作。

（1）輪盤賭選擇

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

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

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

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

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

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

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

3.變異策略

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

（五）移民策略

遺傳算法在進(jìn)化過(guò)程中，種群中的個(gè)體會(huì)趨于相似，種群的多樣性會(huì)急劇下降，產(chǎn)生了遺傳算法早熟收斂現(xiàn)象，算法過(guò)早地收斂于局部最優(yōu)解，此時(shí)，交叉和變異操作很難使得算法跳出局部最優(yōu)解。為了改變算法的早熟收斂現(xiàn)象，通過(guò)設(shè)定閾值判定當(dāng)算法達(dá)到早熟收斂狀態(tài)時(shí)，采用“移民策略”引入外部個(gè)體，替換部分適應(yīng)度值較大的個(gè)體，以此打亂群體結(jié)構(gòu)來(lái)增加種群多樣性，從而進(jìn)一步增強(qiáng)種群搜索能力。由于種群多樣性的減少主要體現(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è)算后獲得。

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

本文選取容量約束車輛路徑問(wèn)題算例集中的SetA、SetB、SetE、SetP部分算例對(duì)改進(jìn)遺傳算法（I-GA）進(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è)置為：種群規(guī)模NP等于所求算例的規(guī)模數(shù);迭代次數(shù)為MaxGen=1000;種群交叉概率PcA=0.9;種群變異概率PmB=0.1;早熟收斂判斷閾值經(jīng)測(cè)算，取值為E=1.0e-14，不滿足約束個(gè)體的適應(yīng)度函數(shù)懲罰值M0=50。圖7給出了改進(jìn)遺傳算法求解算例E-n22-k4和A-n32-k5的配送線路圖以及進(jìn)化迭代曲線。

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

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

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

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

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

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

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

五、結(jié)論

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

參考文獻(xiàn)：

[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ùn)輸路徑優(yōu)化問(wèn)題研究[D].長(zhǎng)沙：中南大學(xué)，2014.

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

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

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

[10]趙燕偉，吳斌，蔣麗，等.車輛路徑問(wèn)題的雙種群遺傳算法求解方法[J].計(jì)算機(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]李陽(yáng)，范厚明.求解帶容量約束車輛路徑問(wèn)題的混合變鄰域生物共棲搜索算法[J].控制與決策，2018，33（7）：1190-1198.

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

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

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

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

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