城市物流配送的車輛路徑算法研究.pdf

1、城市物流配送是城市物流活動(dòng)的一個(gè)重要環(huán)節(jié)。科學(xué)有效的城市物流配送體系，一方面有利于城市經(jīng)濟(jì)健康發(fā)展，另一方面有利于緩解現(xiàn)代城市中環(huán)境污染與交通堵塞嚴(yán)重、交通事故頻發(fā)的問題。物流配送是連接生產(chǎn)與消費(fèi)的一種中介服務(wù)，也是物資供應(yīng)的重要環(huán)節(jié)之一。一般意義上的城市物流配送運(yùn)輸，是指配送中心不同客戶多頻度、小批量的訂貨要求進(jìn)行組織配送，在合適的時(shí)間，合適的地點(diǎn)，將正確的產(chǎn)品以適當(dāng)?shù)臄?shù)量準(zhǔn)確地交給客戶，并保證服務(wù)的質(zhì)量和合理的成本。由于從事城市配送

2、的貨運(yùn)汽車工作條件復(fù)雜，不僅配送點(diǎn)多、貨物種類繁多、路況及道路網(wǎng)復(fù)雜，而且運(yùn)輸服務(wù)地區(qū)內(nèi)運(yùn)輸網(wǎng)點(diǎn)分布也不均勻，因此，設(shè)計(jì)合理、有效的配送路線方案，控制物流成本，減少車輛數(shù)量、配送里程，限制車輛在城市中的運(yùn)行時(shí)間，就成為非?，F(xiàn)實(shí)的問題。城市物流配送作業(yè)的重點(diǎn)將是如何高效的使用車輛并決定最“科學(xué)經(jīng)濟(jì)”的行駛路線，使商品能夠以合理的成本送達(dá)顧客手中。
　　本文研究的是如何在城市環(huán)境中實(shí)現(xiàn)科學(xué)有效的配送規(guī)劃。目前的物流配送規(guī)劃研究大多放在

3、采用啟發(fā)式算法逐漸逼近最優(yōu)解，主要采用的方法是遺傳算法、免疫算法、退火算法、禁忌搜索算法及神經(jīng)網(wǎng)絡(luò)算法等，如姜大立建立了VRP的遺傳算法,WEE-KTI重點(diǎn)研究了禁忌算法和遺傳算法混合的啟發(fā)式算法,1991年，Gendreau等人將禁忌搜索方法應(yīng)用于VRP。
　　本文中采用的是蟻群算法和聚類算法。蟻群算法是受自然界中真實(shí)蟻群覓食行為的啟發(fā)而提出的一種啟發(fā)式搜索算法。它具有正反饋、并行計(jì)算、較強(qiáng)的魯棒性等諸多特點(diǎn)。然而，一般蟻群算法

4、在車輛路徑問題過程中容易出現(xiàn)過早收斂或停滯現(xiàn)象，而且蟻群算法的搜索時(shí)間較長。為了解決這些問題，本文在認(rèn)真分析國內(nèi)外VRP研究的基礎(chǔ)上，將蟻群算法與聚類算法相結(jié)合，提出了一個(gè)二階段啟發(fā)式車輛路徑算法。
　　該算法首先利用空間聚類的方法，對交通網(wǎng)絡(luò)進(jìn)行簡化。以交通網(wǎng)絡(luò)中各個(gè)結(jié)點(diǎn)之間行駛距離作為聚類的度量，以車輛容量為聚類的約束，將所有結(jié)點(diǎn)分配到各個(gè)簇中，形成有限個(gè)簇，再將每個(gè)簇抽象為一個(gè)新的結(jié)點(diǎn)，最終將整個(gè)交通網(wǎng)絡(luò)（或者稱為圖）G簡化