English
| 正體中文 |
简体中文
|
全文筆數/總筆數 : 62830/95882 (66%)
造訪人次 : 4052338 線上人數 : 978
RC Version 7.0 © Powered By DSPACE, MIT. Enhanced by
NTU Library & TKU Library IR team.
搜尋範圍
全部機構典藏
商管學院
資訊管理學系暨研究所
--會議論文
查詢小技巧:
您可在西文檢索詞彙前後加上"雙引號",以獲取較精準的檢索結果
若欲以作者姓名搜尋,建議至進階搜尋限定作者欄位,可獲得較完整資料
進階搜尋
主頁
‧
登入
‧
上傳
‧
說明
‧
關於機構典藏
‧
管理
淡江大學機構典藏
>
商管學院
>
資訊管理學系暨研究所
>
會議論文
>
Item 987654321/63286
資料載入中.....
書目資料匯出
Endnote RIS 格式資料匯出
Bibtex 格式資料匯出
引文資訊
請使用永久網址來引用或連結此文件:
https://tkuir.lib.tku.edu.tw/dspace/handle/987654321/63286
題名:
以演化基礎的塔布搜尋方法解旅行銷售員問題
作者:
李鴻璋
;
張震宇
貢獻者:
淡江大學資訊管理學系
關鍵詞:
旅行銷售員問題
;
基因演算法
;
塔布搜尋法
日期:
2008-05
上傳時間:
2011-10-19 20:40:44 (UTC+8)
出版者:
資訊管理學會
摘要:
組合最佳化問題中,旅行銷售員問題(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%。因此可以看出,本研究所提出的演算法能比單純使用基因演算法有更好的路徑搜尋結果。
關聯:
ICIM 2008第十九屆國際資訊管理學術研討會論文集,9頁
顯示於類別:
[資訊管理學系暨研究所] 會議論文
文件中的檔案:
檔案
描述
大小
格式
瀏覽次數
以演化基礎的塔布搜尋方法解旅行銷售員問題_中文摘要.docx
摘要
14Kb
Microsoft Word
459
檢視/開啟
在機構典藏中所有的資料項目都受到原著作權保護.
TAIR相關文章
DSpace Software
Copyright © 2002-2004
MIT
&
Hewlett-Packard
/
Enhanced by
NTU Library & TKU Library IR teams.
Copyright ©
-
回饋