Colored Points Traveling Salesman Problem

Abstract

The Colored Points Traveling Salesman Problem (Colored Points TSP) is introduced in this work as a novel variation of the traditional Euclidean Traveling Salesman Problem (TSP) in which the set of points is partitioned into multiple classes, each of which is represented by a distinct color (or label). The goal is to find a minimum cost cycle that visits all the colors so that each color appears only once. This problem finds diverse applications across various fields, including transportation, goods distribution, postal services, inspection, insurance, and banking. By reducing the traditional TSP to it, we can demonstrate that Colored Points TSP is NP-hard. Here, we offer a $\frac{2\pi r}{3}$-approximation algorithm for this problem when the points are placed on a unit grid, where $r$ denotes the radius of the points' smallest color-spanning circle. The algorithm has been implemented, executed on random datasets, and compared against the brute force method.