董 攀，陳 陽(yáng)（長(zhǎng)沙理工大學(xué) 經(jīng)濟(jì)與管理學(xué)院，湖南 長(zhǎng)沙 401114）

0 引言

車(chē)輛路徑問(wèn)題（Vehicle Routing Problem,VRP）屬于組合優(yōu)化問(wèn)題，其理論涉及到運(yùn)籌學(xué)、管理學(xué)、交通運(yùn)輸、計(jì)算機(jī)應(yīng)用等多個(gè)學(xué)科。VRP問(wèn)題中加入節(jié)點(diǎn)可訪問(wèn)的時(shí)間窗約束即成為有時(shí)間窗車(chē)輛路徑問(wèn)題（Vehicle Routing Problem with Time Windows,VRPTW）。由于現(xiàn)實(shí)生活中很多問(wèn)題可以歸結(jié)為VRPTW，因此VRPTW的研究受到學(xué)術(shù)界的廣泛重視。

VRPTW已被證明為NP-hard問(wèn)題，這意味著當(dāng)節(jié)點(diǎn)規(guī)模較大時(shí)，很難在多項(xiàng)式時(shí)間內(nèi)得到問(wèn)題的精確解，因此啟發(fā)式算法因其快速高效構(gòu)建可行解的優(yōu)點(diǎn)成為人們的首選。Ombuki Beatrice等[1]利用遺傳算法、Tavakkoli-Moghaddam等[2]利用模擬退火算法來(lái)求解VRPTW問(wèn)題，但二者都存在收斂速度慢的問(wèn)題；張炯和郎茂祥[3]使用的禁忌算法、馬炫等[4]使用的粒子群算法則容易陷入局部最優(yōu)解。為解決這些問(wèn)題，蟻群算法的魯棒性和構(gòu)造簡(jiǎn)單使得其經(jīng)常被用于與其他算法構(gòu)成組合優(yōu)化算法。但無(wú)論是殷志鋒和張巖松[5]提出的基于進(jìn)化規(guī)劃和最大-最小蟻群算法相融合的混合蟻群算法，還是范小寧等[6]采用遺傳算法和蟻群算法的結(jié)合，以及Zhang Xiaoxia[7]將蟻群算法和禁忌搜索結(jié)合等都只是將蟻群算法作為構(gòu)造可行解的方法，并大量使用局部搜索優(yōu)化算法，而缺少對(duì)蟻群算法本身的改進(jìn)。

本文對(duì)Thomas Thutzle和Holger Hoos提出的最大最小蟻群系統(tǒng)（MAX-MIN ant colony system）在轉(zhuǎn)移概率矩陣計(jì)算、信息素更新等關(guān)鍵因素上進(jìn)行改進(jìn)，以提高其全局優(yōu)化能力。為更好地說(shuō)明本改進(jìn)算法的優(yōu)越性，在原始MMAS算法和本文算法測(cè)試Solomon標(biāo)準(zhǔn)數(shù)據(jù)集時(shí)均不使用局部?jī)?yōu)化算法。

1 有時(shí)間窗車(chē)輛路徑問(wèn)題的定義

VRPTW的一般定義如下：從某一物流中心用多臺(tái)配送車(chē)輛從多個(gè)客戶(hù)取貨，每個(gè)客戶(hù)的位置和需求量和需求時(shí)間一定，每個(gè)客戶(hù)只能由一臺(tái)車(chē)輛服務(wù)一次，要求合理安排車(chē)輛配送路線，使目標(biāo)函數(shù)得到最優(yōu)，即在不違背約束條件下所用車(chē)輛數(shù)最少和行走路線長(zhǎng)度最短。本文將最小化車(chē)輛數(shù)量作為第一目標(biāo)，最小化車(chē)輛行駛路線長(zhǎng)度作為第二目標(biāo)。

2 最大最小蟻群算法及其在有時(shí)間窗車(chē)輛路徑問(wèn)題中的應(yīng)用

MMAS對(duì)AS的關(guān)鍵改進(jìn)在于將路徑上的信息素濃度限定 ［τmin,τmax］之間，這較好地避免了搜索陷入局部最優(yōu)解。因?yàn)樵谒阉鬟^(guò)程中，隨著信息素的揮發(fā)和累積，某些路徑上的信息素濃度會(huì)遠(yuǎn)遠(yuǎn)高于其他路徑，從而導(dǎo)致搜索過(guò)早停滯。

