{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,21]],"date-time":"2026-05-21T07:42:17Z","timestamp":1779349337774,"version":"3.51.4"},"reference-count":33,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2018,3,15]],"date-time":"2018-03-15T00:00:00Z","timestamp":1521072000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100004410","name":"T\u00fcrkiye Bilimsel ve Teknolojik Ara\u015ftirma Kurumu","doi-asserted-by":"publisher","award":["2215"],"award-info":[{"award-number":["2215"]}],"id":[{"id":"10.13039\/501100004410","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>The Equality-Generalized Travelling Salesman Problem (E-GTSP), which is an extension of the Travelling Salesman Problem (TSP), is stated as follows: given groups of points within a city, like banks, supermarkets, etc., find a minimum cost Hamiltonian cycle that visits each group exactly once. It can model many real-life combinatorial optimization scenarios more efficiently than TSP. This study presents five spatially driven search-algorithms for possible transformation of E-GTSP to TSP by considering the spatial spread of points in a given urban city. Presented algorithms are tested over 15 different cities, classified by their street-network\u2019s fractal-dimension. Obtained results denote that the R-Search algorithm, which selects the points from each group based on their radial separation with respect to the start\u2013end point, is the best search criterion for any E-GTSP to TSP conversion modelled for a city street network. An 8.8% length error has been reported for this algorithm.<\/jats:p>","DOI":"10.3390\/ijgi7030115","type":"journal-article","created":{"date-parts":[[2018,3,15]],"date-time":"2018-03-15T05:11:28Z","timestamp":1521090688000},"page":"115","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Spatial Transformation of Equality \u2013 Generalized Travelling Salesman Problem to Travelling Salesman Problem"],"prefix":"10.3390","volume":"7","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7708-8352","authenticated-orcid":false,"given":"Mohammed","family":"Zia","sequence":"first","affiliation":[{"name":"Geomatics Engineering Department, Istanbul Technical University, Maslak, Istanbul 34469, Turkey"},{"name":"National Innovation and Research Center for Geographical Information Technologies, Maslak, Istanbul 34469, Turkey"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3050-5619","authenticated-orcid":false,"given":"Ziyadin","family":"Cakir","sequence":"additional","affiliation":[{"name":"National Innovation and Research Center for Geographical Information Technologies, Maslak, Istanbul 34469, Turkey"},{"name":"Department of Geology, Faculty of Mines, Istanbul Technical University, Maslak, Istanbul 34469, Turkey"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7498-1540","authenticated-orcid":false,"given":"Dursun","family":"Seker","sequence":"additional","affiliation":[{"name":"Geomatics Engineering Department, Istanbul Technical University, Maslak, Istanbul 34469, Turkey"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2018,3,15]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1080\/14786445608642212","article-title":"Memorandum respecting a new system of roots of unity","volume":"12","author":"Hamilton","year":"1856","journal-title":"Philos. Mag."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"717","DOI":"10.1057\/jors.1975.151","article-title":"Some Simple Applications of the Travelling Salesman Problem","volume":"26","author":"Lenstra","year":"1975","journal-title":"Oper. Res. Quart."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1002\/net.21628","article-title":"Dynamic vehicle routing problems: Three decades and counting","volume":"67","author":"Psaraftis","year":"2016","journal-title":"Networks"},{"key":"ref_4","first-page":"43","article-title":"The record balancing problem: A dynamic programming solution of a genera salesman problem","volume":"2","year":"1969","journal-title":"RAIRO-Oper. Res."},{"key":"ref_5","first-page":"185","article-title":"Mathematical model for scheduling clients through welfare agencies","volume":"8","author":"Saksena","year":"1970","journal-title":"Can. Oper. Res. Soc."},{"key":"ref_6","first-page":"97","article-title":"Generalized travelling salesman problem through n sets of nodes","volume":"7","author":"Srivastava","year":"1969","journal-title":"Can. Oper. Res. Soc."},{"key":"ref_7","first-page":"61","article-title":"Generalized Travelling Salesman Problem Through n Sets Of Nodes: An Integer Programming Approach","volume":"21","author":"Laporte","year":"1983","journal-title":"INFOR Inf. Syst. Oper. Res."},{"key":"ref_8","first-page":"623","article-title":"A Lagrangian Based Approach for the Asymmetric Generalized Traveling Salesman Problem","volume":"39","author":"Noon","year":"1991","journal-title":"Int. J. Prod. Res."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/s12532-015-0080-8","article-title":"Solving the equality generalized traveling salesman problem using the Lin\u2013Kernighan\u2013Helsgaun Algorithm","volume":"7","author":"Helsgaun","year":"2015","journal-title":"Math. Program. Comput."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Karp, R.M. (2009). Reducibility among Combinatorial Problems. 50 Years of Integer Programming 1958\u20132008, Springer.","DOI":"10.1007\/978-3-540-68279-0_8"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"1461","DOI":"10.1057\/jors.1996.190","article-title":"Some Applications of the Generalized Travelling Salesman Problem","volume":"47","author":"Laporte","year":"1996","journal-title":"J. Oper. Res. Soc."},{"key":"ref_12","first-page":"2581","article-title":"Process planning for rotational parts using the generalized travelling salesman problem","volume":"41","author":"Gutin","year":"2010","journal-title":"Int. J. Prod. Res."},{"key":"ref_13","first-page":"830","article-title":"The Traveling Salesman Problem and Its Variations","volume":"12","author":"Gutin","year":"2007","journal-title":"Comb. Optim."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/s12532-009-0004-6","article-title":"General k-opt submoves for the Lin\u2013Kernighan TSP heuristic","volume":"1","author":"Helsgaun","year":"2009","journal-title":"Math. Program. Comput."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R., and Shmoys, D.B. (1985). The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley.","DOI":"10.2307\/2582681"},{"key":"ref_16","unstructured":"Fu, C., and Cai, D. (arXiv, 2016). EFANNA: An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based on kNN Graph, arXiv."},{"key":"ref_17","unstructured":"Okabe, A., Boots, B., Sugihara, K., Chiu, S.N., and Kendall, D.G. (2008). Spatial Tessellations: Concepts and Applications of Voronoi Diagrams, Wiley."},{"key":"ref_18","first-page":"15","article-title":"A New Spatial Approach for Efficient Transformation of Equality\u2014Generalized TSP to TSP","volume":"17","author":"Zia","year":"2017","journal-title":"Free Open Source Softw. Geospat. (FOSS4G) Conf. Proc."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0166-218X(87)90020-5","article-title":"Generalized travelling salesman problem through n sets of nodes: The asymmetrical case","volume":"18","author":"Laporte","year":"1987","journal-title":"Discret. Appl. Math."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1016\/S0167-6377(03)00031-2","article-title":"Transformations of generalized ATSP into ATSP","volume":"31","author":"Gutin","year":"2003","journal-title":"Oper. Res. Lett."},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/S0020-0255(96)00084-9","article-title":"An efficient transformation of the generalized traveling salesman problem into the traveling salesman problem on digraphs","volume":"102","author":"Dimitrijevic","year":"1997","journal-title":"Inf. Sci."},{"key":"ref_22","first-page":"114","article-title":"Computational Evaluation Of A Transformation Procedure For The Symmetric Generalized Traveling Salesman Problem","volume":"37","author":"Laporte","year":"2016","journal-title":"INFOR Inf. Syst. Oper. Res."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0020-0255(93)90133-7","article-title":"Transformation of the generalized traveling-salesman problem into the standard traveling-salesman problem","volume":"74","author":"Lien","year":"1993","journal-title":"Inf. Sci."},{"key":"ref_24","first-page":"39","article-title":"An Efficient Transformation Of The Generalized Traveling Salesman Problem","volume":"31","author":"Noon","year":"1993","journal-title":"INFOR Inf. Syst. Oper. Res."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1145\/321105.321111","article-title":"Dynamic Programming Treatment of the Travelling Salesman Problem","volume":"9","author":"Bellman","year":"1962","journal-title":"J. ACM"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1287\/opre.45.3.378","article-title":"A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem","volume":"45","author":"Fischetti","year":"1997","journal-title":"Oper. Res. Lett."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by Simulated Annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"key":"ref_28","unstructured":"Munson, D. (2018, January 18). Which Street Pattern Represents Your Continent?. Available online: https:\/\/munsonscity.com\/2013\/10\/09."},{"key":"ref_29","unstructured":"Bourke, P. (2018, January 18). Fractal Dimension Calculator\u2014FDC. Available online: http:\/\/paulbourke.net\/fractals\/fracdim."},{"key":"ref_30","unstructured":"(2018, January 18). Overpass API. OpenStreetMap Overpass API. Available online: http:\/\/overpass-api.de."},{"key":"ref_31","unstructured":"Hijmans, R., Kapoor, J., Wieczorek, J., Garcia, N., Maunahan, A., Rala, A., and Mandel, A. (2018, January 18). GADM Database of Global Administrative Areas. Available online: http:\/\/www.gadm.org."},{"key":"ref_32","unstructured":"Zverovitch, A. (2018, January 18). GTSP iNstances. Available online: http:\/\/www.cs.rhul.ac.uk\/home\/zvero\/GTSPLIB."},{"key":"ref_33","unstructured":"Zia, M. (2018, January 18). E-GTSP-to-TSP-Tested-Instances. Available online: https:\/\/github.com\/Zia-\/E-GTSP-to-TSP-tested-instances."}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/7\/3\/115\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T14:57:09Z","timestamp":1760194629000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/7\/3\/115"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,15]]},"references-count":33,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2018,3]]}},"alternative-id":["ijgi7030115"],"URL":"https:\/\/doi.org\/10.3390\/ijgi7030115","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,15]]}}}