{"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":1779349337367,"version":"3.51.4"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,8,7]],"date-time":"2017-08-07T00:00:00Z","timestamp":1502064000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2017,8,7]],"date-time":"2017-08-07T00:00:00Z","timestamp":1502064000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Editor CASM"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Complex Adapt Syst Model"],"published-print":{"date-parts":[[2017,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A well known <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal{NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>NP<\/mml:mi>\n                    <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-hard problem called the <jats:italic>generalized traveling salesman problem<\/jats:italic> (<jats:italic>GTSP<\/jats:italic>) is considered. In <jats:italic>GTSP<\/jats:italic> the nodes of a complete undirected graph are partitioned into clusters. The objective is to find a minimum cost tour passing through exactly one node from each cluster. An exact exponential time algorithm and an effective meta-heuristic algorithm for the problem are presented. The meta-heuristic proposed is a modified <jats:italic>Ant Colony System<\/jats:italic> (<jats:italic>ACS<\/jats:italic>) algorithm called <jats:italic>reinforcing Ant Colony System<\/jats:italic> which introduces new correction rules in the <jats:italic>ACS<\/jats:italic> algorithm. Computational results are reported for many standard test problems. The proposed algorithm is competitive with the other already proposed heuristics for the <jats:italic>GTSP<\/jats:italic> in both solution quality and computational time.<\/jats:p>","DOI":"10.1186\/s40294-017-0048-9","type":"journal-article","created":{"date-parts":[[2017,8,7]],"date-time":"2017-08-07T09:15:10Z","timestamp":1502097310000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":30,"title":["The generalized traveling salesman problem solved with ant algorithms"],"prefix":"10.1186","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2338-2454","authenticated-orcid":false,"given":"Camelia-M.","family":"Pintea","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petric\u0103 C.","family":"Pop","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Camelia","family":"Chira","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,8,7]]},"reference":[{"key":"48_CR1","unstructured":"Bixby B, Reinelt G (1995) Tsplib a library of travelling salesman and related problem instances"},{"key":"48_CR2","unstructured":"Dahlke K (2008) Np-complete problems. Math Reference Project. Retrieved, pp 6\u201321"},{"key":"48_CR3","unstructured":"Dorigo M (1992) Optimization, learning and natural algorithms. Ph. D. Thesis, Politecnico di Milano, Italy"},{"key":"48_CR4","unstructured":"Dunne PE (2008) An annotated list of selected np-complete problems. COMP202, Dept. of Computer Science, University of Liverpool"},{"issue":"3","key":"48_CR5","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1287\/opre.45.3.378","volume":"45","author":"M Fischetti","year":"1997","unstructured":"Fischetti M, Gonz\u00e1lez JJS, Toth P (1997) A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Oper Res 45(3):378\u2013394","journal-title":"Oper Res"},{"key":"48_CR6","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1007\/0-306-48213-4_13","volume-title":"The generalized traveling salesman and orienteering problems. The traveling salesman problem and its variations","author":"M Fischetti","year":"2007","unstructured":"Fischetti M, Salazar-Gonz\u00e1lez J-J, Toth P (2007) The generalized traveling salesman and orienteering problems. The traveling salesman problem and its variations. Springer, Berlin, pp 609\u2013662"},{"key":"48_CR7","volume-title":"Handbook of metaheuristics","author":"FW Glover","year":"2006","unstructured":"Glover FW, Kochenberger GA (2006) Handbook of metaheuristics, vol 57. Springer, Berlin"},{"issue":"1","key":"48_CR8","first-page":"61","volume":"21","author":"G Laporte","year":"1983","unstructured":"Laporte G, Nobert Y (1983) Generalized travelling salesman problem through n sets of nodes: an integer programming approach. INFOR Inf Syst Oper Res 21(1):61\u201375","journal-title":"INFOR Inf Syst Oper Res"},{"key":"48_CR9","unstructured":"Maniezzo ACMDV (1992) Distributed optimization by ant colonies. In: Toward a practice of autonomous systems: proceedings of the first European conference on artificial life. Mit Press, Cambridge, pp 134"},{"issue":"4","key":"48_CR10","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1287\/opre.39.4.623","volume":"39","author":"CE Noon","year":"1991","unstructured":"Noon CE, Bean JC (1991) A lagrangian based approach for the asymmetric generalized traveling salesman problem. Oper Res 39(4):623\u2013632","journal-title":"Oper Res"},{"key":"48_CR11","doi-asserted-by":"crossref","unstructured":"Pintea C, Dumitrescu D (2005) Improving ant systems using a local updating rule. In: IEEE international symposium on symbolic and numeric algorithms for scientific computing (SYNASC 2005), 25\u201329 September 2005. Timisoara, Romania, pp 295\u2013298","DOI":"10.1109\/SYNASC.2005.38"},{"issue":"3","key":"48_CR12","doi-asserted-by":"publisher","first-page":"571","DOI":"10.1016\/S0377-2217(97)00142-2","volume":"108","author":"J Renaud","year":"1998","unstructured":"Renaud J, Boctor FF (1998) An efficient composite heuristic for the symmetric generalized traveling salesman problem. Eur J Oper Res 108(3):571\u2013584","journal-title":"Eur J Oper Res"},{"issue":"1","key":"48_CR13","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.ejor.2004.09.057","volume":"174","author":"LV Snyder","year":"2006","unstructured":"Snyder LV, Daskin MS (2006) A random-key genetic algorithm for the generalized traveling salesman problem. Eur J Oper Res 174(1):38\u201353","journal-title":"Eur J Oper Res"},{"key":"48_CR14","doi-asserted-by":"crossref","unstructured":"St\u00fctzle T, Hoos H (1997) Max\u2013min ant system and local search for the traveling salesman problem. In: IEEE international conference on evolutionary computation, 1997. pp 309\u2013314","DOI":"10.1109\/ICEC.1997.592327"}],"container-title":["Complex Adaptive Systems Modeling"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s40294-017-0048-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s40294-017-0048-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s40294-017-0048-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,30]],"date-time":"2021-07-30T06:51:52Z","timestamp":1627627912000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1186\/s40294-017-0048-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,8,7]]},"references-count":14,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["48"],"URL":"https:\/\/doi.org\/10.1186\/s40294-017-0048-9","relation":{},"ISSN":["2194-3206"],"issn-type":[{"value":"2194-3206","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,8,7]]},"assertion":[{"value":"3 July 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 July 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 August 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"8"}}