本文選題：組合優(yōu)化 + 旅行商問題��； 參考：《中國科學技術大學》2017年碩士論文

【摘要】：作為組合優(yōu)化中經(jīng)典的NP-hard問題之一,旅行商問題(TSP)在實際生產(chǎn)中有廣泛的應用,如物流路線規(guī)劃、電路板印刷等。對該問題的研究不管是在實際應用中還是在科學研究中都有十分重大的意義。1992年Ejection Chain算法被提出,隨后被證明在求解旅行商問題中和有名的Lin-Kernighan(LK)啟發(fā)式算法一樣高效。在本文中,我們著重研究了 Ejection Chain算法及其混合算法。我們對Ejection Chain算法進行了改進,并進行了大規(guī)模的算法性能實驗測試。與其他研究僅僅關注算法實驗最終結果不同,本文中使用多種時間維度來分析算法在整個運行過程中的狀態(tài)。本文中的工作為以下四個方面:第一,我們研究了高效的Ejection Chain算法,并且在原始的Ejection Chain算法上進行了多項改進,比如針對Ejection Chain算法的特點設計了高效的數(shù)據(jù)存儲結構,對根節(jié)點候選集合的大小進行探索實驗,同時對Ejection Chain算法的終止條件策略進行了調整,得到改進的Ejection Chain算法在測試的110個實例求解全局最優(yōu)解中,比原始Ejection Chain算法多解決了 28%的測試實例。第二,我們對Ejection Chain算法進行了大規(guī)模的實驗測試,通過與LK局部搜索算法相比較,深入分析了 Ejection Chian算法性能。第三,由于局部搜索算法以及組合局部搜索算法(LS-LS混合算法)容易陷入局部最優(yōu),所以我們將交叉算子加入到組合局部搜索算法中得到混合交叉算子的組合搜索算法(LS-LS-X混合算法),其算法在110個測試實例求解最優(yōu)解中比單一的局部搜索算法和組合搜索算法分別多解決41%和28%的實例。最后,我們將局部搜索算法和混合交叉算子的組合搜索算法與進化算法和基于種群的蟻群優(yōu)化算法進行混合,得到的混合算法在時間限制為1小時,求解城市規(guī)模為85900的實例中,所得到的解與全局最優(yōu)解僅僅相差4.85%。
[Abstract]:As one of the classical NP - hard problems in combinatorial optimization , TSP is widely used in practical production , such as logistics route planning and circuit board printing .
【學位授予單位】：中國科學技術大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：TP18

【相似文獻】

相關期刊論文 前10條

1 梁小毅;唐屹;;k-匿名映射的一種局部搜索算法[J];計算機應用與軟件;2009年12期

2 張雁;黃永宣;魏明海;;一種求解最大團問題的自適應過濾局部搜索算法[J];信息與控制;2011年04期

3 肖進杰,朱大銘,馬紹漢,潘銳;多服務中心設置問題局部搜索算法的分析與實驗[J];計算機工程;2005年12期

4 謝嘯虎;黃樟燦;焉炳艷;;多目標遺傳局部搜索算法的研究進展[J];武漢理工大學學報(信息與管理工程版);2006年12期

5 潘銳;朱大銘;董林光;董穎;;求解k中間點問題的新局部搜索算法[J];計算機工程與應用;2008年04期

6 詹青青;;啟發(fā)式局部搜索算法在電路劃分中的應用[J];福建電腦;2010年04期

7 韋煒;藤村茂;席裕庚;;求解旅行錦標賽問題的改進混合局部搜索算法[J];計算機仿真;2012年10期

8 吳貴芳,徐科,徐金梧;邊界局部搜索算法與應用[J];計算機應用;2005年02期

9 肖進杰;謝青松;牛翠霞;;設備定位問題局部搜索算法的實驗[J];計算機工程與應用;2010年02期

10 陳萍;黃厚寬;董興業(yè);;基于多鄰域的車輛路徑優(yōu)化迭代局部搜索算法[J];北京交通大學學報;2009年02期

相關會議論文 前1條

1 劉心報;葉強;;基于模塊設計的蟻群算法研究綜述[A];'2008系統(tǒng)仿真技術及其應用學術會議論文集[C];2008年

相關博士學位論文 前1條

1 李睿智;基于局部搜索策略的若干組合優(yōu)化問題求解算法研究[D];東北師范大學;2017年

相關碩士學位論文 前10條

1 吳越鐘;改進的Lin-Kernighan局部搜索算法和雜交算法在旅行商問題中的應用[D];中國科學技術大學;2016年

2 張崢華;SAT求解局部搜索行為分析與概率控制策略[D];華中科技大學;2014年

3 徐斌;基于索引調制的寬帶MIMO-OFDM無線傳輸技術研究[D];電子科技大學;2016年

4 李雙星;改進迭代局部搜索算法求解需求拆分的校車路徑問題[D];河南大學;2016年

5 劉偉臣;改進的Ejection Chain局部搜索算法與混合算法求解旅行商問題[D];中國科學技術大學;2017年

6 咸愛勇;合取范式最大不全滿足與最大可滿足問題的局部搜索算法研究[D];山東大學;2012年

7 高超;隨機局部搜索算法及其應用研究[D];中國科學技術大學;2015年

8 殷茜;基于局部搜索的最小可滿足問題求解算法研究[D];東北師范大學;2015年

9 趙軒;求解RCPSP問題的迭代局部搜索算法研究[D];北京交通大學;2016年

10 溫真真;需求可拆分車輛路徑問題的迭代局部搜索算法研究[D];北京交通大學;2015年

，

本文編號：2086752