羅曉明

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

0 引言

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

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

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

其中：

滿足的約束條件如下：

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

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

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

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

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

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

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

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

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

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

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

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

若fitness(i)≤averagefitness：

否則：

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

第四步，遺傳操作。

(1)選擇

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

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

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

①交叉概率的定義

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

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

②交叉算子

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

圖1 交叉方式示例

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

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

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

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

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

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

第六步，算法終止判斷。

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

3 實驗結(jié)果及分析

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

表2 三種算法對10個測試實例的20次計算結(jié)果

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

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

4 結(jié)束語

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

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

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

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

[4] 汪祖柱,程家興,方宏兵等.車輛路徑問題的混合優(yōu)化算法[J].運籌與管理,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] 張麗萍,柴躍廷.車輛路徑問題的改進遺傳算法[J].系統(tǒng)工程理論與實踐,2002,(8).