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

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

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

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

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

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

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