A colored traveling salesman problem (CTSP) is a generalization of the well-known multiple traveling salesman problem. It utilizes colors to differentiate the accessibility of its cities to its salesmen. In our prior work, CTSPs are formulated over graphs associated with a city-color matrix. This work redefines a general colored traveling salesman problem (GCTSP) in the framework of hypergraphs and reveals several important properties of GCTSP. In GCTSP, the setting of city colors is richer than that in CTSPs. As results, it can be used to model and address various complex scheduling problems. Then, a Delaunay-triangulation-based Variable Neighborhood Search (DVNS) algorithm is developed to solve large-scale GCTSPs. At the beginning stage of DVNS, a divide and conquer algorithm is exploited to prepare a Delaunay candidate set for lean insertion. Next, the incumbent solution is perturbed by utilizing greedy multi-insertion and exchange mutation to obtain a variety of neighborhoods. Subsequently, 2-opt and 3-opt are used for local search in turn. Extensive experiments are conducted for many large scale GCTSP cases among which two maximal ones are up to 33000+ cities for 4 salesmen and 240 salesmen given 11000+ cities, respectively. The results show that the proposed method outperforms the existing four genetic algorithms and two VNS methods in terms of search ability and convergence rate.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    Delaunay-Triangulation-Based Variable Neighborhood Search to Solve Large-Scale General Colored Traveling Salesman Problems


    Beteiligte:
    Xu, Xiangping (Autor:in) / Li, Jun (Autor:in) / Zhou, MengChu (Autor:in)


    Erscheinungsdatum :

    2021-03-01


    Format / Umfang :

    4291039 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