羅曉明

（華東交通大學(xué) 經(jīng)濟(jì)管理學(xué)院，南昌 330013）

0 引言

車(chē)輛路徑問(wèn)題(VRP)是物流系統(tǒng)優(yōu)化領(lǐng)域一個(gè)著名的優(yōu)化問(wèn)題。一般意義上的VRP指帶有容量約束的車(chē)輛路徑問(wèn)題(CVRP)：服務(wù)于一個(gè)中心出發(fā)點(diǎn)的最小費(fèi)用(如距離、時(shí)間等)路徑，每個(gè)顧客只能被服務(wù)一次；而且一輛車(chē)服務(wù)的顧客數(shù)不能超出它的裝載能力。其包含兩個(gè)著名的組合優(yōu)化問(wèn)題，即裝箱問(wèn)題(BPP)和旅行商問(wèn)題(TSP)。VRP至Dautzig和Ramser于1959年首次提出以來(lái)，由于其極強(qiáng)的實(shí)踐背景，引起眾多學(xué)者的廣泛關(guān)注[1]。按求解該問(wèn)題的方法角度來(lái)分，大致可分為如下幾類(lèi)研究：精確算法、啟發(fā)式算法、智能優(yōu)化算法和計(jì)算機(jī)仿真等。精確算法是指可求出最優(yōu)解的算法，包括動(dòng)態(tài)規(guī)劃法、分枝定界法及切平面法等，但精確算法的計(jì)算量隨問(wèn)題規(guī)模的增大而呈指數(shù)增長(zhǎng)，因此只適用于小規(guī)模問(wèn)題[2]。啟發(fā)式算法一般基于算法設(shè)計(jì)者經(jīng)驗(yàn)構(gòu)造，用來(lái)求解相應(yīng)問(wèn)題的滿意解，啟發(fā)式算法的優(yōu)點(diǎn)是能快速地得到滿意解，因此常用于NP難題的求解中。傳統(tǒng)啟發(fā)式算法主要有節(jié)約算法、最鄰近算法、兩階段法及其相互結(jié)合而成的混合算法等。眾多VRP求解的研究中，遺傳算法由于其適用范圍廣、魯棒性強(qiáng)、隱含并行性等優(yōu)良特性而受到學(xué)者們的廣泛關(guān)注。本文擬設(shè)計(jì)出一種求解VRP的變種群規(guī)模的混合自適應(yīng)遺傳算法，一方面，引入可變的種群規(guī)模函數(shù)控制種群規(guī)模的變化；另一方面，提出一種改進(jìn)的自適應(yīng)遺傳算法，算法中的自適應(yīng)交叉概率和變異概率考慮了每代個(gè)體中不同適應(yīng)度對(duì)算法的作用，這兩個(gè)參數(shù)隨算法的進(jìn)化而自動(dòng)調(diào)整。同時(shí)，為彌補(bǔ)遺傳算法局部搜索能力差的不足，本文還將C-W節(jié)約啟發(fā)式算法與變種群規(guī)模的自適應(yīng)算法相結(jié)合，構(gòu)造出一種新的混合算法，以解決物流配送的車(chē)輛路徑問(wèn)題。

1 VRP問(wèn)題及其數(shù)學(xué)模型

VRP問(wèn)題可描述如下：以容量為Wk的k輛車(chē)從一個(gè)中心倉(cāng)庫(kù){0}將物品運(yùn)到n個(gè)需求點(diǎn)，每個(gè)需求點(diǎn)的物品需求量為gi，i=1,2,…,n；設(shè)cij為從節(jié)點(diǎn)i到j(luò)的距離，與貨物重量無(wú)關(guān)；要求車(chē)輛以總運(yùn)輸距離最小為目標(biāo)來(lái)完成運(yùn)輸任務(wù)，則其數(shù)學(xué)模型為

其中：

滿足的約束條件如下：

其中式(4)表示每輛車(chē)運(yùn)送的貨物量不超出其載重量；式(5)表示每個(gè)需求點(diǎn)必須有且只需一輛車(chē)送貨；式(6)表示若客戶點(diǎn)j由車(chē)輛k送貨，則車(chē)輛k必從某點(diǎn)i到達(dá)點(diǎn)j；式(7)表示若客戶點(diǎn)i由車(chē)輛k送貨，則車(chē)輛k送完該點(diǎn)的貨后必達(dá)到另一個(gè)點(diǎn)j。

2 混合遺傳算法的設(shè)計(jì)

