新型遺傳算法求解車輛路徑問題研究

張瑞鋒，汪同三

(中國(guó)社會(huì)科學(xué)院數(shù)量經(jīng)濟(jì)與技術(shù)經(jīng)濟(jì)研究所，北京 100732)

0 引言

車輛路徑問題[1](Vehide routing problem,VRP)是物流配送優(yōu)化中關(guān)鍵的一環(huán)，也是電子商務(wù)活動(dòng)中不可缺少的內(nèi)容.自1959年Dantzing和Ramser首次提出VRP以來，很快引起運(yùn)籌學(xué)、應(yīng)用數(shù)學(xué)、網(wǎng)絡(luò)分析、圖論及計(jì)算機(jī)應(yīng)用等學(xué)科的專家與運(yùn)輸計(jì)劃制定者和管理者的極大重視.歷經(jīng)多年的研究發(fā)展，衍生出多種不同類型的問題.VRP一般定義為：對(duì)一系列發(fā)貨點(diǎn)和/或收貨點(diǎn)，組織適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過它們，在滿足一定的約束條件(如貨物需求量、發(fā)送量、交發(fā)貨時(shí)間、車輛容量限制、行駛里程限制及時(shí)間限制)下，達(dá)到一定的目標(biāo)(如路程最短、費(fèi)用最小、時(shí)間盡量少及使用車輛盡量少).由于VRP已被證明是一個(gè)NP難題[2]，求解該問題高效的精確算法存在的可能性不大，為此專家們主要將精力用于構(gòu)造高質(zhì)量的啟發(fā)式算法上.比知一些學(xué)者嘗試了用一般啟發(fā)式算法、神經(jīng)網(wǎng)絡(luò)、遺傳算法、禁忌搜索及模擬退火等智能化啟發(fā)式算法，均取得了較好的結(jié)果[3-4].但是，這些算法在求解問題時(shí)都存在“早熟收斂”、搜索效率低和求解速度慢的問題.針對(duì)遺傳算法的不足，本文中通過將模擬退火的思想引入遺傳算法，并對(duì)交叉和變異后的個(gè)體實(shí)施接收策略，不但能有效地緩解遺傳算法的選擇壓力，并且能增強(qiáng)遺傳算法的全局收斂性，克服其易限于局部最優(yōu)的缺陷.實(shí)驗(yàn)結(jié)果表明該算法具有較強(qiáng)的尋優(yōu)性能和較快的收斂速度，得到的優(yōu)化結(jié)果也更接近最優(yōu)解.

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

車輛路徑問題的一般描述為：有一個(gè)中心倉庫，擁有K輛車，容量為q，有L個(gè)客戶點(diǎn)，其需求為gi(i=1，2，…，L)，且gi≤q，頂點(diǎn)集為V={1，2，…，L}，求滿足貨運(yùn)需求的總最短行車路線.

根據(jù)不同的約束，VRP有多種不同類型，從上述描述中可知，該問題是車輛數(shù)固定的單車場(chǎng)單車型非滿載車輛路徑問題.用cij表示從點(diǎn)i到點(diǎn)j的運(yùn)輸成本，其含義可以是距離、費(fèi)用及時(shí)間等，設(shè)配送中心編碼為0，客戶編碼為1，2，…，L，定義變量

(i)xijk=1,表示車輛k由客戶i行駛到客戶j，xijk=0表示否定；

(ii)yik=1,表示客戶i的任務(wù)由車輛k完成，yik=0表示否定.

建立數(shù)學(xué)模型

(1)

(2)

(3)

(4)

(5)

xijk=0或1，i，j=1，2，…L，k=1，2，…，K

(6)

yik=0或1，i=1，2，…，L，k=1，2，…，K

(7)

其中，目標(biāo)式(1)保證總成本Z最??；式(2)為車輛的容量約束，式(3)保證每個(gè)客戶點(diǎn)的運(yùn)輸任務(wù)僅由一輛車來完成，而所有的運(yùn)輸任務(wù)則由K輛車共同完成,式(4)和式(5)保證每個(gè)客戶能且只能被一輛車服務(wù)一次.

2 求解問題的遺傳模擬退火算法

遺傳模擬退火算法(genetic simulated annealing algorithm， GSAG)是遺傳算法和模擬退火算法相結(jié)合的一種優(yōu)化方法.它既具有遺傳算法的全局性和并行性，又具有模擬退火算法的局部搜索能力和退火特征，將這兩種算法結(jié)合起來所構(gòu)成的遺傳模擬退火算法使得遺傳算法的搜索性能得到極大改進(jìn).具體分為5個(gè)步驟.

步驟1:給定種群規(guī)模pop_size，k=0；初始溫度tk=t0，為了算法的效率t0=(最大成本-最小成本)/(pop_size/2)，產(chǎn)生初始種群pop(k)；對(duì)初始種群計(jì)算目標(biāo)值，找出函數(shù)值最小的染色體i和這個(gè)函數(shù)值f，記min=i,s*=f.

