Colored points traveling salesman problem

Document Type : Research Paper

Author

Department of Computer Science, Faculty of Mathematical Sciences, University of Kashan, P.O.Box 87317-53153, Kashan, I. R. Iran

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.

Keywords

Main Subjects

References

[1] A. Acharyya, R. K. Jallu, V. Keikha, M. L¨offler and M. Saumell, Minimum color spanning circle of imprecise points, Theoret. Comput. Sci., 930 (2022) 116–127.
[2] B. Cou¨etoux, L. Gourves, J. Monnot and O. A. Telelis, Labeled traveling salesman problems: complexity and approximation, Discrete Optim., 7 no. 1-2 (2010) 74–85.
[3] C. H. Papadimitriou, The Euclidean traveling salesman problem is NP-complete, Theoret. Comput. Sci., 4 no. 3 (1977) 237–244.
[4] E. Tresoldi, R. Wolfler Calvo and S. Borne, Solving the multicolor tsp, in: 24th European Conference on Operational Research (EURO XXIV), Lisbon, Portugal, (2010).
[5] G. Laporte, The traveling salesman problem: An overview of exact and approximate algorithms, European J. Oper. Res., 59 no. 2 (1992) 231–247.
[6] J. J. Sylvester, A question in the geometry of situation, Q. J. Pure Appl. Math., 1 no. 1 (1857) 79–80.
[7] J. Li, M. Zhou, Q. Sun, X. Dai and X. Yu, Colored traveling salesman problem, IEEE transactions on cybernetics, 45 no. 11 (2014) 2390–2401.
[8] J. O’Rourke, Computational geometry in C, Second edition. Cambridge University Press, Cambridge, 1998.
[9] M. Abellanas, F. Hurtado, C. Icking, R. Klein, E. Langetepe, L. Ma, B. Palop and V. Sacrist´an, The farthest color voronoi diagram and related problems, in: Abstracts 17th European Workshop Comput. Geom, Freie Universit¨at, Berlin, (2001) 113–116.
[10] M. Abellanas, F. Hurtado, C. Icking, R. Klein, E. Langetepe, L. Ma, B. Palop and V. Sacrist´an, Smallest color-spanning objects, in: Algorithms—ESA 2001: 9th Annual European Symposium ËšArhus, Denmark, August 28–31, 2001 Proceedings 9, Springer, (2001) 278–289.
[11] M. E. Harvey, R. T. Hocking and J. R. Brown, The chromatic traveling-salesmen problem and its application to planning and structuring geographic space, Geographical Analysis, 6 no. 1 (1974) 33–52.
[12] N. Megiddo, Linear-time algorithms for linear programming in R3 and related problems, SIAM J. Comput., 12 no. 4 (1983) 759–776.
[13] X. Meng, J. Li and M. Zhou, A colored traveling salesman problem with varying city colors, Discrete Dynamics in Nature and Society 2021 (2021) 1–14.
[14] Y. Xiong, B. Golden and E. Wasil, The colorful traveling salesman problem, Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies, Chapter, (2007) 115–123.
Transactions on Combinatorics
Volume 15, Issue 4 - Serial Number 4
December 2026
Pages 305-315

Files

History

  • Receive Date: 24 February 2024
  • Revise Date: 29 November 2025
  • Accept Date: 01 December 2025
  • Published Online: 04 December 2025

Share

How to cite

Statistics