旅行商問題(Traveling Salesman Problem,TSP)是一個經(jīng)典的NP-hard組合優(yōu)化問題,多旅行商問題(Multiple Traveling Salesman Problem,MTSP)作為其擴展模型,具有更強的實際意義。而在理想情況下的旅行商問題及多旅行商問題幾乎是不存在的,本文介紹了兩種更符合實際意義的限容量多旅行商問題(Multiple Traveling Salesman Problem With Limited Capacity,LCMTSP)和不確定性多旅行商問題(Uncertain Multiple Traveling Salesman Problem,UMTSP)模型,并設(shè)計了遺傳算法(Genetic Algorithm,GA)對這兩種模型進行求解。本文首先對LCMTSP問題模型進行了研究,將容量限制條件加入到多旅行商問題模型中,以控制每個旅行商訪問城市個數(shù)范圍。鑒于問題的復(fù)雜性,本文在傳統(tǒng)GA的種群初始化過程中,采用完全隨機法和適用于多旅行商問題模型的次優(yōu)選擇法,并在交叉算子中加入最小路徑交叉等規(guī)則,且引入DI算子和3-opt算子。實驗結(jié)果證明了所設(shè)計IGA求解LCMTSP問題時的可行性和有效性以及較高的計算效率。考慮到理想化的多旅行商問題在現(xiàn)實環(huán)境中的不可靠性,本文將現(xiàn)實情況下的不確定性因素歸納為一種路況系數(shù),從而構(gòu)建了不確定性多旅行商問題(UMTSP)模型。針對該問題,設(shè)計了遺傳算法對其進行了求解,并比較基本MTSP問題與UMTSP問題的實驗結(jié)果。實驗結(jié)果證明了UMTSP問題模型的實際意義以及所提遺傳算法的可行性與實用性。
【學(xué)位單位】：安慶師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位年份】：2018
【中圖分類】：C81
【部分圖文】：

TSP問題的研究方法

種群初始化

種群初始化
【參考文獻(xiàn)】

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

1 麻存瑞;馬昌喜;;不確定旅行商問題的魯棒模型與算法[J];計算機應(yīng)用;2014年07期

2 柯良軍;尚可;馮祖仁;;不確定旅行商問題的魯棒模型及其算法研究[J];計算機科學(xué);2012年S1期

3 崔瑾娟;;基于遺傳算法的旅行商問題的研究[J];安陽師范學(xué)院學(xué)報;2012年02期

4 王越;許全文;黃麗豐;;基于改進遺傳算法的連續(xù)函數(shù)優(yōu)化[J];重慶理工大學(xué)學(xué)報(自然科學(xué)版);2011年02期

5 張建強;方衛(wèi)國;;有時間窗約束車輛路徑問題的改進遺傳算法[J];計算機工程與應(yīng)用;2010年32期

6 郭強;遲洪欽;;基于GA的MTSP問題的研究[J];計算機與數(shù)字工程;2010年10期

7 黃寶珠;肖菁;;改進的MIMIC算法求解旅行商問題[J];計算機工程與設(shè)計;2010年16期

8 高岳林;劉軍民;;差分進化算法的參數(shù)研究[J];黑龍江大學(xué)自然科學(xué)學(xué)報;2009年01期

9 徐志偉;張耀坤;張勇;黃雷;;求解旅行商問題的一種改進遺傳算法[J];四川兵工學(xué)報;2009年01期

10 楊尚達(dá);李世平;;遺傳算法研究[J];兵工自動化;2008年09期

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

1 王雪紅;基于遺傳算法的車輛路徑優(yōu)化問題的應(yīng)用研究[D];天津科技大學(xué);2016年

2 楊俊雷;基于改進遺傳算法的結(jié)構(gòu)可靠度計算[D];河北工程大學(xué);2012年

3 張虎;遺傳算法的改進研究及其在工程優(yōu)化中的應(yīng)用[D];三峽大學(xué);2012年

4 王娜;求解TSP的改進遺傳算法[D];西安電子科技大學(xué);2010年

5 姜薇;遺傳算法中交叉算法的改進[D];吉林大學(xué);2009年

6 王進;蟻群算法在物流系統(tǒng)中的應(yīng)用研究[D];南昌大學(xué);2008年

7 王爽;改進的自適應(yīng)遺傳算法在知識庫中的應(yīng)用研究[D];大連交通大學(xué);2008年

8 劉道軍;向量編碼遺傳算法求解TSP問題的研究[D];中南民族大學(xué);2008年

9 程娜;基于混合進化算法的車輛路徑優(yōu)化問題的研究[D];延邊大學(xué);2008年

10 支姝;基于遺傳算法的配送路線優(yōu)化研究[D];長安大學(xué);2008年

本文編號：2841304