Colored points traveling salesman problem

Asaeedi, Saeed

doi:10.22108/toc.2025.140814.2153

تعداد نشریات	44
تعداد شماره‌ها	1,877
تعداد مقالات	15,278
تعداد مشاهده مقاله	43,730,695
تعداد دریافت فایل اصل مقاله	17,562,976

	Colored points traveling salesman problem
Transactions on Combinatorics
دوره 15، شماره 4، اسفند 2026، صفحه 305-315 اصل مقاله (942.44 K)
نوع مقاله: Research Paper
شناسه دیجیتال (DOI): 10.22108/toc.2025.140814.2153
نویسنده
Saeed Asaeedi^*
Department of Computer Science, Faculty of Mathematical Sciences, University of Kashan, P.O.Box 87317-53153, Kashan, I. R. Iran
چکیده
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.
کلیدواژه‌ها
Colored Points TSP؛ Colored TSP؛ TSP؛ Approximation Algorithm؛ Computational Geometry

مراجع
[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.
آمار تعداد مشاهده مقاله: 299 تعداد دریافت فایل اصل مقاله: 378

سامانه مدیریت نشریات علمی. طراحی و پیاده سازی از سیناوب

پیوندهای مفید

اخبار و اعلانات

آمار

Colored points traveling salesman problem