考慮車輛利用率的車輛路徑問題的蟻群算法研究與實現(xiàn).pdf

1、Dantzig和Ramser于1959年首次提出車輛路徑問題(VRP，Vehicle RoutingProblem)。近幾十年來，無論是國外還是國內(nèi)，VRP問題都是一個非常活躍的研究領域。優(yōu)化物流車輛配送路徑，不僅能降低物流成本，還能緩解交通壓力、減少運輸污染和保護生態(tài)環(huán)境。安排合理的車輛配送路徑是配送業(yè)務中一項非常重要的工作。 本文對一般VRP問題的數(shù)學模型進行了分析研究，針對其未考慮參與運輸車輛的利用效率的問題，將車輛利用率

2、成本引入到優(yōu)化函數(shù)中，建立了考慮車輛利用率的VRP問題的數(shù)學模型。 在解決考慮車輛利用率的VRP問題時，采用了仿生學優(yōu)化算法一蟻群算法(ACA，Ant Colony Algorithm)。根據(jù)實際模型，首先將螞蟻、目的地、路徑、路徑總長度、信息素、路徑期望度這些要素對應到具體模型中；其次，改進了集合tabu的設置，tabu表示螞蟻不允許選擇的客戶點集合，本文中集合tabu除經(jīng)典蟻群算法中所包括的螞蟻目前己經(jīng)走過的客戶點外，還增加

3、了具體模型的約束條件限制不能訪問的三類客戶點；并將客戶點的貨物需求量qi引入到路徑期望度參數(shù)ηij的計算中，使螞蟻在選擇客戶點時，除了考慮優(yōu)先選擇路徑最短的客戶外，還要優(yōu)先選擇能使車輛總貨運量最大的客戶；另外，為了增加搜索范圍，本文借鑒了蟻群系統(tǒng)(ACS)中所采用的狀態(tài)轉(zhuǎn)移規(guī)則；最后通過具體算例，驗證了該改進算法的有效性及穩(wěn)定性。 在理論研究的基礎上，設計開發(fā)了基于改進蟻群算法的車輛路徑問題的實驗系統(tǒng)，一方面，便于分析比較算法改