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

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

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

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

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