遺傳算法的一般步驟為：首先是針對(duì)要解決的問(wèn)題設(shè)計(jì)染色體編碼方案；然后根據(jù)編碼方案生成初始群體，并在一定的條件下(比如在規(guī)定的進(jìn)化代數(shù)之內(nèi))進(jìn)行遺傳操作[11]。其中，遺傳算子主要包括選擇、交叉、及變異三種，選擇算子的作用是根據(jù)個(gè)體的適應(yīng)度選擇種群中的優(yōu)良個(gè)體進(jìn)入下一代種群；交叉算子在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法；變異運(yùn)算是產(chǎn)生新個(gè)體的輔助方法，它決定了遺傳算法的局部搜索能力，同時(shí)保持種群的多樣性。由于遺傳算法局部搜索能力較弱，本文在遺傳算法中融入C-W節(jié)約啟發(fā)式算法以改善其局部搜索能力，算法步驟如下。

第一步，編碼及產(chǎn)生初始群體。

運(yùn)用遺傳算法求解VRP問(wèn)題首先要解決的是編碼問(wèn)題。一個(gè)解的編碼稱(chēng)為一個(gè)染色體，組成編碼的元素稱(chēng)為基因。本文采用自然數(shù)編碼方式，設(shè)計(jì)染色體為V={vi}(i=1,2,…,n)，其中vi表示染色體中的基因，對(duì)應(yīng)于第i個(gè)客戶號(hào)。假設(shè)問(wèn)題中所需車(chē)輛數(shù)為k，則問(wèn)題解可表示為k條對(duì)應(yīng)配送子路線，每條子路線由若干需求點(diǎn)所形成的一個(gè)排列表示，且每個(gè)需求點(diǎn)只能出現(xiàn)在其中的一條子路徑中。

按照上述編碼規(guī)則，染色體的形成包括兩個(gè)階段，第一階段為需求點(diǎn)序列的形成；第二階段為將該序列可行化，即在滿足車(chē)輛容量約束的前提下劃分子路徑[4]。根據(jù)文獻(xiàn)[4]，首先將隨機(jī)產(chǎn)生需求點(diǎn)的排列形成集合S，S中元素的個(gè)數(shù)按初始種群規(guī)模確定。然后，對(duì)于集合S中的任一元素s，按照車(chē)輛的容量及s中的各需求點(diǎn)的商品需求量，將s劃分成若干個(gè)子序列(即子路徑，子路徑數(shù)不超過(guò)k)，這些子路徑可構(gòu)成為問(wèn)題的一個(gè)可行解的染色體個(gè)體。例如對(duì)一個(gè)具有5輛車(chē)(每輛車(chē)的容量均為W)、10個(gè)需求點(diǎn)(商品需求量分別為gi,i=1,2,…,10)的 VRP 問(wèn)題，假定s為{2,4,6,1,10,9,8,5,3,7}，若g2+g4+g6≤W且g2+g4+g6+g1＞W(wǎng)，則按照上述方法產(chǎn)生的個(gè)體的第一個(gè)子路徑為{2,4,6}，同樣按照該方法產(chǎn)生的子路徑為{1,10}、{9,8}、{5,3,7}，因此最終產(chǎn)生的一個(gè)染色體個(gè)體為{2,4,6}，{1,10}，{9,8}，{5,3,7}。在接下來(lái)的遺傳操作后，均按上述第二階段的可行化方案進(jìn)行可行化操作。

第二步，計(jì)算適應(yīng)度函數(shù)。

適應(yīng)度函數(shù)的定義一般根據(jù)求解問(wèn)題的目標(biāo)函數(shù)而定，當(dāng)適應(yīng)度函數(shù)確定后，自然選擇規(guī)律是按照適應(yīng)度的大小決定的概率分布來(lái)確定哪些染色體適應(yīng)生存，哪些被淘汰。生存下來(lái)的染色體通過(guò)遺傳操作而產(chǎn)生新的種群。對(duì)種群中每一個(gè)染色體，首先進(jìn)行可行化操作得到對(duì)應(yīng)的可行解，然后根據(jù)式(1)求得相應(yīng)的目標(biāo)函數(shù)值Zh，結(jié)合已有相關(guān)文獻(xiàn)及多次試驗(yàn)結(jié)果，確定其適應(yīng)度函數(shù)為fh=1/Zh，fh越大則表示Zh性能越好，對(duì)應(yīng)的解越接近最優(yōu)解。

第三步，確定種群規(guī)模。

眾多學(xué)者對(duì)于種群規(guī)模的確定進(jìn)行了研究，如Goldberg[13,14]對(duì)最優(yōu)種群規(guī)模進(jìn)行了理論的分析，Arabas等[15]討論了變種群規(guī)模遺傳算法。變種群規(guī)模遺傳算法中，種群規(guī)模由如下公式確定：

