教師資料查詢 | 類別: 會議論文 | 教師: 張茂椿 Chang Mauh-tsun (瀏覽個人網頁)

標題:以演化基礎的塔布搜尋方法解旅行銷售員問題
學年96
學期2
發表日期2008/05/16
作品名稱以演化基礎的塔布搜尋方法解旅行銷售員問題
作品名稱(其他語言)
著者李鴻璋;張震宇
作品所屬單位淡江大學資訊管理學系
出版者資訊管理學會
會議名稱ICIM 2008第十九屆國際資訊管理學術研討會
會議地點臺北市, 臺灣
摘要組合最佳化問題中,旅行銷售員問題(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%。因此可以看出,本研究所提出的演算法能比單純使用基因演算法有更好的路徑搜尋結果。
關鍵字旅行銷售員問題;基因演算法;塔布搜尋法
語言中文
收錄於
會議性質國際
校內研討會地點
研討會時間20080516~20080517
通訊作者
國別中華民國
公開徵稿Y
出版型式紙本
出處ICIM 2008第十九屆國際資訊管理學術研討會論文集9頁
相關連結
Google+ 推薦功能,讓全世界都能看到您的推薦!