| Two-Level Genetic Algorithm for Clustered Traveling Salesman Problem with Application in Large-Scale TSPs |
| |
| 作者姓名： | 丁超 成晔 何苗 |
| |
| 作者单位： | Department of Industrial Engineering Tsinghua University，Department of Industrial Engineering Tsinghua University，Department of Industrial Engineering Tsinghua University，Beijing 100084 China，Beijing 100084 China，Beijing 100084 China |
| |
| 基金项目： | The authors thank Prof. Refael Hassin in the Department of Statistics and 0perations Research of Tel Aviv University in Israel for his help during this research. |
| |
| 摘 要： | Let G = (V, E) be a complete undirected graph with vertex set V, edge set E, and edge weights l(e) satisfying the triangle inequality. The vertex set V is partitioned into clusters V1, V2, …, Vk. The clustered traveling salesman problem (CTSP) seeks to compute the shortest Hamiltonian tour that visits all the verti- ces, in which the vertices of each cluster are visited consecutively. A two-level genetic algorithm (TLGA) was developed for the problem, which favors neither intra-cluster paths nor inter-cluster paths, thus realized inte- grated evolutionary optimization for both levels of the CTSP. Results show that the algorithm is more effec- tive than known algorithms. A large-scale traveling salesman problem (TSP) can be converted into a CTSP by clustering so that it can then be solved by the algorithm. Test results demonstrate that the clustering TLGA for large TSPs is more effective and efficient than the classical genetic algorithm.
|
| 关 键 词： | ＂货郎担＂ 问题 遗传算法 哈密顿圈 CTSP |
| 收稿时间： | 30 September 2006 |
| 修稿时间： | 2006-09-30 |
Two-Level Genetic Algorithm for Clustered Traveling Salesman Problem with Application in Large-Scale TSPs |
| |
| DING Chao,CHENG Ye,HE Miao.Two-Level Genetic Algorithm for Clustered Traveling Salesman Problem with Application in Large-Scale TSPs[J].Tsinghua Science and Technology,2007,12(4):459-465. |
| |
| Authors: | DING Chao CHENG Ye HE Miao |
| |
| Affiliation: | Department of Industrial Engineering, Tsinghua University, Beijing 100084, China |
| |
| Abstract: | Let G = (V, E) be a complete undirected graph with vertex set V, edge set E, and edge weights I(e)satisfying the triangle inequality. The vertex set V is partitioned into clusters V1, V2 Vk. The clustered traveling salesman problem (CTSP) seeks to compute the shortest Hamiltonian tour that visits all the vertices, in which the vertices of each cluster are visited consecutively. A two-level genetic algorithm (TLGA) was developed for the problem, which favors neither intra-cluster paths nor inter-cluster paths, thus realized integrated evolutionary optimization for both levels of the CTSP. Results show that the algorithm is more effective than known algorithms. A large-scale traveling salesman problem (TSP) can be converted into a CTSP by clustering so that it can then be solved by the algorithm. Test results demonstrate that the clustering TLGA for large TSPs is more effective and efficient than the classical genetic algorithm. |
| |
| Keywords: | clustered traveling salesman problem (CTSP) traveling salesman problem (TSP) Hamiltonian cycle genetic algorithm integrated evolutionary optimization |
| 本文献已被 CNKI 维普 万方数据 ScienceDirect 等数据库收录！ |
