基于改進(jìn)的遺傳算法的車輛路徑問題研究.pdf

1、車輛路徑問題是一個經(jīng)典的組合優(yōu)化問題，最早由著名學(xué)者Dantzig和Ramser于1959年提出。由于該問題將理論研究和實際應(yīng)用緊密地聯(lián)系在一起，因此自提出以來就引起了包括計算機(jī)科學(xué)、運(yùn)籌學(xué)、組合數(shù)學(xué)、管理學(xué)等多個學(xué)科專家學(xué)者的高度重視。到目前為止，用于求解車輛路徑問題的方法已可劃分為三類，即精確優(yōu)化方法、傳統(tǒng)啟發(fā)式方法、現(xiàn)代啟發(fā)式算法即智能優(yōu)化算法。國內(nèi)外研究者目前基本都集中在對智能優(yōu)化算法的研究上。
　　 遺傳算法是一種模擬

2、自然界生物進(jìn)化過程的智能搜索算法，作為一種有效的全局優(yōu)化工具，它具有簡單通用、穩(wěn)健性強(qiáng)和適合于并行分布處理等特點，以及自組織性、自適應(yīng)性和自學(xué)習(xí)性等智能特性，可用于解決組合優(yōu)化、機(jī)器學(xué)習(xí)、自適應(yīng)控制等智能問題。本文采用遺傳算法來求解車輛路徑問題，主要的研究工作和創(chuàng)新如下:
　　 1）通過對大量相關(guān)文獻(xiàn)進(jìn)行分析、總結(jié)和提煉，對車輛路徑問題的起源和發(fā)展、研究及應(yīng)用的價值以及研究現(xiàn)狀進(jìn)行了概述；闡明了論文研究的背景及意義、選題的理由及

3、本文的主要工作；并指出了目前車輛路徑問題研究中存在的不足，為本文的研究做了鋪墊。
　　 2）討論了遺傳算法的基本優(yōu)化原理、算法結(jié)構(gòu)和設(shè)計過程；分析了遺傳算法的特點以及它的不足之處和優(yōu)化策略；針對遺傳算法在進(jìn)化過程中，由于種群多樣性降低而導(dǎo)致過早收斂的缺點，設(shè)計了一個雙重改進(jìn)的遺傳算法DIGA：借鑒免疫算法通過抗體濃度抑制以保持種群多樣性的優(yōu)勢，在遺傳算法中引入個體濃度控制操作；借鑒模擬退火算法的個體選擇方法，改進(jìn)了遺傳算法的選擇

4、策略，使算法能夠以一定的概率跳出局部最優(yōu)的狀態(tài)；在遺傳算法中引入“精英保留”策略，保證算法的全局收斂性。
　　 3）分析了車輛路徑問題所包含的各類約束條件；總結(jié)了求解車輛路徑問題的幾類方法及其特點；重點研究了車輛數(shù)和容量均受限的多目標(biāo)車輛路徑問題，為其建立了相應(yīng)的數(shù)學(xué)模型，并將改進(jìn)的遺傳算法DIGA用于求解該問題，給出了算法的結(jié)構(gòu)和詳細(xì)設(shè)計過程。
　　 4）從實驗的角度分析了DIGA算法求解車輛路徑問題的性能：①選用目前