設施定位和車輛路線問題模型及其啟發(fā)式算法研究.pdf

1、隨著物質需求的多樣性和不規(guī)則性以及貿(mào)易呈全球化趨勢的發(fā)展，作為“第三利潤源泉”的物流，其作用和地位顯得比任何時候都更為重要，對經(jīng)濟活動的影響也日益明顯。目前，許多發(fā)達國家和地區(qū)已形成了比較成熟的物流管理理念、先進的物流技術和高效的物流運營系統(tǒng)。我國在進入21世紀之后，也逐漸加快了現(xiàn)代物流的發(fā)展，以提高生產(chǎn)企業(yè)在國際上的競爭能力。為此企業(yè)管理者都希望能協(xié)調物流系統(tǒng)中的各個環(huán)節(jié)，以最低的價格、最好的服務來滿足顧客的需要，所以物流決策顯得極為

2、重要。 在傳統(tǒng)的物流決策模型中，定位-配給問題(location allocationproblems，LAP)和車輛運輸路線問題(vehicle routing problem，VRP)是最值得關注的兩個方面。但是在LAP模型中僅考慮設施(工廠、庫存點、分銷中心等)的定位與貨物配給之間的相互關系，卻忽視了對車輛巡回行程路線的考慮，這就有可能導致分銷成本的增長；而在VRP模型中，雖然考慮了車輛在各個客戶點間巡回訪問的特性，使提高

3、運輸效率成為可能，但卻沒有分析設施的選址問題，這將會使得整個物流系統(tǒng)成本仍有一定的下降空間。因此，本文運用系統(tǒng)分析的思想和方法，研究了物流系統(tǒng)中的設施定位配給和車輛路線組合優(yōu)化問題--定位車輛路線問題(location routing problem，LRP)。 由于LRP及其擴展模型屬于NP-hard問題，在具有一定規(guī)模節(jié)點數(shù)情況下目前仍難以求得最優(yōu)解。因此對LRP模型進行系統(tǒng)化優(yōu)化求解研究具有重要的理論價值，其理論意義則在于

4、針對NP-hard模型大規(guī)模數(shù)值計算的解法突破和創(chuàng)新，同時也是發(fā)展基于電子商務的城市物流配送理論的重要理論基礎，這將為日后面對巨大交易量的電子商務環(huán)境下開發(fā)自動物流配送調度系統(tǒng)軟件具有非常重要的現(xiàn)實意義。 本文在分析了物流系統(tǒng)中選址、運輸以及庫存的互相制約關系基礎上，從提高物流系統(tǒng)整體效率為出發(fā)點，站在理論研究層面，針對物流集成化數(shù)學模型及其啟發(fā)式解法進行了系統(tǒng)研究，即從系統(tǒng)化的角度分析和研究了復雜物流環(huán)境下的LRP優(yōu)化問題，論

5、文從問題的界定、模型的建立、模型的檢驗、啟發(fā)式算法求解途徑、組合優(yōu)化求解思路、算法實現(xiàn)及數(shù)據(jù)分析等多個方面對LRP問題進行了深入、具體的研究分析，得到了如下研究成果： (1)論文系統(tǒng)性地研究了LRP數(shù)學模型，對定位-配給問題、車輛路線問題、定位-車輛路線問題、帶庫存的定位-車輛路線問題典型數(shù)學模型及其構成進行了科學描述，通過小規(guī)模測試數(shù)據(jù)采用LINGO軟件對LRP數(shù)學模型給予了標定，為今后人們在此方面的進一步研究奠定了模型基礎：

6、 (2)針對LRP數(shù)學模型屬性特點，分別采用禁忌搜索算法(Tabu searchalgorithm，TS)、模擬退火算法(Simulated annealing algorithm，SA)對LRP數(shù)學模型進行了優(yōu)化求解，編制了相應算法程序軟件，并采用具有一定規(guī)模的仿真測試數(shù)據(jù)測算了所提出算法求解LRP模型的有效性，同時經(jīng)過大量數(shù)值模擬計算找出了其算法求解LRP模型的優(yōu)良參數(shù)搭配。通過與有關文獻對比，證明本文提出的求解思路對于LR

7、P模型求解更具有優(yōu)良特性； (3)提出了遺傳一模擬退火組合算法和遺傳一禁忌搜索組合算法求解LRP模型的思路，并進行了相應的算法研究，通過編制計算軟件和具有一定規(guī)模的數(shù)據(jù)測試，實現(xiàn)了組合啟發(fā)式算法求解LRP模型的設想，這對于發(fā)展和完善組合優(yōu)化理論亦具有重要的科學理論價值。 (4)分析了在庫存管理策略下，庫存控制策略對設施選址和路線優(yōu)化問題的影響，在此基礎上建立了更為復雜的定位-路線-庫存組合優(yōu)化模型(Combined Lo

8、cation Routing and Inventory Problems，CLRIP)，并設計了求解該模型的一種兩階段啟發(fā)式算法，通過小規(guī)模測試數(shù)據(jù)測算證明帶庫存的定位路線組合優(yōu)化模型比定位-路線問題和庫存控制模型獨立優(yōu)化的情形更能有效降低物流系統(tǒng)成本，并為進一步深入研究該問題的解法提供了基本思路。 (5)提供了LRP模型從8個節(jié)點至200個節(jié)點不同規(guī)模情形下的系列測試數(shù)據(jù)源，為今后開展LRP研究者提供了算法科學對比途徑，同時