有時間窗車輛路徑問題的模型及算法研究.pdf

1、配送是物流系統(tǒng)中很重要的一個環(huán)節(jié)，是一系列狹義的物流活動的集成，它要求在規(guī)定的時間內(nèi)以一定的方式將確定的貨物送到指定的地點。而車輛路徑問題是研究貨物運輸成本最小的物流配送問題。車輛路徑問題是運輸組織優(yōu)化中的核心問題，由于它將運籌學(xué)理論與生產(chǎn)實踐緊密地結(jié)合，因此近幾十年取得了豐富的研究成果，并且被稱為“最近幾十年運籌學(xué)領(lǐng)域最成功的研究之一”。 本文分析和總結(jié)了車輛路徑問題的歷史和研究現(xiàn)狀，以及常用模型、時間復(fù)雜度，以綜合性能的角度

2、對求解VRPTW問題的算法進(jìn)行了一定的歸納和分析，并在此基礎(chǔ)上確定了本文的研究方法和目標(biāo)。同時結(jié)合實際提出了本文的研究問題——帶時間窗的車輛路徑問題(VRPTW)，建立了以車輛容量和客戶需求等為約束條件，以配送運輸成本為目標(biāo)函數(shù)的VRPTW數(shù)學(xué)模型。提出了一種兩步優(yōu)化的實現(xiàn)策略。 第一步，選取動態(tài)的push forward insertion heuristics(Stochastic PFIH)算法產(chǎn)生機制構(gòu)建問題的初始解，保

3、證了初始解的多樣性，同時在產(chǎn)生的初始解中設(shè)置了限制條件，實現(xiàn)對初始解的篩選，為第二階段路徑優(yōu)化提供了高質(zhì)量的初始解；以改進(jìn)的大規(guī)模鄰域搜索為新解產(chǎn)生機制，并將模擬退火算法和大規(guī)模鄰域搜索算法混合來進(jìn)行路徑優(yōu)化，得到問題的最優(yōu)解，該混合算法充分利用了兩種算法的優(yōu)點，克服了它們的缺點。 第二步，提出一種時間窗修正規(guī)則來調(diào)整時間窗，使得車輛在每個客戶的等待時間為零，真正實現(xiàn)了路徑的優(yōu)化，節(jié)省了成本，并給出了理論證明。最后通過VC++編