SavedAdd your journal

Journals / Afyon Kocatepe Üniversitesi Fen ve Mühendislik Bilimleri Dergisi / 2026 / Cilt: 24 Sayı: 3

Selective Clustered Traveling Salesman Problem and Mathematical Formulations

Seçici Kümelendirilmiş Gezgin Satıcı Problemi ve Matematiksel Formülasyonları

Tusan Derya(BAŞKENT ÜNİVERSİTESİ)0000-0002-2851-4463
Esra Dinler(BAŞKENT ÜNİVERSİTESİ)0000-0001-8868-8484
Barış Keçeci(BAŞKENT ÜNİVERSİTESİ)0000-0002-2730-5993
Pages
531–551
Publication Date
2024-06-27
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

The performance of the formulations is tested on 416 problems derived from 52 test problems and the results are included.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:The Clustered Traveling Salesman Problem (CTSP) is an extension of the Traveling Salesman Problem (GSP).
📊
Key Findings & Data:All nodes must be divided into clusters that whose intersections are empty sets, and each cluster must be visited once in a tour.
💡
Conclusion & Impact:The performance of the formulations is tested on 416 problems derived from 52 test problems and the results are included.
🔬Design:Araştırma Makalesi
📍Scope:Comprehensive Sample
⚙️Variables:Kümelendirilmiş gezgin satıcı problemi · Oryantiring problemi · Kâr getirili gezgin satıcı problemi

Abstract

The Clustered Traveling Salesman Problem (CTSP) is an extension of the Traveling Salesman Problem (GSP). All nodes must be divided into clusters that whose intersections are empty sets, and each cluster must be visited once in a tour. In addition, all nodes in each cluster must be visited. In this study, Selective Clustered TSP (SCTSP), which is a general extension of CTSP, is defined. The aim of SCTSP is to find the order of nodes to be visited by selecting clusters to obtain the largest total profit within a certain time limit. In the problem, if the traveler is to visit a cluster, it must visit all nodes in the cluster. This problem includes cluster selection and determination of the shortest path between nodes in selected clusters. In this study, the SCTSP is defined and new formulations are proposed for this problem. The performance of the formulations is tested on 416 problems derived from 52 test problems and the results are included.

Özet

Kümelendirilmiş gezgin satıcı problemi (KGSP), gezgin satıcı probleminin (GSP) bir uzantısıdır ve tüm düğümler kesişimleri boş küme olan kümelere bölünerek her küme bir turda mutlaka bir kez ziyaret edilmelidir. Ayrıca uğranan her kümede bulunan tüm düğümler mutlaka ziyaret edilmelidir. Bu çalışmada, KGSP'nin genel bir uzantısı olan Seçici Kümelendirilmiş GSP (SKGSP) tanımlanmaktadır. SKGSP’de amaç, belirli bir zaman kısıtı içerisinde en büyük toplam kazancı elde edecek şekilde kümelerin seçilerek ziyaret edilecek düğüm sırasının bulunmasıdır. Problemde, gezgin eğer bir kümeyi ziyaret edecek ise küme içindeki tüm düğümleri ziyaret etmelidir. Bu problem, küme seçimi ve seçilen kümelerde düğümler arasındaki en kısa yolun belirlenmesi karar problemlerini birlikte içerir. Çalışmada, SKGSP tanımı ve ilgili problem için yeni formülasyonlar önerilmektedir. Formülasyonların performansı, 52 test probleminden türetilmiş 416 problem üzerinde denenerek sonuçlara yer verilmiştir.

🔖

Cite This Article

