基于改進的遺傳算法的車輛路徑問題研究.pdf

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

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

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

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