A Colored Traveling Salesman Problem with Varying City Colors
A Colored Traveling Salesman Problem with Varying City Colors
复制标题
不同城市颜色的有色旅行推销员问题
DOI：
10.1155/2021/4533483
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
M.C. Zhou
中科院分区：
文献类型：
--
作者：
X. Meng;J. Li;M.C. Zhou
有色旅行商问题（CTSP）是一个用颜色来表征城市和推销员之间不同匹配关系的路径优化问题。也就是说，每个销售员都有一种颜色，而每个城市都有一个或多个销售员的颜色，从而允许销售员只访问一次他们颜色的城市。值得注意的是，城市对销售人员的可访问性可能会随着时间的推移而发生变化，这通常发生在在线零售商的多仓库配送中。本文提出了一种新的动态变化城市颜色的CTSP，用于描述和建模一些可变城市访问量的调度问题。该问题比先前提出的具有变化边缘权重的CTSP更复杂。具体地，解的可行性随着城市改变其颜色而改变，即，可行的原始解路径可能在城市颜色改变之后变得不再可行。提出了一种可变邻域搜索算法来解决该问题。具体而言，设计了具有可调频率和振幅的动态环境模拟器来模拟这种颜色变化。然后，直接路由编码，贪婪初始化，并提出了适当的人口移民，形成一个增强的VNS，然后其性能进行了评估。大量实验结果表明，该方法能够快速跟踪环境变化，有效解决了环境变化问题。
A colored traveling salesman problem (CTSP) is a path optimization problem in which colors are used to characterize diverse matching relationship between cities and salesmen. Namely, each salesman has a single color while every city has one to multiple salesmen’s colors, thus allowing salesmen to visit exactly once the cities of their colors. It is noteworthy that cities’ accessibilities to salesmen may change over time, which usually takes place in the multiwarehouse distribution of online retailers. This work presents a new CTSP with dynamically varying city colors for describing and modeling some scheduling problems with variable city accessibilities. The problem is more complicated than the previously proposed CTSP with varying edge weights. In particular, the solution feasibility changes as the cities change their colors, that is, a feasible original solution path may become no longer feasible after city colors change. A variable neighborhood search (VNS) algorithm is presented to solve the new problem. Specifically, a dynamic environment simulator with an adjustable frequency and amplitude is designed to mimic such color changes. Then, direct-route encoding, greedy initialization, and appropriate population immigrant are proposed to form an enhanced VNS, and then its performance is evaluated. The results of extensive experiments show that the proposed VNS can quickly track the environmental changes and effectively resolve the problem.
登录
查看更多内容
DOI：
10.1109/tsmcc.2009.2023676
发表时间：
2010
期刊：
IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews)
影响因子：
--
作者：
Shengxiang Yang;Hui Cheng;Fang Wang
通讯作者：
Shengxiang Yang;Hui Cheng;Fang Wang
DOI：
10.1016/j.trc.2010.09.007
发表时间：
2011-08
影响因子：
8.3
作者：
A. Juan;J. Faulin;S. Grasman;D. Riera;J. Marull;C. Méndez
通讯作者：
A. Juan;J. Faulin;S. Grasman;D. Riera;J. Marull;C. Méndez
DOI：
10.1109/cis-ram47153.2019.9095780
发表时间：
2019-11
期刊：
2019 IEEE International Conference on Cybernetics and Intelligent Systems (CIS) and IEEE Conference on Robotics, Automation and Mechatronics (RAM)
影响因子：
--
作者：
Shuo Wang;Jiandong Zhang;Zhen Zhang;Xiao Yu
通讯作者：
Shuo Wang;Jiandong Zhang;Zhen Zhang;Xiao Yu
影响因子：
7.8
作者：
S. Bopardikar;Stephen L. Smith;F. Bullo
通讯作者：
S. Bopardikar;Stephen L. Smith;F. Bullo
影响因子：
1.4
作者：
Hong-min Chen;Yuanhang Zhang
通讯作者：
Hong-min Chen;Yuanhang Zhang