a国产,中文字幕久久波多野结衣AV,欧美粗大猛烈老熟妇,女人av天堂

當(dāng)前位置:主頁 > 管理論文 > 物流管理論文 >

改進的Ejection Chain局部搜索算法與混合算法求解旅行商問題

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

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


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

【相似文獻】

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

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

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

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

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

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

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

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

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

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

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

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

1 劉心報;葉強;;基于模塊設(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 吳越鐘;改進的Lin-Kernighan局部搜索算法和雜交算法在旅行商問題中的應(yīng)用[D];中國科學(xué)技術(shù)大學(xué);2016年

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

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

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

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

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

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

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

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

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

,

本文編號:2086752

資料下載
論文發(fā)表

本文鏈接:http://www.wukwdryxk.cn/guanlilunwen/wuliuguanlilunwen/2086752.html


Copyright(c)文論論文網(wǎng)All Rights Reserved | 網(wǎng)站地圖 |

版權(quán)申明:資料由用戶74fab***提供,本站僅收錄摘要或目錄,作者需要刪除請E-mail郵箱bigeng88@qq.com
赤峰市| 欧美色欧美亚洲高清在线观看| 女狠狠噜天天噜日日噜| 91精品国产乱码久久久久| 九九热国产| 男女啪啪激烈高潮喷出gif免费| 中文国产成人精品久久不卡| 欧美成人精品 一区二区三区| 国产精品无码不卡一区二区三区| 久久久亚洲一区二区三区| 成人免费| 天天爱综合| 精品久久人妻av中文字幕| 三级中文字幕永久在线| 久久精品无码鲁网中文电影| 丰满少妇被猛烈进入毛片| 欧美日韩一二三区| 激情久久av一区av二区av三区| 久久久久逼| 91色porny| 亚洲一区二区中文字幕| 亚洲AV无码久久精品色欲| 亚洲AV无码成人精品区狼人影院| 亚洲无卡无码在线观看| 亚洲精品无码专区久久| 久久久久亚洲AV无码专区导航 | 中文无码久久精品| 飘飘欲仙狼太郎| 香蕉久久人人爽人人爽人人片av| 热99re久久精品这里都是精品免费 | 巨乳| 国产精品bbwbbw| 免费人成激情视频在线观看| 国产真实偷乱视频| 男女性杂交内射妇女BBWXZ| 被别人巨茎征服的娇妻3D动漫| 色诱久久久久综合网ywww| 免费无码成人AV片在线在线播放 | 夜色成人| 免费专区一一色哟哟| www精品|