基于改進(jìn)蟻群算法的帶時間窗廢品收集車輛路徑問題

劉　瓊　劉秀城　張超勇　饒運(yùn)清

華中科技大學(xué)數(shù)字制造裝備與技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，武漢，430074

基于改進(jìn)蟻群算法的帶時間窗廢品收集車輛路徑問題

劉瓊劉秀城張超勇饒運(yùn)清

華中科技大學(xué)數(shù)字制造裝備與技術(shù)國家重點(diǎn)實(shí)驗(yàn)室，武漢，430074

建立了以最小化燃油消耗為優(yōu)化目標(biāo)的帶時間窗、司機(jī)休息時間以及多個中轉(zhuǎn)處理中心的廢品收集車輛路徑問題模型。提出了一種改進(jìn)最大最小蟻群算法,針對時間窗特點(diǎn),設(shè)計了兩類滿足時間窗約束的動態(tài)候選列表以提高算法的搜索效率。在最大最小蟻群算法的概率狀態(tài)轉(zhuǎn)移規(guī)則中引入了帶距離限制的最近鄰域搜索。10個基準(zhǔn)實(shí)例中的9個實(shí)例比當(dāng)前文獻(xiàn)的最優(yōu)解更好,從而驗(yàn)證了該模型和算法的可行性和有效性。

大規(guī)模帶時間窗車輛;路徑問題;蟻群算法;燃油消耗

0　引言

有效的廢品收集和處理對保護(hù)環(huán)境和節(jié)約資源有重要的意義。過去針對廢品收集車輛路徑問題,通常都是通過使廢品收集車輛運(yùn)輸時間或運(yùn)輸距離最短,來達(dá)到降低總費(fèi)用的目的,如Sahoo等[1]建立的帶有時間窗、司機(jī)午餐休息時間以及多個中轉(zhuǎn)廢品處理中心的最小化車輛運(yùn)輸時間的廢品收集車輛路徑問題模型和Angelelli等[2]提出的車輛容量不同、多個廢品處理中心的最小化車輛運(yùn)輸距離的多周期廢品收集車輛路徑問題模型。由于車輛運(yùn)輸所產(chǎn)生的運(yùn)輸費(fèi)用直接取決于車輛燃油消耗，而影響車輛燃油消耗費(fèi)用的因素除車輛運(yùn)輸距離外,還涉及車輛載重、車速、道路傾斜度和輪胎狀況等因素[3]。因此,目前車輛路徑優(yōu)化問題中普遍考慮的車輛運(yùn)輸距離或運(yùn)輸時間往往不能準(zhǔn)確反映車輛的實(shí)際運(yùn)輸費(fèi)用,還必須考慮對燃油消耗具有較大影響的因素如車輛載重、車速等。目前,在車輛路徑問題中已開始研究油耗問題，如Xiao等[4]在容量受限的車輛路徑問題(capacitated vehicle routing problem,CVRP)中,分別以最小化油耗和最小化距離為優(yōu)化目標(biāo)對27個CVRP基準(zhǔn)實(shí)例進(jìn)行測試，結(jié)果表明：考慮車輛載重和距離的最小化燃油消耗的車輛路徑問題與單純以最小化車輛運(yùn)輸距離為優(yōu)化目標(biāo)的模型平均能降低5%的燃油消耗。但是，與一般的車輛路徑問題不同的是，廢品收集車輛路徑問題中存在車輛達(dá)到滿載時需要選取合適的廢品處理中心進(jìn)行廢品清空等極大影響車輛載重及燃油消耗的問題。目前，在廢品收集車輛點(diǎn)路徑問題中考慮燃油消耗的研究還不多。Tavares等[5]在廢品收集車輛路徑問題中考慮道路傾斜度和車輛載重對燃油消耗的影響，以最小化燃油消耗為目標(biāo)進(jìn)行優(yōu)化，與單純以最小化車輛運(yùn)輸距離為優(yōu)化目標(biāo)的結(jié)果相比，減少了52%的燃油消耗，但該研究沒有考慮車輛載重和燃油消耗之間的具體函數(shù)關(guān)系。Zsigraiova等[6]以車輛載重為變量，對廢品收集車輛路徑進(jìn)行了靈敏性分析,分析結(jié)果表明,車輛載重的確對廢品收集車輛路徑問題中的燃油消耗有較大影響,但沒有進(jìn)行具體的路徑優(yōu)化。

