用遺傳算法解決車輛優(yōu)化調(diào)度問題
2.5萬字 52頁
論文+源代碼+任務(wù)書



摘 要
近年來，物流作為“第三方利潤的源泉”受到國內(nèi)各行業(yè)的極大重視并得到了較大的發(fā)展。在高度發(fā)展的商業(yè)社會中，傳統(tǒng)的VSP算法已無法滿足顧客需求對物流配送提出的要求，于是時間窗的概念應(yīng)運(yùn)而生。帶有時間窗的車輛優(yōu)化調(diào)度問題是比VSP復(fù)雜程度更高的NP難題。
本文在研究物流配送車輛優(yōu)化調(diào)度問題的基礎(chǔ)上，對有時間窗的車輛優(yōu)化調(diào)度問題進(jìn)行了分析。并對所采用的遺傳算法的基本理論做了論述。
對于有時間窗的非滿載VSP問題，將貨運(yùn)量約束和軟時間窗約束轉(zhuǎn)化為目標(biāo)約束，建立了非滿載VSP模型，設(shè)計了基于自然數(shù)編碼，使用最大保留交叉、改進(jìn)的反轉(zhuǎn)變異等技術(shù)的遺傳算法。經(jīng)實驗分析，取得了較好的結(jié)果。由于此問題為小組成員共同研究，本文重點論述了本人完成的關(guān)于適應(yīng)度函數(shù)和變異操作的部分。

關(guān)鍵詞：物流配送 車輛優(yōu)化調(diào)度 遺傳算法 時間窗



Abstract
Recent years, logistics, taken as "third profit resource”, has been developing rapidly. In the developed commercial society, traditional VSP algorithm have been unable to meet the requirement that Quick Response to customer demand had brought forth, then the conception of Time Window has come into being. The vehicle-scheduling problem with time window is also a NP-hard problem being more complicated than VSP.
This text has been researched to the vehicle-scheduling problem with time window on the basis of researched to logistic vehicle scheduling problem. And it has explained the basic theory of genetic algorithm.
On the VSP with time window, while the restraints of capacity and time windows are changed into ......



目 錄
摘 要 I
Abstract II
目 錄 III
引 言 1
第1章 概 述 2
1.1 研究背景 2
1.2 物流配送車輛優(yōu)化調(diào)度的研究動態(tài)和水平 4
1.2.1 問題的提出 4
1.2.2 分類 5
1.2.3 基本問題與基本方法 6
1.2.4 算法 6
1.2.5 貨運(yùn)車輛優(yōu)化調(diào)度問題的分類 8
1.3 研究的意義 9
1.4 研究的范圍 10
第2章 有時間窗的車輛優(yōu)化調(diào)度問題(VSPTW) 11
2.1 時間窗的定義 11
2.2 VSPTW問題的結(jié)構(gòu) 13
第3章 遺傳算法基本理論 14
3.1 遺傳算法的基本原理 14
3.1.1 遺傳算法的特點 14
3.1.2 遺傳算法的基本步驟和處理流程 15
3.1.3 遺傳算法的應(yīng)用 16
3.2 編碼 17
3.2.1 二進(jìn)制編碼 18
3.2.2 Gray編碼 18
3.2.3 實數(shù)向量編碼 18
3.2.4 排列編碼 19
3.3 適應(yīng)度函數(shù) 19
3.3.1 目標(biāo)函數(shù)映射成適應(yīng)度函數(shù) 19
3.3.2 適應(yīng)度定標(biāo) 20
3.4 遺傳算法的基因操作 21
3.4.1 選擇算子 21
3.4.2 交叉算子 22
3.4.3 變異算子 25
3.5 遺傳算法控制參數(shù)設(shè)定 28
第4章 遺傳算法求解有時間窗非滿載VSP 30
4.1 問題描述 30
4.2 數(shù)學(xué)模型 31
4.2.1 一般VSP模型 31
4.2.2 有時間窗VSP模型 32
4.3 算法設(shè)計 33
4.3.1 算法流程圖 33
4.3.2 染色體結(jié)構(gòu) 33
4.3.3 約束處理 35
4.3.4 適應(yīng)度函數(shù) 36
4.3.5 初始種群 36
4.3.6 遺傳算子 36
4.3.7 控制參數(shù)和終止條件 37
4.4 算法實現(xiàn) 39
4.5 實驗及結(jié)果分析 39
4.5.1 控制參數(shù)選定 39
4.5.2 實例實驗 43
4.5.3 實例數(shù)據(jù) 44
4.5.4 實例數(shù)據(jù)分析 44
結(jié) 論 45
參考文獻(xiàn) 47
謝 辭 48



參考文獻(xiàn)
[1] 姜大立等，“車輛路徑問題的遺傳算法研究”，北京，《系統(tǒng)工程理論與實踐》，1999年第18卷， 第40-45頁。
[2] 李大衛(wèi)等，“一個求解帶有時間窗口約束的車輛路徑問題的啟發(fā)式算法”，長沙，《系統(tǒng)工程》，1998年第16卷第4期，第20-24頁。