基于模擬退火算法求解隨機需求定位路線問題研究.pdf

1、隨著社會經濟的飛速發(fā)展，市場競爭已越來越激烈，企業(yè)建立競爭優(yōu)勢的關鍵，已由節(jié)約原材料和提高勞動生產率，轉向建立高效的物流系統(tǒng)。在經濟日益全球化的今天，現代物流作為第三種利潤和第三產業(yè)的重要組成部分，正受到日益廣泛的重視。 物流中心的選址作為物流運作中的基礎要素，其優(yōu)化和求解意義重大，對此問題的研究即為定位配給問題(Location Allocation Problem，LAP)；而車輛路線安排問題(Vehicle Routing

2、 Problem，VRP)作為物流系統(tǒng)的重要組成部分，對物流系統(tǒng)成本也有較大影響，綜合考慮這兩個方面并對其進行優(yōu)化求解設計就形成了定位路線問題(Location Routing Problem，LRP)。LRP以集成的眼光來求解物流系統(tǒng)問題，因此可以從整體上大大降低物流系統(tǒng)總成本。 本文研究的隨機需求LRP問題(Location Routing Problem with Stochastic Demands，LRPSD)是對上述

3、LRP問題的一個擴展，在這一問題中，客戶的需求是不能事先確切獲知的，只是滿足同一種概率分布。由于客戶需求的不確定性和車輛容量的限制，必然使得車輛在行駛至某一客戶處時發(fā)生路由失敗，發(fā)生失敗的車輛返回站點裝貨(或卸貨)之后重新返回服務路線上剩余的客戶。針對這一問題，本文對車輛發(fā)生失敗的次數上限進行了限制，在考慮車輛固定成本、設施建設成本的情況下建立了隨機需求LRP問題的數學模型。 由于上述問題的NP-Hard屬性，本文運用模擬退火算

4、法對求解該問題進行了設計，并用C++和Matlab編程實現了這一算法對問題的求解。求解數據來源于對車輛路線問題solomon25個客戶點的國際標準測試數據的改造而獲得的，求解過程中先利用空間填充曲線和模擬退火算法求解定位配給問題，再用模擬退火算法求解帶隨機客戶需求的車輛路線安排問題，最后將后者的輸出結果返代回定位階段，對設施的選擇進一步優(yōu)化，從而最終求得本文問題的優(yōu)化解。 本文對各階段的求解結果進行了統(tǒng)計分析，結果顯示：對于一定