廢品收集車輛路徑問題往往是包含大規(guī)模數(shù)據(jù)的NP難問題[1]。傳統(tǒng)的精確算法無法在短時間內(nèi)獲得模型的滿意解，因此較多地使用元啟發(fā)式方法進(jìn)行求解,如禁忌搜索、遺傳算法和蟻群算法等。其中，蟻群算法是成功用于求解TSP(travelling salesman problem)的構(gòu)造元啟發(fā)式方法,但隨著數(shù)據(jù)規(guī)模的增大,算法性能會急劇劣化。為了改善蟻群算法性能，Stützle等[7]提出了最大最小蟻群算法，該算法在求解較大數(shù)據(jù)規(guī)模的TSP等組合優(yōu)化問題方面具有良好的性能而得到廣泛研究。

為了準(zhǔn)確分析車輛載重和車輛運(yùn)輸距離對廢品收集車輛路徑問題中燃油消耗的影響,本文在考慮車輛載重和車輛運(yùn)輸距離對燃油消耗影響的情況下,建立了帶有時間窗、司機(jī)午餐休息時間以及多個中轉(zhuǎn)廢品處理中心的最小化燃油消耗的廢品收集車輛路徑問題模型。為了進(jìn)一步提高最大最小蟻群算法求解大規(guī)模數(shù)據(jù)的廢品收集車輛路徑問題的效果，本文提出一種嵌入帶距離限制的最近鄰域搜索的最大最小蟻群算法,并采用兩兩交換局部搜索進(jìn)行進(jìn)一步優(yōu)化。對基準(zhǔn)實(shí)例的測試驗(yàn)證了所提出算法的有效性。

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

1.1模型描述

帶時間窗、司機(jī)午餐休息時間及多個中轉(zhuǎn)廢品處理中心的最小化燃油消耗的廢品收集車輛路徑問題模型可以用一張平面圖G=(V,A,T)表示。其中,平面中的點(diǎn)集V={0,1,2,…,N+M+1},T表示V中每個點(diǎn)的時間窗約束,A為任意兩端點(diǎn)之間線段的集合,0表示停車場P,N個顧客的集合S={1,2,…,N},M個廢品處理中心的集合F={N+1,N+2,…,N+M},假設(shè)司機(jī)午餐休息時間為模型中的一個虛擬點(diǎn),用LB={N+M+1}表示。模型參數(shù)見表1。圖1是該模型的廢品收集車輛運(yùn)輸路徑示意圖。

表1　模型參數(shù)

圖1　廢品收集車輛運(yùn)輸路徑示意圖

該模型的約束主要包括停車場、顧客和廢品處理中心的時間窗約束，司機(jī)的午餐休息時間約束以及車輛和運(yùn)輸路徑的容量約束等。具體如下：

(1)時間窗約束[ai,bi]指最早和最遲允許的開始服務(wù)時間。每個顧客、每個廢品處理中心和停車場都有時間窗約束，車輛只能在規(guī)定的時間段內(nèi)為顧客服務(wù)、到達(dá)廢品處理中心清空廢品和從停車場出發(fā)并返回。

(2)每個司機(jī)在上午11點(diǎn)到下午1點(diǎn)的時間段內(nèi)有1h的午餐休息時間。

(3)每輛車的最大容量為Q，且所有車的類型相同。

(4)每輛車每天能夠訪問的最大顧客總數(shù)為R，每天能夠收集的最大廢品總質(zhì)量為mW。

(5)每輛車可多次到廢品處理中心清空廢品，最后空車返回停車場。

(6)顧客i有質(zhì)量為Wi的廢品要收集，每輛車在每個顧客點(diǎn)收集廢品或在廢品處理中心清空廢品所用的時間為ti。

(7)每個顧客有且只能被訪問一次。

1.2模型的建立

