A colored traveling salesman problem (CTSP) is a generalization of the well-known multiple traveling salesman problem. In our prior CTSP, each salesman is allocated a particular color and each city, carrying 1, 2, or all salesmen’s colors depending on the problem types, allows any salesmen with the same color to visit exactly once. This paper presents a more common CTSP, in which city colors are diverse, i.e., each city has one to all salesmen’s colors while other elements of the problem keeps unchanged. It is a generalization of the existing CTSPs, i.e., the radial and serial ones, and can be used to model the scheduling problems with different accessibility of jobs toward executors. A city color matrix is introduced to describe the accessibility difference of cities to all salesmen. Since CTSP is NP-hard, this paper presents a variable neighborhood search (VNS) approach, instead of computationally intractable exact solutions. First, the repetitive solution space due to the dual-chromosome encoding for the prior genetic algorithms can be entirely avoided by using direct-route encoding. Then, a two-stage greedy initialization algorithm is utilized by VNS to generate the initial solution. A city removal mechanism and a reinsertion operation are introduced to change the neighborhood space of the current solution and 2-opt method is adopted for the local search. Extensive simulation is conducted and the results show that the proposed VNS is an efficient heuristics to solve CTSP.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Variable Neighborhood Search for a Colored Traveling Salesman Problem


    Beteiligte:
    Meng, Xianghu (Autor:in) / Li, Jun (Autor:in) / Dai, Xianzhong (Autor:in) / Dou, Jianping (Autor:in)


    Erscheinungsdatum :

    2018-04-01


    Format / Umfang :

    2379387 byte




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch





    Bi-Objective Colored Traveling Salesman Problems

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


    A Dynamic Colored Traveling Salesman Problem With Varying Edge Weights

    Meng, Xianghu / Li, Jun / Zhou, Mengchu et al. | IEEE | 2022