文章基本信息

标题：A Metaheuristic Algorithm with Hybrid Insertion Procedure for the Traveling Salesman Problem
本地全文：下载
作者：Takahiro Hoshino ; Chuan Tian ; Hisashi Kondo 等
期刊名称：International Journal of Computer Science Issues
印刷版ISSN：1694-0784
电子版ISSN：1694-0814
出版年度：2016
卷号：13
期号：3
出版社：IJCSI Press
摘要：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.
关键词：Traveling Salesman Problem; Threshold; CCA Algorithm; Minimum Spanning Tree