本模型的優(yōu)化目標(biāo)是最小化所有車輛的總?cè)加拖?主要考慮車輛載重和運(yùn)輸距離對燃油消耗的影響。在i、j兩點(diǎn)之間運(yùn)輸時,車輛每千米的燃油消耗ρi j與車輛載重Li k的函數(shù)關(guān)系使用Xiao等[4]提出的計算方法，最小化所有車輛的總?cè)加拖臑?/p>

(1)

約束為

(2)

(3)

Li k≤Q?k∈K,i∈{1,2,…,N,N+M+1}

(4)

Li k=0?k∈K,i∈{0,N+1,N+2,…,N+M}

(5)

Li k+Wj-Lj k≤(1-xi j k)MB

(6)

?k∈K,i,j∈{0,1,…,N+M+1}

式中,MB為大常數(shù)。

(7)

(8)

(9)

(10)

(11)

(12)

j∈{0,1,…,N+M+1}

(13)

Ti k+ti+di j/vS-Tj k≤(1-xi j k)MB

?k∈K,(i,j)∈A

(14)

Ti k+ti+tN+M+1+vS-Tj k≤

(2-xi,N+M+1,k-xN+M+1,j,k)MB?k∈K,(i,j)∈A

(15)

ai≤Ti k≤bi?k∈K,i∈{0,1,…,N+M+1}

(16)

(17)

(18)

xijk∈{0,1}?k∈K,(i,j)∈A

(19)

Nk=0,1,2,…?k∈K

(20)

Lik≥0?k∈K,i∈{0,1,…,N+M+1}

(21)

式(2)保證每個顧客有且只能被一輛車服務(wù)一次;式(3)保證每輛車都從停車場出發(fā);式(4)保證車輛的載重在收集顧客廢品的過程中始終小于車輛的最大載重；式(5)保證車輛離開廢品處理中心或從停車場出發(fā)時,車輛的載重為0;式(6)表示車輛從一個顧客收集點(diǎn)到下一個顧客收集點(diǎn)時車內(nèi)廢品質(zhì)量所要滿足的約束;式(7)、式(8)保證每天每輛車所收集的廢品總質(zhì)量不超過車輛到廢品處理中心的次數(shù)所能運(yùn)輸?shù)膹U品總質(zhì)量；因?yàn)檐囕v最后要經(jīng)過廢品處理中心返回停車場,所以式(9)保證車輛離開廢品處理中心到顧客和午餐休息時間點(diǎn)的次數(shù)比車輛到達(dá)廢品處理中心的次數(shù)少1;式(10)保證車輛最后經(jīng)過廢品處理中心返回停車場；式(11)、式(12)保證車輛在每天的運(yùn)輸中，司機(jī)都有一個午餐休息時間；式(13)保證車輛到達(dá)收集點(diǎn)后必須離開該收集點(diǎn)；式(14)～式(16)是保證顧客、廢品處理中心、司機(jī)午餐休息時間和停車場的時間窗約束；式(17)保證每輛車訪問的最大顧客總數(shù)有限；式(18)保證每輛車收集的最大廢品總質(zhì)量有限；式(19)～式(21)是相關(guān)變量的非負(fù)約束。

2　算法設(shè)計

由于最大最小蟻群算法構(gòu)造的可行解質(zhì)量直接影響最終算法的整體效果,而最大最小蟻群算法求解大規(guī)模廢品收集車輛路徑問題的質(zhì)量和效果往往較差，因此，提出一種改進(jìn)的最大最小蟻群算法，具體的流程如圖2所示，針對可行解質(zhì)量問題，提出一種在最大最小蟻群算法的概率狀態(tài)轉(zhuǎn)移規(guī)則中引入帶距離限制的最近鄰域搜索的方法，通過此方法構(gòu)造可行解。

圖2　改進(jìn)最大最小蟻群算法流程圖

2.1可行解構(gòu)造方法

開始時在停車場放置NANT只螞蟻,每只螞蟻所走過的完整路徑代表該模型的1個可行解，每個可行解可能包含多輛車。每只螞蟻在構(gòu)造可行解時，假設(shè)停車場有足夠的車輛，且1輛車在滿足時間窗、總顧客數(shù)和總質(zhì)量等約束范圍內(nèi)完成運(yùn)輸后，接著安排下一輛車從停車場出發(fā)到各顧客收集廢品，直到所有顧客的廢品都收集完畢。每只螞蟻構(gòu)造可行解的流程如圖3所示。

