多車場滿載車輛路徑問題遺傳算法

范昌勝， 郭 強， 岳愛峰

(1.陜西廣播電視大學工程管理部， 陜西 西安 710068；2.西北工業(yè)大學理學院， 陜西 西安 710129； 3.山東師范大學圖書館, 山東 濟南 250014)

0 引 言

VRP(Vehicle Routing Problem)是一個典型的NP-hard問題，屬于經(jīng)典的復雜組合優(yōu)化問題[1].圖1所示為有兩個車場兩個配送中心的車輛路徑問題.研究求解約束條件下VRP問題的有效算法具有現(xiàn)實意義.

一般地，很難找到VRP問題的最優(yōu)解，或者花費很多的時間才可尋找到最優(yōu)解[2].即使在規(guī)模比較小的情況下，求解也比較困難.研究車輛路徑問題(VRP)的方法，有針對小規(guī)模問題的精確算法、啟發(fā)式算法和人工智能優(yōu)化算法[3-12].啟發(fā)式算法在求解車輛路徑問題中占有重要地位.近些年來，模擬退火[12]、遺傳算法[6,10]、禁忌搜索算法[5]、蟻群算法[9]以及它們之間結(jié)合形成的混合算法等仿生學智能優(yōu)化算法[13,15]的興起，為解決VRP 提供了新的工具.禁忌搜索被普遍認為是解決VRP 問題的最快的算法，而遺傳算法則在快速搜索能力和全局最優(yōu)性上有著明顯的優(yōu)勢.本文將問題的數(shù)學模型做了更貼近實際的改進，將模擬退火算法和小生境遺傳算法結(jié)合求解，不僅克服了遺傳算法容易早熟、不穩(wěn)定等缺點，而且可以很好地控制其早熟.在染色體編碼上，與目前出現(xiàn)的編碼方式不同[6]，充分利用車輛路徑問題解的特點，采用分段編碼，使雜交變異方便有效，加快獲得近似最優(yōu)解.

1 完整的問題描述與數(shù)學模型

多車場、多個配送中心、整車配送、多用戶的VRP問題描述：(1)物流配送網(wǎng)絡(luò)是由相互連通的多個車場、多個配送中心和多用戶組成, 車場的車足夠用，配送中心的貨物足夠多；(2)車輛從車場出發(fā)到配送中心裝貨，完成整車配送任務后可返回任意車場；(3)要求完成任務前后每個車場車輛數(shù)目保持不變；(4)優(yōu)化目標為車輛完成所有配送任務的總運輸成本(或路程)最低.

1.1 數(shù)學描述

將車場、配送點、用戶點都視為同一個網(wǎng)絡(luò)上的節(jié)點，并視為連接相鄰兩個節(jié)點之間弧上的權(quán)值，一般網(wǎng)絡(luò)上的多車場多配送中心車輛路徑問題的描述如下：

1.2 數(shù)學模型

根據(jù)問題的描述，建立的數(shù)學模型如下：

(1)

(2)

(3)

(4)

(5)

xij≥0i,j=1,2,…,n

(6)

此模型中，xij表示從節(jié)點i到節(jié)點j的發(fā)車數(shù)目.其中，(1)式是目標函數(shù)，也即所有派出車輛花費的總費用；不等式(2)保證了從車場發(fā)出的車不超過其擁有的車輛數(shù)目；不等式(3)保證配送中心發(fā)出的貨不超過其存放的貨物量；等式(4)要求滿足用戶的貨物需求量；等式(5)保證每個節(jié)點進出的車數(shù)前后保持不變.

2 算法設(shè)計

在運輸網(wǎng)絡(luò)中，為了使總運費最小，從車場派往配送中心、從配送中心到用戶、從用戶返回車場的車輛都會選擇走兩點間的最小費用路.在現(xiàn)有文獻中，幾乎所有的多車場問題都轉(zhuǎn)化為單車場來處理，即對每個車場首先確定它所服務的任務.如sweep算法，根據(jù)就近分配的原則，通過計算每個任務點離車場最近距離與次近距離的比值，按比值從大到小的順序，將任務分派給車場.又如Saving算法，類似TSP的節(jié)約算法，首先將每個點分派給最近的車場，然后根據(jù)節(jié)約值修改初始分派.文獻[11]結(jié)合sweep算法和Saving算法將多車場轉(zhuǎn)化為單車場.

這種轉(zhuǎn)化既不方便，而且當規(guī)模較大時也不易被計算機所操作，因此我們可以在原始運輸網(wǎng)絡(luò)中用Floyd算法求解任意兩點間的最小運送費用，同時在Floyd算法的表中尋找一輛車從節(jié)點i派往節(jié)點j的最小費用路徑，于是我們可以用兩點間的最小費用Sij(元/單位)作為兩點間的運費，兩點之間的運輸路徑就是最小費用路徑.

2.1 染色體編碼及其對應的解

