混合蟻群算法求解帶時(shí)間窗的車輛路徑問題.pdf

《混合蟻群算法求解帶時(shí)間窗的車輛路徑問題.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、·混合蟻群算法求解帶時(shí)間窗的車輛路徑問題·文章編號(hào)：10O2-4581(2015)03—0006—06混合蟻群算法求解帶時(shí)間窗的車輛路徑問題王建，李紅云，楊燕飛WangJian，LiHongyun，YangYanfei(北京航空航天大學(xué)交通科學(xué)與工程學(xué)院，北京100191)摘要：采用營運(yùn)車輛的最短行駛距離作為帶時(shí)間窗車輛路徑問題的優(yōu)化目標(biāo)，在混合蟻群算法中采用信息素3層更新策略以完成對車輛的調(diào)度，信息素?fù)]發(fā)自適應(yīng)策略充分考慮實(shí)時(shí)路況，考慮信息素空間擴(kuò)散特性的局部更新策略，更加忠實(shí)于自然界的真實(shí)螞蟻系統(tǒng)，可以提高算法的收斂速度，采用閾值判斷的全局信息素更新策

2、略可以防止算法陷入局部最優(yōu)。通過cjfj}語言實(shí)現(xiàn)了混合蟻群算法的計(jì)算機(jī)求解，最后對10個(gè)仿真實(shí)例進(jìn)行仿真計(jì)算，結(jié)果表明，混合蟻群算法收斂快，尋優(yōu)結(jié)果穩(wěn)定。關(guān)鍵詞：車輛路徑；時(shí)間窗；信息素更新策略；蟻群算法中圖分類號(hào)：U491．2l：TP391．9文獻(xiàn)標(biāo)志碼：ADOI：10．14175~．issn．1002．4581．2015．03．002車輛路徑問題(VehicleRoutingProblem，善蟻群算法的全局收斂性，并拓寬蟻群算法的應(yīng)VRP)是營運(yùn)車輛研究領(lǐng)域中一個(gè)具有重要理論用領(lǐng)域。和現(xiàn)實(shí)意義的問題L1J。由于該問題屬于NP—hard文中對蟻群算法的

3、分布和協(xié)作機(jī)制進(jìn)行了深(Non—deterministicPolynomialHard，非確定性多項(xiàng)入研究，在分析已有蟻群系統(tǒng)的優(yōu)缺點(diǎn)的基礎(chǔ)上式難題)，所以尋找到一種高效而精確的算法的可提出了基于實(shí)時(shí)路況的3層信息素更新策略，提能性微乎其微，而自然界中生物群體的合作與競出了考慮時(shí)間窗約束的基于多種蟻群系統(tǒng)的混合爭等復(fù)雜行為產(chǎn)生的群體智能往往對解決某些特蟻群算法(MixedAntColonyAlgorithm，MACO)，定的隨機(jī)尋優(yōu)問題提供了高效的解決方法，因此在算法中充分考慮實(shí)時(shí)路況更新對道路通行能力人們開始嘗試?yán)梅律悄芩惴ㄇ蠼?。的影響，以增?qiáng)蟻群算

4、法在求解動(dòng)態(tài)車輛路徑問蟻群算法模型來源于對自然界真實(shí)螞蟻行為題的算法性能。的觀測，蟻群在解決優(yōu)化以及分布控制問題上具有很高的智能性，因此蟻群算法對解決復(fù)雜尋優(yōu)1車輛路徑問題描述問題的新型算法的開發(fā)與應(yīng)用具有重要的啟發(fā)價(jià)值。蟻群算法隨機(jī)尋優(yōu)機(jī)制的核心內(nèi)容是分布性營運(yùn)車輛的調(diào)度問題屬于車輛路徑問題，但和協(xié)作性，而營運(yùn)車輛具有同蟻群相似的分布性在普通的車輛路徑問題上增加了一些約束，主要與協(xié)作性。目前采用蟻群算法求解車輛路徑問題體現(xiàn)在以下3個(gè)方面：已經(jīng)取得了很多的研究成果[2-4]。但是蟻群算法也1)營運(yùn)車輛的調(diào)度不只是單純地考慮最短路存在著前期收斂速度慢，容易陷

5、入局部最優(yōu)等缺徑，同時(shí)考慮車輛運(yùn)行過程中所經(jīng)路徑等級、運(yùn)點(diǎn)。國內(nèi)外學(xué)者針對蟻群算法存在的缺點(diǎn)進(jìn)行一行時(shí)間等問題，最終達(dá)到降低整體成本的目的；系列的改進(jìn)，包括Max—Min螞蟻系統(tǒng)，精英螞蟻2)營運(yùn)車輛作為一種商業(yè)化的信息溝通形系統(tǒng)，基于排序的螞蟻系統(tǒng)，基于混沌理論的螞式，要充分考慮以人為本，要注重企業(yè)形象、提蟻系統(tǒng)等【5]，這些改進(jìn)有一個(gè)共同的目的，就是高顧客滿意度；在合理時(shí)間復(fù)雜度的限制條件下，盡可能提高蟻3)營運(yùn)車輛數(shù)目有限，載貨量一定并且客戶群算法在一定空間復(fù)雜度下的尋優(yōu)能力，從而改的訂單具有時(shí)間要求?！せ旌舷伻核惴ㄇ蠼鈳r(shí)間窗的車輛路徑問題·營運(yùn)車

6、輛領(lǐng)域的車輛路徑問題可以簡單描述從蟻巢和食物源之間出發(fā)，路徑AB的長度等于路為：每個(gè)廠商都有一個(gè)倉庫和一批客戶集合，倉徑BC的長度，并且均為路徑AD以及DC的2倍。庫即是配送中心，擁有輛可用于調(diào)度的運(yùn)輸車此時(shí)路徑ABC與路徑ADC上的信息素濃度均為輛，車輛的最大載重量、最大行駛距離和車況已，螞蟻選擇路徑的概率嚴(yán)格與信息素濃度成線知，每個(gè)客戶的位置信息、需求信息已知，車輛性比例關(guān)系，因此分別有p／2只螞蟻選擇ABC與都由倉庫出發(fā)，經(jīng)過若干客戶點(diǎn)之后返回倉庫，ADC。當(dāng)?shù)竭_(dá)什時(shí)刻時(shí)，DC路徑上的螞蟻已形成一個(gè)子回路，假如若干車輛構(gòu)成的子回路集經(jīng)從出發(fā)地到達(dá)目的

7、地，然而由于路徑較長，AB合可以完成對客戶點(diǎn)的不重復(fù)遍歷，那么就構(gòu)成路徑和BC路徑上的螞蟻在點(diǎn)相遇，此時(shí)路徑車輛路徑問題的一個(gè)可行解。通過一定的算法以ADC的信息素濃度為及約束條件尋找可行解，并從可行解的集合中發(fā)TADc+n)=f(f)一f()+P·f()(1)掘滿足總行程最短或者總體成本最低的可行解就是營運(yùn)車輛領(lǐng)域的車輛路徑問題。而此時(shí)路徑ABC上的信息素濃度為鑒于營運(yùn)車輛調(diào)度問題與普通的車輛路徑問c-I-)=(f)一f()+·()(2)題存在以上不同，同時(shí)我國“十二五”提出到2015年構(gòu)建完善的營運(yùn)車輛車聯(lián)網(wǎng)系統(tǒng)，以完成對路式中，zip)表示揮發(fā)掉的信

8、息素?cái)?shù)量，，．c)表況信息的實(shí)時(shí)更新，因此有必要對蟻群算法做出示每