Two-Level Genetic Algorithm for Clustered Traveling Salesman Problem with Application in L

Two-Level Genetic Algorithm for Clustered Traveling Salesman Problem with Application in

Large-Scale TSPs

佚名

【期刊名称】《清华大学学报（英文版）》 【年(卷),期】2007(012)004

【摘要】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. 【总页数】7页(459-465)

【关键词】clustered traveling salesman problem (CTSP);traveling

salesman problem (TSP);Hamiltonian cycle;genetic algorithm;integrated evolutionary optimization 【作者】佚名

【作者单位】Department of Industrial Engineering, Tsinghua University, Beijing 100084, China;Department of Industrial Engineering, Tsinghua University, Beijing 100084, China;Department of Industrial Engineering, Tsinghua University, Beijing 100084, China 【正文语种】中文 【中图分类】O1 【文献来源】

https://www.zhangqiaokeyan.com/academic-journal-cn_tsinghua-science-technology_thesis/0201250461729.html 【相关文献】

1.Algorithm for solving the bi-level decision making problem with continuous variables in the upper level based on genetic algorithm [J], XIAO Jian; CHEN Yi-hua

2.Clustering face algorithm of Multi-level blocks using high-level feature [J], ZHANG Xiangxiang; FANG Zhijun

3.A combination algorithm of Chaos optimization and genetic algorithm and its application in maneuvering multiple targets data association [J], 4.Solving traveling salesman problems using generalized chromosome genetic algorithm [J], Jinhui Yang; Chunguo Wu; Heow Pueh Lee;

Yanchun Liang

5.Solving constrained traveling salesman problems by genetic algorithms [J], WU Chunguo; LIANG Yanchun; LEE Heowpueh; LU Chun; LIN Wuzhong

以上内容为文献基本信息，获取文献全文请下载