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

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

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

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