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

劉　瓊　劉秀城　張超勇　饒運清

華中科技大學數字制造裝備與技術國家重點實驗室，武漢，430074

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

劉瓊劉秀城張超勇饒運清

華中科技大學數字制造裝備與技術國家重點實驗室，武漢，430074

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

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

0　引言

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

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

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

1　數學模型

1.1模型描述

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

表1　模型參數

圖1　廢品收集車輛運輸路徑示意圖

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

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

(2)每個司機在上午11點到下午1點的時間段內有1h的午餐休息時間。

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

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

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

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

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

1.2模型的建立

本模型的優化目標是最小化所有車輛的總燃油消耗,主要考慮車輛載重和運輸距離對燃油消耗的影響。在i、j兩點之間運輸時,車輛每千米的燃油消耗ρi j與車輛載重Li k的函數關系使用Xiao等[4]提出的計算方法，最小化所有車輛的總燃油消耗為

(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為大常數。

(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)保證每個顧客有且只能被一輛車服務一次;式(3)保證每輛車都從停車場出發;式(4)保證車輛的載重在收集顧客廢品的過程中始終小于車輛的最大載重；式(5)保證車輛離開廢品處理中心或從停車場出發時,車輛的載重為0;式(6)表示車輛從一個顧客收集點到下一個顧客收集點時車內廢品質量所要滿足的約束;式(7)、式(8)保證每天每輛車所收集的廢品總質量不超過車輛到廢品處理中心的次數所能運輸的廢品總質量；因為車輛最后要經過廢品處理中心返回停車場,所以式(9)保證車輛離開廢品處理中心到顧客和午餐休息時間點的次數比車輛到達廢品處理中心的次數少1;式(10)保證車輛最后經過廢品處理中心返回停車場；式(11)、式(12)保證車輛在每天的運輸中，司機都有一個午餐休息時間；式(13)保證車輛到達收集點后必須離開該收集點；式(14)～式(16)是保證顧客、廢品處理中心、司機午餐休息時間和停車場的時間窗約束；式(17)保證每輛車訪問的最大顧客總數有限；式(18)保證每輛車收集的最大廢品總質量有限；式(19)～式(21)是相關變量的非負約束。

2　算法設計

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

圖2　改進最大最小蟻群算法流程圖

2.1可行解構造方法

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

圖3　可行解構造流程圖

2.1.1滿足時間窗約束的動態候選列表

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

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

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

2.1.2帶距離限制最近鄰域搜索的概率狀態轉移

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

(22)

(23)

(24)

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

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

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

圖4　概率狀態轉移規則示意圖

2.2兩兩交換局部搜索

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

(1)設SS0為NANT只螞蟻所構造出來解中的最優解,FD0為其對應的目標函數值,設k=1表示SS0中的第一輛車，所訪問的顧客和廢品處理中心總數為vn k,該車訪問的第一個顧客為i,假設i=1,下一個顧客或者廢品處理中心j=i+1=2,令變量SS*=SS0,SS*對應的目標函數值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*中下一輛車的路徑執行步驟(2)和步驟(3),直到可行解SS0中所有車輛路徑都進行了局部搜索，輸出SS*和FD*。

2.3信息素更新

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

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

(25)

然后對所有路徑按下式進行信息素的蒸發:

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

(26)

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

τ0=1/(ρCn n)

(27)

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

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

(28)

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

τmax=1/(ρFD*)

(29)

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

3　實驗結果與分析

3.1運輸距離最小的基準實例測試

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

表2　問題基準實例

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

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

3.2最小化距離和油耗的實例測試

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

表3　與其他文獻得到的距離最小值比較　miles

表4　兩種優化目標的結果比較

(31)

其中,φ為偏差;Fρmin為最小化燃油消耗目標的對應值;Fdmin為最小化距離目標的對應值。

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

圖5　最小化距離目標下102實例的車輛路徑示意圖

圖6　最小化燃油消耗目標下102實例的車輛路徑示意圖

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

4　結語

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

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

[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

國家自然科學基金資助重點項目(51035001);國家自然科學基金資助項目(51275190);國家科技重大專項(2011ZX04015-011-07)；中央高校基本科研業務費專項資金資助項目(HUST:2013ZZGH002)

TP391< class="emphasis_italic">DOI

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

劉瓊,女,1965年生。華中科技大學數字制造裝備與技術國家重點實驗室教授、博士。主要研究方向為物流系統管理、制造系統集成優化。劉秀城,男,1989年生。華中科技大學數字制造裝備與技術國家重點實驗室碩士研究生。張超勇,男,1972年生。華中科技大學數字制造裝備與技術國家重點實驗室副教授、博士。饒運清,男,1968年生。華中科技大學數字制造裝備與技術國家重點實驗室教授、博士。