用多種群自適應(yīng)混合遺傳算法求解車輛路徑問題.pdf

1、人工智能(Artificial Intelligence)一直以來是計(jì)算機(jī)科學(xué)中的重要的研究方向,而智能規(guī)劃(Intelligent Planning)領(lǐng)域又是人工智能研究中的重要分支.智能規(guī)劃研究的是如何利用計(jì)算機(jī)高速度高性能的計(jì)算來優(yōu)化規(guī)劃問題中經(jīng)常出現(xiàn)的冗余現(xiàn)象,由此節(jié)約大量的人力和物力.在智能規(guī)劃領(lǐng)域中存在的一個(gè)重要問題是車輛路徑問題(Vehicle Routing Problems,VRP),即研究如何利用有限的運(yùn)輸資源來完成

2、一定量的運(yùn)輸任務(wù),并且使得運(yùn)輸成本最低.如果在此基礎(chǔ)上加上時(shí)間窗的限制,問題就演變成了有時(shí)間窗的車輛路徑問題(Vehicle RoutingProblems with Time Windows,VRPTW).有時(shí)間窗的車輛路徑問題由于其巨大的經(jīng)濟(jì)效益,所以從它被提出以來一直就是計(jì)算機(jī)學(xué)者和管理者研究的重要課題,并且在過去的40多年間得到了突飛猛進(jìn)的發(fā)展.各種方法,包括:線性規(guī)劃方法、非線性規(guī)劃方法、動態(tài)規(guī)劃方法、組合優(yōu)化方法、啟發(fā)式方法

3、、分枝界定法、爬山法、貪婪法等,都被應(yīng)用于問題的求解,并且取得了不錯(cuò)的求解效果.然而,以往的這些方法都不可避免地存在各自的缺點(diǎn),例如求解時(shí)間過長,容易陷入局部最優(yōu),系統(tǒng)資源消耗過大等.該文在以往方法研究的基礎(chǔ)上,對傳統(tǒng)的遺傳算法進(jìn)行改進(jìn),提出了多種群自適應(yīng)混合遺傳算法(Multiplepopulation AdaptiveHybrid Genetic Algorithms),并設(shè)計(jì)開發(fā)出了基于改進(jìn)遺傳算法的有時(shí)間窗的車輛路徑問題求解系統(tǒng)