A Metaheuristic Algorithm with Hybrid Insertion Procedure for the Traveling Salesman Problem
Finding the optimal solution to combinatorial optimization problems can be difficult, even when a partial structure (solution) of the optimal solution may be found easily. How to expand the partial solution into a full solution and how to insert other elements are important considerations for the construction of initial solutions. We propose a new procedure for constructing initial solutions of combinatorial optimization problems. This procedure employs hybrid insertion, which combines standard insertion with other heuristics. The proposed algorithm is applied to the traveling salesman problem (TSP), an NP-hard combinatorial optimization problem, to demonstrate the efficiency of the proposed algorithm. The accuracy of the obtained solutions is evaluated against the solutions of benchmark problems. On most problems, the proposed algorithm found shorter tours than other construction algorithms did.
Keywords: Traveling Salesman Problem, Threshold, CCA Algorithm, Minimum Spanning Tree
Download Full-Text
ABOUT THE AUTHORS
Takahiro Hoshino
College of Science and Technology, Nihon University
Chuan Tian
College of Science and Technology, Nihon University
Hisashi Kondo
Ibaraki University
Kazuhiro Tsuboi
Ibaraki University
Yoshio Hamamatsu
College of Science and Technology, Nihon University
Takahiro Hoshino
College of Science and Technology, Nihon University
Chuan Tian
College of Science and Technology, Nihon University
Hisashi Kondo
Ibaraki University
Kazuhiro Tsuboi
Ibaraki University
Yoshio Hamamatsu
College of Science and Technology, Nihon University