其中，popsize(t)代表第t代種群的規(guī)模；auxpopsize(t)=ρ×popsize(t)，ρ為繁殖率，一般取ρ為0.4；D(t)代表每代中死亡個(gè)體的個(gè)數(shù)。下面說(shuō)明D(t)的確定方法。

引入D(t)的目的是為了控制子種群的快速增長(zhǎng)，為確定D(t)，必須對(duì)個(gè)體設(shè)置兩個(gè)相關(guān)的參數(shù)：一個(gè)是個(gè)體的年齡age(i)，另一個(gè)是個(gè)體的壽命lifetime(i)。個(gè)體每存活一代則年齡age(i)加1，其存活的代數(shù)不能超其壽命值lifetime(i)，壽命值lifetime(i)與個(gè)體的適應(yīng)度有關(guān)，高適應(yīng)度的個(gè)體壽命較長(zhǎng)，低適應(yīng)度的個(gè)體壽命則較短，個(gè)體的壽命值一旦確定則不再改變。當(dāng)個(gè)體的滿足時(shí)age(i)＞lifetime(i)，個(gè)體死亡，由此來(lái)確定D(t)的取值。其中，壽命值lifetime(i)的確定比較關(guān)鍵，必須使適應(yīng)度較好的個(gè)體具有較長(zhǎng)的壽命，從而限制適應(yīng)度低于平均水平的個(gè)體的發(fā)展，因此可定義如下。

若fitness(i)≤averagefitness：

否則：

公式中minLT和maxLT是允許的最小和最大的壽命，按照arabas等[15]的建議，本文取 minLT=1，maxLT=7；minfitness和maxfitness是當(dāng)前群體最小和最大的適應(yīng)度，averagefitness代表當(dāng)前群體的平均適應(yīng)度。

第四步，遺傳操作。

(1)選擇

本文采用輪盤(pán)選擇及精英保留的選擇策略。將每代種群中的染色體按適應(yīng)度f(wàn)h排序，適應(yīng)度值最大的染色體直接進(jìn)入下一代，下一代種群中剩下的染色體用輪盤(pán)選擇法生成。這樣可保證最優(yōu)個(gè)體可以生存到下一代，既給了適應(yīng)度較大的個(gè)體較大的機(jī)會(huì)進(jìn)入下一代，又避免了個(gè)體間因適應(yīng)度值不同而被選入下一代的機(jī)會(huì)懸殊[16]。

(2)自適應(yīng)交叉操作

交叉操作是指按較大的概率從交配池中選擇兩個(gè)個(gè)體，交換兩個(gè)個(gè)體的某個(gè)或某些基因，從而形成兩個(gè)新的個(gè)體。這包括交叉概率的定義和交叉算子的選擇兩個(gè)方面。

①交叉概率的定義

根據(jù)要進(jìn)化個(gè)體的不同適應(yīng)度選擇不同的交叉概率，適應(yīng)度高的個(gè)體，選擇較小的交叉概率；適應(yīng)度低的個(gè)體選擇較大的交叉概率。這樣，能使交叉概率隨適應(yīng)度自動(dòng)改變，保護(hù)高適應(yīng)度的對(duì)應(yīng)的解盡可能地進(jìn)入下一代。同時(shí)，對(duì)于種群中各個(gè)體適應(yīng)度趨于一致或趨于局部最優(yōu)時(shí)，有較大交叉概率，避免進(jìn)入局部最優(yōu)。定義交叉概率函數(shù)如下：

其中，pc1和pc2取(0,1)之間的合適的值，一般取pc1為0.9，pc2為 0.6。確定交叉概率 pc后，由系統(tǒng)產(chǎn)生隨機(jī)數(shù)r，若 r＜pc，則交叉。

②交叉算子

交叉算子是遺傳算法區(qū)別于其它進(jìn)化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個(gè)體的主要方法，決定了遺傳算法的全局搜索能力。本文引入一種新的前置交叉遺傳算子，其中兩父串相同時(shí)仍能產(chǎn)生新的個(gè)體，這樣削弱了對(duì)群體多樣性的要求，能夠有效地避免傳統(tǒng)遺傳算法“早熟收斂”的缺點(diǎn)，在實(shí)驗(yàn)中也顯示了優(yōu)良的效果。其操作如下：任意給定兩個(gè)染色體A和B，首先在A和B中分別隨機(jī)地產(chǎn)生兩個(gè)交叉點(diǎn)，然后將每個(gè)染色體的交叉段移到對(duì)方染色體的首部得到染色體A1和B1，最后后消去相同項(xiàng)得到兩個(gè)新個(gè)體A2和B2。圖1可說(shuō)明其操作過(guò)程，并且可看出，當(dāng)染色體相同時(shí)，該交叉算子仍然可以產(chǎn)生不同于父體的新個(gè)體，從而有效地克服“早熟收斂”的缺點(diǎn)。

