VRPSTW的混合改進蟻群優化算法

摘 要:軟時間窗車輛路徑問題(VRPSTW)是VRP的一種重要擴展類型，定義了其懲罰函數并建立數學模型。設計用于求解該問題的混合改進型蟻群算法并求解標準數據庫中的緊時間窗實例。經過大量數據測試，獲得了較好的效果，并驗證了蟻群算法用于求解軟時間窗車輛路徑問題的成功實現。

關鍵詞:軟時間窗車輛路徑問題; 蟻群算法; 懲罰函數

中圖分類號:O223 文獻標志碼:A

文章編號:1001-3695(2010)03-0845-04

doi:10.3969/j.issn.1001-3695.2010.03.010

Hybrid improved ant algorithm for VRPSTW

CUI Xue-li1， MA Liang2

(1.Dept. of Logistics Management， College of Economy Management， Suzhou University of Science Technology， Suzhou Jiangsu 215011， China; 2.Dept. of Management Science Technology， College of Management， University of Shanghai for Science Technology， Shanghai 200093， China)

Abstract:Vehicle routing problem with soft time windows is a very important extended type of vehicle routing problem. This paper defined penalty function and established mathematical model of VRPSTW. Designed a hybrid improved ant algorithm for solving this problem and solved some Solomon instances with hard time windows. Computational experiments show that this approach is promising in good performances and verify the success of applying ant algorithm in solving vehicle routing problem with soft time windows.

Key words:VRPSTW(vehicle routing problem with soft time windows); ant algorithm; penalty function

帶時間窗的車輛路徑問題(vehicle routing problem with time windows，VRPTW)[1]是目前人們普遍研究的VRP的一種擴展類型，它是在VRP的基礎上增加了客戶要求訪問的時間窗口，即給定每個客戶一個時間范圍，車輛對客戶的服務時間必須在這個范圍內開始。時間窗問題其實又有硬時間窗和軟時間窗之分[2]。在以往的文獻中，提到的時間窗問題如果沒有特別說明，通常都是指硬時間窗車輛路徑問題。

VRPSTW，即軟時間窗車輛路徑問題[3]，它允許車輛對客戶開始服務的時間早于客戶允許的最早開始時間或晚于客戶允許的最遲開始時間，但是要給予一定的懲罰。緊時間窗不僅對服務造成很大的局限性，還會因為嚴格遵守時間窗的限制而增加車輛數導致總費用的增加。軟時間窗這種服務方式雖然增加了一定的懲罰費用，但如果能夠節省車輛，以此來減少人力、物力，則最終的總費用反而有可能減少。近年來人們對VRP、VRPTW等這些經典車輛路徑問題的研究非常多，而目前在國內外公開發表的文獻中對VRPSTW的研究和求解還很少。

VRPTW也已被證明為NP-難題，歷年來對其算法的研究主要集中在各種智能化啟發式算法上。Koskosidis等人[4]、Balakrishnan[5]、Taillard[6]、Ioannou等人[3]曾先后提出VRPSTW的一些實際性定義以及應用禁忌搜索法、最近鄰算法等對其進行求解，得到了一系列的結果。

蟻群算法是受自然界中真實蟻群行為的啟發而產生的一種模擬進化算法[7]，其基本思想就是對真實蟻群協作過程的模擬，每只螞蟻在候選解的空間中獨立搜索解，并在所尋得的解上留下一定的信息素。解的性能越好螞蟻留在其上的信息素越多，而信息素越多的解被再次選擇的可能性也越大。在算法的初級階段，所有解上的信息素相同，隨著算法的推進，較優解上的信息素逐漸增加，算法最終收斂到最優解或近似最優解。蟻群算法目前已被擴展應用到許多問題領域中[8~13]，近幾年很多學者將其應用于VRP[14~17]、VRPTW等問題的求解，也獲得了很好的效果。本文在蟻群算法思想的基礎上，結合線路改進算法中的幾種鄰域局部改進機制設計了VRPSTW的求解算法，計算Solomon問題庫中的實例獲得了很好的效果，并與VRPTW結果進行了比較和分析。

1 問題描述

VRPSTW的一般提法[3]為:已知有一批客戶，每個客戶點的位置坐標和貨物需求已知，每輛車都從起點(depot)出發，完成運送任務后再回到起點。每個客戶只被訪問一次，每輛車所訪問的需求總和不能超過車輛的負載能力。給每個客戶i一個正常服務時間窗口[ei，li]，如果車輛早于ei或者晚于li到達客戶i，則由客戶給定一個允許服務提前開始的時間lbvi或者允許延遲開始的時間ubvi，但必須以給予客戶一定的賠償為條件。問題的最終目標是以最少的總費用完成所有任務，車輛在這些時間內進行服務的情況如圖1所示。

