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

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

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

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

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