Selective Clustered Traveling Salesman Problem and Mathematical Formulations

Year 2024, , 531 - 551, 27.06.2024

Tusan Derya , Esra Dinler , Barış Keçeci

https://doi.org/10.35414/akufemubid.1368379

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.

Keywords

Clustered traveling salesman problem, Orienteering problem, Traveling salesman problem with profits, Mixed integer mathematical programming

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

Abstract

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.

Keywords

Kümelendirilmiş gezgin satıcı problemi;, Oryantiring problemi;, Kâr getirili gezgin satıcı problemi, Karma tamsayılı matematiksel modelleme

References

• 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
• 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
• 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
• 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
• 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<205::AID-NET3>3.0.CO;2-J
• Balas, E., 1989. The prize collecting traveling salesman problem. Networks, 19(6), 621-636. https://doi.org/10.1002/net.3230190602
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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.
• 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
• Gendreau, M., Laporte, G., and Potvin, J. Y., 1994. Heuristics for the clustered traveling salesman problem (No. CRT-94-54).
• 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
• 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<307::AID-NAV3220340302>3.0.CO;2-D
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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.
• 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
• 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
• 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
• 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
• 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
• 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
• 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