The traveling salesman problem (TSP) is a typical combinatorial optimization problem, which is often applied to sensor placement, path planning, etc. In this paper, an improved ACO algorithm based on an adaptive heuristic factor (AHACO) is proposed to deal with the TSP. In the AHACO, three main improvements are proposed to improve the performance of the algorithm. First, the k-means algorithm is introduced to classify cities. The AHACO provides different movement strategies for different city classes, which improves the diversity of the population and improves the search ability of the algorithm. A modified 2-opt local optimizer is proposed to further tune the solution. Finally, a mechanism to jump out of the local optimum is introduced to avoid the stagnation of the algorithm. The proposed algorithm is tested in numerical experiments using 39 TSP instances, and results shows that the solution quality of the AHACO is 83.33% higher than that of the comparison algorithms on average. For large-scale TSP instances, the algorithm is also far better than the comparison algorithms.


    Access

    Download


    Export, share and cite



    Title :

    An Improved Ant Colony Optimization Based on an Adaptive Heuristic Factor for the Traveling Salesman Problem


    Contributors:
    Pengzhen Du (author) / Ning Liu (author) / Haofeng Zhang (author) / Jianfeng Lu (author)


    Publication date :

    2021




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    Unknown




    Heuristic Approach to the Traveling Salesman Problem

    C. Y. Huang / S. H. Lane | NTIS | 1987


    A heuristic approach to the traveling salesman problem

    HUANG, CHIEN / LANE, STEPHEN | AIAA | 1987



    A heuristic algorithm for traveling salesman problems

    Ashour, Said / Vega, J.F. / Parker, R.G. | Elsevier | 1971