時(shí)變網(wǎng)絡(luò)環(huán)境下車輛調(diào)度問題研究.pdf

1、我國(guó)十一五規(guī)劃中將現(xiàn)代物流業(yè)作為今后重點(diǎn)發(fā)展領(lǐng)域，提出到2010年全社會(huì)物流成本下降2—3個(gè)百分點(diǎn)。運(yùn)輸配送是影響物流總成本的重要因素，大約占物流成本的60％。作為物流系統(tǒng)優(yōu)化中關(guān)鍵的一環(huán)，物流配送車輛的優(yōu)化調(diào)度問題成為研究的熱點(diǎn)。在以往的靜態(tài)車輛調(diào)度問題（vehicle routing problem，簡(jiǎn)寫VRP）研究中，車輛路徑安排大部分都是基于確定性的信息，其中包括需求確定、車輛位置確定和車輛在路途的行駛時(shí)間確定，尤其考慮車輛在任

2、意兩節(jié)點(diǎn)（顧客或車場(chǎng)）間的運(yùn)行成本（時(shí)間）只取決于節(jié)點(diǎn)間的距離，通常被認(rèn)為是已知且靜態(tài)的常量。但在實(shí)際的車輛行駛過程中，由于交通管理、交通流量、交通事故、天氣變化、上下班高峰期等因素的影響，車輛的行駛速度總是處在不斷變化之中，從而導(dǎo)致了路網(wǎng)中各個(gè)路段上的運(yùn)行成本（時(shí)間）也相應(yīng)地發(fā)生變化。這種動(dòng)態(tài)變化的情況，靜態(tài)VRP問題的理論和方法已無法適用，這就使得對(duì)時(shí)變網(wǎng)絡(luò)VRP問題的研究成為迫切需要。本論文主要以時(shí)變網(wǎng)絡(luò)VRP的三類子問題作為研究

3、對(duì)象，分別是基于時(shí)段的時(shí)間依賴型旅行商問題（time dependent traveling salesman problem，簡(jiǎn)寫TDTSP）、基于具體位置的TDTSP問題和時(shí)間依賴型車輛調(diào)度問題（time dependent vehicle routing problem，簡(jiǎn)寫TDVRP）。主要研究?jī)?nèi)容如下： 第1章首先介紹了論文所要研究問題的來源及研究目的，進(jìn)而分析了時(shí)變網(wǎng)絡(luò)VRP問題的背景和研究意義，并描述了本文即將討論

4、的三類子問題的研究特點(diǎn)，最后指出了本文的技術(shù)路線和主要研究工作。 第2章在對(duì)大量相關(guān)文獻(xiàn)進(jìn)行總結(jié)提煉的基礎(chǔ)上，綜述時(shí)變網(wǎng)絡(luò)VRP問題的研究現(xiàn)狀。描述了目前對(duì)時(shí)變網(wǎng)絡(luò)問題的研究情況，并對(duì)已研究的時(shí)變網(wǎng)絡(luò)VRP問題進(jìn)行分類，總結(jié)了時(shí)變網(wǎng)絡(luò)特性處理方法的研究現(xiàn)狀。在求解算法方面，對(duì)靜態(tài)VRP問題和時(shí)變網(wǎng)絡(luò)VRP問題的求解算法進(jìn)行綜述，并引入本文將用于求解時(shí)變網(wǎng)絡(luò)VRP問題的大規(guī)模鄰域（very large scale neighbor

5、hood，簡(jiǎn)寫VLSN）搜索技術(shù)，最后指出現(xiàn)有文獻(xiàn)中存在的問題及進(jìn)一步需要研究的方向。 第3章以基于時(shí)段的TDTSP問題作為研究對(duì)象，描述該問題的特征與性質(zhì)，提出一種滿足先入先出（first in first out，簡(jiǎn)寫FIFO）準(zhǔn)則的時(shí)變網(wǎng)絡(luò)特征處理方法，建立問題的數(shù)學(xué)模型，并給出傳統(tǒng)的動(dòng)態(tài)規(guī)劃啟發(fā)式算法求解策略。在求解算法上，采用一種基于VLSN搜索技術(shù)的動(dòng)態(tài)搜索算法求解該問題。通過實(shí)驗(yàn)比較不同算法的性能，并對(duì)算法性能進(jìn)行

6、分析。 第4章以基于位置的TDTSP問題作為研究對(duì)象，描述該問題的特征與性質(zhì)，建立問題的數(shù)學(xué)模型。在求解算法上，同樣采用一種基于VLSN搜索技術(shù)的動(dòng)態(tài)搜索算法求解該問題。通過實(shí)驗(yàn)比較不同算法的性能，并對(duì)算法性能進(jìn)行分析。 第5章以TDVRP問題作為研究對(duì)象，描述該問題的特征與性質(zhì)，提出一種滿足FIFO準(zhǔn)則的時(shí)變網(wǎng)絡(luò)特性處理方法，建立問題的數(shù)學(xué)模型，并給出傳統(tǒng)的最近鄰算法求解策略。在求解算法上，采用一種基于VLSN搜索技術(shù)

7、的動(dòng)態(tài)規(guī)劃啟發(fā)式算法和環(huán)狀交換算法分別求解該問題，共有五類策略。通過實(shí)驗(yàn)比較不同算法的性能，并對(duì)算法性能進(jìn)行分析。 第6章以成都某物流企業(yè)的配送作為背景，收集實(shí)際數(shù)據(jù)，建立該企業(yè)配送的數(shù)學(xué)模型。通過實(shí)際數(shù)據(jù)分析，對(duì)配送環(huán)境進(jìn)行合理假設(shè)，得出不同情形下的最優(yōu)配送路線，該路線同樣也是本論文中所提算法的計(jì)算結(jié)果。該實(shí)際案例為本文所提算法的有效性提供了一個(gè)很好的實(shí)際驗(yàn)證背景，為企業(yè)配送作出滿意決策。 結(jié)論部分對(duì)論文內(nèi)容進(jìn)行了全面