圖3　可行解構(gòu)造流程圖

2.1.1滿足時間窗約束的動態(tài)候選列表

最大最小蟻群算法求解較大數(shù)據(jù)規(guī)模(包含200個以上的顧客)的車輛路徑問題時性能仍然會劣化[8-9]。以往,為了優(yōu)化此問題和提高最大最小蟻群算法的收斂速度,往往將固定數(shù)量的距離當(dāng)前顧客最近的未訪問顧客作為當(dāng)前顧客的候選列表(candidatelist),但難以確定該固定數(shù)量的最優(yōu)值,如Bullnheimer等[10]不管車輛路徑問題所包含的總顧客數(shù)多大，都將顧客的候選列表(從當(dāng)前顧客出發(fā)，滿足約束的下一個顧客的集合)大小設(shè)為總顧客數(shù)的1/4。

本文考慮的帶時間窗廢品收集車輛路徑問題的總顧客數(shù)往往超過2000,將顧客候選列表的大小設(shè)為總顧客數(shù)的1/4對提高最大最小蟻群算法的收斂速度幾乎沒有影響。同時,由于選取顧客的候選列表是基于距離最近的規(guī)則，在算法的整個過程中，每個顧客的候選列表包含的顧客都是固定的,從而縮小了可行解的范圍。因此，針對不同規(guī)模車輛路徑問題難以確定最優(yōu)的顧客候選列表大小和采用固定顧客候選列表導(dǎo)致可行解范圍縮小的問題,本文設(shè)計了滿足時間窗約束的優(yōu)先候選列表和次要候選列表。計算這兩類動態(tài)候選列表的方法為：假設(shè)被訪問的當(dāng)前顧客為顧客i,未被訪問的顧客(顧客j)的時間窗為[aj,bj]。若訪問顧客i后,車輛從i到達(dá)j的時間恰好落在顧客j的時間窗內(nèi),即到達(dá)顧客j的時間tj滿足約束aj≤tj≤bj,則顧客j放入優(yōu)先候選列表;若訪問顧客i后,從i到達(dá)j的時間早于顧客j的開始服務(wù)時間,即tj

從以上設(shè)計可以看到,由于優(yōu)先候選列表和次要候選列表的劃分滿足時間窗約束,每個顧客的候選列表的大小可能不一樣,并隨顧客的訪問順序和各自時間窗的不同而變化,因此與采用固定數(shù)量的顧客候選列表的方法相比，這種采用滿足時間窗約束的優(yōu)先候選列表和次要候選列表的劃分方法沒有丟失可行解。從當(dāng)前顧客的優(yōu)先候選列表中選取1個顧客時，車輛無需等待即可為該顧客服務(wù)；從次要候選列表中選取1個顧客時，還需等到該顧客的時間窗開始才能服務(wù)。因此，為了盡可能減少車輛的等待時間，從當(dāng)前顧客的候選列表中選擇下一個要訪問的顧客時，優(yōu)先從優(yōu)先顧客候選列表中選擇，只有當(dāng)優(yōu)先候選列表為空時，才從次要候選列表中選取下一個顧客。

2.1.2帶距離限制最近鄰域搜索的概率狀態(tài)轉(zhuǎn)移

為了克服最大最小蟻群算法收斂速度慢的缺點(diǎn)，本文在Stützle等[7]所提最大最小蟻群算法所采用的從當(dāng)前顧客的候選列表中隨機(jī)選取下一個顧客j的概率狀態(tài)轉(zhuǎn)移規(guī)則中,引入帶距離限制的最近鄰域搜索,新的概率狀態(tài)轉(zhuǎn)移規(guī)則為

(22)

(23)

(24)

η(i,j)=1/dij(i,j)∈A且i≠j

其中,arg()函數(shù)表示滿足arg括號內(nèi)約束時的定義域內(nèi)的值;Tk(i)為第k只螞蟻在當(dāng)前顧客i時可選擇的滿足時間窗約束的下一個顧客的候選列表;div為顧客i與下一個顧客(顧客v)之間的距離;τ(i,v)為顧客i與顧客v之間的路徑上的信息素;η(i,v)為顧客i與顧客v之間路徑上的啟發(fā)式信息;α、β為常數(shù);J表示滿足約束C0

