查看文章

The Traveling Salesman Problem (TSP) belongs to the class of NP-hard optimization problems. Its solving procedure is complicated, especially for large scale problems. In order to solve the large scale TSPs efficiently, this paper presents a bilevel genetic algorithm with clustering (BLGAC). BLGA-C uses a clustering method to divide a large scale TSP into several subproblems, each subproblem corresponds to a cluster. K-Means clustering method is adopted in this paper. In the lower level, a genetic algorithm is used to find the shortest hamiltonian cycle for each cluster. All these clusters can be handled parallelly. Then, we need to select two nearest vertices between two clusters, and determine which edges will be deleted from the shortest hamiltonian cycle for each cluster, and which edges will be linked for combining two adjacent clusters into one. Repeat this procedure until all clusters are joined into one whole …