車輛數目未知的帶時間窗口的車輛路徑混合遺傳算法＊

曹二保 湯春華

(湖南大學經濟與貿易學院1) 長沙 410079) (湖南涉外經濟與貿易學院商學部2) 長沙 410205)

車輛路徑問題(vehicle routing problem, VRP)由Dantzing[1]于1959年提出,屬于經典的復雜組合優化問題.而VRPTW問題是在VRP問題的基礎上加上時間窗口約束,它是強NP難題[2],對它的求解主要集中在啟發式算法上.本文提出了一種求解VRPT W問題的混合優化算法,遺傳算法(genetic algorithm)[3]和鄰域搜索算法(neighborhood search)[4]是求解VRP問題的常用方法.鄰域搜索算法求解速度快,但容易陷入局部最優解,因而解的質量不高;而遺傳算法具有較好的全局搜索能力,可以用極快的速度達到最優解的90%左右,要真正達到最優解則需要花費很長時間,同時遺傳算法的設計有時比較復雜;基于鄰域搜索的混合遺傳算法是綜合了遺傳算法和鄰域搜索算法各自優勢的全局搜索算法,它既具有遺傳算法的全局搜索能力,又有高效的局部搜索能力,使兩種算法的優勢得到互補.

1 問題描述及數學模型

帶時間窗口的車輛路徑問題(VRPTW)的一般表述為：配送中心擁有相同容量的K輛車,車的最大負荷為q,現有n個顧客的運輸任務需要完成,設V={1,2,…,k},C={1,2,…,n},N= {0,1,2,…,n+1},0和n+1表示配送中心,第i個顧客的需求量為di(i=1,2,…,n)且有max di≤q,完成顧客i的任務需要的時間為T,且任務i必須在時間窗口[ai,bi]內完成.ai為任務i的最早開始時間,bi為允許最遲開始時間.若車輛到達顧客i的時間早于ai,則車輛需在i處等待,如果到達時間晚于bi,則任務將被延遲,每個顧客能且只能由一輛車一次完成運送任務,每輛車從配送中心出發完成運送任務后最終都回到配送中心,最終目標有兩個：(1)所使用的汽車數目最少;(2)所使用的汽車總的運輸距離最短.其中：第一目標高于第二目標,也就是說,需要更少數目車的解總比需要更多車的解要好,而不管第二目標的值如何.這主要是由于多派一輛汽車的成本較大的緣故.tij為汽車從客戶i到客戶j的行駛時間(正比于i和j之間的歐幾里得距離dij);sik為汽車k開始為客戶i服務的時間,令s0k=0,如果汽車k沒有為客戶i服務,則sik沒有任何意義.變量 xijk=

則VRPTW的數學模型可以表示為

在上述表達式中：式(1)為使需要的汽車數目最少;式(2)為使所有的汽車走過的路程(時間)最短;式(3)為每個客戶僅能被訪問一次;式(4)為被調用的汽車都滿足負載要求;式(5)～(7)保證每輛汽車從出發點出發,訪問客戶后,最終回到出發點;式(8)為汽車k在從客戶i向客戶j行駛的過程中,在時間sik+Ti+tij之前不能到達客戶j,其中M是一個較大的標量;式(9)為汽車為客戶i服務的開始時間必須在其時間窗口內;式(10)為最大距離約束,dij為顧客i到顧客j的距離,L為每輛車行駛的距離上限;式(11)為整數化的約束.該模型通用性很強,經過參數的不同設定,可以將其轉換為其他組合優化問題的數學模型.例如,設定ai=0,bi=M(是一個很大的數),則可以把約束式(8)和(9)去掉,這樣VRPTW模型就變成了普通的VRP模型;如果只提供一輛汽車,則該問題就是TSP;如果有多輛汽車可利用,且附加條件t0,j=1,?j∈C和tij=0,就得到了裝箱問題的數學模型.

2 編碼

