現(xiàn)代物流配送中心車輛線路優(yōu)化方案研究與應用.pdf

1、物流配送是物流活動中直接與消費者相連的環(huán)節(jié)。在物流的各項成本中,配送成本占了相當高的比例。配送車輛優(yōu)化調(diào)度管理的合理與否對配送速度、成本、效益影響很大,是物流配送中非常重要的一項活動。車輛優(yōu)化調(diào)度問題一般可根據(jù)空間特性和時間特性分為車輛線路規(guī)劃問題和車輛調(diào)度問題。當不考慮時間要求,僅根據(jù)空間位置安排車輛的線路時稱為車輛線路或車輛路徑規(guī)劃問題(VRP——Vehicle Routing Problem)；當考慮時間要求安排運輸線路時稱為車輛

2、調(diào)度問題VSP(VSP--Vehicle Scheduling Problem)。某些學者將有時間要求的車輛路徑規(guī)劃問題稱為Vehicle Routing Problem with Time Windows(VRPTW)。 本文以“濟南煙草集團現(xiàn)代化物流配送系統(tǒng)”為研究和實踐背景,在對現(xiàn)有配送車輛線路優(yōu)化問題(VRP)算法歸類分析和對企業(yè)實際業(yè)務要求提煉基礎(chǔ)上,考慮城市街道中方向性和具體路況等因素,將城市配送用戶數(shù)量非常多的大規(guī)模VRP

3、問題分解為兩個求解過程：首先,進行配送線路區(qū)域劃分,對于煙草行業(yè)城市銷售網(wǎng)點超過1萬個甚至是幾萬個網(wǎng)點的情況下將配送線路劃分為幾個物理區(qū)域,是考慮計算機運行效率行之有效的方法；其次,在每個已劃分的區(qū)域中進行單車線路優(yōu)化即TSP(Traveling Salesman Problem,旅行商問題)問題的求解。通過以上兩個過程可以較好地解決大規(guī)模配送網(wǎng)點情況下要在計算機運行效率能滿足用戶要求的時間內(nèi)求得VRP這類NP-hard問題最優(yōu)或較優(yōu)解

4、的矛盾。這種方法對一個配送中心,但配送網(wǎng)點數(shù)目極大的配送車輛線路優(yōu)化問題具有普適性。 本文主要以VRP車輛線路優(yōu)化運籌學理論為指導,重點運用啟發(fā)式VRP算法,包括節(jié)約里程和改進的節(jié)約時程算法、先分組后單車線路優(yōu)化的二階段方法以及帶軟時間窗(即用戶對時間要求不是非?？量潭侨蝿罩灰谀扯螘r間內(nèi)完成即可的配送方式)和車輛配載能力的VRP模型。對城市真實道路建立基于GIS系統(tǒng)的配送網(wǎng)點、關(guān)鍵點的道路信息庫,并運用最短路徑Dijkstra算法求