根據VRPSTW定義，現假設懲罰量是違反時間量的線性函數[5]，則懲罰函數可定義為

cei:車輛早于時間ei到達客戶i的單位懲罰數;

cli:車輛晚于時間li到達客戶i的單位懲罰數;

Pi:懲罰函數。

假設sei為對客戶i服務的開始時刻，則懲罰函數Pi的公式為

Pi=∞if sei

cei(ei-sei)iflbvi≤sei

0ifei≤sei≤li

cli(sei-li)ifli

∞ifubvi

其中:系數cei和cli可以根據客戶的重要程度或者對時間要求的苛求性來取值。比如有些特別緊急的、對時間要求比較苛刻的客戶，其費用系數可能相對較大，由此來體現時間窗對目標函數的影響。從懲罰函數公式可以看出，等待時間越長懲罰費用就越高，因此限制等待時間可以間接減少懲罰費用。這里設定一個最大等待時間wtmax，使得

sei-(sei+si+tij)≤wtmax

2 數學建模

首先對模型中的常量和變量進行簡要說明:D為車輛的載重量;di為顧客i的需求量;cij為從顧客i行駛到顧客j的距離;sei為對客戶i服務的開始時刻;sli為對客戶i服務的終止時刻;tij為車輛從客戶i到客戶j的行駛時間;tcij為車輛從點i到點j的費用系數;zk為車輛的參與費用。

變量定義以及數學模型如下:

yki=1 點i的顧客需求由車輛k完成0 其他

xijk=1 車輛k從點i行駛到點j0 其他

min Z=∑i∑j∑ktcijxijk+∑j∑kzkx0jk+∑iPi

s.t.

∑idiyki≤Dk(1)

∑kyki=1i∈V(2)

∑ixijk=ykjj∈V，k(3)

∑jxijk=ykii∈V，k(4)

∑i，j∑∈S×Sxijk≤|S|-1SV(5)

sli+tij≤seji，j∈V，k(6)

lbvi≤sei≤ubvii∈V(7)

xijk，yki∈(0，1)i，j∈V，k

其中:|S|為集合S中所含圖G的頂點個數;約束式(1)為車輛負載限制;式(2)保證每輛車對每個客戶只能訪問一次;式(3)~(5)是為了保證能形成回路;式(6)表示一條線路上兩鄰接任務存在的條件;式(7)為時間窗約束，目標為總費用最少。

3 算法設計

3.1 蟻群算法基本設置

ηij為邊弧(i，j)的能見度(visibility)，即1/cij(cij為點i與j間的距離);τij為邊弧(i，j)的軌跡強度(intensity);rij為車輛從i點走到j點，到達時間與客戶允許的服務最遲開始時間的時間差;wij為車輛從i點走到j點，在j點的等待時間。

位于i處的螞蟻k移至鄰域中節點j處概率為

Pkij=[τij]α#8226;[ηij]β#8226;[rij]γ#8226;[wij]θ

∑l[τil]α#8226;[ηil]β#8226;[ril]γ#8226;[wil]θ

其中:α、β、γ、θ分別為各變量的相對重要性。

上述轉移概率中，經典的蟻群算法只有ηij和τij兩個變量，本文結合時間窗問題的特性又增加了反映車輛的等待時間wij和與時間窗上限的時間差rij這兩個因素的變量。后面經過大量的實驗證明，對轉移概率公式的改進使得求解效果確實得到了很大的改善。

3.2 線路改進算法

為了對所求得結果的線路進一步優化，本文采用蟻群算法與局部改進鄰域搜索算法相結合產生的混合改進型算法。下面分別通過簡單圖示來解釋這幾種算法:

a)2-opt搜索。對給定的初始回路解，通過每次交換兩條邊來進行改進，如圖2所示。

b)邊替換搜索(edge-exchange)，即從任意多條路線中取任意多條邊進行替換的操作，如圖3所示。

c)點重新定位搜索(relocation)，即點的剝離(unstringing)和點的插入(insertion)，如圖4所示。

在求解過程中，可針對具體情況采用上述三種局部改進搜索方法對初始解進行改進。

3.3 λ-soft問題