C≤C0時,采取最近鄰域搜索選取下一個要訪問的顧客。為了解決最近鄰域搜索的過度貪心導(dǎo)致收斂到次優(yōu)解的缺點(diǎn)，將所有顧客兩兩之間距離的算數(shù)平均值d作為最近鄰域搜索的最大搜索半徑。采用所有顧客兩兩之間距離的算數(shù)平均值d作為最近鄰域搜索的最大搜索半徑獲取下一個顧客的具體方法為：從滿足時間窗約束的優(yōu)先候選列表或次要候選列表中篩選出與當(dāng)前顧客的距離小于d,且與當(dāng)前顧客距離最近的顧客作為下一個要訪問的顧客。如圖4所示,假如產(chǎn)生的隨機(jī)數(shù)C≤C0,則從以當(dāng)前顧客為圓心、以d為半徑的圓內(nèi)選取離當(dāng)前顧客最近,且滿足時間窗約束的顧客點(diǎn)1進(jìn)行訪問。C0

圖4　概率狀態(tài)轉(zhuǎn)移規(guī)則示意圖

2.2兩兩交換局部搜索

制定嵌入帶距離限制最近鄰域搜索的概率狀態(tài)轉(zhuǎn)移規(guī)則,當(dāng)NANT只螞蟻按照此規(guī)則構(gòu)造出可行解后,為了提高最終解的質(zhì)量,對構(gòu)造出最優(yōu)解的那只螞蟻的路徑進(jìn)行兩兩交換局部搜索。為減少算法的運(yùn)行時間，只對最好解中每條車輛路徑的顧客或者廢品處理中心進(jìn)行交換，不進(jìn)行不同車輛路徑之間的顧客或者廢品處理中心的交換,具體步驟如下。

(1)設(shè)SS0為NANT只螞蟻所構(gòu)造出來解中的最優(yōu)解,FD0為其對應(yīng)的目標(biāo)函數(shù)值,設(shè)k=1表示SS0中的第一輛車，所訪問的顧客和廢品處理中心總數(shù)為vn k,該車訪問的第一個顧客為i,假設(shè)i=1,下一個顧客或者廢品處理中心j=i+1=2,令變量SS*=SS0,SS*對應(yīng)的目標(biāo)函數(shù)值FD*=FD0。

(2)若i

(3)j

(4)i=vn k時,對可行解SS0中第k輛車的局部搜索完畢,令k←k+1,j=i+1,i=1,j=i+1=2,然后對解SS*中下一輛車的路徑執(zhí)行步驟(2)和步驟(3),直到可行解SS0中所有車輛路徑都進(jìn)行了局部搜索，輸出SS*和FD*。

2.3信息素更新

在最大最小蟻群算法中，只允許在迭代最優(yōu)路徑或全局最優(yōu)路徑上遺留信息素。為了防止算法過早收斂，限制路徑上的信息素在[τmin,τmax]范圍內(nèi),并在算法開始時將所有路徑上的信息素初始化為信息素最大值τmax以增加算法的探索能力[9]。本文選擇在迭代最優(yōu)路徑SS*上遺留信息素,即有

τi j(t+1)=τi j(t)+1/FD*

(25)

然后對所有路徑按下式進(jìn)行信息素的蒸發(fā):

τi j(t+1)=(1-ρ)τi j(t)

(26)

最后檢查所有路徑上的信息素是否在[τmin,τmax]范圍內(nèi),若不是則調(diào)整到相應(yīng)的信息素最小值τmin或最大值τmax。在算法開始時將所有路徑上的信息素初始化為信息素最大值τmax=τ0,τ0按下式計算:

τ0=1/(ρCn n)

(27)

其中,Cn n為使用最近鄰域搜索獲得的目標(biāo)函數(shù)值,信息素最小值τmin采用下式進(jìn)行計算:

τmin=τmax/(2M+2N)

(28)

每次迭代后,對信息素的限制范圍[τmin,τmax]進(jìn)行更新,τmax采用下式進(jìn)行計算:

τmax=1/(ρFD*)