采用比較直觀的自然數編碼,用矢量(l1,l2,…,ln)表示染色體G.其中,元素(基因)l1為[l,n]之間的一個互不重復的自然數,隨機產生一組染色體Gh(h=1,2,…,k).其中：k為每一代種群中的個體數目,即為種群規模,Gh各不相同,它為第一代種群.首先根據經驗對完成配送任務可能需要的車輛數目進行設定,設為m,對于某個個體,設其對應的配送路徑方案的配送路徑條數與m之差為J,若配送路徑條數不超過m,則取J=0,表示該個體對應一個可行解;然后將m的取值逐一減小,直到減小m后不能得到滿足所有約束的可行解;此時m即為最小的車輛數目;若配送路徑條數大于m,則J＞0,表示該個體對應一個不可行解).若設定的m只有不可行解,將m的取值逐一增大,直到增大m后能得到滿足所有約束的可行解.設個體的目標函數值為Zh,將J看成該個體對應的配送路徑方案的不可行路徑條數,并設對每條不可行路徑的懲罰權重為pw(該權重可根據目標函數的取值范圍取一個相對較大的正數),根據式(2)可以得到該個體的目標函數值Zh,若染色體對應不可行解,則其適應值函數為越大,表明Gh的性能越好,對應的解越接近最優解.

3 VRPTW的混合遺傳算法

3.1 遺傳操作

采用比例選擇和精華模型相結合的選擇策略.將每代種群k個染色體按 fh值排序 ,將 fh值最大的染色體復制一個直接進入下一代.下一代種群中剩下的k-1個染色體用輪盤選擇法產生.這樣,可以保證最優個體可以生存到下一代 ,既給了適應度較大的個體較大的機會進入下一代,又避免了個體間因適應值不同而被選入下一代的機會懸殊.本文設計了一種新的前置交叉算子.用9個頂點為例說明交叉原理：設P1={1 2 3 |4 5 6 7|8 9};P2={4 5 2|1 8 7 6 |9 3}.其中：|表示交叉點,子個體按以下方式確定——取P2中的2個交叉點中間的點放在子代C1的開始處,其狀態暫時為C1={1 8 7 6 X X X X X}.對未確定的位置X,在P1中找到暫時沒有在C1中出現的離6最近的點3,將3放在6的后面,從左到右將P1中未出現的點移到C1中,最后C1為{1 8 7 6 3 4 5 9

2}.前置交叉操作過程如圖1所示.

圖1 交叉操作

給定2個相同的染色體,經過新的交叉算子仍然可以產生不同于父體的新個體 ,這就是說 ,由于新穎交叉算子的引入 ,當個體都相同時 ,仍然能夠進行迭代進化 ,繼續尋找問題的優化解 ,跳出了局部最優解 ,克服了“早熟收斂”的缺點.而以往的交叉算子 ,當個體都相同時無法繼續迭代進化 ,只能尋找到問題的局部最優解.如則經過新的交叉算子后兩個子代為{1 8 7 6 3 4 5 2 9}.

3.2 鄰域搜索算法

本文主要考慮的鄰域結構有 NS={Nswap,},經過交叉操作后用作為變異操作, Nswap是隨機互換染色體中的2個基因,Ninversion隨機逆轉染色體中的基因.具體操作過程如圖2、圖3所示.

圖2 互換操作

圖3 逆轉操作

4 基于鄰域搜索的混合遺傳算法

按照前文所述的方法產生初始種群S,種群規模視客戶數量來確定,在進行遺傳操作過程中,結合了約束檢驗機制,即無論是交叉還是變異操作,每當新的個體產生的時候都要檢驗是否滿足相關約束,如最大行使時間、容量、時窗等,若滿足則保留,否則棄之.選擇操作執行的是比例選擇和精華模型相結合的選擇策略,具體算法步驟如下.

步驟1 i=0,pi為空集.pi用來保存每代中的最好解.

步驟2 產生某代初始群體si.

步驟3 計算適應度,若滿足最優準則,則轉步驟8.

步驟4 執行選擇操作,i=i+1.

步驟5 以一定的概率進行交叉操作和變異操作.

步驟6 產生當前最好解.

步驟7 對當前最好解進行鄰域搜索中的逆轉操作,將改善的當前解保存于pi中,轉步驟3.

