{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T03:53:12Z","timestamp":1760241192214,"version":"build-2065373602"},"reference-count":17,"publisher":"MDPI AG","issue":"1","license":[{"start":{"date-parts":[[2019,12,21]],"date-time":"2019-12-21T00:00:00Z","timestamp":1576886400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The Traveling Salesman Problem (TSP) aims at finding the shortest trip for a salesman, who has to visit each of the locations from a given set exactly once, starting and ending at the same location. Here, we consider the Euclidean version of the problem, in which the locations are points in the two-dimensional Euclidean space and the distances are correspondingly Euclidean distances. We propose simple, fast, and easily implementable heuristics that work well, in practice, for large real-life problem instances. The algorithm works on three phases, the constructive, the insertion, and the improvement phases. The first two phases run in time     O (  n 2  )     and the number of repetitions in the improvement phase, in practice, is bounded by a small constant. We have tested the practical behavior of our heuristics on the available benchmark problem instances. The approximation provided by our algorithm for the tested benchmark problem instances did not beat best known results. At the same time, comparing the CPU time used by our algorithm with that of the earlier known ones, in about 92% of the cases our algorithm has required less computational time. Our algorithm is also memory efficient: for the largest tested problem instance with 744,710 cities, it has used about 50 MiB, whereas the average memory usage for the remained 217 instances was 1.6 MiB.<\/jats:p>","DOI":"10.3390\/a13010005","type":"journal-article","created":{"date-parts":[[2019,12,23]],"date-time":"2019-12-23T03:15:01Z","timestamp":1577070901000},"page":"5","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Simple Constructive, Insertion, and Improvement Heuristics Based on the Girding Polygon for the Euclidean Traveling Salesman Problem"],"prefix":"10.3390","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8834-4710","authenticated-orcid":false,"given":"V\u00edctor","family":"Pacheco-Valencia","sequence":"first","affiliation":[{"name":"Centro de Investigaci\u00f3n en Ciencias UAEMor, Universidad Aut\u00f3noma del Estado de Morelos, 62209 Cuernavaca, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5184-0005","authenticated-orcid":false,"given":"Jos\u00e9 Alberto","family":"Hern\u00e1ndez","sequence":"additional","affiliation":[{"name":"Facultad de Contadur\u00eda, Administraci\u00f3n e Inform\u00e1tica UAEMor, 62209 Cuernavaca, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jos\u00e9 Mar\u00eda","family":"Sigarreta","sequence":"additional","affiliation":[{"name":"Facultad de Matem\u00e1ticas UAGro, Universidad Aut\u00f3noma de Guerrero, 39650 Acapulco, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9013-9334","authenticated-orcid":false,"given":"Nodari","family":"Vakhania","sequence":"additional","affiliation":[{"name":"Centro de Investigaci\u00f3n en Ciencias UAEMor, Universidad Aut\u00f3noma del Estado de Morelos, 62209 Cuernavaca, Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,12,21]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(77)90012-3","article-title":"The Euclidean travelling salesman problem is NP-complete","volume":"4","author":"Papadimitriou","year":"1977","journal-title":"Theor. Comput. Sci."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Garey, M.R., Graham, R.L., and Jhonson, D.S. (1976, January 3\u20135). Some NP-Complete geometric problems. Proceedings of the Eight Annual ACM Symposium on Theory of Computing, Hershey, PA, USA.","DOI":"10.1145\/800113.803626"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H., and Shmoys, D.B. (1985). The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley.","DOI":"10.2307\/2582681"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"225","DOI":"10.1016\/S0927-0507(05)80121-5","article-title":"The traveling salesman problem","volume":"Volume 7","author":"Reinelt","year":"1995","journal-title":"Handbooks in Operations Research and Management Science"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1287\/opre.21.2.498","article-title":"An effective heuristic algorithm for the traveling-salesman problem","volume":"21","author":"Lin","year":"1973","journal-title":"Oper. Res."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Chitty, D.M. (2017). Applying ACO to large scale TSP instances. UK Workshop on Computational Intelligence, Springer.","DOI":"10.1007\/978-3-319-66939-7_9"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1016\/j.swevo.2016.06.006","article-title":"Effective heuristics for ant colony optimization to handle large-scale problems","volume":"32","author":"Ismkhan","year":"2017","journal-title":"Swarm Evol. Comput."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"1669","DOI":"10.1007\/s00500-016-2432-3","article-title":"A parallel cooperative hybrid method based on ant colony optimization and 3-Opt algorithm for solving traveling salesman problem","volume":"22","author":"Mahi","year":"2018","journal-title":"Soft Comput."},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Peake, J., Amos, M., Yiapanis, P., and Lloyd, H. (2019, January 13\u201317). Scaling Techniques for Parallel Ant Colony Optimization on Large Problem Instances. Proceedings of the Gecco\u201919\u2014The Genetic and Evolutionary Computation Conference 2019, Prague, Czech Republic.","DOI":"10.1145\/3321707.3321832"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Dahan, F., El Hindi, K., Mathkour, H., and AlSalman, H. (2019). Dynamic Flying Ant Colony Optimization (DFACO) for Solving the Traveling Salesman Problem. Sensors, 19.","DOI":"10.3390\/s19081837"},{"key":"ref_11","first-page":"1","article-title":"Solving traveling salesman problem using parallel repetitive nearest neighbor algorithm on OTIS-Hypercube and OTIS-Mesh optoelectronic architectures","volume":"74","author":"Mahafzah","year":"2008","journal-title":"J. Supercomput."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/j.swevo.2019.04.002","article-title":"Discrete pigeon-inspired optimization algorithm with Metropolis acceptance criterion for large-scale traveling salesman problem","volume":"48","author":"Zhong","year":"2019","journal-title":"Swarm Evol. Comput."},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"791","DOI":"10.1287\/opre.6.6.791","article-title":"A method for solving traveling-salesman problems","volume":"6","author":"Croes","year":"1958","journal-title":"Oper. Res."},{"key":"ref_14","first-page":"39","article-title":"A Simple Heuristic for Basic Vehicle Routing Problem","volume":"3","author":"Vakhania","year":"2016","journal-title":"J. Comput. Sci."},{"key":"ref_15","unstructured":"Sahni, S., and Horowitz, E. (1978). Fundamentals of Computer Algorithms, Computer Science Press, Inc."},{"key":"ref_16","unstructured":"Universit\u00e4t Heidelberg, Institut f\u00fcr Informatik, and Reinelt, G. (2019, June 08). Symmetric Traveling Salesman Problem (TSP). Available online: https:\/\/www.iwr.uni-heidelberg.de\/groups\/comopt\/software\/TSPLIB95\/."},{"key":"ref_17","unstructured":"Natural Sciences and Engineering Research Council of Canada (NSERC) and Department of Combinatorics and Optimization at the University of Waterloo (2019, June 08). TSP Test Data. Available online: http:\/\/www.math.uwaterloo.ca\/tsp\/data\/index.html."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/1\/5\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T13:44:33Z","timestamp":1760190273000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/13\/1\/5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,12,21]]},"references-count":17,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2020,1]]}},"alternative-id":["a13010005"],"URL":"https:\/\/doi.org\/10.3390\/a13010005","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2019,12,21]]}}}