帶時間窗車輛路徑問題及其算法研究.pdf

1、帶時間窗的車輛路徑問題(VehicleRoutingProblemwithTimeWindows，VRPTW)是對物流配送管理的核心問題——配送車輛調(diào)度的問題抽象，其是在基本VRP基礎(chǔ)上添加了時間窗約束衍生而來的，可以將VRPTW描述為:使車輛從站點(diǎn)出發(fā)服務(wù)用戶，完成用戶需求后仍返回站點(diǎn)，規(guī)定每個用戶只能被一輛車服務(wù)且僅服務(wù)一次，且對用戶的服務(wù)必須在用戶事先指定的時間窗內(nèi)進(jìn)行，問題的優(yōu)化目標(biāo)是如何選擇適當(dāng)?shù)穆窂?，使得在滿足以上約束條件的

2、情況下，完成全部需求花費(fèi)的總成本最小或總利潤最大。實(shí)踐中許多運(yùn)輸管理問題均可抽象為VRPTW，如銀行運(yùn)鈔車調(diào)度、郵政配送問題、工廠廢棄物回收問題、校車問題、JIT生產(chǎn)調(diào)度等。本文圍繞三類帶時間窗車輛路徑問題（基本的帶時間窗車輛路徑問題、帶時間窗的取送貨問題、帶工作時間與時間窗的開放式車輛路徑問題）展開研究，主要研究內(nèi)容如下:
　　 對帶時間窗車輛路徑問題的插入檢測法進(jìn)行了深入研究。主要作了以下三個方面的工作:一是對求解VRP的插

3、入檢測法進(jìn)行了定義與分類，并對求解VRPTW插入檢測法的已有研究成果進(jìn)行梳理總結(jié);二是對前推值插入檢測法原理進(jìn)行了數(shù)學(xué)證明，分析該插入檢測法的計(jì)算復(fù)雜度表明:前推值插入檢測法與傳統(tǒng)的基于時間窗約束條件的插入檢測法計(jì)算復(fù)雜度相當(dāng)。三是提出了時差的概念及時差插入檢測法，證明了該檢測法的充要條件，分析其計(jì)算復(fù)雜度表明:其計(jì)算復(fù)雜度優(yōu)于前推值插入檢測法及傳統(tǒng)的基于時間窗約束條件的插入檢測法。仿真測試結(jié)果顯示:時差插入檢測法與前推值插入檢測法一樣

4、有效，而前者的檢測速度優(yōu)于后者。
　　 對帶時間窗車輛路徑問題的插入啟發(fā)式算法進(jìn)行了深入研究。在介紹三種經(jīng)典插入啟發(fā)式算法的啟發(fā)原理基礎(chǔ)上，提出了時差插入啟發(fā)式算法，介紹了時差插入啟發(fā)式算法的啟發(fā)規(guī)則，算法構(gòu)架，仿真測試了該算法的最佳參數(shù)組合，比較該算法與三種經(jīng)典插入啟發(fā)式算法的求解質(zhì)量表明:該算法的求解質(zhì)量優(yōu)于Solomon的插入啟發(fā)式算法。
　　 對帶時間窗取送貨問題的深入研究。提出了求解帶時間窗取送貨問題的非代際遺

5、傳算法。相比于基本遺傳算法，該算法有以下特點(diǎn):一是采用基于個體的搜索機(jī)制，該機(jī)制能更好的保留優(yōu)異個體與種群的多樣性。二是改進(jìn)編碼方法，設(shè)計(jì)了包含最早完成時間、最遲開始時間的整數(shù)編碼方法，該方法不僅能表示客戶編號，而且能表示車輛在客戶處的到達(dá)順序，還能在變異、交叉過程及初始解生成過程中運(yùn)用時差插入檢測法。三是設(shè)計(jì)了適用于帶時窗取送貨問題的非對稱匹配交叉、對稱匹配交叉、線路交叉以及R1變異與R2變異等算子。仿真測試表明該算法比已有報(bào)道的求解