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

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

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

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

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