【摘要】：蟻群算法是一種模擬螞蟻覓食行為的群體智能算法。蟻群算法具有自組織性和正反饋性,使其具有高度的適應(yīng)性,因此被廣泛的用于路徑規(guī)劃問題、圖著色問題、集成電路設(shè)計(jì)、數(shù)據(jù)聚類分析等領(lǐng)域。但蟻群算法也具有收斂慢、易于陷入局部最優(yōu)的缺點(diǎn)。因此,研究蟻群算法的改進(jìn)具有重要的理論意義。隨著經(jīng)濟(jì)全球化和信息化的發(fā)展,物流業(yè)迅速成為具有巨大潛力和發(fā)展空間的新興服務(wù)產(chǎn)業(yè),物流業(yè)也是我國(guó)十大產(chǎn)業(yè)振興計(jì)劃中的第十個(gè)產(chǎn)業(yè)。車輛路徑問題是物流配送問題的理論模型,因此,研究車輛路徑問題具有重要的實(shí)用價(jià)值。本文主要工作如下:1.討論了蟻群算法的基本原理和發(fā)展過程,詳細(xì)描述了螞蟻系統(tǒng)、精英螞蟻、螞蟻排序和最大最小蟻群算法。討論了蟻群算法的參數(shù)設(shè)置對(duì)算法性能的影響,以及蟻群算法的特點(diǎn)。2.針對(duì)帶時(shí)間窗的車輛路徑問題模型,本文提出了一種蟻群優(yōu)化算法。該方法改進(jìn)了狀態(tài)轉(zhuǎn)移概率,增加了時(shí)間窗的影響因子,并將信息素?fù)]發(fā)率做遞增調(diào)整。同時(shí),提出了一種快速構(gòu)造初始解的方法。通過與已知最優(yōu)解的對(duì)比證明了該算法的有效性。3.討論了蟻群算法在帶時(shí)間窗同時(shí)送取貨車輛路徑問題中的應(yīng)用,提出了一種混合蟻群優(yōu)化算法。該算法增加了候選集策略,提前排除不滿足條件的客戶。并在蟻群優(yōu)化算法的基礎(chǔ)上繼續(xù)改進(jìn)了狀態(tài)轉(zhuǎn)移概率,增加了需求量的影響因子。該算法將蟻群算法與蛙跳算法相融合,先將蟻群排序后分組,再進(jìn)化每個(gè)組內(nèi)用三角概率分布選擇出來的螞蟻,進(jìn)化步驟采用局部搜索算法,最后重新排序和分組,如此循環(huán)一定次數(shù)。實(shí)驗(yàn)表明將這兩種群體智能算法相融合,減少了計(jì)算量,同時(shí)提高了解的質(zhì)量。4.討論了動(dòng)態(tài)車輛路徑問題,提出了并行蟻群優(yōu)化算法。該算法將解決動(dòng)態(tài)問題的過程分成了兩個(gè)階段,第一階段通過混合蟻群優(yōu)化算法來規(guī)劃初始路徑。第二階段把工作日分成等長(zhǎng)的時(shí)間片段,每個(gè)時(shí)間片段檢查是否有新客戶,有則重新規(guī)劃路徑。每次完成規(guī)劃,信息素得到保留,繼續(xù)參與下一次的規(guī)劃,所以時(shí)間片段之間形成了正反饋,最終方案不斷得到改善。同時(shí)利用了蟻群算法的并行性,引入了并行計(jì)算,每只螞蟻并行的構(gòu)建路徑。實(shí)驗(yàn)表明,該并行蟻群優(yōu)化算法不但提高了解決方案的質(zhì)量,同時(shí)也減少了運(yùn)算時(shí)間。
【圖文】：

發(fā)式全局優(yōu)化算法。2.1 蟻群算法的基本原理根據(jù)文獻(xiàn)[35]所描述，蟻群算法的理論來源是：在自然界中，，在螞蟻覓食的過程中，螞蟻會(huì)在所經(jīng)過的路徑上留下一種分泌物，螞蟻相互之間能夠感知到這種分泌物，這就形成了螞蟻之間相互交流的信息。因此學(xué)者們將這種分泌物稱為“信息素”。更短的路徑上的信息素積累的更快，螞蟻更傾向于選擇信息素更濃的路徑，這就形成了一個(gè)正反饋的現(xiàn)象。但是，信息素會(huì)隨著時(shí)間揮發(fā)。一段時(shí)間過后，最短的路徑積累的信息素遠(yuǎn)遠(yuǎn)多過揮發(fā)的信息素，而在更長(zhǎng)的路徑上，大部分的信息素都被揮發(fā)了，因?yàn)閮煞N路徑信息素累積量顯著的差距，最終所有螞蟻都會(huì)選擇最短的路徑。螞蟻的覓食過程如圖 2.1 所示：A巢 食A巢 食

圖 3.1 使用初始解算法對(duì)比圖，加強(qiáng)了初始解路徑上的信息素之后，算法一開始就，提高了初始解集的質(zhì)量，而且算法的收斂速度也大時(shí)就得到了最優(yōu)解。而不加強(qiáng)初始解路徑上的信息素很差，且陷入了局部最優(yōu)解。概率算法很少考慮時(shí)間窗，但是對(duì)于帶時(shí)間窗的問題，時(shí)此，本算法考慮進(jìn)了時(shí)間窗因子，提出了一種新的狀窗的緊迫性因子和時(shí)間窗最早開始時(shí)間因子。時(shí)間窗緊的客戶。時(shí)間窗最早開始時(shí)間確保了開始時(shí)間晚的因素都可以幫助改進(jìn)蟻群算法找到最有效的路徑，并
【學(xué)位授予單位】：重慶郵電大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2018
【分類號(hào)】：U491;TP18

【參考文獻(xiàn)】

相關(guān)期刊論文 前6條

1 譚巍;文慶;;基于蟻群系統(tǒng)和2-opt方法求解同時(shí)送取貨車輛路徑VRPSPD問題[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2015年24期

2 黃震;羅中良;黃時(shí)慰;;一種帶時(shí)間窗車輛路徑問題的混合蟻群算法[J];中山大學(xué)學(xué)報(bào)(自然科學(xué)版);2015年01期

3 盧冰;王夢(mèng)蘭;;一種改進(jìn)螞蟻算法在TSP問題中的應(yīng)用[J];科技創(chuàng)業(yè)月刊;2010年06期

4 王訓(xùn)斌;陸慧娟;陳五濤;;帶時(shí)間窗動(dòng)態(tài)車輛路徑問題的改進(jìn)蟻群算法[J];工業(yè)控制計(jì)算機(jī);2009年01期

5 吳兆福;董文永;;求解動(dòng)態(tài)車輛路徑問題的演化蟻群算法[J];武漢大學(xué)學(xué)報(bào)(理學(xué)版);2007年05期

6 郭耀煌;;復(fù)雜道路網(wǎng)上貨運(yùn)卡車的優(yōu)化調(diào)度[J];西南交通大學(xué)學(xué)報(bào);1988年04期

相關(guān)博士學(xué)位論文 前1條

1 陸琳;不確定信息車輛路徑問題及其算法研究[D];南京航空航天大學(xué);2007年

相關(guān)碩士學(xué)位論文 前1條

1 胡夏云;基于蟻群算法的動(dòng)態(tài)車輛調(diào)度問題的研究[D];廣東工業(yè)大學(xué);2013年

本文編號(hào)：2680846