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

張瑞鋒，汪同三

(中國社會科學院數量經濟與技術經濟研究所，北京 100732)

0 引言

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

1 問題的描述及數學模型

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

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

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

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

建立數學模型

(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)

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

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

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

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

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

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

步驟4:對pop2進行交叉和變異操作.

步驟5:計算種群pop2中個體的目標函數值，找出函數值最小的染色體i和這個函數值f，如果f

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

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

(1)優先關系指的是客戶被服務的先后次序.它可以根據起點到各分店的距離確定，也可以根據每個分店的時間窗來確定，還可以通過加權因子由二者共同來確定.在滿足車容量和時間窗的約束前提下，我們有理由訪問與起點0 距離成本較小的客戶.為此，構造下面的評價函數

式中，ω1，ω2,ω3為權重系數，滿足0 ≤ω1，ω2，ω3≤1，且ω1+ω2+ω3=1；式中前兩項分別為：從起點0訪問客戶j的時間窗口左右邊界的絕對差與整個時間窗口寬度的比值，第三項為距離因素，把客戶按照其評價值從小到大的順序進行排列，就得到一個各分店被服務的優先關系.

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

(3)對照優先關系確定的各個基因段，檢查是否車輛容量約束和各個顧客的時間窗口約束，若滿足，則該染色體對應問題的一個可行解，否則，該染色體對應不可行解.

2.3個體的評價對種群中每一個染色體Gh(h=1，2，…，pop_size)，可行化后求得對應的可行解，根據式(1)求得這一可行解對應的目標函數值Zh，若染色體對應不可行解，賦予Zh一個很大的正整數M.令其適應度函數為fh=1/Zh，則fh越大，表明Gh性能越好，對應的解越接近最優解.

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

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

2.6鄰域結構每個染色體的鄰域包括隨機使用兩點交換、2-op交換和3-opt交換.

3 算例比較

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

表1 任務的特征及需求

表3 不同算法的優化結果比較

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

距離0123456780040607590200100160801400654010050751101002606507510010075757537540750100509090150490100100100010075751005200501005010007090756100757590757007010071601107590759070010088010075150100751001000

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

表4 本文中算法在群體規模為80的計算結果

表5本文中算法在群體規模為120的計算結果

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

4 結論

在建立帶時間窗車輛路徑問題的數學模型基礎上，針對遺傳算法因局部搜索能力不強造成尋優效果較差的缺陷，將局部搜索能力很強的模擬退火算法與之結合，從而構造了求解帶時間窗車輛路徑問題的混合遺傳算法.實驗計算結果表明，用混合算法求解帶時間窗的車輛路徑問題，可以在一定程度上克服遺傳算法在局部搜索能力方面的不足和模擬退火算法在全局搜索能力方面的不足，從而得到較好的計算結果，同時混合遺傳算法還具有計算效率較高，計算結果較穩定和魯棒性強的特點，充分顯示了其良好的尋優性能.

[1] 李軍，郭耀煌.物流配送——車輛優化調度理論與方法[M].北京:中國物資出版社，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].計算機集成制造系統，2004，10(3):303-306.

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

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