基于此，我們設(shè)計了一個長度為3N的自然數(shù)染色體編碼：前N個基因接收車場發(fā)出車輛的配送中心號碼，接下來的N個基因接收貨物的用戶號碼，最后N個基因接收返回車輛的車場號碼.為了獲得更多的可行解，在編碼中要求對應用戶的N個基因滿足用戶需求，即每個用戶號碼出現(xiàn)的次數(shù)跟它需要的整車貨物數(shù)相等.

圖1 2個車場、2個配送中心、3個用戶的網(wǎng)絡(luò)

對一個有2個車場、2個配送中心、3個用戶的運送網(wǎng)絡(luò)，如果用戶需求向量為(1,1,2)，對染色體(3334 5677 1212)，由車場基因段1212，可知兩個車場發(fā)出的車數(shù)為(2,2)，于是在配送中心段3334中，前2個配送中心(33)接受車場1發(fā)出的車，接下來的2個配送中心(34)接受車場2發(fā)出的車；由配送中心段3334，可知配送中心3和4分別提供3車貨物和1車貨，于是在用戶段5677中，前3個用戶(567)接收配送中心3的貨物，同時用戶7接收配送中心4的貨物.同理可以知道車輛返回車場的情況：用戶5的車返回車場1，用戶6的車返回車場2，用戶7分別向車場1、2返回一輛車.這個分配方案對應模型的一個解，如圖1所示.

這種將同類點放在一個基因段的編碼方法方便了雜交變異操作，在不考慮車數(shù)約束時，任意的一個編碼對應一個車輛運輸方案，使得雜交變異在可行運輸域進行.

2.2 適應值函數(shù)

給定一個個體s，該個體對應一個派送方案，即對應著模型的一個解x(s)，從而對應一個目標函數(shù)值z(x(s)).由于目標函數(shù)是求最小值的，z(x(s))越小的個體，其適應性更強.由于目標函數(shù)不會出現(xiàn)負值，我們可以用z(x(s))的倒數(shù)作為對應的適應值.但有些個體對應的解x(s)不一定是可行解，上例中如果配送中心3只有2個整車的貨物，個體(3334 5677 1212)對應的解不滿足約束(3)，就不是可行解.顯然，非可行解的適應值較小，于是我們可以給它的目標函數(shù)加上一個較大的懲罰函數(shù)M(x(s))，這樣其適應值就相應地變的較小了.

2.3 個體的選擇

2.4 雜交和變異

依據(jù)編碼的特性，在此使用改進的單點雜交方法.當雜交點在車場基因段或配送中心段的時候，采用一般的單點雜交，將兩個父代的染色體在雜交點處交叉，得到兩個子代，如圖2所示.當雜交點在用戶基因段的時候，直接將兩個父代的用戶基因段交換得到兩個子代，如圖3所示.顯然，如果雜交點隨機選取，用戶段交換的概率是比較大的，這樣會使得雜交集中在用戶基因段，對產(chǎn)生新個體不利.因此，減小雜交點在用戶段出現(xiàn)的概率是必要的，根據(jù)試驗，發(fā)現(xiàn)將雜交點在用戶段出現(xiàn)的概率設(shè)為其他基因段的1/3是合適的.

圖2 一般的單點雜交

圖3 父代用戶基因段的交換

模仿生物界變異特點，在進化早期，變異比較頻繁，以后變異概率逐漸變小，趨于穩(wěn)定的小概率.可以取pm=(50×step)-1(step≤20)，到20步的時候就已經(jīng)到了0.001的較小概率，以后就保持這個較小的概率pm=0.001進行變異.

選擇了變異基因位置im后，如果這個位置在用戶基因段，則進行循環(huán)變異，從im處將用戶段基因分開，然后首尾對接構(gòu)成新的基因段；如果im不在用戶段，則直接將im處基因改變，如圖4所示.

圖4 變異

2.5 小生境遺傳算法

為了在進化過程中保持種群個體的多樣性，父代產(chǎn)生的新個體中，適應度比父代高的子代替換父代中適應度低的那個，而不代替其他適應度低的個體，這樣就避免了那些適應度高的個體排擠適應度低的個體，使得種群中隱藏在適應度較低個體中的優(yōu)良基因過早地遺失，而得不到滿意的解，因為最優(yōu)解有可能從兩個適應度低的個體雜交得到.

根據(jù)以上分析，該問題的算法步驟如下：

Step 1: 給定遺傳代數(shù)Gen_N，種群大小Pop_N，選擇概率Ps，雜交概率Pc，變異概率Pc.

Step 2: 隨機選取Pop_N個個體構(gòu)成初始種群，計算每個個體的適應值，令step=1.

Step 3: 若step≥Gen_N，當前適應值最大的個體作為近似最優(yōu)解；否則轉(zhuǎn)Step 4.

Step 4: 所有個體適應值尺度變換

然后用輪盤賭方法以概率Ps選擇個體作為父代個體，轉(zhuǎn)Step 5.

Step 5: 對選擇的父代按2.4的方法雜交變異，得到新的種群，轉(zhuǎn)Step 6.

Step 6:計算新種群的適應值，令step=step+1，轉(zhuǎn)Step 3.