2.1 狀態(tài)轉(zhuǎn)移概率。螞蟻在選擇下一個(gè)節(jié)點(diǎn)時(shí)，在滿(mǎn)足容量約束和時(shí)間窗約束下，需要考慮如下三個(gè)因素：①通往下個(gè)節(jié)點(diǎn)的路徑長(zhǎng)度以及路徑上的信息素濃度[8]。②時(shí)間窗因素的擇優(yōu)性[8]，由下個(gè)客戶(hù)j的時(shí)間窗寬度和所在客戶(hù)i到達(dá)下個(gè)客戶(hù)j的時(shí)間等因素決定。這種擇優(yōu)性的優(yōu)先原則為，需等待時(shí)間較短優(yōu)先原則和時(shí)間窗較小優(yōu)先原則。③基于Wissner-Gross,A.D.[9]的事物傾向于向自由度大的方向進(jìn)化的理論，潛在下一可行節(jié)點(diǎn)數(shù)多的節(jié)點(diǎn)有優(yōu)先權(quán)。

其中，Ω=｛vj|vj為可被訪問(wèn)的客戶(hù) ｝，v0為配送中心。為客戶(hù)j的時(shí)間窗；tij為從客戶(hù)i到達(dá)客戶(hù)j的時(shí)間（等于開(kāi)始為客戶(hù)i服務(wù)的時(shí)刻+客戶(hù)i所需服務(wù)時(shí)間+從客戶(hù)i到客戶(hù)j的時(shí)間）；VCij為客戶(hù)j的下一潛在可被訪問(wèn)客戶(hù)數(shù)，由所有滿(mǎn)足LTi+Si+Lij≤LTj的客戶(hù)組成。τij為vi和vj之間路徑上的信息素；ηij為路徑可見(jiàn)性，這里ηij=1 dij，dij為客戶(hù)i與j之間路徑長(zhǎng)度。α和β為路徑上信息素與路徑可見(jiàn)性的權(quán)重。

2.2 動(dòng)態(tài)啟發(fā)式信息更新。因?yàn)閂RPTW問(wèn)題的第一目標(biāo)值為最小化車(chē)輛數(shù)量，因此為強(qiáng)化改進(jìn)蟻群算法構(gòu)建最小化車(chē)輛數(shù)量路徑的性能，本文對(duì)上面狀態(tài)轉(zhuǎn)移概率中的信息素和路徑長(zhǎng)度啟發(fā)式做如下改變：

式中antTypei為精英螞蟻策略中進(jìn)行信息素更新的螞蟻類(lèi)型。Rand（）為隨機(jī)值。t為信息素更新隨機(jī)因子。因?yàn)棣莍j為路徑值啟發(fā)式信息，因此將其以t的概率增加螞蟻構(gòu)建更優(yōu)的車(chē)輛數(shù)量的解集合。

2.3 精英螞蟻策略。鑒于MMAS有搜索時(shí)間過(guò)長(zhǎng)問(wèn)題，現(xiàn)有文獻(xiàn)通常采用兩種方式最鄰近城市和精英螞蟻，這兩種方式并不能改善最終解，只是起到加快搜索的作用。本文將精英螞蟻策略引入到改進(jìn)蟻群算法。

現(xiàn)有文獻(xiàn)傾向于使用固定數(shù)量或某種逐步縮小數(shù)量的辦法來(lái)使用精英螞蟻，這兩種方式忽略了蟻群算法的易于收斂于次優(yōu)解的特性。在蟻群搜索過(guò)程中，由于信息素的累積作用，構(gòu)建的路徑中次優(yōu)解往往大量出現(xiàn)。為此本文采用動(dòng)態(tài)固定數(shù)量精英螞蟻，即螞蟻數(shù)量固定，但不是單純的迭代最優(yōu)的前幾個(gè)，而是選擇固定數(shù)量的目標(biāo)值各不相同的前幾個(gè)螞蟻進(jìn)行迭代，這是通過(guò)將一次迭代中構(gòu)建的目標(biāo)值排序，將重復(fù)值剔除后選擇迭代最優(yōu)的幾個(gè)實(shí)現(xiàn)的。本文通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，對(duì)于具有n=100個(gè)客戶(hù)的VRPTW，精英螞蟻數(shù)選擇5個(gè)，最多能節(jié)約三分之一的有效迭代次數(shù)，即得到全局最優(yōu)解的最大迭代。

3 試驗(yàn)結(jié)果及分析

將改進(jìn)的蟻群算法應(yīng)用于Solomon[10]標(biāo)準(zhǔn)數(shù)據(jù)集，這些實(shí)例共56個(gè)。每個(gè)問(wèn)題中包含100個(gè)客戶(hù)點(diǎn)。程序用JAVA語(yǔ)言編寫(xiě)，并在eclipse下編譯運(yùn)行。

3.1 參數(shù)設(shè)定。通過(guò)逐步改進(jìn)法得到參數(shù)如下：螞蟻數(shù)M=100，迭代次數(shù)N=1 500，信息素權(quán)重α=1.18；路徑可見(jiàn)性權(quán)重β=2.26；信息素?fù)]發(fā)率ρ=0.0118；PBest=0.058；信息素更新隨機(jī)因子t=0.5。