步驟2:若滿足結(jié)束條件則停止計(jì)算，輸出最優(yōu)染色體min和最優(yōu)解s*；否則，在染色體i的鄰域N(i)中隨機(jī)選取一個(gè)狀態(tài)，按模擬退火中的接受概率接受或拒絕j，共迭代pop_size次選出新種群pop1.

步驟3:在pop1(k+1)中計(jì)算適應(yīng)度函數(shù)fitness(tk)=1/fi(tk)，然后采用改進(jìn)的比例選擇策略進(jìn)行染色體的選擇.將在pop1(k+1)中的染色體按fitness(tk)值排序，將值最大的染色體復(fù)制一個(gè)直接進(jìn)入下一代，下一代種群中剩下的pop-1個(gè)染色體用輪盤選擇法產(chǎn)生.這樣首先可以保證最優(yōu)個(gè)體可以生存到下一代，既給了適應(yīng)度較大的個(gè)體以較大的機(jī)會(huì)進(jìn)入下一代，又避免了個(gè)體間因適應(yīng)值不同而被選入下一代的機(jī)會(huì)懸殊.最后形成種群pop2.

步驟4:對(duì)pop2進(jìn)行交叉和變異操作.

步驟5:計(jì)算種群pop2中個(gè)體的目標(biāo)函數(shù)值，找出函數(shù)值最小的染色體i和這個(gè)函數(shù)值f，如果f

2.1染色體結(jié)構(gòu)出于表示簡(jiǎn)單，計(jì)算機(jī)處理方便的目的，本文中擬采用自然編碼.問題的解向量可編成一條長(zhǎng)度為N的染色體(c1，c2，…，cN)，其中基因ci為[1，N]之間的一個(gè)互不重復(fù)的自然數(shù).隨機(jī)產(chǎn)生一組互不相同的pop_size個(gè)染色體作為第一代種群.

2.2可行化過程將染色體的編碼向量映射為滿足全部約束條件的可行解的過程，稱可行化過程.具體過程：

(1)優(yōu)先關(guān)系指的是客戶被服務(wù)的先后次序.它可以根據(jù)起點(diǎn)到各分店的距離確定，也可以根據(jù)每個(gè)分店的時(shí)間窗來確定，還可以通過加權(quán)因子由二者共同來確定.在滿足車容量和時(shí)間窗的約束前提下，我們有理由訪問與起點(diǎn)0 距離成本較小的客戶.為此，構(gòu)造下面的評(píng)價(jià)函數(shù)

式中，ω1，ω2,ω3為權(quán)重系數(shù)，滿足0 ≤ω1，ω2，ω3≤1，且ω1+ω2+ω3=1；式中前兩項(xiàng)分別為：從起點(diǎn)0訪問客戶j的時(shí)間窗口左右邊界的絕對(duì)差與整個(gè)時(shí)間窗口寬度的比值，第三項(xiàng)為距離因素，把客戶按照其評(píng)價(jià)值從小到大的順序進(jìn)行排列，就得到一個(gè)各分店被服務(wù)的優(yōu)先關(guān)系.

(2)在一個(gè)染色體中，按照從左到右的順序，滿足優(yōu)先關(guān)系的基因段確定一個(gè)車輛路徑，例如8個(gè)顧客的優(yōu)先關(guān)系為1 2 3 4 5 6 7 8，則s：3 1 4 7 2 8 5 6這個(gè)染色體，共有4個(gè)基因段滿足優(yōu)先關(guān)系，它們分別是：(3)，(1 4 7)，(2 8)和(5 6).因此s表示使用的車輛數(shù)為4.其中ω1=0.4，ω2=0.4，ω3=0.2，優(yōu)先關(guān)系為3-8-1-7-5-4-6-2.

(3)對(duì)照優(yōu)先關(guān)系確定的各個(gè)基因段，檢查是否車輛容量約束和各個(gè)顧客的時(shí)間窗口約束，若滿足，則該染色體對(duì)應(yīng)問題的一個(gè)可行解，否則，該染色體對(duì)應(yīng)不可行解.

2.3個(gè)體的評(píng)價(jià)對(duì)種群中每一個(gè)染色體Gh(h=1，2，…，pop_size)，可行化后求得對(duì)應(yīng)的可行解，根據(jù)式(1)求得這一可行解對(duì)應(yīng)的目標(biāo)函數(shù)值Zh，若染色體對(duì)應(yīng)不可行解，賦予Zh一個(gè)很大的正整數(shù)M.令其適應(yīng)度函數(shù)為fh=1/Zh，則fh越大，表明Gh性能越好，對(duì)應(yīng)的解越接近最優(yōu)解.

