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

0 引言

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

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

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

1 有時間窗車輛路徑問題的定義

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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

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

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

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

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

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

表6 RC2類數(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] 張炯，郎茂祥.有時間窗配送車輛調(diào)度問題的禁忌搜索算法[J].北方交通大學(xué)學(xué)報，2004(2):103－107.

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

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

[6] 范小寧，徐格寧，楊瑞剛.車輛配送路徑優(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] 萬旭，林建良，楊曉偉.改進(jì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.