圖1 交叉方式示例

(3)自適應(yīng)變異操作

變異操作是指以較小的概率將染色體中的某些基因值用其他可能的基因值來(lái)替換，從而形成新的個(gè)體。變異操作用來(lái)維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。本文同時(shí)采用2-OPT法和2-Exchange法進(jìn)行變異操作。其中，2-OPT法是指任取同一子路徑上的兩個(gè)客戶點(diǎn)i和j互換位置；2-Exchange法是對(duì)2-OPT法的擴(kuò)展，指從不同的兩條子路徑中分別選取兩個(gè)客戶點(diǎn)i和j互換位置。變異概率按如下公式確定：

其中，pm1和 pm2取(0,1)之間的合適的值，一般取pm1為0.1，pm2為0.001。確定變異概率pm后，由系統(tǒng)產(chǎn)生隨機(jī)數(shù)r，若r＜pm，則發(fā)生變異。

第五步，用C-W節(jié)約啟發(fā)式算法優(yōu)化子路徑。

遺傳算法是一種全局優(yōu)化算法，其局部搜索能力較弱，而C-W節(jié)約啟發(fā)式算法則具有較強(qiáng)的局部搜索能力。C-W節(jié)約啟發(fā)式算法的基本思想是首先把各個(gè)客戶單獨(dú)與車(chē)場(chǎng)相連，構(gòu)成m條“0-i-0”(i=1,2,…,m)初始化線路，第i條線路的運(yùn)輸距離為ci0；然后把客戶i和客戶j連接在一起，形成線路“0-i-j-0”(i,j=1,2,…,m)，計(jì)算連接后的距離節(jié)約值：

s(i,j)越大，則客說(shuō)明把客戶i和客戶j連接在一起時(shí)總距離節(jié)約值越多，因此應(yīng)優(yōu)先連接s(i,j)值大的點(diǎn)i和點(diǎn)j，如此根據(jù)節(jié)約值的大小，將所要服務(wù)的客戶依次連入行車(chē)路線，使問(wèn)題得到解決。

第六步，算法終止判斷。

若算法執(zhí)行了最大進(jìn)化代數(shù)，則終止，選擇性能最好的染色體所對(duì)應(yīng)的路徑集合作為原VRP問(wèn)題的優(yōu)化解輸出，否則返回第二步。

3 實(shí)驗(yàn)結(jié)果及分析