VRPSTW是基于違反時間窗的客戶的多少不同的一種多維問題。比如，根據允許5%、10%、15%的客戶違反時間窗，可以生成三種不同類型的問題集。因此，應用到實際中，根據不同數量的客戶允許服務的提前或延遲不同以及他們對賠償要求的不同，可以生成多種不同的VRPSTW問題。為了能夠清晰的描述問題類型和性質，下面先來看一個定義。

定義 設λ-soft問題為所有客戶當中的前面λ%位客戶允許時間窗被違反，即服務可提前或延遲時的一種問題類型。

這樣，一個λ-soft問題至少有(100-λ)%的客戶不允許違反最初的時間窗要求，因此λ的取值也直接影響著最終的結果。實際應用中可以根據具體情況和要求來確定λ的值。

3.4 基本符號及含義

為了方便描述算法步驟，先給出程序中要用到的一些主要參數和變量的定義:n為節點數;max_capacity為車輛的載重量;demand[i]為點i的需求量;capacity為車輛上剩余貨物的重量;early[i]為客戶i允許的服務最早開始時間;last[i]為客戶i允許的服務最遲開始時間;waita[i， j]為車輛完成i點任務后從i點到達j點，在j點的等待時間;waitb[i， j]為車輛完成i點任務后到達j點的時間與客戶j要求的服務最遲開始時間的時間差;d[i， j]為車輛從i點走到j點所需要的時間;w[i，j]為點i與點j之間的距離;delta[i， j]為邊弧(i， j)上的單位長度軌跡信息素數量;finish[k]為車輛k完成i點任務后到達j點的時間;route[k，i]為第k輛車的路徑;penalty為違反時間窗要求的懲罰費用;max_pemalty為最大懲罰費用;lower_bound[i]為客戶允許服務提前開始的時間;upper_bound[i]為客戶允許服務延遲開始的時間。

3.5 算法流程

function PValue//計算轉移概率子程序

for l=2 to n do 計算waitb[i， l]，waita[i， l]

if (capacity>=demand[l]) and (滿足時間窗口) then 計算轉移概率PValue

procedure AntMove//尋找路徑子程序

初始化變量

select: //判斷某點是否滿足要求

while j<=n do

selected = random(n)+1 //在剩余點中隨機選取

finish[k] = finish[k] + d[i， selected]

//從上一點服務結束時間到運行到該點時間

if (滿足時間窗口) and (滿足載重量限制) then 計算等待時間; index = selected //符合條件被放入路徑中的點

