A coloring traveling salesman problem (CTSP) generalizes the well-known multiple traveling salesman problem, where colors are used to differentiate salesmen’s the accessibility to individual cities to be visited. As a useful model for a variety of complex scheduling problems, CTSP is computationally challenging. In this paper, we propose a Multi-neighborhood Simulated Annealing-based Iterated Local Search (MSAILS) to solve it. Starting from an initial solution, it iterates through three sequential search procedures: a multi-neighborhood simulated annealing search to find a local optimum, a local search-enhanced edge assembly crossover to find nearby high-quality solutions around a local optimum, and a solution reconstruction procedure to move away from the current search region. Experimental results on two groups of 45 medium and large benchmark instances show that it significantly outperforms state-of-the-art algorithms. In particular, it is able to discover new upper bounds for 29 instances while matching 8 previous best-known upper bounds. Hence, this work greatly advances the field of CTSP.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Multi-Neighborhood Simulated Annealing-Based Iterated Local Search for Colored Traveling Salesman Problems


    Beteiligte:
    Zhou, Yangming (Autor:in) / Xu, Wenqiang (Autor:in) / Fu, Zhang-Hua (Autor:in) / Zhou, MengChu (Autor:in)

    Erschienen in:

    Erscheinungsdatum :

    01.09.2022


    Format / Umfang :

    2301654 byte




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Variable Neighborhood Search for a Colored Traveling Salesman Problem

    Meng, Xianghu / Li, Jun / Dai, Xianzhong et al. | IEEE | 2018



    Bi-Objective Colored Traveling Salesman Problems

    Xu, Xiangping / Li, Jun / Zhou, MengChu | IEEE | 2022


    Traveling Salesman Problems with Profits

    Feillet, Dominique | Online Contents | 2005


    Traveling Salesman Problems with Profits

    Feillet, D. / Dejax, P. / Gendreau, M. | British Library Online Contents | 2005