教師資料查詢 | 類別: 期刊論文 | 教師: 鄭啟斌 Chi-Bin Cheng (瀏覽個人網頁)

標題:A modified ant colony system for solving the travelling salesman problem with time windows
學年96
學期1
出版(發表)日期2007/11/01
作品名稱A modified ant colony system for solving the travelling salesman problem with time windows
作品名稱(其他語言)
著者鄭啟斌; Cheng, Chi-bin; Mao, Chun-Pin
單位淡江大學資訊管理學系
出版者Elsevier
著錄名稱、卷期、頁數Mathematical and Computer Modelling 46(9-10), pp.1125-1135
摘要The travelling salesman problem with time windows (TSPTW) involves finding the minimum cost tour in which all cities are visited exactly once within their requested time windows. This problem has a number of important practical applications, including scheduling and routing. The problem is regarded as NP-complete, and hence traditional optimization algorithms are inefficient when applied to solve larger scale TSPTW problems. Consequently, the development of approximation algorithms has received considerable attention in recent years. Ant colony optimization (ACO), inspired by the foraging behaviour of real ants, is one of the most attractive approximation algorithms. Accordingly, this study develops a modified ant algorithm, named ACS-TSPTW, based on the ACO technique to solve the TSPTW. Two local heuristics are embedded in the ACS-TSPTW algorithm to manage the time-window constraints of the problem. The numerical results obtained for a series of benchmark problem instances confirm that the performance of the ACS-TSPTW is comparable to that of ACS-Time, an existing ACO scheme for solving the TSPTW problem.
關鍵字Ant colony optimization (ACO);Travelling salesman problem with time windows (TSPTW);Meta-heuristic;Nature-inspired algorithm
語言英文
ISSN0895-7177
期刊性質國外
收錄於
產學合作
通訊作者
審稿制度
國別英國
公開徵稿
出版型式,紙本
相關連結
Google+ 推薦功能,讓全世界都能看到您的推薦!