(29)

τmin仍然按式(28)計算。

3　實(shí)驗(yàn)結(jié)果與分析

3.1運(yùn)輸距離最小的基準(zhǔn)實(shí)例測試

為了說明在求解大規(guī)模廢品收集車輛路徑問題時在最大最小蟻群算法中嵌入帶距離限制的最近鄰域搜索的有效性，將所提出的改進(jìn)最大最小蟻群算法用于求解Kim等[9]針對帶有時間窗、司機(jī)休息時間以及多個中轉(zhuǎn)廢品處理中心的廢品收集車輛路徑問題模型所設(shè)計的10個基準(zhǔn)實(shí)例。為了便于比較，統(tǒng)一以車輛運(yùn)輸距離最小為優(yōu)化目標(biāo)。具體的基準(zhǔn)實(shí)例如表2所示,其中,基準(zhǔn)實(shí)例中的數(shù)字表示廢品收集車輛路徑問題中顧客廢品收集點(diǎn)、中轉(zhuǎn)站和停車場的總數(shù)。

表2　問題基準(zhǔn)實(shí)例

本算法采用C++編程實(shí)現(xiàn),試驗(yàn)次數(shù)為10,具體結(jié)果如表3所示,其中,C0=0表示沒有使用最近鄰域搜索，C0=0.8表示使用了帶有距離限制的最近鄰域搜索。其他參數(shù)都相同，分別為α=1，β=2，ρ=0.2,Q0=0.9,蟻數(shù)NANT=20,迭代次數(shù)為50。將上述結(jié)果與3種以最小化車輛運(yùn)輸距離為優(yōu)化目標(biāo)的求解該基準(zhǔn)實(shí)例的效果較好算法(Benjamin等[10]采用的禁忌搜索和變鄰域搜索的混合算法、Buhrkal等[11]所采用的自適應(yīng)大規(guī)模鄰域搜索算法和Islam等[12]采用的蟻群算法)進(jìn)行比較，結(jié)果如表3所示。

從表3可以看出,對于小數(shù)據(jù)規(guī)模廢品收集車輛路徑問題，如實(shí)例102和277，本文提出的算法沒有顯著優(yōu)越性。對于廢品收集點(diǎn)個數(shù)達(dá)到804以上的大規(guī)模廢品收集車輛路徑問題，嵌入帶距離限制的最近鄰域搜索的最大最小蟻群算法的效果明顯要好，如實(shí)例1932所示，這說明通過在最大最小蟻群算法中嵌入帶距離限制的最近鄰域搜索，能夠在求解大規(guī)模的廢品收集車輛路徑問題時實(shí)現(xiàn)對算法的改進(jìn)。同時，與其他3種算法相比，本文提出的帶距離限制的最近鄰域搜索的最大最小蟻群算法在10個基準(zhǔn)實(shí)例中獲得了9個更好解，從而驗(yàn)證了該算法在求解大規(guī)模廢品收集車輛路徑問題的有效性。

3.2最小化距離和油耗的實(shí)例測試

為了驗(yàn)證本文提出的考慮車輛載重和距離對車輛燃油消耗的影響的情況下所得最小化燃油消耗優(yōu)化目標(biāo)的有效性，分別以最小化距離和最小化燃油消耗為優(yōu)化目標(biāo)，將所設(shè)計的帶距離限制的最近鄰域搜索的最大最小蟻群算法用于求解表2中的基準(zhǔn)實(shí)例，結(jié)果如表4所示。計算過程相關(guān)參數(shù)設(shè)置如下：ρ*=2，ρ0=1,C0=0.8,其他參數(shù)如3.1節(jié)所述。為了更直觀地說明兩種優(yōu)化目標(biāo)對距離和油耗的影響，采用下式計算兩種優(yōu)化目標(biāo)情況下的距離偏差和油耗偏差：

表3　與其他文獻(xiàn)得到的距離最小值比較　miles

表4　兩種優(yōu)化目標(biāo)的結(jié)果比較

(31)

其中,φ為偏差;Fρmin為最小化燃油消耗目標(biāo)的對應(yīng)值;Fdmin為最小化距離目標(biāo)的對應(yīng)值。

