Thursday 28th of March 2024
 

A Metaheuristic Algorithm with Hybrid Insertion Procedure for the Traveling Salesman Problem


Takahiro Hoshino, Chuan Tian, Hisashi Kondo, Kazuhiro Tsuboi and Yoshio Hamamatsu

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


IJCSI Published Papers Indexed By:

 

 

 

 
+++
About IJCSI

IJCSI is a refereed open access international journal for scientific papers dealing in all areas of computer science research...

Learn more »
Join Us
FAQs

Read the most frequently asked questions about IJCSI.

Frequently Asked Questions (FAQs) »
Get in touch

Phone: +230 911 5482
Email: info@ijcsi.org

More contact details »