植基於分散搜尋之優化演算法求解旅行銷售員問題之研究

勤益科大機構典藏 > 電資學院 > 電子工程系(所) > 【電子工程系所】博碩士論文 > Item 987654321/5032

請使用永久網址來引用或連結此文件: http://ir.lib.ncut.edu.tw/handle/987654321/5032

題名:	植基於分散搜尋之優化演算法求解旅行銷售員問題之研究
作者:	陳宇靖陳瑞茂
貢獻者:	電子工程系
關鍵詞:	旅行銷售員問題分散搜尋演算法局部搜尋演算法基因演算法
日期:	2012
上傳時間:	2013-08-05 15:02:45 (UTC+8)
出版者:	台中;國立勤益科技大學
摘要:	旅行銷售員問題(Traveling Salesman Problem, TSP)乃序列組合最佳化問題中最典型的一種，亦是管理科學、計算機科學、以及作業研究等領域長期探討之議題。旅行銷售員問題也常被應用於驗證演算法其效率與穩定度，由於其容易使用與實作等特性，在現實世界中其應用也很廣泛。旅行銷售員問題已被證明為NP-Complete問題，依據其求解的精確度與求解的速度所發展之演算法可分類為精確解法(Exact Algorithm)與近似解法(Approximation Algorithm)。精確解法其可求得誤差值極小的解，但隨著問題規模的擴大(節點數增加)，其求解的運算時間也呈指數增加；近似解法其求解精確度小於精確解法，但其時間複雜度(Time Complexity)小於精確解法，故可在較短的時間求得不錯的解。分散搜尋(Scatter Search)演算法是基於路徑重新連接(Path Relinking)之進化演算法(Evolutionary Algorithm)，其主架構由五個元件所組成：(1)多樣化產生(Diversification Generation Method, DGM)，(2)改善方法(Improvement Method, IM)，(3)參考解更新方法(Reference Set Update Method, RSUM)。(4)子集合產生方法(Subset Generation Method, SGM)，(5)新解組合方法(Solution Combination Method, SCM)。由於各個元件可用不同的方法與複雜度實現，因此讓分散搜尋演算法具有高度靈活性與彈性。本研究提出以分散搜尋演算法為主架構，應用局部搜尋法2-Opt於改善方法(IM)之中，藉此改善多樣化生產(DGM)與新解組合方法(SCM)所產生之新解的品質。基因演算法之部分對應交配方法應用於新解組合方法(SCM)之中，借此產生出多於一個以上之新解。最後建構一完整應用於旅行銷售員問題之求解模組。求解模組已於本研究建立完成且經過TSPLIB之Benchmark之驗證。其演算法對於小規模之例題有著顯著的效果。而對於大規模例題，本研究之演算法其效率相對於小規模來的較差。
顯示於類別:	[電子工程系(所)] 【電子工程系所】博碩士論文

文件中的檔案:

沒有與此文件相關的檔案.

檢視Licence

在NCUTIR中所有的資料項目都受到原著作權保護.

資料載入中.....