為驗(yàn)證算法的有效性，本文采用C++語(yǔ)言對(duì)上述混合遺傳算法(VPHAGA)編制了求解程序，并從VRP基準(zhǔn)測(cè)試實(shí)例中隨機(jī)選取10例進(jìn)行了計(jì)算(基準(zhǔn)測(cè)試實(shí)例可從網(wǎng)址http://branchandcut.org/VRP/data下載得到)，實(shí)例相關(guān)描述見(jiàn)表1，每例實(shí)例均計(jì)算20次；本文設(shè)定的初始種群規(guī)模為40；同時(shí)，本文對(duì)文獻(xiàn)[4]介紹的結(jié)合2-opt局部?jī)?yōu)化算法的GA with 2-opt及文獻(xiàn)[8]所介紹的改進(jìn)交叉算子的NGA對(duì)該10例實(shí)例也分別計(jì)算20次，參數(shù)設(shè)置與文獻(xiàn)[4]和文獻(xiàn)[8]完全一致(選擇文獻(xiàn)[4]和文獻(xiàn)[8]所介紹的算法進(jìn)行對(duì)比的原因是這兩個(gè)文獻(xiàn)的計(jì)算結(jié)果較好，具有一定的代表性)；三種算法的最大迭代次數(shù)設(shè)定為1000次，計(jì)算結(jié)果如表2所示。

表2 三種算法對(duì)10個(gè)測(cè)試實(shí)例的20次計(jì)算結(jié)果

由表2可以看出，本文設(shè)計(jì)的變種群規(guī)模混合自適應(yīng)遺傳算法在隨機(jī)選取的10個(gè)實(shí)例上的計(jì)算結(jié)果均優(yōu)于文獻(xiàn)[4]和文獻(xiàn)[8]方法所得的解。在前5例實(shí)例中VPHAGA均能找到已知最好解；在后5例實(shí)例的計(jì)算中，雖然20次的運(yùn)算沒(méi)有達(dá)到已知最好解，但結(jié)果與已知最好解的差距非常微小，相對(duì)誤差最大的是對(duì)大規(guī)模實(shí)例F-n135-k7的求解結(jié)果，但誤差也僅為2.32%。這說(shuō)明本文設(shè)計(jì)的算法的尋優(yōu)能力是有效的。

為測(cè)試算法的穩(wěn)定性，表2給出了20次計(jì)算中求得的解的平均值、最差值和標(biāo)準(zhǔn)差。從表2中可以看出，本文算法求解的平均值及最差值也均優(yōu)于文獻(xiàn)[4]及文獻(xiàn)[8]所介紹的方法；除實(shí)例P-n76-k5，本文算法的標(biāo)準(zhǔn)差均小于文獻(xiàn)[4]及文獻(xiàn)[8]中方法計(jì)算得到的標(biāo)準(zhǔn)差，這一結(jié)果表明利用本文設(shè)計(jì)的算法求解VRP是穩(wěn)定的。另外還可以看到，隨著實(shí)例規(guī)模的增大，VPHAGA的求解標(biāo)準(zhǔn)差并沒(méi)有明顯增大的趨勢(shì)，這表明該算法對(duì)大規(guī)模問(wèn)題的求解也較為穩(wěn)定，具有一定的普適性。

4 結(jié)束語(yǔ)

本文設(shè)計(jì)了一種求解VRP的變種群規(guī)?；旌献赃m應(yīng)遺傳算法。首先，引入一種與進(jìn)化代數(shù)和適應(yīng)度值相關(guān)的變種群規(guī)模函數(shù)來(lái)控制種群規(guī)模的變化；然后，利用改進(jìn)的自適應(yīng)交叉概率函數(shù)和變異概率函數(shù)動(dòng)態(tài)調(diào)整交叉概率和變異概率，這種交叉概率函數(shù)及變異概率函數(shù)均隨個(gè)體適應(yīng)度值的變化而發(fā)生改變。為改善遺傳算法局部搜索能力差的弱點(diǎn)，本文在對(duì)染色體進(jìn)行遺傳操作后，應(yīng)用C-W節(jié)約啟發(fā)式算法對(duì)生成的子路徑進(jìn)行進(jìn)一步的優(yōu)化，充分將遺傳算法的全局搜索能力與節(jié)約算法的局部搜索能力有機(jī)地結(jié)合在一起，做到優(yōu)勢(shì)互補(bǔ)。為證明該算法的有效性，本文從VRP基準(zhǔn)測(cè)試實(shí)例中隨機(jī)選取10例進(jìn)行了計(jì)算，并與已有文獻(xiàn)進(jìn)行了對(duì)比分析，結(jié)果表明本文設(shè)計(jì)的算法具有更好的尋優(yōu)能力及穩(wěn)定性，且對(duì)大規(guī)模VRP問(wèn)題仍具有良好的性能。

[1] 李軍,郭耀煌.物流配送車(chē)輛優(yōu)化調(diào)度理論與方法[M].北京:中國(guó)物資出版社,2001.

[2] Toth,Paolo,Vigo.Exact Algorithm for the Vehicle Routing Problem with Backhauls[J].Transportation Science,1997,31(4).

[3] 周明,孫樹(shù)東.遺傳算法原理及應(yīng)用[M].北京：國(guó)防工業(yè)出版社,2002.

[4] 汪祖柱,程家興,方宏兵等.車(chē)輛路徑問(wèn)題的混合優(yōu)化算法[J].運(yùn)籌與管理,2004,13(6).

[5] Goldberg D E.Optimal Initial Popolation Size for Binary-Coded Genetic Algorithms[R].TCGA Report No.85001,Tuscaloosa,University of Alabama,1985.

[6] Goldberg D E.Sizing Populations for Serial and Parallel Genetic Algorithms[A].Proceedings of the 3rd International Conference on Genetic Algorithms[C].Morgan Kaufmann Publishers,San Mateo,CA,1989.

[7] Arabas J,Michalewics Z,Mulawka J.Gavaps-A Genetic Algorithm with Varing Population Size[A].Proceedings of the First IEEE International Conference on Evolutionary Computation[C].IEEE Service Center,Piscataway,NJ,1994.

[8] 張麗萍,柴躍廷.車(chē)輛路徑問(wèn)題的改進(jìn)遺傳算法[J].系統(tǒng)工程理論與實(shí)踐,2002,(8).