A colored traveling salesman problem with varying city colors

DOI10.1155/2021/4533483MaRDI QIDQ2065425zbMATH OpenOpenAlexFDO

Authors Xianghu Meng, Jun Li, MengChu Zhou

Publication date 7 January 2022

Published in Discrete Dynamics in Nature and Society (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1155/2021/4533483

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Deterministic network models in operations research (90B10) Stochastic programming (90C15)

Review text

Summary: 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.

Recommendations

• The traveling salesman problem with flexible coloring
• Traveling salesman problem in a time varying network
• Comparison of heuristics for the colourful travelling salesman problem
• The Colorful Traveling Salesman Problem
• A multivariant travelling-salesman problem

Cites work

• Adaptive and Distributed Algorithms for Vehicle Routing in a Stochastic and Dynamic Environment
• Distribution of waiting time for dynamic pickup and delivery problems
• Dynamic path optimization in sharing mode to relieve urban traffic congestion
• Integrating stochastic time-dependent travel speed in solution methods for the dynamic dial-a-ride problem

Cited in

(3)

• Comparison of heuristics for the colourful travelling salesman problem
• The traveling salesman problem with flexible coloring
• Colored points traveling salesman problem

Describes a project that uses

Uses Software

• TSPLIB

This page was built for publication: A colored traveling salesman problem with varying city colors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2065425)