以演化基礎的塔布搜尋方法解旅行銷售員問題
學年 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%。因此可以看出，本研究所提出的演算法能比單純使用基因演算法有更好的路徑搜尋結果。
關鍵字 旅行銷售員問題;基因演算法;塔布搜尋法
語言 zh_TW
收錄於
會議性質 國際
校內研討會地點
研討會時間 20080516~20080517
通訊作者
國別 TWN
公開徵稿 Y
出版型式 紙本
出處 ICIM 2008第十九屆國際資訊管理學術研討會論文集，9頁
相關連結

機構典藏連結 ( http://tkuir.lib.tku.edu.tw:8080/dspace/handle/987654321/63286 )

機構典藏連結