求解車(chē)輛路徑問(wèn)題的蟻群優(yōu)化算法研究及應(yīng)用.pdf

1、交通運(yùn)輸控制著國(guó)民經(jīng)濟(jì)發(fā)展的動(dòng)脈，隨著社會(huì)經(jīng)濟(jì)的高速發(fā)展，物流管理領(lǐng)域受到企業(yè)與學(xué)者越來(lái)越多的關(guān)注，并從早期傳統(tǒng)的運(yùn)輸服務(wù)逐步發(fā)展成為以信息技術(shù)和管理技術(shù)為核心的綜合物流體系。車(chē)輛路徑問(wèn)題(Vehicle Routing Problem，VRP)作為運(yùn)籌學(xué)和組合優(yōu)化領(lǐng)域的熱點(diǎn)問(wèn)題，如企業(yè)鐵路的智能調(diào)度，物流公司的車(chē)輛調(diào)度，城市公交車(chē)的路線制定，鐵路及航空日程的安排，校車(chē)的路線制定等。這些問(wèn)題與現(xiàn)實(shí)生活息息相關(guān)，因此，研究車(chē)輛路徑問(wèn)題有很

2、重要的現(xiàn)實(shí)意義。
　　目前，車(chē)輛路徑問(wèn)題有一定的研究成果，主要集中在:多配送中心問(wèn)題的研究側(cè)重為尋求整個(gè)行車(chē)路程最短或費(fèi)用最少方面;同時(shí)取送貨問(wèn)題、帶時(shí)間窗問(wèn)題的研究大多是單一性問(wèn)題方面。而對(duì)于最小最大的車(chē)輛路徑問(wèn)題研究文獻(xiàn)的報(bào)導(dǎo)較少見(jiàn)，需要開(kāi)創(chuàng)性探討;帶時(shí)間窗同時(shí)取送貨車(chē)輛路徑問(wèn)題、開(kāi)放式車(chē)輛路徑問(wèn)題等此類(lèi)VRP的研究也缺乏有效的算法來(lái)進(jìn)行求解，亟待進(jìn)一步拓展。
　　近年來(lái)，蟻群算法(Ant Colony Algorith

3、m，ACA)憑借著其極強(qiáng)的魯棒性在很多研究領(lǐng)域被廣泛應(yīng)用。本文采用改進(jìn)的蟻群優(yōu)化算法實(shí)現(xiàn)對(duì)各類(lèi)車(chē)輛路徑問(wèn)題進(jìn)行求解，通過(guò)實(shí)驗(yàn)仿真并對(duì)比相關(guān)算法分析，本文提出的算法有較好的優(yōu)化性能和應(yīng)用效果。
　　本論文的主要研究工作如下:
　　(1)為求解最小最大車(chē)輛路徑問(wèn)題，提出一種動(dòng)態(tài)自適應(yīng)蟻群優(yōu)化算法(Dynamic Max Min Ant System-Min Max Vehicle Routing Problem,DMMAS-MM

4、VRP)，算法采用動(dòng)態(tài)最大最小螞蟻系統(tǒng)策略對(duì)最優(yōu)解進(jìn)行調(diào)整，每次迭代更新τmin，將τmin作為當(dāng)前信息素矩陣最大值的函數(shù)，根據(jù)當(dāng)前最優(yōu)弧來(lái)調(diào)整選擇弧的概率;采用一種灰色模型來(lái)預(yù)測(cè)及控制信息素矩陣的邊界，以增強(qiáng)蟻群算法參數(shù)的自適應(yīng)性能;并對(duì)信息素濃度相對(duì)較高的多個(gè)節(jié)點(diǎn)及其附近的邊，利用信息素關(guān)聯(lián)累積規(guī)則進(jìn)行信息素更新。將DMMAS-MMVRP算法進(jìn)行3種場(chǎng)景的實(shí)例測(cè)試，仿真結(jié)果表明，該算法與線性規(guī)劃(Linear Program，LP)

