Volume 14 Number 6 (Jun. 2019)
Home > Archive > 2019 > Volume 14 Number 6 (Jun. 2019) >
JCP 2019 Vol.14(6): 426-437 ISSN: 1796-203X
doi: 10.17706/jcp.14.6.426-437

A Method to Search Traveling Salesman Problem Backbones Based on GA and Frequency Graph

Yong Wang, Changxin Geng, Yiwen Wu
School of Renewable Energy, North China Electric Power University, Beijing 102206, China.

Abstract—The traveling salesman problem (TSP) is a well-known NP-hard problem in combinatorial optimization. The search space of the optimal Hamiltonian cycle (OHC) is increasing exponentially according to the scale n. In order to reduce the search space of TSP, we first convert the complete graph Kn into the frequency graph (FG) with the approximate optimal n-vertex paths computed with an improved GA. The GA is improved with a four-vertex-three-line inequality to compute the approximate paths of TSP. Then, TSP backbones with 2n edges are derived from the FG. The experimental results show that the TSP backbones include at least 95% edges in the OHC. Based on the backbones, the search space of the OHC or approximations is greatly reduced.

Index Terms—TSP, Backbone, frequency graph, GA.

[PDF]

Cite: Yong Wang, Changxin Geng, Yiwen Wu, "A Method to Search Traveling Salesman Problem Backbones Based on GA and Frequency Graph," Journal of Computers vol. 14, no. 6, pp. 426-437, 2019.

General Information

ISSN: 1796-203X
Abbreviated Title: J.Comput.
Frequency: Monthly
Editor-in-Chief: Prof. Liansheng Tan
Executive Editor: Ms. Nina Lee
Abstracting/ Indexing: DBLP, EBSCO,  ProQuest, INSPEC, ULRICH's Periodicals Directory, WorldCat, CNKI,etc
E-mail: jcp@iap.org
  • Sep 16, 2019 News!

    Vol 14, No 9 has been published with online version   [Click]

  • Aug 16, 2019 News!

    Vol 14, No 8 has been published with online version   [Click]

  • Jul 19, 2019 News!

    Vol 14, No 7 has been published with online version   [Click]

  • Jun 21, 2019 News!

    Vol 14, No 6 has been published with online version   [Click]

  • Apr 28, 2019 News!

    Vol 14, No 5 has been published with online version 7 papers are published in this issue after peer review   [Click]

  • Read more>>