if (random

//按照轉移概率限制選擇下一點

if 路徑結束 then goto next

Check: //記錄滿足要求的點

if finish[k]< lower_bound [index] then

//車輛到達時間早于客戶允許的最早開始時間

if lower_bound [index]<>early[index] then

//若客戶屬于所有客戶中的前面λ%位客戶

計算違反時間窗的車輛數

if 等待時間>0 then penalty = penalty+ lower_bound [index] - early[index]

else penalty = penalty+ lower_bound [index] - finish[k]

if finish[k]> upper_bound [index] then

//車輛到達時間晚于客戶允許的最遲開始時間

計算違反時間窗的車輛數

penalty = penalty + finish[k]- upper_bound [index]

route[k， i] = selected //將符合條件的點放入路徑中

更新finish[k]; capacity = capacity - demand[selected]

//計算車輛的剩余載重量

n= n-1; if n>=1 then goto select

next: //增加下一條路徑

k= k+1;capacity = max_capacity;

goto Select

記錄總車輛數

procedure ThreeModel //信息素軌跡強度更新子程序

for k=1 to m do

case model of

1: for l=1 to count[k] do delta[ii， jj] = delta[ii， jj] + q/len[k]

/*count[k]為第k輛車經過的節點數;螞蟻圈(ant-cycle)模型，Q為體現螞蟻所留軌跡數量的常數*/

2: for l=1 to count[k] do delta[ii， jj] = delta[ii，jj]+q

//螞蟻密度(ant-density)模型

3: for l=1 to count[k] do delta[ii， jj]=delta[ii， jj]+q/w[ii， jj]

//螞蟻數量(ant-quantity)模型

更新軌跡強度

begin //主程序

輸入數據，初始化

Loop:

for j =1 to lambda+1 do

early[j]=lower_bound[j]- max_penalty

last[j]=upper_bound[j]+max_penalty//放寬前λ位客戶時間窗口

for j =lambda+2 to n do

early[j] = lower_bound [j]

last[j] = upper_bound[j]

Antmove //螞蟻移動(尋找路徑)

TwoOpt//應用局部改進算法進一步優化結果

計算路長;比較保留非劣解

ThreeModel //信息素軌跡強度更新

count = count +1

if count

輸出非劣解

lambda =lambda+10 //λ的值每次增加10個單位

if lambda

end

算法采用Delphi 7.0編程實現，在PC機上Windows 2000環境下運行通過。

4 實例求解與分析

由于VRPSTW沒有現成的測試數據庫，采用Solomon的標準測試問題。在C1、C2、R1、R2、RC1、RC2六類問題中，R1和RC1的時間窗約束很緊(只有10個時間單位)，同時車輛的載重量只有200，即每條路徑的客戶點數較少而路徑數量相對較多，因此通常都選擇R1和RC1作為VRPSTW的問題測試實例。這樣，在允許放寬時間窗的情況下，相對其他幾類問題，對結果產生的影響比較大。

蟻群算法中的參數取值，經過大量實驗發現，當α=1，β=2，γ=1，θ=2時結果最好。

為了驗證算法的有效性，這里求解R1所有測試實例，取Pmax=23，wtmax=Pmax[3]。同時，為了計算方便，系數cli和cei均取1，λ的初始值取為10。在實際問題的求解中可以根據具體情況和要求而定。表1給出R1的求解結果，同時給出VRPTW的結果以供比較。

表1 R1的VRPSTW求解結果

probitemVRPSTWvalueVRPTW value

R101

車輛數201918171615141321

違反的時間窗口數512273647566471

懲罰費用681661893775697899231257

R102

車輛數201918171615141321

違反的時間窗口數616243344556674

懲罰費用9721626740857772510111436

R103

車輛數1312111014

違反的時間窗口數7162844

懲罰費用63222381496

R104

車輛數1211109813

違反的時間窗口數515234266

懲罰費用91207306423870

R105

車輛數15141312111016

違反的時間窗口數81724476277

懲罰費用882122945488091330

R106

車輛數13121110914

違反的時間窗口數415213642

懲罰費用70184299420505

R107

車輛數1110912

違反的時間窗口數132647

懲罰費用232394617

R108

車輛數11109812

違反的時間窗口數8131637

懲罰費用129247303535

R109

車輛數13121114

違反的時間窗口數71436

懲罰費用110243478

R110

車輛數12111013

違反的時間窗口數81746

懲罰費用111209572

R111

車輛數12111013

違反的時間窗口數83142

懲罰費用160447620

R1112

車輛數1110912

違反的時間窗口數61731

懲罰費用101299541

由表1看出，可以通過少量的違反時間窗而達到減少車輛的效果。比如R101中，用VRPTW求解的結果是所需車輛為21輛，而在VRPSTW中，僅僅對5%的客戶服務提前或延遲即可減少一輛車輛。雖然增加了一定的懲罰費用，但因為車輛數的減少反而可能導致總費用減少。圖5是求解過程中，隨機選取了一個計算過程，部分結果未能列出，在程序運行過程中需要下拉滾動條查看全部結果。

下面給出R1中的一個具體實例結果。

實例:R102，n=100，D=200(即取Solomon問題庫中的實例R102，其中節點數為100，車輛的載重量為200)。分別列出VRPTW和VRPSTW的路徑以及路長以供比較和分析，如表2所示。

表2 R102的VRPTW與VRPSTW結果比較

VRPTWVRPSTW

kLkrouteLkroute

1981，34，30，52，21，78，13，11611，63，99，16，44，58，25，51，1

2941，29，88，55，26，27，11591，64，12，70，31，52，11，33，95，1

3951，28，20，47，49，8，2，51，11491，93，96，43，15，39，87，85，75，94，1

41361，43，45，17，25，22，59，11511，49，34，79，21，2，69，81，27，13，1

5831，93，60，86，99，100，85，18，32，11261，84，17，62，41，22，56，26，55，78，4，1

61031，66，80，56，11571，28，65，91，20，50，14，60，86，1

7921，70，89，36，4，81，11361，29，53，9，5，57，73，76，59，3，1

8951，48，9，84，14，90，96，11591，32，77，82，30，10，36，35，6，1

9921，64，63，19，7，98，38，94，11351，45，92，100，89，7，90，83，61，97，1

101311，46，12，91，67，33，71，53，11581，37，46，98，88，18，71，1

111041，39，44，83，11281，48，19，47，8，67，1

121061，72，10，35，69，3，11061，40，68，24，74，23，42，38，1

131331，37，87，75，76，73，11281，66，72，80，54，101，1

14771，15，16，42，5，1

151401，95，6，77，79，92，97，1

16951，31，82，11，61，1

17581，65，50，1

18551，74，23，101，1

19411，41，54，57，1

20531，40，24，68，1

21481，62，58，1

在對R102的求解結果中，VRPTW所得結果為:車輛數21，車輛總行程1 929。VRPSTW所得結果為:車輛數13，車輛總行程為1 853，總懲罰為1 436。從這些數據來分析，VRPSTW所需車輛比VRPTW減少7輛，總行程減少76，但是增加了1 436的懲罰。

綜上所述，由于時間窗的放寬，最終會引起車輛數、車輛總行程、路徑等的變化，從而導致總費用的變化。當然，單純從上述數字中無法判斷總費用是增加還是減少，因為實例中為了計算方便將各個費用系數均取為1，而實際問題的求解中，決策者可以依據車輛的固定費用、車輛的行駛費用以及顧客要求的懲罰費用等具體的費用系數計算真正的總費用。

5 結束語

軟時間窗車輛路徑問題是在考慮到硬時間窗口對服務造成的不便以及容易引起車輛資源浪費的情況下，對VRPTW的一種改進類型。本文設計了用于求解該問題的改進型蟻群算法，為了檢驗其運行性能，測試實例采用Solomon問題中的緊時間窗問題。模擬計算通過放寬時間窗，車隊的總費用是增加還是減少，應用到現實中可以根據具體費用系數求解，這里只是提供一個求解思想和解決工具，以及對蟻群算法的一個擴展和實施。通過大量實驗證明，用蟻群算法求解VRPSTW是可行的，而且獲得了令人滿意的效果。

參考文獻:

[1]SOLOMON M M. Algorithms for the vehicle routing and scheduling problems with time windows constraints[J]. Operations Research， 1987，3(5):254-265.

[2]李軍， 郭耀煌. 物流配送—車輛優化調度理論與方法[M]. 北京:中國物資出版社， 2001.

[3]IOANNOU G， KRITIKOS M， PRASTACOS G. A problem generator solver heuristic for vehicle routing with soft time windows[J]. Omega， 2003，31(1):41-53.

[4]KOSKOSIDIS Y A， POWELL W B， SOLOMON M M. An optimization-based heuristic for vehicle routing and scheduling with soft time window constraints[J]. Transportation Science， 1992，26(2):69-85.

[5]BALAKRISHNAN N. Simple heuristics for the vehicle routing problem with soft time windows[J]. Journal of the Operational Research Society， 1993，44(3):279-287.

[6]TAILLARD E， BADEAU P， GENDREAU M，et al. A tabu search heuristic for the vehicle routing problem with soft time windows[J]. Trans on Science， 1997，31(2):170-186.

[7]DORIGO M， MANIEZZO V， COLORNI A. Ant system: optimization by a colony of cooperating agents[J]. IEEE Trans on SMC， 1996，26(1):29-41.

[8]馬良， 項培軍. 螞蟻算法在組合優化中的應用[J]. 管理科學學報， 2001，4(2):32-37.

[9]孫新宇， 李剛， 孫林巖. 基于螞蟻算法的工件排序優化[J]. 系統工程理論與實踐， 2003，23(11):20-24，53.

[10]張勇德， 黃莎白. 多目標優化問題的蟻群算法研究[J]. 控制與決策， 2005，20(2):170-173，178.

[11]DORIGO M. Ant colony optimization and swarm intelligence[C]//Proc of Lecture Notes in Computer Science.[S.l.]: Springer-Verlag， 2006.

[12]MOHAMMAD A， MIGUEL M. Application of an ant algorithm for layout optimization of tree networks[J]. Engineering Optimization， 2006，38(3):353-369.

[13]鄭松， 侯迪波， 周澤魁. 動態調整選擇策略的改進蟻群算法[J].控制與決策， 2008，23(2):225-228.

[14]BULLNHEIMER B， HARTL R F， STRAUSS C. An improved ant system algorithm for the vehicle routing problem[J]. Annals of Ope-rations Research， 1999，89:319-328.

[15]崔雪麗， 馬良， 范炳全. 車輛路徑問題(VRP)的螞蟻搜索算法[J]. 系統工程學報， 2004，19(4):418-422.

[16]張建勇， 李軍， 郭耀煌. 具有模糊預約時間的VRP混合遺傳算法[J]. 管理科學學報， 2005，8(3): 64-71.

[17]李相勇， 田彭. 開放式車輛路徑問題的蟻群優化算法[J]. 系統工程理論與實踐， 2008，28(6):81-93.