求解VRP的變種群規(guī)?；旌献赃m應遺傳算法

羅曉明

（華東交通大學 經濟管理學院，南昌 330013）

0 引言

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

1 VRP問題及其數學模型

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

其中：

滿足的約束條件如下：

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

2 混合遺傳算法的設計

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

第一步，編碼及產生初始群體。

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

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

第二步，計算適應度函數。

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

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

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

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

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

若fitness(i)≤averagefitness：

否則：

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

第四步，遺傳操作。

(1)選擇

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

(2)自適應交叉操作

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

①交叉概率的定義

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

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

②交叉算子

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

圖1 交叉方式示例

(3)自適應變異操作

變異操作是指以較小的概率將染色體中的某些基因值用其他可能的基因值來替換，從而形成新的個體。變異操作用來維持群體的多樣性，防止出現早熟現象。本文同時采用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)產生隨機數r，若r＜pm，則發(fā)生變異。

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

遺傳算法是一種全局優(yōu)化算法，其局部搜索能力較弱，而C-W節(jié)約啟發(fā)式算法則具有較強的局部搜索能力。C-W節(jié)約啟發(fā)式算法的基本思想是首先把各個客戶單獨與車場相連，構成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ōu)先連接s(i,j)值大的點i和點j，如此根據節(jié)約值的大小，將所要服務的客戶依次連入行車路線，使問題得到解決。

第六步，算法終止判斷。

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

3 實驗結果及分析

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

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

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

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

4 結束語

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

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

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

[3] 周明,孫樹東.遺傳算法原理及應用[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).