2.4染色體的交叉在每代種群中，以一定的交叉概率對(duì)染色體進(jìn)行交叉操作，在此引入一種新穎的交叉算子，這種交叉算子的最大特點(diǎn)是當(dāng)兩父代相同時(shí)，仍能產(chǎn)生新的個(gè)體，這就減弱了對(duì)種群多樣性的要求，能夠有效地避免傳統(tǒng)遺傳算法“早熟收斂”的缺點(diǎn)，這是以往交叉算子所不具備的.舉例說明其操作：隨機(jī)在父代個(gè)體中選擇一個(gè)交配區(qū)域，如兩父代個(gè)體及交配區(qū)域選定為：A=51|2438|679，B=96|1243|578；將B的交配區(qū)域加到A的前面，A的交配區(qū)域加到B的前面，得：A′=1243|512438679，B′=2438|961243578；在A′B′中自交配區(qū)域后依次刪除與交配區(qū)相同的自然數(shù)，得到最終的兩個(gè)體為124358679，243896157.與其他交叉方法相比，這種方法在兩父代個(gè)體相同的情況下仍能產(chǎn)生一定的變異效果，這對(duì)維持種群的多樣性有一定的作用.

2.5染色體變異物種變異的可能性較小，所以在遺傳算法中變異操作只起輔助作用，對(duì)每代種群以一定概率變異.變異的策略是隨機(jī)產(chǎn)生兩變異點(diǎn)，將變異段逆轉(zhuǎn)得新個(gè)體.

2.6鄰域結(jié)構(gòu)每個(gè)染色體的鄰域包括隨機(jī)使用兩點(diǎn)交換、2-op交換和3-opt交換.

3 算例比較

本文中討論的問題中有8個(gè)顧客和1個(gè)服務(wù)中心，各顧客的需求量、服務(wù)時(shí)間、各顧客要求的服務(wù)時(shí)間范圍由表1給出，服務(wù)中心與各分店間的距離由表2給出.這些顧客由容量為8噸的車輛完成服務(wù)，要求合理安排車輛的行駛路線，使總的運(yùn)距最短.在計(jì)算過程中，設(shè)置GSAG算法的進(jìn)化代數(shù)為300，每組計(jì)算次數(shù)為50，并同文獻(xiàn)[5]中的分派啟發(fā)式算法的結(jié)果進(jìn)行了比較.具體結(jié)果見表3.

表1 任務(wù)的特征及需求

表3 不同算法的優(yōu)化結(jié)果比較

表2分店及分店與配送中心的距離

距離0123456780040607590200100160801400654010050751101002606507510010075757537540750100509090150490100100100010075751005200501005010007090756100757590757007010071601107590759070010088010075150100751001000

通過表3可以得出，提出的遺傳模擬退火算法在求解VRPTW問題時(shí)，求得的最優(yōu)解行駛成本比文獻(xiàn)[5]中的分派式啟發(fā)式算法少13.7%，這說明本文中的算法求解質(zhì)量較高；通過表4可以得出，算法在群體規(guī)模為80時(shí)得到最優(yōu)解的概率在78%以上，這可以說明本文中算法具有較強(qiáng)的克服陷入局部最優(yōu)的能力.通過表5可以得出，算法在群體規(guī)模為120時(shí)得到最優(yōu)解的概率為94%以上，并且在交叉概率為0.8，變異概率為0.2時(shí)，得到最優(yōu)解的概率為100%.通過表3和表4的平均搜索時(shí)間，還可以得出算法的收斂速度較快.

表4 本文中算法在群體規(guī)模為80的計(jì)算結(jié)果

表5本文中算法在群體規(guī)模為120的計(jì)算結(jié)果

變異概率交叉概率0.60.70.8平均搜索時(shí)間/s0.1049/049/045/00.1549/048/050/02.900.2048/047/050/0

4 結(jié)論

在建立帶時(shí)間窗車輛路徑問題的數(shù)學(xué)模型基礎(chǔ)上，針對(duì)遺傳算法因局部搜索能力不強(qiáng)造成尋優(yōu)效果較差的缺陷，將局部搜索能力很強(qiáng)的模擬退火算法與之結(jié)合，從而構(gòu)造了求解帶時(shí)間窗車輛路徑問題的混合遺傳算法.實(shí)驗(yàn)計(jì)算結(jié)果表明，用混合算法求解帶時(shí)間窗的車輛路徑問題，可以在一定程度上克服遺傳算法在局部搜索能力方面的不足和模擬退火算法在全局搜索能力方面的不足，從而得到較好的計(jì)算結(jié)果，同時(shí)混合遺傳算法還具有計(jì)算效率較高，計(jì)算結(jié)果較穩(wěn)定和魯棒性強(qiáng)的特點(diǎn)，充分顯示了其良好的尋優(yōu)性能.

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

[2] Laporte G.The vehicle routing problem:an overview of exact and approximation algorithms[J].European Journal of Operational Research， 1992，5 (9):345-358.

[3] 趙燕偉，吳斌，蔣麗，等.車輛路徑問題的雙種群遺傳算法求解方法[J].計(jì)算機(jī)集成制造系統(tǒng)，2004，10(3):303-306.

[4] 肖健梅，李軍軍，王錫淮.求解車輛路徑問題的改進(jìn)微粒群優(yōu)化算法[J].計(jì)算機(jī)集成制造系統(tǒng)，2005，11 (4):577-581.

[5] 鄒彤，李寧，孫德寶.不確定車輛數(shù)的有時(shí)間窗車輛路徑問題的遺傳算法[J].系統(tǒng)工程理論與實(shí)踐，2004，24(6):134-138.