由表4可以看出,10次結(jié)果中的平均值情況是，最小化油耗目標(biāo)得出的油耗都低于最小化距離目標(biāo)得到的油耗；最小值情況下，除實(shí)例277外也是最小化油耗目標(biāo)得出的油耗都低于最小化距離目標(biāo)得到的油耗。這說明單純以最小化距離為優(yōu)化目標(biāo)進(jìn)行路徑優(yōu)化并不能得到最小的燃油消耗，同時以燃油消耗為優(yōu)化目標(biāo)盡管在運(yùn)輸距離上可能有所增加但可以有效降低總油耗，驗(yàn)證了本文所提最小化燃油消耗優(yōu)化目標(biāo)的有效性。

圖5　最小化距離目標(biāo)下102實(shí)例的車輛路徑示意圖

圖6　最小化燃油消耗目標(biāo)下102實(shí)例的車輛路徑示意圖

為了進(jìn)一步說明最小化燃油消耗優(yōu)化目標(biāo)的重要性，將最小化距離為優(yōu)化目標(biāo)所得的距離最小值對應(yīng)的車輛路徑和以最小化燃油消耗為優(yōu)化目標(biāo)所得油耗最小值對應(yīng)的車輛路徑畫出，如圖5、圖6所示，限于篇幅，僅畫出102實(shí)例。從圖5、圖6可以看出，最小化距離和最小化燃油消耗為優(yōu)化目標(biāo)所得到的車輛路徑大不相同，且最小化距離目標(biāo)的車輛路徑中只用到了中轉(zhuǎn)廢品處理中心1；最小化燃油消耗目標(biāo)的車輛路徑中,中轉(zhuǎn)廢品處理中心1、2都用到了。因此，如果只從最小化距離目標(biāo)的角度來看,中轉(zhuǎn)廢品處理中心2是無需設(shè)置的，但從最小化燃油消耗的角度來看，中轉(zhuǎn)廢品處理中心2的設(shè)置可以有效減少燃油消耗。由此可見，以最小化燃油消耗為目標(biāo)進(jìn)行優(yōu)化不僅會改變車輛訪問廢品收集點(diǎn)的順序從而節(jié)省油耗，而且還可能影響到設(shè)施規(guī)劃等其他相關(guān)決策的制定和實(shí)施。

4　結(jié)語

為了研究車輛載重和距離這兩個因素對帶有時間窗和多個中轉(zhuǎn)廢品處理中心的廢品收集車輛路徑問題中燃油消耗的影響，本文在考慮車輛載重和距離對燃油消耗影響的情況下,建立了帶有時間窗、司機(jī)休息時間以及多個中轉(zhuǎn)廢品處理中心的最小化燃油消耗的廢品收集車輛路徑問題模型。針對廢品收集車輛路徑問題數(shù)據(jù)規(guī)模大的特點(diǎn)，設(shè)計了一種改進(jìn)的最大最小蟻群算法進(jìn)行求解，對基準(zhǔn)實(shí)例的測試證明了所提優(yōu)化目標(biāo)和算法的有效性。

由于車輛的燃油消耗不僅與車輛行駛路程和車輛載重有關(guān)，還與車輛行駛速度等因素有關(guān)，而本研究假設(shè)車輛行駛速度恒定，因此，后續(xù)研究可進(jìn)一步考慮車輛行駛速度、載重、車輛運(yùn)輸距離等多因素作用下的廢品收集車輛路徑問題中的燃油消耗問題。

[1]Sahoo S,Kim S,Kim B I,et al.Routing Optimization for Waste Management[J].Interfaces，2005，35(1)：24-36.

[2]Angelelli E,Speranza M G.The Application of a Vehicle Routing Model to a Waste-collection Problem:Two Case Studies[J].The Journal of the Operational Research Society,2002,53(9):944-952.

[3]Baldacci R,Hadjiconstantionou E,Mingozzi A.An Exact Algorithm for the Capacitated Vehicle Routing Problem Based on a Two-commodity Network Flow Formulation[J].Operations Research,2004,52(5):723-738.

[4]Xiao Y,Zhao Q,Kaku I,et al.Development of a Fuel Consumption Optimization Model for the Capacitated Vehicle Routing Problem[J].Computers & Operations Research,2012,39(7):1419-1431.

