A colored traveling salesman problem (CTSP) is a generalization of the well-known multiple traveling salesman problem. In it, each city has one to multiple colors and allows a salesman in the same color to visit exactly once. This work presents for the first time a CTSP whose edge weights among the cities change over time. It can be applied to dynamic routing problems arising in logistic distribution systems with various goods accessibilities to different types of vehicles. A non-linear integer mathematical program is constructed. A Variable Neighborhood Search (VNS) algorithm with a direct-route encoding and random initialization is then presented to solve it. To increase the convergence rate and population diversity of VNS, it is further combined with two-stage greedy initialization and an appropriate population immigrant scheme to perform the population search in a dynamic environment. Then, off-line performance evaluation and Wilcoxon test of the proposed algorithms are performed. The results show that their solution quality is improved by 30% ~ 60% over the basic VNS’s. They can track the environmental changes of CTSP-VEW more rapidly and effectively. In the end, a case study with a practical scenario is conducted.


    Zugriff

    Zugriff prüfen

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

    A Dynamic Colored Traveling Salesman Problem With Varying Edge Weights


    Beteiligte:
    Meng, Xianghu (Autor:in) / Li, Jun (Autor:in) / Zhou, Mengchu (Autor:in) / Dai, Xianzhong (Autor:in)

    Erschienen in:

    Erscheinungsdatum :

    2022-08-01


    Format / Umfang :

    1606560 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


    Probabilistic Traveling Salesman Problem with Deadlines

    Campbell, Ann M. | Online Contents | 2008



    Probabilistic Traveling Salesman Problem with Deadlines

    Campbell, A.M. / Thomas, B.W. | British Library Online Contents | 2008