5、算法、其他相關(guān)的蟻群算法相比，優(yōu)化性能和應(yīng)用效果較好。
　　(2)為求解開(kāi)放式車(chē)輛路徑問(wèn)題，提出一種基于隨機(jī)配載的混合蟻群優(yōu)化算法(Hybrid Ant Colony Optimization，HACO)。首先采用一種隨機(jī)配載車(chē)輛的方法生成初始解集，利用蟻群優(yōu)化算法得到最優(yōu)解，然后對(duì)其進(jìn)行編碼作為粒子群算法的第0個(gè)粒子，選擇初始適應(yīng)值將其設(shè)置為個(gè)體歷史最優(yōu)解，再進(jìn)行全局最優(yōu)解的計(jì)算，對(duì)每個(gè)粒子的交換序V給出求解結(jié)果，將交換序操作于

6、每個(gè)微粒的位置，并利用側(cè)步爬山策略進(jìn)行局部搜索，以得到個(gè)體歷史最優(yōu)解和全局最優(yōu)解。對(duì)基準(zhǔn)問(wèn)題進(jìn)行仿真，結(jié)果表明與其他相關(guān)啟發(fā)式算法相比，本文算法可以快速、有效得到已知最優(yōu)解或近似解。
　　(3)為求解帶時(shí)間窗車(chē)輛路徑問(wèn)題，針對(duì)傳統(tǒng)螞蟻遺傳混合算法參數(shù)靜態(tài)設(shè)置、冗余迭代以及收斂速度慢等缺點(diǎn)，提出一種動(dòng)態(tài)混合蟻群優(yōu)化算法(Dynamically Hybrid Ant Colony Optimization，DHACO)。首先借助最大最

7、小蟻群系統(tǒng)(Max-Min Ant System，MMAS)得到初始解，利用蟻群優(yōu)化算法求解帶時(shí)間窗車(chē)輛路徑問(wèn)題的基本可行解;接著采用遺傳算法交叉和變異操作對(duì)局部解和全局最優(yōu)解進(jìn)行二次優(yōu)化，從而得到最優(yōu)解;最后利用螞蟻遺傳混合算法融合策略，動(dòng)態(tài)交叉調(diào)用兩種算法，根據(jù)云關(guān)聯(lián)規(guī)則自適應(yīng)控制蟻群算法參數(shù)。該動(dòng)態(tài)混合蟻群優(yōu)化算法有效減小無(wú)效迭代次數(shù)，加快了收斂速度。仿真結(jié)果分析表明，該算法與其他相關(guān)的啟發(fā)式算法相比，優(yōu)于某些實(shí)例的已知最優(yōu)解。<

8、br>　　(4)為求解帶時(shí)間窗的同時(shí)取送貨車(chē)輛路徑問(wèn)題，針對(duì)傳統(tǒng)螞蟻與其他啟發(fā)式算法混合所得算法的優(yōu)缺點(diǎn)，提出一種改進(jìn)混合蟻群優(yōu)化算法(Improved Hybrid Ant Colony Optimization，IHACO)。首先將蟻群分成數(shù)目相同的若干螞蟻?zhàn)尤?，利用粒子群?lái)優(yōu)化ACO算法的參數(shù)，并對(duì)每個(gè)螞蟻?zhàn)尤哼M(jìn)行信息素交換操作;其次利用一種基于插入的啟發(fā)式方法來(lái)構(gòu)造帶時(shí)間窗的同時(shí)取送貨車(chē)輛路徑問(wèn)題的弱可行解，再利用類(lèi)似的方法將弱

9、可行解轉(zhuǎn)化為強(qiáng)可行解;局部搜索采用變鄰域下降搜索、交叉、反轉(zhuǎn)，有助于在當(dāng)前的鄰域中搜索更好的解。該改進(jìn)混合蟻群優(yōu)化算法與其他相關(guān)的啟發(fā)式算法相比，大大加快收斂速度。
　　(5)為了驗(yàn)證求解車(chē)輛路徑問(wèn)題所提出的蟻群優(yōu)化算法的可行性與有效性，結(jié)合企業(yè)鐵路運(yùn)輸?shù)膶?shí)際狀況，將算法應(yīng)用到企業(yè)鐵路智能調(diào)度計(jì)劃系統(tǒng)中。本文以企業(yè)鐵路取送貨作業(yè)為研究對(duì)象，將蟻群優(yōu)化算法應(yīng)用于解決現(xiàn)實(shí)中的車(chē)輛調(diào)度問(wèn)題。首先分析了車(chē)輛調(diào)度問(wèn)題中車(chē)輛作業(yè)的特點(diǎn)，建立企