[5]Tavares G,Zdena Z,Viriato S,et al.A Case Study of Fuel Savings through Optimization of MSW Transportation Routes[J].Management of Environmental Quality:An International Journal，2008,19(4):444-454.

[6]Zsigraiova Z,Semiao V,Beijoco F.Operation Costs and Pollutant Emissions Reduction by Definition of New Collection Scheduling and Optimization of MSW Collection Routes Using GIS.The Case Study of Barreiro,Portugal[J].Waste Management,2013,33(4):793-806.

[7]Stützle T,Hoos H.The Max-min Ant System and Local Search for Combinatorial Optimization Problems[C]//1997 IEEE International Conference on Evolutionary Computation.Indianapolis,1997:309-314.

[8]Bullnheimer B,Hartl R F,Strauss C.An Improved Ant System Algorithm for the Vehicle Routing Problem[J].Annals of Operations Research,1999,89:319-328.

[9]Kim B I,Kim S,Sahoo S.Waste Collection Vehicle Routing Problem with Time Windows[J].Computers & Operations Research,2006,33(12):3624-3642.

[10]Benjamin A M,Beasley J E.Metaheuristics with Disposal Facility Positioning for the Waste Collection VRP with Time Windows[J].Optimization Letters,2013,7(7):1433-1449.

[11]Buhrkal K,Larsen A,Ropke S.The Waste Collection Vehicle Routing Problem with Time Windows in a City Logistics Context[J].Procedia Social and Behavioral Sciences,2012,39:241-254.

[12]Islam R,Rahman M S.An Ant Colony Optimization Algorithm for Waste Collection Vehicle Routing with Time Windows,Driver Rest Period and Multiple Disposal Facilities[C]//2012 International Conference on Informatics,Electronics & Vision.Dhaka,2012:774-779.

(編輯張洋)

Waste Collection Vehicle Routing Problem with Time Windows Based on Improved Ant Colony Optimization

Liu QiongLiu XiuchengZhang ChaoyongRao Yunqing

State Key Laboratory of Digital Manufacturing Equipment & Technology,Huazhong University of Science and Technology,Wuhan,430074

A mathematical model aiming at minimizing the fuel consumption for the waste collection vehicle routing problem with time windows,driver rest period and multiple disposal facilities was set up.The main factors to affect the fuel consumption of a vehicle considered herein were the load of a vehicle and distance traveled.An improved MAX-MIN ant system algorithm was proposed.Based on characteristics of the time windows,two kinds of dynamic candidate lists were designed to improve the searching efficiency of the algorithm.A new probabilistic condition transition rule for the MAX-MIN ant system algorithm was proposed.The nearest neighborhood search with distance limitation was integrated in the transition rule of proposed algorithm.The proposed model and algorithm were validated by comparion with benchmark problems in literatures.

large scale vehicle with time windows;routing problem;ant colony optimization;fuel consumption

2013-10-08

國家自然科學(xué)基金資助重點(diǎn)項(xiàng)目(51035001);國家自然科學(xué)基金資助項(xiàng)目(51275190);國家科技重大專項(xiàng)(2011ZX04015-011-07)；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資金資助項(xiàng)目(HUST:2013ZZGH002)

TP391< class="emphasis_italic">DOI

：10.3969/j.issn.1004-132X.2015.02.022

劉瓊,女,1965年生。華中科技大學(xué)數(shù)字制造裝備與技術(shù)國家重點(diǎn)實(shí)驗(yàn)室教授、博士。主要研究方向?yàn)槲锪飨到y(tǒng)管理、制造系統(tǒng)集成優(yōu)化。劉秀城,男,1989年生。華中科技大學(xué)數(shù)字制造裝備與技術(shù)國家重點(diǎn)實(shí)驗(yàn)室碩士研究生。張超勇,男,1972年生。華中科技大學(xué)數(shù)字制造裝備與技術(shù)國家重點(diǎn)實(shí)驗(yàn)室副教授、博士。饒運(yùn)清,男,1968年生。華中科技大學(xué)數(shù)字制造裝備與技術(shù)國家重點(diǎn)實(shí)驗(yàn)室教授、博士。