TY - JOUR
T1 - A Colored Traveling Salesman Problem with Varying City Colors
AU - Meng, Xianghu
AU - Li, Jun
AU - Zhou, Mengchu
N1 - Publisher Copyright:
© 2021 Xianghu Meng et al.
PY - 2021
Y1 - 2021
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85122192769&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85122192769&partnerID=8YFLogxK
U2 - 10.1155/2021/4533483
DO - 10.1155/2021/4533483
M3 - Article
AN - SCOPUS:85122192769
SN - 1026-0226
VL - 2021
JO - Discrete Dynamics in Nature and Society
JF - Discrete Dynamics in Nature and Society
M1 - 4533483
ER -