A Dynamic Colored Traveling Salesman Problem and Its Solution

详细信息    查看官网全文

• 英文论文题名：A Dynamic Colored Traveling Salesman Problem and Its Solution
• 论文作者：Xianghu Meng ; Jun Li ; Xianzhong Dai
• 英文论文作者：Xianghu Meng ; Jun Li ; Xianzhong Dai ; Ministry of Education Key Laboratory of Measurement and Control of Complex Engineering Systems ; Southeast University
• 年：2017
• 作者机构：Ministry of Education Key Laboratory of Measurement and Control of Complex Engineering Systems,Southeast University;
• 英文论文关键词：Dynamic colored traveling salesman problem ; Variable neighborhood search ; Dynamic optimization problem
• 会议召开时间：2017-07-26
• 会议录名称：第36届中国控制会议论文集（B）
• 英文会议录名称：Proceedings of the 36th Chinese Control Conference（B）
• 语种：英文
• 分类号：TP18
• 学会代码：KZLL
• 会议名称：第36届中国控制会议
• 会议地点：中国辽宁大连
• 主办单位：中国自动化学会控制理论专业委员会
• 学会名称：中国自动化学会控制理论专业委员会
• 页数：6
• 文件大小：1078k
• 原文格式：D
• 会议级别：全国

摘要

The colored traveling salesman problem(CTSP) is a generalization of the well-known multiple traveling salesman problem(MTSP). In CTSP, each city has one to multiple colors, allowing a salesman in the same color to visit exactly once. This work presents a dynamic CTSP(DCTSP) in which the weights of edges among the cities change over time. To solve the DCTSP, we propose a variable neighborhood search(VNS) algorithm with a direct-route encoding and random initialization. The VNS is initialized by greedy operations at two stages and an appropriate population immigrant scheme is used in it to perform the population search in the dynamic environment. Extensive experiments are conducted to test the effectiveness of the greedy initialization and the immigrant scheme with the best population. The results show that the enhanced VNS can track the environment changes of DCTSP more rapidly and effectively.
The colored traveling salesman problem(CTSP) is a generalization of the well-known multiple traveling salesman problem(MTSP). In CTSP, each city has one to multiple colors, allowing a salesman in the same color to visit exactly once. This work presents a dynamic CTSP(DCTSP) in which the weights of edges among the cities change over time. To solve the DCTSP, we propose a variable neighborhood search(VNS) algorithm with a direct-route encoding and random initialization. The VNS is initialized by greedy operations at two stages and an appropriate population immigrant scheme is used in it to perform the population search in the dynamic environment. Extensive experiments are conducted to test the effectiveness of the greedy initialization and the immigrant scheme with the best population. The results show that the enhanced VNS can track the environment changes of DCTSP more rapidly and effectively.

引文

[1]S.Yang,H.Cheng,and F.Wang,Genetic algorithms with immigrants and memory schemes for dynamic shortest path routing problems in mobile ad hoc networks,IEEE Transactions on Systems,Man,and Cybernetics,Part C(Applications and Reviews),40(1):52-63,2010.
    [2]N.R.Sabar,A.Song,Z.Tari,X.Yi,and A.Zomaya,A Memetic Algorithm for Dynamic Shortest Path Routing on Mobile Ad-hoc Networks,in Proc.IEEE 21st International Conference on Parallel and Distributed Systems(ICPADS),Melbourne,Australia,2015:60-67.
    [3]T.,Ayad,N.R.Sabar,and A.Song,A multi-population memetic algorithm for dynamic shortest path routing in mobile ad-hoc networks,in Proc.IEEE Congress on Evolutionary Computation(CEC),Vancouver,Canada 2016:4119-4126.
    [4]M.Michalis,and S.Yang,Ant algorithms with immigrants schemes for the dynamic vehicle routing problem,Information Sciences,294(1):456-477,2015.
    [5]J.Li,Q.Sun,M.C.Zhou,Z.Dai,and X.Yu,Colored traveling salesman problem,IEEE transactions on cybernetics,45(11):2390-2401,2015.
    [6]X.Meng,J.Li,M.C.Zhou,X.Dai,and J.Dou,Population-based incremental learning algorithm for a serial colored traveling salesman problem,IEEE Transactions on Systems,Man,and Cybernetics:Systems,[Online],doi:10.1109/TSMC.2016.2591267.
    [7]J.Li,X.Meng,M.C.Zhou,and X.Dai,A Two-Stage Approach to Path Planning and Collision Avoidance of Multibridge Machining Systems,IEEE Transactions on Systems,Man,and Cybernetics:Systems,[Online],doi:10.1109/TSMC.2016.2531648.
    [8]P.Hansen,N.Mladenovi,and JoséA.Moreno Pérez,Variable neighbourhood search:methods and applications,Annals of Operations Research,175(1):367-407,2010.
    [9]X.Meng,J.Li,X.Dai,and J.Dou,Variable Neighborhood Search for Colored Traveling Salesman Problem,IEEE Transactions on Intelligent Transportation Systems,[under review].