An optimization framework of K-means clustering and metaheuristic for traveling salesman problem

• Main Author: Wang, Benquan
• Other Authors: Meng-Hiot Lim
• Format: Thesis-Master by Coursework
• Language: English
• Published: Nanyang Technological University 2021
• Subjects: Engineering::Electrical and electronic engineering
• Online Access: https://hdl.handle.net/10356/154401
• Institution: Nanyang Technological University

In this dissertation, we first studied the optimization framework of K-means clustering genetic algorithm. By comparing with traditional genetic algorithm, we verified that the optimization framework can effectively save computing time when solving large-scale traveling salesman problems and the final path length also meets the requirements. Based on the randomness of the genetic algorithm, we make the improvement of this optimization framework. By adjusting the sequence of operations about the framework, we compute the path length on each iteration during cluster process and select the optimal results through comparison. The improved framework has a better path length than before. In addition, we selected the combination of ant colony algorithm and K-means clustering to form another optimization framework, which also verified the optimization effect on the running time when solving large-scale traveling salesman problems and could decrease calculation error rate. At the same time, we conduct related research on the parameter analysis of ant colony algorithm and summarize properties of each parameter of the ant colony algorithm and their influence on the final optimization result.