發(fā)布時間：2018-06-30 20:27

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

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

【相似文獻(xiàn)】

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

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

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

3 肖進(jìn)杰,朱大銘,馬紹漢,潘銳;多服務(wù)中心設(shè)置問題局部搜索算法的分析與實(shí)驗(yàn)[J];計算機(jī)工程;2005年12期

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

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

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

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

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

9 肖進(jìn)杰;謝青松;牛翠霞;;設(shè)備定位問題局部搜索算法的實(shí)驗(yàn)[J];計算機(jī)工程與應(yīng)用;2010年02期

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

相關(guān)會議論文 前1條

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

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

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

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

1 吳越鐘;改進(jìn)的Lin-Kernighan局部搜索算法和雜交算法在旅行商問題中的應(yīng)用[D];中國科學(xué)技術(shù)大學(xué);2016年

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

3 徐斌;基于索引調(diào)制的寬帶MIMO-OFDM無線傳輸技術(shù)研究[D];電子科技大學(xué);2016年

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

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

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

7 高超;隨機(jī)局部搜索算法及其應(yīng)用研究[D];中國科學(xué)技術(shù)大學(xué);2015年

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

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

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

，

本文編號：2086752