資源描述：
《有時(shí)間窗的車輛路徑問題改進(jìn)蟻群算法研究》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫(kù)。
1、有時(shí)間窗的車輛路徑問題改進(jìn)蟻群算法研究摘要：針對(duì)目前蟻群算法在求解有時(shí)間窗的車輛路徑問題上較少對(duì)蟻群算法本身進(jìn)行優(yōu)化的問題，提出了一種改進(jìn)蟻群算法，通過改進(jìn)狀態(tài)轉(zhuǎn)移概率和信息素更新規(guī)則，以及使用改進(jìn)的精英螞蟻策略，改善蟻群算法搜索能力。通過對(duì)Solomon標(biāo)準(zhǔn)數(shù)據(jù)集的實(shí)驗(yàn)，結(jié)果表明改進(jìn)的蟻群算法在求解有時(shí)間窗車輛路徑問題上是有效的。關(guān)鍵詞：最大最小蟻群算法；有時(shí)間窗車輛路徑問題；Solomon標(biāo)準(zhǔn)數(shù)據(jù)集中圖分類號(hào)：U116.2文獻(xiàn)標(biāo)識(shí)碼：AAbstract：Currentresearchonantcolonyalgorithmforvehicleroutingproblemwi
2、thtimewindows，theantcolonyalgorithmitselfislesstobeoptimized，soanimprovedantcolonyalgorithmwasestablishedtoimprovetheantcolonyalgorithmsearchcapabilitiesbyimprovingthestatetransitionprobabilityandpheromoneupdaterule，andusingimprovedeliteantstrategy.ByusingSolomonstandarddatasets，theexperimen
3、talresultsshowthattheimprovedantcolonyalgorithmforsolving8vehicleroutingproblemwithtimewindowsisvalid.Keywords：max-minantcolonyoptimization；vehicleroutingproblemwithtimewindows；Solomondataset0引言車輛路徑問題（VehicleRoutingProblem，VRP）屬于組合優(yōu)化問題，其理論涉及到運(yùn)籌學(xué)、管理學(xué)、交通運(yùn)輸、計(jì)算機(jī)應(yīng)用等多個(gè)學(xué)科。VRP問題中加入節(jié)點(diǎn)可訪問的時(shí)間窗約束即成為有時(shí)間窗
4、車輛路徑問題（VehicleRoutingProblemwithTimeWindows，VRPTW）。由于現(xiàn)實(shí)生活中很多問題可以歸結(jié)為VRPTW，因此VRPTW的研究受到學(xué)術(shù)界的廣泛重視。VRPTW已被證明為NP-hard問題，這意味著當(dāng)節(jié)點(diǎn)規(guī)模較大時(shí)，很難在多項(xiàng)式時(shí)間內(nèi)得到問題的精確解，因此啟發(fā)式算法因其快速高效構(gòu)建可行解的優(yōu)點(diǎn)成為人們的首選。Ombuki8Beatrice等[1]利用遺傳算法、Tavakkoli-Moghaddam等[2]利用模擬退火算法來求解VRPTW問題，但二者都存在收斂速度慢的問題；張炯和郎茂祥[3]使用的禁忌算法、馬炫等[4]使用的粒子群算法則容易陷
5、入局部最優(yōu)解。為解決這些問題，蟻群算法的魯棒性和構(gòu)造簡(jiǎn)單使得其經(jīng)常被用于與其他算法構(gòu)成組合優(yōu)化算法。但無論是殷志鋒和張巖松[5]提出的基于進(jìn)化規(guī)劃和最大-最小蟻群算法相融合的混合蟻群算法，還是范小寧等[6]采用遺傳算法和蟻群算法的結(jié)合，以及ZhangXiaoxia[7]將蟻群算法和禁忌搜索結(jié)合等都只是將蟻群算法作為構(gòu)造可行解的方法，并大量使用局部搜索優(yōu)化算法，而缺少對(duì)蟻群算法本身的改進(jìn)。本文對(duì)ThomasThutzle和HolgerHoos提出的最大最小蟻群系統(tǒng)（MAX-MINantcolonysystem）在轉(zhuǎn)移概率矩陣計(jì)算、信息素更新等關(guān)鍵因素上進(jìn)行改進(jìn)，以提高其全局優(yōu)化能
6、力。為更好地說明本改進(jìn)算法的優(yōu)越性，在原始MMAS算法和本文算法測(cè)試Solomon標(biāo)準(zhǔn)數(shù)據(jù)集時(shí)均不使用局部?jī)?yōu)化算法。1有時(shí)間窗車輛路徑問題的定義VRPTW的一般定義如下：從某一物流中心用多臺(tái)配送車輛從多個(gè)客戶取貨，每個(gè)客戶的位置和需求量和需求時(shí)間一定，每個(gè)客戶只能由一臺(tái)車輛服務(wù)一次，要求合理安排車輛配送路線，使目標(biāo)函數(shù)得到最優(yōu)，即在不違背約束條件下所用車輛數(shù)最少和行走路線長(zhǎng)度最短。本文將最小化車輛數(shù)量作為第一目標(biāo)，最小化車輛行駛路線長(zhǎng)度作為第二目標(biāo)。2最大最小蟻群算法及其在有時(shí)間窗車輛路徑問題中的應(yīng)用8MMAS對(duì)AS的關(guān)鍵改進(jìn)在于將路徑上的信息素濃度限定τ■，τ■之間，這較好地
7、避免了搜索陷入局部最優(yōu)解。因?yàn)樵谒阉鬟^程中，隨著信息素的揮發(fā)和累積，某些路徑上的信息素濃度會(huì)遠(yuǎn)遠(yuǎn)高于其他路徑，從而導(dǎo)致搜索過早停滯。2.1狀態(tài)轉(zhuǎn)移概率。螞蟻在選擇下一個(gè)節(jié)點(diǎn)時(shí)，在滿足容量約束和時(shí)間窗約束下，需要考慮如下三個(gè)因素：①通往下個(gè)節(jié)點(diǎn)的路徑長(zhǎng)度以及路徑上的信息素濃度[8]。②時(shí)間窗因素的擇優(yōu)性[8]，由下個(gè)客戶j的時(shí)間窗寬度和所在客戶i到達(dá)下個(gè)客戶j的時(shí)間等因素決定。這種擇優(yōu)性的優(yōu)先原則為，需等待時(shí)間較短優(yōu)先原則和時(shí)間窗較小優(yōu)先原則。③基于Wissner-Gross，A.D.[9]的
