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

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

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

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