范昌勝， 郭 強(qiáng)， 岳愛峰

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

0 引 言

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

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

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

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

1.1 數(shù)學(xué)描述

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

1.2 數(shù)學(xué)模型

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

(1)

(2)

(3)

(4)

(5)

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

(6)

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

2 算法設(shè)計(jì)

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

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

2.1 染色體編碼及其對(duì)應(yīng)的解

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

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

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

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

2.2 適應(yīng)值函數(shù)

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

2.3 個(gè)體的選擇

2.4 雜交和變異

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

圖2 一般的單點(diǎn)雜交

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

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

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

圖4 變異

2.5 小生境遺傳算法

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

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

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

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

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

Step 4: 所有個(gè)體適應(yīng)值尺度變換

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

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

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

3 實(shí)例計(jì)算與實(shí)驗(yàn)結(jié)果

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

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

取遺傳代數(shù)Gen_step=200，種群大小Pop_Num=500，選擇概率Pc=0.6，模擬退火初始溫度T=500，計(jì)算得到近似最優(yōu)解70，對(duì)應(yīng)的染色體為：(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 實(shí)例中的運(yùn)輸網(wǎng)絡(luò)和單位費(fèi)用情況

根據(jù)染色體編碼特性，得到3個(gè)基因段，車場基因段：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ù)編碼特征解碼后，得到相應(yīng)的車輛路徑如表2所示.

4 算法比較

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

表2 編碼特征解碼后相應(yīng)的車輛路徑

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

5 結(jié)束語

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

參考文獻(xiàn)

[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].計(jì)算機(jī)工程與應(yīng)用,2004,40(21):82-83.

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

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

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

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

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

[10] 許國平,葉效峰,鮑立威.基于模擬退火遺傳算法車輛問題研究[J].工業(yè)控制計(jì)算機(jī),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.