TY - JOUR
T1 - A Dynamic Colored Traveling Salesman Problem With Varying Edge Weights
AU - Meng, Xianghu
AU - Li, Jun
AU - Zhou, Mengchu
AU - Dai, Xianzhong
N1 - Funding Information:
This work was supported in part by the National Natural Science Foundation of China under Grant 61773115, in part by the Natural Science Foundation of Anhui Province under Grant 2008085QF300, in part by the Shenzhen Fundamental Research Program under Grant JCYJ20190813152401690, and in part by the Fundo para o Desenvolvimento das Ciencias e da Tecnologia under Grant 0047/2021/A1.
Publisher Copyright:
© 2000-2011 IEEE.
PY - 2022/8/1
Y1 - 2022/8/1
N2 - 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.
AB - 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.
KW - Dynamic colored traveling salesman problem
KW - Dynamic optimization problem
KW - Variable neighborhood search
UR - http://www.scopus.com/inward/record.url?scp=85136232714&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85136232714&partnerID=8YFLogxK
U2 - 10.1109/TITS.2021.3125721
DO - 10.1109/TITS.2021.3125721
M3 - Article
AN - SCOPUS:85136232714
SN - 1524-9050
VL - 23
SP - 13549
EP - 13558
JO - IEEE Transactions on Intelligent Transportation Systems
JF - IEEE Transactions on Intelligent Transportation Systems
IS - 8
ER -