步驟8 pi中的最優個體即為問題的解或近似解.

5 算例分析

有8個分店和1個配送中心,各分店的需求量為di(單位：t).服務時間Ti(單位：h)以及分店要求的服務時間范圍[ai,bi],由表 2給出.這些分店由容量為8 t的車輛完成配送 ,汽車的行駛速度設為50 km/h,配送中心與各分店間的距離(單位：km),由表1給出.要求合理安排車輛的行駛路線,使總的車輛數目和總的行使距離最短[5-7].

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

表2 任務的特征及需求

表3 運行500次的平均計算結果

運用Matlab語言對上述混合遺傳算法進行編碼,設置遺傳算法的種群規模為40,交叉概率為0.9,變異概率為0.1,使用Pentium 4,3.06 GHz微機運行程序,分10次實驗得到迭代500次的算法的平均結果如表3(其中標準差為計算10次的結果),得到的最好結果如圖4所示.

運行500次后得到的40條染色體表現為相同的配送方案,達到最優解的概率為100%,最終結果為：總的路徑長度為910 km,使用3輛車完成配送任務,其中第一輛車的配送線路為：0-8-5-7-0,離開配送中心時的實際裝載量為7 t,滿載率為87.5%,路徑長度為405 km..第二輛車的配送線路為：0-6-4-0,離開配送中心時的實際裝載量為7 t,滿載率為87.5%,路徑長度為265 km.第三輛車的配送線路為：0-3-1-2-0,離開配送中心時的實際裝載量為8 t,實現滿載,路徑長度為240 km.本文的算法與其他優化算法找到的最好結果比較如表5.

圖4 經過500次迭代后的運行結果

表5 本文算法與其他優化算法的最好結果比較

此外,用本文的算法來優化[8]中的算例,在種群規模為40,進化300代后,無時間窗時需要的車輛數目為2,最優路徑長度為655 km,最優行駛方案為：0-1-3-5-8-0;0-2-6-7-4-0;運行時間為1.625 0 s,且達到最優解的概率為100%.帶時間窗口時,在種群規模為40,進化500代后,需要的車輛數目為3,最優路徑長度為910 km,最優行駛方案為：0-8-5-7-0;0-6-4 -0;0-3-1-2-0;且運行時間為5.781 0 s.

由上述比較分析可知,本文的基于鄰域搜索的混合遺傳算法在求解質量、求解速度、解的穩定性等方面明顯優于其他算法.

6 結束語

運用本文提出的基于鄰域搜索的混合遺傳算法求解帶時間窗口的車輛路徑問題,能使完成配送任務所需的車輛數目和總路徑長度得到同時優化,該算法既具有遺傳算法的全局搜索能力,又具有鄰域搜索算法的局部搜索能力,實驗結果表明該算法具有很強的尋優能力,具有較強的克服陷入局部最優的能力,算法的求解質量高,具有較快的收斂速度,減少問題的約束后,該算法同樣能有效求解它們.

[1]Dantzing G,Ramser J.The truck dispatching problem[J].Management Science,1959,10(6)：80-91.

[2] Savelsbergh M.Local search for routing problem with time windows[J].Annals of Operations Research,1985,16(4)：285-305.

[3] Potvin J Y,Bengio S.The vehicle routing problem with time windows——part II：genetic search[J]. INFORMS Journal on Computing,1996,8(2)：165-172.

[4] Liu Fuhhwa,Shen Shengyuan.A route-neighborhood-based metaheuristic for vehicle routing problem with time windows[J].European Journal of Operational Research,1999,118(3)：485-504.

[5]李 軍.車輛調度問題的分派啟發式算法[J].系統工程理論與實踐,1999,117(1)：27-33.

[6]李 寧,鄒 彤,孫德寶.帶時間窗車輛路徑問題的粒子群算法[J].系統工程理論與實踐,2004,24(4)： 130-135.

[7]李 軍.有時間窗車輛路線安排問題的啟發式算法[J].系統工程,1996,14(5)：45-50.

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