{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T04:21:40Z","timestamp":1774930900000,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,12,3]],"date-time":"2013-12-03T00:00:00Z","timestamp":1386028800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Heuristics"],"published-print":{"date-parts":[[2014,2]]},"DOI":"10.1007\/s10732-013-9233-y","type":"journal-article","created":{"date-parts":[[2013,12,2]],"date-time":"2013-12-02T11:18:29Z","timestamp":1385983109000},"page":"107-124","source":"Crossref","is-referenced-by-count":11,"title":["A backbone based TSP heuristic for large instances"],"prefix":"10.1007","volume":"20","author":[{"given":"Gerold","family":"J\u00e4ger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Changxing","family":"Dong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boris","family":"Goldengorin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paul","family":"Molitor","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dirk","family":"Richter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,12,3]]},"reference":[{"key":"9233_CR1","volume-title":"The Traveling Salesman Problem: A Computational Study","author":"DL Applegate","year":"2006","unstructured":"Applegate, D.L., Bixby, R.E., Chv\u00e1tal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study. Princeton University Press, Princeton (2006)"},{"issue":"1","key":"9233_CR2","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1016\/j.orl.2008.09.006","volume":"37","author":"DL Applegate","year":"2009","unstructured":"Applegate, D.L., Bixby, R.E., Chv\u00e1tal, V., Cook, W.J., Espinoza, D., Goycoolea, M., Helsgaun, K.: Certification of an optimal tour through 85900 cities. Oper. Res. Lett. 37(1), 11\u201315 (2009)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"9233_CR3","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1287\/ijoc.15.1.82.15157","volume":"15","author":"D Applegate","year":"2003","unstructured":"Applegate, D., Cook, W., Rohe, A.: Chained Lin-Kernighan for large traveling salesman problems. INFORMS J. Comput. 15(1), 82\u201392 (2003)","journal-title":"INFORMS J. Comput."},{"key":"9233_CR4","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1287\/ijoc.13.1.56.9748","volume":"13","author":"E Balas","year":"2001","unstructured":"Balas, E., Simonetti, N.: Linear time dynamic programming algorithms for new classes of restricted TSPs: a computational study. INFORMS J. Comput. 13, 56\u201375 (2001)","journal-title":"INFORMS J. Comput."},{"key":"9233_CR5","first-page":"397","volume-title":"Computational Science and Its Applications-ICCSA, Lecture Notes in Computer Science","author":"H Bekker","year":"2005","unstructured":"Bekker, H., Braad, E.P., Goldengorin, B., et al.: Using bipartite and multidimensional matching to select the roots of a system of polynomial equation. In: Gervasi, O. (ed.) Computational Science and Its Applications-ICCSA, Lecture Notes in Computer Science, pp. 397\u2013406. Springer, Berlin (2005)"},{"key":"9233_CR6","unstructured":"Climer, S., Zhang, W.: Searching for Backbones and Fat: A Limit-Crossing Approach with Applications. Proceedings of the 18th National Conference on Artificial Intelligence (AAAI), pp. 707\u2013712. AAAI Press, Menlo Park (2002)."},{"key":"9233_CR7","doi-asserted-by":"crossref","DOI":"10.1515\/9781400841103","volume-title":"In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation","author":"W Cook","year":"2011","unstructured":"Cook, W.: In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation. Princeton University Press, Princeton (2011)"},{"issue":"3","key":"9233_CR8","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/ijoc.15.3.233.16078","volume":"15","author":"W Cook","year":"2003","unstructured":"Cook, W., Seymour, P.: Tour merging via branch-decomposition. INFORMS J. Comput. 15(3), 233\u2013248 (2003)","journal-title":"INFORMS J. Comput."},{"key":"9233_CR9","first-page":"119","volume-title":"AAIM 2010, Lecture Notes in Computer Science","author":"C Ernst","year":"2010","unstructured":"Ernst, C., Dong, C., J\u00e4ger, G., Molitor, P., Richter, D.: Finding good tours for huge Euclidean TSP instances by iterative backbone contraction. In: Chen, B. (ed.) AAIM 2010, Lecture Notes in Computer Science, pp. 119\u2013130. Springer, Berlin (2010)"},{"key":"9233_CR10","first-page":"72","volume-title":"EvoCOP 2007, Lecture Notes in Computer Science","author":"T Fischer","year":"2007","unstructured":"Fischer, T., Merz, P.: Reducing the size of traveling salesman problem instances by fixing edges. EvoCOP 2007, Lecture Notes in Computer Science, pp. 72\u201383. Springer, Berlin (2007)"},{"issue":"1","key":"9233_CR11","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1016\/j.ejor.2004.04.023","volume":"160","author":"D Gamboa","year":"2005","unstructured":"Gamboa, D., Rego, C., Glover, F.: Data structures and ejection chains for solving large scale traveling salesman problems. Eur. J. Oper. Res. 160(1), 154\u2013171 (2005)","journal-title":"Eur. J. Oper. Res."},{"issue":"4","key":"9233_CR12","doi-asserted-by":"crossref","first-page":"1154","DOI":"10.1016\/j.cor.2005.06.014","volume":"33","author":"D Gamboa","year":"2006","unstructured":"Gamboa, D., Rego, C., Glover, F.: Implementation analysis of efficient heuristic algorithms for the traveling salesman problem. Comput. Oper. Res. 33(4), 1154\u20131172 (2006)","journal-title":"Comput. Oper. Res."},{"key":"9233_CR13","volume-title":"Computers and Intractability: A Guide to the Theory of $${\\cal NP}$$ NP","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of $${\\cal NP}$$ NP -Completeness. Series of Books in the Mathematical Sciences. W.H. Freeman and Company, San Francisco (1979)"},{"issue":"2","key":"9233_CR14","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/j.cor.2011.04.003","volume":"39","author":"R Germs","year":"2012","unstructured":"Germs, R., Goldengorin, B., Turkensteen, M.: Lower tolerance-based branch and bound algorithms for the ATSP. Comput. Oper. Res. 39(2), 291\u2013298 (2012)","journal-title":"Comput. Oper. Res."},{"key":"9233_CR15","first-page":"194","volume-title":"AAIM 2006, Lecture Notes in Computer Science","author":"B Goldengorin","year":"2006","unstructured":"Goldengorin, B., J\u00e4ger, G., Molitor, P.: Some Basics on tolerances. In: Cheng, S.-W., Poon, C.K. (eds.) AAIM 2006, Lecture Notes in Computer Science, pp. 194\u2013206. Springer, Berlin (2006a)"},{"issue":"9","key":"9233_CR16","doi-asserted-by":"crossref","first-page":"716","DOI":"10.3844\/jcssp.2006.716.734","volume":"2","author":"B Goldengorin","year":"2006","unstructured":"Goldengorin, B., J\u00e4ger, G., Molitor, P.: Tolerances applied in combinatorial optimization. J. Comput. Sci. 2(9), 716\u2013734 (2006b)","journal-title":"J. Comput. Sci."},{"key":"9233_CR17","volume-title":"The Traveling Salesman Problem and Its Variations","year":"2002","unstructured":"Gutin, G., Punnen, A.P. (eds.): The Traveling Salesman Problem and Its Variations. Kluwer, Dordrecht (2002)"},{"issue":"1","key":"9233_CR18","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1016\/S0377-2217(99)00284-2","volume":"126","author":"K Helsgaun","year":"2000","unstructured":"Helsgaun, K.: An effective implementation of the Lin-Kernighan traveling salesman heuristic. Eur. J. Oper. Res. 126(1), 106\u2013130 (2000)","journal-title":"Eur. J. Oper. Res."},{"issue":"2\u20133","key":"9233_CR19","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1007\/s12532-009-0004-6","volume":"1","author":"K Helsgaun","year":"2009","unstructured":"Helsgaun, K.: General $$k$$ k -opt submoves for the Lin-Kernighan TSP heuristic. Math. Program. Comput. 1(2\u20133), 119\u2013163 (2009)","journal-title":"Math. Program. Comput."},{"key":"9233_CR20","first-page":"215","volume-title":"Local Search in Combinatorial Optimization","author":"D Johnson","year":"1997","unstructured":"Johnson, D., McGeoch, L.: The traveling salesman problem: a case study in local optimization. In: Aarts, E., Lenstra, J.K. (eds.) Local Search in Combinatorial Optimization, pp. 215\u2013310. Wiley, Chicester (1997)"},{"key":"9233_CR21","unstructured":"Kilby, P., Slaney, J.K., Walsh, T.: The backbone of the travelling salesperson. In: Kaelbling, L.P., Saffiotti A. (Eds.): Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI-05), pp. 175\u2013180, 2005."},{"key":"9233_CR22","volume-title":"The traveling salesman problem\u2014a guided tour of combinatorial optimization","year":"1985","unstructured":"Lawler, E.L., Lenstra, J.K., Rinnooy-Kan, A.H.G., Shmoys, D.B. (eds.): The traveling salesman problem\u2014a guided tour of combinatorial optimization. Wiley, Chicester (1985)"},{"key":"9233_CR23","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1287\/opre.21.2.498","volume":"21","author":"S Lin","year":"1973","unstructured":"Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the traveling salesman problem. Oper. Res. 21, 498\u2013516 (1973)","journal-title":"Oper. Res."},{"issue":"3","key":"9233_CR24","first-page":"299","volume":"5","author":"O Martin","year":"1991","unstructured":"Martin, O., Otto, S.W., Felten, E.W.: Large-step Markov chains for the traveling salesman problem. Complex Syst. 5(3), 299\u2013326 (1991)","journal-title":"Complex Syst."},{"key":"9233_CR25","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/0167-6377(92)90028-2","volume":"11","author":"O Martin","year":"1992","unstructured":"Martin, O., Otto, S.W., Felten, E.W.: Large-step Markov chains for the TSP incorporating local search heuristics. Oper. Res. Lett. 11, 219\u2013224 (1992)","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"9233_CR26","doi-asserted-by":"crossref","first-page":"4667","DOI":"10.1103\/PhysRevE.59.4667","volume":"59","author":"A M\u00f6bius","year":"1999","unstructured":"M\u00f6bius, A., Freisleben, B., Merz, P., Schreiber, M.: Combinatorial optimization by iterative partial transcription. Phys. Rev. E 59(4), 4667\u20134674 (1999)","journal-title":"Phys. Rev. E"},{"key":"9233_CR27","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1038\/22055","volume":"400","author":"R Monasson","year":"1998","unstructured":"Monasson, R., Zecchina, R., Kirkpatrick, S., Selman, B., Troyanski, L.: Determining computational complexity for characteristic phase transitions. Nature 400, 133\u2013137 (1998)","journal-title":"Nature"},{"key":"9233_CR28","unstructured":"Richter, D.: Toleranzen in Helsgauns Lin-Kernighan-Heuristik f\u00fcr das TSP. Diploma Thesis, University of Halle-Wittenberg, Germany (2006)"},{"key":"9233_CR29","first-page":"99","volume-title":"CAAN 2007, Lecture Notes in Computer Science","author":"D Richter","year":"2007","unstructured":"Richter, D., Goldengorin, B., J\u00e4ger, G., Molitor, P.: Improving the efficiency of Helsgaun\u2019s Lin-Kernighan heuristic for the symmetric TSP. In: Janssen, J., Pralat, P. (eds.) CAAN 2007, Lecture Notes in Computer Science, pp. 99\u2013111. Springer, Berlin (2007)"},{"key":"9233_CR30","unstructured":"Schilham, R.M.F.: Commonalities in Local Search. Ph.D. Thesis, Technische Universiteit Eindhoven, The Netherlands (2001)"},{"key":"9233_CR31","unstructured":"Slaney, J.K., Walsh, T.: The backbones in optimization and approximation. Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI-01), pp. 254\u2013259. Kaufmann Publishers, San Francisco (2001)"},{"key":"9233_CR32","unstructured":"Tamaki, H.: Alternating cycles contribution: a tour merging strategy for the traveling salesman problem. Research Report MPI-I-2003-1-007, Max-Planck-Institut f\u00fcr Informatik, Saarbr\u00fccken, Germany (2003)"},{"issue":"3","key":"9233_CR33","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1016\/j.ejor.2006.10.062","volume":"189","author":"M Turkensteen","year":"2008","unstructured":"Turkensteen, M., Ghosh, D., Goldengorin, B., Sierksma, G.: Tolerance-based branch and bound algorithms for the ATSP. Eur. J. Oper. Res. 189(3), 775\u2013788 (2008)","journal-title":"Eur. J. Oper. Res."},{"issue":"5","key":"9233_CR34","doi-asserted-by":"crossref","first-page":"862","DOI":"10.1287\/opre.50.5.862.373","volume":"50","author":"C Walshaw","year":"2002","unstructured":"Walshaw, C.: A multilevel approach to the traveling salesman problem. Oper. Res. 50(5), 862\u2013877 (2002)","journal-title":"Oper. Res."},{"key":"9233_CR35","unstructured":"Zhang, W., Looks, M.: A novel local search Algorithm for the traveling salesman problem that exploits backbones. In Kaelbling, L.P., Saffiotti, A. (eds.) Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI-05), pp. 343\u2013350 (2005)"}],"container-title":["Journal of Heuristics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-013-9233-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10732-013-9233-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10732-013-9233-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,4]],"date-time":"2019-08-04T09:34:49Z","timestamp":1564911289000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10732-013-9233-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12,3]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,2]]}},"alternative-id":["9233"],"URL":"https:\/\/doi.org\/10.1007\/s10732-013-9233-y","relation":{},"ISSN":["1381-1231","1572-9397"],"issn-type":[{"value":"1381-1231","type":"print"},{"value":"1572-9397","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,12,3]]}}}