以演化基礎的塔布搜尋方法解旅行銷售員問題

機構典藏 > College of Business and Management > Graduate Institute & Department of Information Management > Proceeding > Item 987654321/63286

Please use this identifier to cite or link to this item: https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/63286

Title:	以演化基礎的塔布搜尋方法解旅行銷售員問題
Authors:	李鴻璋;張震宇
Contributors:	淡江大學資訊管理學系
Keywords:	旅行銷售員問題;基因演算法;塔布搜尋法
Date:	2008-05
Issue Date:	2011-10-19 20:40:44 (UTC+8)
Publisher:	資訊管理學會
Abstract:	組合最佳化問題中，旅行銷售員問題(Traveling Salesman Problem, TSP)是最基本且典型的例子，許多問題都可以轉變成TSP的形式求解，又由於TSP是屬於NP-Complete問題，在資料量龐大的情況之下無法找出最佳解，所以又有將大型TSP變換成數個小型TSP的分群旅行銷售員問題(Clustered Traveling Salesman Problem, CTSP)的研究提出。所以，如何設計一個良好的演算法，使得我們能夠能找出近似最佳解變得相當重要。因此，本研究提出以基因演算法及塔布演算法為核心的演算架構，並將TSP問題轉為CTSP問題型式，以期能找出近似最佳解。本研究所提出的演算架構分為二個部分，第一部分為分群及群路建立，第二部分為全域最佳路徑搜尋。分群為階層式，由上而下分群，首先將頂點做初步分群，完成後再將每一群分為若干子群並建立群路路徑。第二部分的全域最佳路徑，搜尋方法採用塔布搜尋法，首先使用雙點式塔布搜尋做大範圍的路徑搜尋，接著使用單點式塔布搜尋做細部改善，最後使用MNIO演算法將解收斂。在TSPLIB國際範例lin105中，基因演算法所得的路徑長度比最佳解長25.18%，本研究只多出0.5%；在fl417 中，基因演算法的路徑長度比最佳解多出73.96%，本研究只多出2.5%；而在fl1400 中，基因演算法的路徑長度比最佳解多出68.33%，本研究只多出6.30%。因此可以看出，本研究所提出的演算法能比單純使用基因演算法有更好的路徑搜尋結果。
Relation:	ICIM 2008第十九屆國際資訊管理學術研討會論文集，9頁
Appears in Collections:	[Graduate Institute & Department of Information Management] Proceeding

Files in This Item:

File	Description	Size	Format
以演化基礎的塔布搜尋方法解旅行銷售員問題_中文摘要.docx	摘要	14Kb	Microsoft Word	499	View/Open

Loading...