求解車輛路徑問題的蟻群優(yōu)化算法研究及應用.pdf

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

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

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

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

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

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

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

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

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