Derya, T., Dinler, E., Keçeci, B. (2024). Selective Clustered Traveling Salesman Problem and Mathematical Formulations. Afyon Kocatepe Üniversitesi Fen ve Mühendislik Bilimleri Dergisi, Cilt: 24 Sayı: 3, 531–551. https://doi.org/10.35414/akufemubid.1368379

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (45)

  1. Angelelli, E., Archetti, C., and Vindigni, M.,2014. The clustered orienteering problem. European Journal of Operational Research, 238(2), 404-414. https://doi.org/10.1016/j.ejor.2014.04.006
  2. Anily, S., Bramel, J., and Hertz, A., 1999. A 53-approximation algorithm for the clustered traveling salesman tour and path problems. Operations Research Letters, 24(1-2), 29-35. https://doi.org/10.1016/S0167-6377(98)00046-7
  3. Archetti, C., Bianchessi, N., and Speranza, M. G., 2013. Optimal solutions for routing problems with profits. Discrete Applied Mathematics, 161(4), 547-557. https://doi.org/10.1016/j.dam.2011.12.021
  4. Archetti, C., Carrabs, F., and Cerulli, R., 2018. The set orienteering problem. European Journal of Operational Research, 267(1), 264-272. https://doi.org/10.1016/j.ejor.2017.11.009
  5. Arkin, E. M., Hassin, R., and Klein, L., 1997. Restricted delivery problems on a network. Networks: An International Journal, 29(4), 205-216. https://doi.org/10.1002/(SICI)1097-0037(199707)29:4 3.0.CO;2-J
  6. Balas, E., 1989. The prize collecting traveling salesman problem. Networks, 19(6), 621-636. https://doi.org/10.1002/net.3230190602
  7. Bao, X., and Liu, Z., 2012. An improved approximation algorithm for the clustered traveling salesman problem. Information Processing Letters, 112(23), 908-910. https://doi.org/10.1016/j.ipl.2012.08.020
  8. Carrabs, F., 2021. A biased random-key genetic algorithm for the set orienteering problem. European Journal of Operational Research, 292(3), 830-854. https://doi.org/10.1016/j.ejor.2020.11.043
  9. Chisman, J. A., 1975. The clustered traveling salesman problem. Computers & Operations Research, 2(2), 115-119. https://doi.org/10.1016/0305-0548(75)90015-5
  10. Dell'Amico, M., Maffioli, F., and Värbrand, P., 1995. On prize collecting tours and the asymmetric travelling salesman problem. International Transactions in Operational Research, 2(3), 297-308. https://doi.org/10.1111/j.1475-3995.1995.tb00023.x
  11. Derya, T., Dinler, E., and Keçeci, B., 2020. Selective generalized travelling salesman problem. Mathematical and Computer Modelling of Dynamical Systems, 26(1), 80-118. https://doi.org/10.1080/13873954.2019.1705496
  12. Derya, T., Keçeci, B., and Dinler, E., 2023. Selective clustered traveling salesman problem. International Journal of Systems Science: Operations & Logistics, 10(1), 2235266. https://doi.org/10.1080/23302674.2023.2235266
  13. Ding, C., Cheng, Y., and He, M., 2007. Two-level genetic algorithm for clustered traveling salesman problem with application in large-scale TSPs. Tsinghua Science & Technology, 12(4), 459-465. https://doi.org/10.1016/S1007-0214(07)70068-8
  14. Feillet, D., Dejax, P., and Gendreau, M., 2005. Traveling salesman problems with profits. Transportation science, 39(2), 188-205. https://doi.org/10.1287/trsc.1030.0079
  15. Fischetti, M., Salazar González, J. J., and Toth, P., 1997. A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Operations Research, 45(3), 378-394. https://doi.org/10.1287/opre.45.3.378
  16. Gavish, B., and Graves, S. C., 1978. The travelling salesman problem and related problems. Working Paper GR-078-78, Operations Research Center, Massachusetts Institute of Technology.
  17. Gendreau, M., Laporte, G., and Hertz, A., 1997. An approximation algorithm for the traveling salesman problem with backhauls. Operations Research, 45(4), 639-641. https://doi.org/10.1287/opre.45.4.639
  18. Gendreau, M., Laporte, G., and Potvin, J. Y., 1994. Heuristics for the clustered traveling salesman problem (No. CRT-94-54).
  19. Ghaziri, H., and Osman, I. H., 2003. A neural network algorithm for the traveling salesman problem with backhauls. Computers & Industrial Engineering, 44(2), 267-281. https://doi.org/10.1016/S0360-8352(02)00179-1
  20. Golden, B. L., Levy, L., and Vohra, R., 1987. The orienteering problem. Naval research logistics, 34(3), 307-318. https://doi.org/10.1002/1520-6750(198706)34:3 3.0.CO;2-D
  21. Gunawan, A., Lau, H. C., and Vansteenwegen, P., 2016. Orienteering problem: A survey of recent variants, solution approaches and applications. European Journal of Operational Research. https://doi.org/10.1016/j.ejor.2016.04.059
  22. Guttmann-Beck, N., Hassin, R., Khuller, S., and Raghavachari, B., 2000. Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica, 28(4), 422-437. https://doi.org/10.1016/j.ejor.2016.04.059
  23. Jepsen, M. K., Petersen, B., Spoorendonk, S., and Pisinger, D., 2014. A branch-and-cut algorithm for the capacitated profitable tour problem. Discrete Optimization, 14, 78-96. https://doi.org/10.1016/j.disopt.2014.08.001
  24. Jongens, K., and Volgenant, T., 1985. The symmetric clustered traveling salesman problem. European Journal of Operational Research, 19(1), 68-75. https://doi.org/10.1016/0377-2217(85)90309-1
  25. Juan, A. A., Lourenço, H. R., Mateo, M., Luo, R., and Castella, Q., 2014. Using iterated local search for solving the flow‐shop problem: parallelization, parametrization, and randomization issues. International Transactions in Operational Research, 21(1), 103-126. https://doi.org/10.1111/itor.12028
  26. Laporte, G., ve Palekar, U., 2002. Some applications of the clustered travelling salesman problem. Journal of the Operational Research Society, 53(9), 972-976. https://doi.org/10.1057/palgrave.jors.2601420
  27. Laporte, G., Potvin, J. Y., and Quilleret, F., 1997. A tabu search heuristic using genetic diversification for the clustered traveling salesman problem. Journal of Heuristics, 2(3), 187-200. https://doi.org/10.1007/BF00127356
  28. Lokin, F. C. J., 1979. Procedures for travelling salesman problems with additional constraints. European Journal of Operational Research, 3(2), 135-141. https://doi.org/10.1016/0377-2217(79)90099-7
  29. López-Ibánez, M., Mascia, F., Marmion, M. É., and Stützle, T., 2014, July. A template for designing single-solution hybrid metaheuristics. In Proceedings of the Companion Publication of the 2014 Annual Conference on Genetic and Evolutionary Computation (pp. 1423-1426). https://doi.org/10.1145/2598394.2609846
  30. Mestria, M., Ochi, L. S., and de Lima Martins, S., 2013. GRASP with path relinking for the symmetric euclidean clustered traveling salesman problem. Computers & Operations Research, 40(12), 3218-3229. https://doi.org/10.1016/j.cor.2012.10.001
  31. Mestria, M., 2016. A hybrid heuristic algorithm for the clustered traveling salesman problem. Pesquisa Operacional, 36(1), 113-132. https://doi.org/10.1590/0101-7438.2016.036.01.0113
  32. Mestria, M., 2018. New hybrid heuristic algorithm for the clustered traveling salesman problem. Computers & Industrial Engineering, 116, 1-12. https://doi.org/10.1016/j.cie.2017.12.018
  33. Miller, C. E., Tucker, A. W., and Zemlin, R. A., 1960. Integer programming formulation of traveling salesman problems. Journal of the ACM, 7(4), 326-329. https://doi.org/10.1145/321043.321046
  34. Pedro, O., Saldanha, R., and Camargo, R., 2013. A tabu search approach for the prize collecting traveling salesman problem. Electronic Notes in Discrete Mathematics, 41, 261-268. https://doi.org/10.1016/j.endm.2013.05.101
  35. Pěnička, R., Faigl, J., ve Saska, M., 2019. Variable neighborhood search for the set orienteering problem and its application to other orienteering problem variants. European Journal of Operational Research, 276(3), 816-825. https://doi.org/10.1016/j.ejor.2019.01.047
  36. Potvin, J. Y., and Guertin, F., 1996. The clustered traveling salesman problem: A genetic approach. In Meta-Heuristics (pp. 619-631). Springer, Boston, MA. https://doi.org/10.1007/978-1-4613-1361-8_37
  37. Souffriau, W., Vansteenwegen, P., Vertommen, J., Berghe, G. V., and Oudheusden, D. V., 2008. A personalized tourist trip design algorithm for mobile tourist guides. Applied Artificial Intelligence, 22(10), 964-985. https://doi.org/10.1080/08839510802379626
  38. Thomadsen, T., and Stidsen, T. K., 2003. The quadratic selective travelling salesman problem. Informatics and Mathematical Modelling Technical Report 2003-17, Technical University of Denmark.
  39. Tsiligirides, T., 1984. Heuristic methods applied to orienteering. Journal of the Operational Research Society, 35(9), 797-809. https://doi.org/10.1057/jors.1984.162
  40. Vansteenwegen, P., Souffriau, W., and Van Oudheusden, D., 2011. The orienteering problem: A survey. European Journal of Operational Research, 209(1), 1-10. https://doi.org/10.1016/j.ejor.2010.03.045
  41. Vansteenwegen, P., and Van Oudheusden, D., 2007. The mobile tourist guide: an OR opportunity. OR insight, 20(3), 21-27. https://doi.org/10.1057/ori.2007.17
  42. Verbeeck, C., Aghezzaf, E. H., and Vansteenwegen, P., 2016. Solving the stochastic time-dependent orienteering problem with time windows. European Journal of Operational Research, 255, 699-718. https://doi.org/10.1016/j.ejor.2016.05.031
  43. Weintraub, A., Aboud, J., Fernandez, C., Laporte, G., and Ramirez, E., 1999. An emergency vehicle dispatching system for an electric utility in Chile. Journal of the Operational Research Society, 50(7), 690-696. https://doi.org/10.1057/palgrave.jors.2600746
  44. Yahiaoui, A. E., Moukrim, A., and Serairi, M., 2017. Hybrid heuristic for the clustered orienteering problem. In Computational Logistics: 8th International Conference, ICCL 2017, Southampton, UK, October 18-20, 2017, Proceedings 8 (pp. 19-33). Springer International Publishing. https://doi.org/10.1007/978-3-319-68496-3_2
  45. Zhang, W., Wang, K., Wang, S., and Laporte, G., 2020. Clustered coverage orienteering problem of unmanned surface vehicles for water sampling. Naval Research Logistics, 67(5), 353-367. https://doi.org/10.1002/nav.21906