3 實例計算與實驗結(jié)果

按照上述算法，在一個有12個節(jié)點的網(wǎng)絡(luò)中，表1給出了車場停車數(shù)目、配送中心存放的貨物數(shù)和每個用戶點需要的貨物數(shù)，圖5給出了原始運輸網(wǎng)絡(luò)的連接狀況和相鄰兩節(jié)點間的單車行駛費用，尋找最優(yōu)運送方案.

表1 實例中的配送網(wǎng)絡(luò)

取遺傳代數(shù)Gen_step=200，種群大小Pop_Num=500，選擇概率Pc=0.6，模擬退火初始溫度T=500，計算得到近似最優(yōu)解70，對應的染色體為：(3,5,3,4,3,3,3,5,5,4,11,11,9,8,9,6,10,12,7,7,2,2,1,1,1,1,2,1,1,1).

圖5 實例中的運輸網(wǎng)絡(luò)和單位費用情況

根據(jù)染色體編碼特性，得到3個基因段，車場基因段：2,2,1,1,1,1,2,1,1,1；配送中心基因段：11,11,9,8,9,6,10,12；用戶基因段：3,5,3,4,3,3,3,5,5,4.根據(jù)編碼特征解碼后，得到相應的車輛路徑如表2所示.

4 算法比較

在現(xiàn)有文獻中，幾乎所有的多車場問題都是將多車場轉(zhuǎn)化為單車場來處理，即對每個車場首先確定它所服務的任務.基于單車場的轉(zhuǎn)化處理方法既不方便，而且當規(guī)模較大時也不易被計算機所操作.使用遺傳算法的編碼方式都是基于用戶的編碼方式，沒有考慮到車場的匹配，更沒有考慮車場和配送中心分離的情況.

表2 編碼特征解碼后相應的車輛路徑

本文設(shè)計的遺傳算法中，初始基因都是有效解，并且后續(xù)雜交變異得到的新基因也是有效解，具有更好的健壯性；無序的雜交方式和隨機點的基因變異，保證了種群的多樣性；雜交選擇方式?jīng)Q定了算法的收斂性.這3個方面保證了本算法在可行解的集合內(nèi)收斂于最優(yōu)解.

5 結(jié)束語

本文利用小生境遺傳算法同時結(jié)合模擬退伙算法，成功解決了多車場多用戶整車配送問題.求解過程中為了克服普通遺傳算法早熟或不收斂的缺點，制定了特別的染色體編碼方案，設(shè)定了合適的適應值函數(shù)，設(shè)計了新的選擇進化方案.實例證明該算法可以很好地解決整車MDVRP問題.在實際操作中，運送的貨物不一定是整車，而且用戶還會有特別的要求，如配送車輛有最大配送距離約束和容量約束；配送車輛有多種車型，每種車型容量不同；每個配送對有服務時間窗約束，要求配送車輛在時間窗內(nèi)到達客戶點等要求；這就使得問題變得更復雜，有待于更進一步的研究.

參考文獻

[1] Hipolito, Hernandez Perez. A branch-and-cut algorithm for a traveling salesman problem with pick-up and delivery[J].Discrete Applied Mathematics, 2004, 145(1): 126-139.

[2] Toth P,Vigo D. Exact solution of the vehicle routing problem[M]. Fleet Management and Logistics. Dordrecht:Kluwer,1998:1-31.

[3] Gillett B E，Miller L R.A heuristic algorithm for the vehicle dispatch problem[J].Operations Research，1974，22(2)：340-349.

[4] 鄒 彤,李 寧. 多車場車輛路徑問題的遺傳算法[J].計算機工程與應用,2004,40(21):82-83.

[5] 鄧 欣,朱征宇,曾凡超.多車場車輛路徑問題的單親遺傳算法[J].交通與計算機2007,1(25):31-47.

[6] 陳新莊,郭 強. 多車場滿載車輛路徑優(yōu)化算法[J].計算機工程與設(shè)計, 2008,29(22):5 866-5 871.

[7] 陳美軍,張志勝,陳春詠,等. 多車場車輛路徑問題的新型聚類蟻群算法[J].中國制造業(yè)信息化,2008,37(11) :1-5.

[8] 屈 援,汪 波,鐘石泉. 單車場多送貨點車輛路徑問題的改進遺傳算法[J].計算機工程與應用,2007, 43(25): 237-239.

[9] 張思偉.單車場多送貨點車輛調(diào)度優(yōu)化的一種改進禁忌算法[J].工業(yè)工程,2006,9 (3):55-58.

[10] 許國平,葉效峰,鮑立威.基于模擬退火遺傳算法車輛問題研究[J].工業(yè)控制計算機,2004,17(6):49-50.

[11] H. Paessens. The savings algorithm for the vehicle routing problem[J]. European Journal of Operational Research，1998,34(3):336-344.

[12] Guo. Z.G, Mac K L. A heuristic algorithm for the stochastic vehicle routing problems with soft time windows[C].Proc of the 2004 Congress on Evolutionary Computation，CEC2004，Portland，2004：1 449-1 456.