| Solving constrained traveling salesman problems by genetic algorithms |
| |
| 作者姓名： | WU Chunguo LIANG Yanchun LEE Heowpueh LU Chun LIN Wuzhong |
| |
| 作者单位： | College of Computer Science and Technology, Jilin University; Key Laboratory for Symbol Computation and Knowledge Engineering, Ministry of Education of China, Changchun 130012, China;Institute of High Performance Computing, Singapore 117528, Singapore,College of Computer Science and Technology, Jilin University; Key Laboratory for Symbol Computation and Knowledge Engineering, Ministry of Education of China, Changchun 130012, China;Institute of High Performance Computing, Singapore 117528, Singapore,Institute of High Performance Computing, Singapore 117528, Singapore,Institute of High Performance Computing, Singapore 117528, Singapore,Institute of High Performance Computing, Singapore 117528, Singapore |
| |
| 基金项目： | Supported by the Science-Technology Development Project of Jilin Province of China (Grant No. 20030520) and the Key Science-Technology Project of the Education Ministry of China (Grant No. 02090) |
| |
| 摘 要： | Three kinds of constrained traveling salesman problems (TSP) arising from application problems, namely the open route TSP, the end-fixed TSP, and the path-constrained TSP, are proposed. The corresponding approaches based on modified genetic algorithms (GA) for solving these constrained TSPs are presented. Numerical experiments demonstrate that the algorithm for the open route TSP shows its advantages when the open route is required, the algorithm for the end-fixed TSP can deal with route optimization with constraint of fixed ends effectively, and the algorithm for the path-constraint could benefit the traffic problems where some cities cannot be visited from each other.
|
| 关 键 词： | constrained traveling salesman problem genetic algorithm Hamiltonian path open route fixed end |
Solving constrained traveling salesman problems by genetic algorithms |
| |
| WU Chunguo,LIANG Yanchun,LEE Heowpueh,LU Chun,LIN Wuzhong.Solving constrained traveling salesman problems by genetic algorithms[J].Progress in Natural Science,2004,14(7):631-637. |
| |
| Authors: | WU Chunguo LIANG Yanchun LEE Heowpueh LU Chun LIN Wuzhong |
| |
| Institution: | 1. College of Computer Science and Technology, Jilin University; Key Laboratory for Symbol Computation and Knowledge Engineering, Ministry of Education of China, Changchun 130012, China;Institute of High Performance Computing, Singapore 117528, Singapore
2. Institute of High Performance Computing, Singapore 117528, Singapore |
| |
| Abstract: | Three kinds of constrained traveling salesman problems (TSP) arising from application problems, namely the open route TSP, the end-fixed TSP, and the path-constrained TSP, are proposed. The corresponding approaches based on modified genetic algorithms (GA) for solving these constrained TSPs are presented. Numerical experiments demonstrate that the algorithm for the open route TSP shows its advantages when the open route is required, the algorithm for the end-fixed TSP can deal with route optimization with constraint of fixed ends effectively, and the algorithm for the path-constraint could benefit the traffic problems where some cities cannot be visited from each other. |
| |
| Keywords: | constrained traveling salesman problem genetic algorithm Hamiltonian path open route fixed end |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《自然科学进展(英文版)》浏览原始摘要信息 |
| 点击此处可从《自然科学进展(英文版)》下载免费的PDF全文 |
|
