蟻群算法及其在車輛路徑問題中的應(yīng)用研究.pdf

1、隨著市場競爭的加劇，物流已經(jīng)成為提高市場競爭力和核心競爭力的重要手段，而運(yùn)輸通常代表物流成本中最大的單項成本。所以研究車輛路徑問題（Vehicle Routing Problem，VRP），通過設(shè)計合理的運(yùn)輸路線，使車輛在滿足服務(wù)要求的同時，成本最小化，從而減少物流整體費(fèi)用，具有重要意義。根據(jù)車輛容量、車型等限制的不同，有多種類型的VRP，本文針對兩種問題進(jìn)行了討論：有時間窗的車輛路徑問題(the Multi-depots Vehicl

2、e Routing Problem with Time Windows,MDVRPTW）和有時間窗的具有同時配送與回收的車輛路徑問題（the Vehicle Routing Problem with Simultaneous Pick-up and Delivery,VRPSDP）。
　　VRP已被證明為NP難題，對其算法的研究大部分集中在啟發(fā)式算法上，而蟻群算法是近年來新興的啟發(fā)式算法，本文采用蟻群算法對上述兩個問題進(jìn)行求解。<

3、br>　　本文主要工作有：
　　1、針對基本蟻群算法易陷入局部最優(yōu)的缺陷，本文從調(diào)整起始搜索節(jié)點和交換信息素兩個方面提出了改進(jìn)，在基準(zhǔn)問題上的實驗表明該算法取得的目標(biāo)值較優(yōu)，而且取得目標(biāo)值時所需的迭代次數(shù)較少。
　　2、給出MDVRPTW的數(shù)學(xué)模型，并采用蟻群算法對該模型求解。求解時采用整體法將多個車場虛擬為一個車場，每次搜索從虛擬車場中隨機(jī)選擇一個實際車場作為出發(fā)車場，采用SOLOMON的Nearest Neighbour

4、插入式算法，搜索一條可行路徑，服務(wù)結(jié)束后回到出發(fā)車場。
　　3、給出了VRPSDPTW的數(shù)學(xué)模型，采用蟻群算法求解該模型時，引入一個變量解決了該問題中車輛的容量判斷問題，并給出了同時考慮剩余容量符合度和時間窗的啟發(fā)式函數(shù)，在此基礎(chǔ)上給出了蟻群算法的實現(xiàn)過程。
　　4、對上述兩個問題編寫C＋＋程序，選擇VRP Web提供的基準(zhǔn)問題進(jìn)行實驗，結(jié)果表明本文給出的兩個算法得到的結(jié)果較優(yōu)，具有較強(qiáng)的實際意義，且所需計算時間也在合理范圍