3.2 結(jié)果及分析。本文對(duì)Solomon標(biāo)準(zhǔn)數(shù)據(jù)集中的所有實(shí)例均運(yùn)行8次，計(jì)算結(jié)果的最優(yōu)值和平均值，并與原始MMAS方法以及目前已知最優(yōu)解進(jìn)行了比較。結(jié)果如表1～6所示。

從以上結(jié)果分析中可以得出：（1）MMAS原算法的計(jì)算性能已經(jīng)非常好。相比于引進(jìn)了時(shí)間窗啟發(fā)式信息的改進(jìn)算法，沒(méi)有使用時(shí)間窗啟發(fā)式信息并沒(méi)有造成性能上非常大的損失，其原因首先是因?yàn)槭褂眠^(guò)的參數(shù)是事先經(jīng)過(guò)了優(yōu)化的；其次的一個(gè)重要原因是最早開(kāi)始服務(wù)時(shí)間窗約束實(shí)質(zhì)上沒(méi)有起作用。因?yàn)橹虚g的等待時(shí)間按照與距離同單位換算原則，應(yīng)該加入到路徑長(zhǎng)度中，但事實(shí)上即便是目前學(xué)術(shù)界取得的最優(yōu)解中公布了路徑節(jié)點(diǎn)排列清單的也沒(méi)有將其考慮進(jìn)去。（2）改進(jìn)的蟻群算法明顯優(yōu)于原始MMAS算法。與原始MMAS方法的比較可知，改進(jìn)的蟻群算法在解決R類(lèi)和RC類(lèi)問(wèn)題上較好，但在C類(lèi)問(wèn)題上稍弱。

4 結(jié)束語(yǔ)

本文研究了在不使用局部搜索算法的情況下，通過(guò)改進(jìn)螞蟻選擇路徑的狀態(tài)轉(zhuǎn)移概率和信息素更新方式，很好地將MMAS運(yùn)用于解決VRPTW問(wèn)題。通過(guò)使用Solomon標(biāo)準(zhǔn)數(shù)據(jù)集，驗(yàn)證了改進(jìn)的蟻群算法的有效性。

表1 C1類(lèi)數(shù)據(jù)集結(jié)果比較

表2 R1類(lèi)數(shù)據(jù)集結(jié)果比較

表3 C2類(lèi)數(shù)據(jù)集結(jié)果比較

表4 R2類(lèi)數(shù)據(jù)集結(jié)果比較

表5 RC1類(lèi)數(shù)據(jù)集結(jié)果比較

表6 RC2類(lèi)數(shù)據(jù)集結(jié)果比較

[1] Franklin,O.B.B..Multi－Objective Genetic Algorithms for Vehicle Routing Problem with Time Windows[J].Applied Intelligence,2006,24:17－30.

[2] Tavakkoli－Moghaddam R.,Gazanfari M.,Alinaghian M,et al.A new mathematical model for a competitive vehicle routing problem with time windows solved by simulated annealing[J].Journal of Manufacturing Systems,2011,30:83－92.

[3] 張炯，郎茂祥.有時(shí)間窗配送車(chē)輛調(diào)度問(wèn)題的禁忌搜索算法[J].北方交通大學(xué)學(xué)報(bào)，2004(2):103－107.

[4] 馬炫，彭破，劉慶.求解帶時(shí)間窗車(chē)輛路徑問(wèn)題的改進(jìn)粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用，2009,45(27):200－202.

[5] 殷志鋒，張巖松.帶時(shí)間窗車(chē)輛路徑問(wèn)題的混合蟻群算法[J].許昌學(xué)院學(xué)報(bào)，2008,27(2):88－90.

[6] 范小寧，徐格寧，楊瑞剛.車(chē)輛配送路徑優(yōu)化的新型蟻群算法[J].計(jì)算機(jī)工程與應(yīng)用，2011,47(26):232－234.

[7] Yu B.,Yang Z.B..A hybrid algorithm for vehicle routing problem with time windows[J].Expert Systems with Applications,2011,38:435－441.

[8] 萬(wàn)旭，林建良，楊曉偉.改進(jìn)的最大最小螞蟻算法在有時(shí)間窗車(chē)輛路徑問(wèn)題中的應(yīng)用[J].計(jì)算機(jī)集成制造系統(tǒng)，2005,4(11):572－576.

[9] Wissner－Gross,A.D.,C.E.Freer.Causal Entropic Forces[J].Physical Review Letters,2013,110:16.

[10] Solomon M M.Algorithms for the vehicle routing and scheduling problems with time window constraints[J].Operations research,1987,35(2):254-265.