帶時(shí)間窗車(chē)輛路徑問(wèn)題及其算法研究.pdf

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

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

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

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

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