{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T23:28:49Z","timestamp":1780788529281,"version":"3.54.1"},"publisher-location":"Berlin\/Heidelberg","reference-count":49,"publisher":"Springer-Verlag","isbn-type":[{"value":"3540528261","type":"print"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0032050","type":"book-chapter","created":{"date-parts":[[2005,12,11]],"date-time":"2005-12-11T06:05:31Z","timestamp":1134281131000},"page":"446-461","source":"Crossref","is-referenced-by-count":198,"title":["Local optimization and the Traveling Salesman Problem"],"prefix":"10.1007","author":[{"given":"David S.","family":"Johnson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"34_CR1","first-page":"91","volume-title":"Proc. 1st Ann. ACM-SIAM Symp. on Discrete Algorithms","author":"J. L. Bentley","year":"1990","unstructured":"J. L. Bentley, \u201cExperiments on traveling salesman heuristics,\u201d in Proc. 1st Ann. ACM-SIAM Symp. on Discrete Algorithms, SIAM, Philadelphia, PA, 1990, 91\u201399."},{"key":"34_CR2","unstructured":"J. L. Bentley, \u201cFast algorithms for geometric traveling salesman problems,\u201d in preparation."},{"key":"34_CR3","unstructured":"J. L. Bentley, D. S. Johnson, L. A. McGeoch, and E. E. Rothberg, \u201cNear-optimal solutions to very large traveling salesman problems,\u201d in preparation."},{"key":"34_CR4","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/0167-6377(89)90037-0","volume":"8","author":"R. G. Bland","year":"1989","unstructured":"R. G. Bland and D. F. Shallcross, \u201cLarge traveling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computation,\u201d Operations Res. Lett.8 (1989), 125\u2013128.","journal-title":"Operations Res. Lett."},{"key":"34_CR5","doi-asserted-by":"crossref","first-page":"804","DOI":"10.1038\/317804a0","volume":"317","author":"R. M. Brady","year":"1985","unstructured":"R. M. Brady, \u201cOptimization strategies gleaned from biological evolution,\u201d Nature317 (October 31, 1985), 804\u2013806.","journal-title":"Nature"},{"key":"34_CR6","first-page":"205","volume":"8","author":"N. E. Collins","year":"1988","unstructured":"N. E. Collins, R. W. Eglese, and B. L. Golden, \u201cSimulated Annealing: An Annotated Bibliography,\u201d Amer. J. Math. & Mgmt. Sci.8 (1988), 205\u2013307.","journal-title":"Amer. J. Math. & Mgmt. Sci."},{"key":"34_CR7","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/BF00940812","volume":"45","author":"V. Cerny","year":"1985","unstructured":"V. Cerny, \u201cA Thermodynamical Approach to the Travelling Salesman Problem: An Efficient Simulation Algorithm,\u201d J. Optimization Theory and Appl.45 (1985), 41\u201351.","journal-title":"J. Optimization Theory and Appl."},{"key":"34_CR8","volume-title":"\u201cWorst-case analysis of a new heuristic for the travelling salesman problem,\u201d Report No. 388","author":"N. Christofides","year":"1976","unstructured":"N. Christofides, \u201cWorst-case analysis of a new heuristic for the travelling salesman problem,\u201d Report No. 388, GSIA, Carnegie-Mellon University, Pittsburgh, PA, 1976."},{"key":"34_CR9","volume-title":"Threshold Accepting: A general purpose optimization algorithm appearing superior to simulated annealing","author":"G. Dueck","year":"1988","unstructured":"G. Dueck, \u201cThreshold Accepting: A general purpose optimization algorithm appearing superior to simulated annealing,\u201d TR88.10.011, Heidelberg Scientific Center, IBM Germany, 1988."},{"key":"34_CR10","doi-asserted-by":"crossref","first-page":"689","DOI":"10.1038\/326689a0","volume":"326","author":"R. Durbin","year":"1987","unstructured":"R. Durbin and D. Willshaw, \u201cAn analogue approach to the travelling salesman problem using an elastic net method,\u201d Nature326 (April 16, 1987), 689\u2013691.","journal-title":"Nature"},{"key":"34_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey, and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, San Francisco, 1979."},{"key":"34_CR12","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1287\/ijoc.1.3.190","volume":"1","author":"F. Glover","year":"1989","unstructured":"F. Glover, \u201cTabu search \u2014 Part I,\u201d ORSA J. Comput.1 (1989), 190\u2013206.","journal-title":"ORSA J. Comput."},{"key":"34_CR13","unstructured":"M. Gr\u00f6tschel and O. Holland, \u201cSolution of large-scale symmetric travelling salesman problems,\u201d Report No. 73, Institut f\u00fcr Mathematik, Universit\u00e4t Augsburg, 1988."},{"key":"34_CR14","doi-asserted-by":"crossref","first-page":"1138","DOI":"10.1287\/opre.18.6.1138","volume":"18","author":"M. Held","year":"1970","unstructured":"M. Held and R. M. Karp, \u201cThe traveling-salesman problem and minimum spanning trees,\u201d Operations Res.18 (1970), 1138\u20131162.","journal-title":"Operations Res."},{"key":"34_CR15","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1007\/BF01584070","volume":"1","author":"M. Held","year":"1971","unstructured":"M. Held and R. M. Karp, \u201cThe traveling-salesman problem and minimum spanning trees: Part II,\u201d Math. Programming1 (1971), 6\u201325.","journal-title":"Math. Programming"},{"key":"34_CR16","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF00339943","volume":"52","author":"J. J. Hopfield","year":"1985","unstructured":"J. J. Hopfield and D. W. Tank, \u201c'Neural\u2019 computation of decisions in optimization problems,\u201d Biol. Cybern52 (1985), 141\u2013152.","journal-title":"Biol. Cybern"},{"key":"34_CR17","doi-asserted-by":"crossref","first-page":"525","DOI":"10.1038\/330525a0","volume":"330","author":"D. S. Johnson","year":"1987","unstructured":"D. S. Johnson, \u201cMore approaches to the travelling salesman guide,\u201d Nature330 (December 10, 1987), 525.","journal-title":"Nature"},{"key":"34_CR18","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1287\/opre.37.6.865","volume":"37","author":"D. S. Johnson","year":"1989","unstructured":"D. S. Johnson, C. R. Aragon, L. A. McGeoch, and C. Schevon, \u201cOptimization by Simulated Annealing: An Experimental Evaluation, Part I (Graph Partitioning),\u201d Operations Res.37 (1989), 865\u2013892.","journal-title":"Operations Res."},{"key":"34_CR19","unstructured":"D. S. Johnson, C. R. Aragon, L. A. McGeoch, and C. Schevon, \u201cOptimization by Simulated Annealing: An Experimental Evaluation, Part III (The Traveling Salesman Problem),\u201d in preparation."},{"key":"34_CR20","unstructured":"D. S. Johnson, L. A. McGeoch, and G. Ostheimer, \u201cData structures for traveling salesmen,\u201d in preparation."},{"key":"34_CR21","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"D. S. Johnson","year":"1988","unstructured":"D. S. Johnson, C. H. Papadimitriou, and M. Yannakakis, \u201cHow easy is local search?,\u201d J. Comput. System Sci.37 (1988), 79\u2013100.","journal-title":"J. Comput. System Sci."},{"key":"34_CR22","unstructured":"D. S. Johnson and E. E. Rothberg, \u201cAsymptotic experimental analysis of the Held-Karp lower bound for the traveling salesman problem,\u201d in preparation."},{"key":"34_CR23","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1287\/moor.2.3.209","volume":"2","author":"R. M. Karp","year":"1977","unstructured":"R. M. Karp, \u201cProbabilistic analysis of partitioning algorithms for the traveling-salesman in the plane,\u201d Math. Oper. Res.2 (1977), 209\u2013224.","journal-title":"Math. Oper. Res."},{"key":"34_CR24","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/BF01587089","volume":"44","author":"W. Kern","year":"1989","unstructured":"W. Kern, \u201cA probabilistic analysis of the switching algorithm for the Euclidean TSP,\u201d Math. Programming44 (1989), 213\u2013219.","journal-title":"Math. Programming"},{"key":"34_CR25","doi-asserted-by":"crossref","first-page":"976","DOI":"10.1007\/BF01009452","volume":"34","author":"S. Kirkpatrick","year":"1984","unstructured":"S. Kirkpatrick, \u201cOptimization by simulated annealing: Quantitative studies,\u201d J. Stat. Physics34 (1984), 976\u2013986.","journal-title":"J. Stat. Physics"},{"key":"34_CR26","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","volume":"220","author":"S. Kirkpatrick","year":"1983","unstructured":"S. Kirkpatrick, C. D. Gelatt, Jr, and M. P. Vecchi, \u201cOptimization by Simulated Annealing,\u201d Science220 (13 May 1983), 671\u2013680.","journal-title":"Science"},{"key":"34_CR27","doi-asserted-by":"crossref","first-page":"1277","DOI":"10.1051\/jphys:019850046080127700","volume":"46","author":"S. Kirkpatrick","year":"1985","unstructured":"S. Kirkpatrick and G. Toulouse, \u201cConfiguration space and the travelling salesman problem,\u201d J. Physique46 (1985), 1277\u20131292.","journal-title":"J. Physique"},{"key":"34_CR28","unstructured":"B. Korte, \u201cApplications of combinatorial optimization,\u201d talk at the 13th International Mathematical Programming Symposium, Tokyo, 1988."},{"key":"34_CR29","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1209\/0295-5075\/8\/3\/002","volume":"8","author":"W. Krauth","year":"1989","unstructured":"W. Krauth and M. M\u00e9zard, \u201cThe cavity method and the travelling-salesman problem,\u201d Europhys. Lett.8 (1989), 213\u2013218.","journal-title":"Europhys. Lett."},{"key":"34_CR30","unstructured":"J. Lam and J.-M. Delosme, \u201cAn efficient simulated annealing schedule: implementation and evaluation,\u201d manuscript (1988)."},{"key":"34_CR31","volume-title":"The Traveling Salesman Problem","author":"E. L. Lawler","year":"1985","unstructured":"E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, The Traveling Salesman Problem, John Wiley & Sons, Chichester, 1985."},{"key":"34_CR32","doi-asserted-by":"crossref","first-page":"2245","DOI":"10.1002\/j.1538-7305.1965.tb04146.x","volume":"44","author":"S. Lin","year":"1965","unstructured":"S. Lin, \u201cComputer solutions of the traveling salesman problem,\u201d Bell Syst. Tech. J.44 (1965), 2245\u20132269.","journal-title":"Bell Syst. Tech. J."},{"key":"34_CR33","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1287\/opre.21.2.498","volume":"21","author":"S. Lin","year":"1973","unstructured":"S. Lin and B. W. Kernighan, \u201cAn Effective Heuristic Algorithm for the Traveling-Salesman Problem,\u201d Operations Res.21 (1973), 498\u2013516.","journal-title":"Operations Res."},{"key":"34_CR34","doi-asserted-by":"crossref","first-page":"1227","DOI":"10.1145\/2135.2141","volume":"27","author":"J. D. Litke","year":"1984","unstructured":"J. D. Litke, \u201cAn improved solution to the traveling salesman problem with thousands of nodes,\u201d Comm. ACM27 (1984), 1227\u20131236.","journal-title":"Comm. ACM"},{"key":"34_CR35","unstructured":"G. Lueker, manuscript, Princeton University, 1976."},{"key":"34_CR36","unstructured":"O. Martin, S. W. Otto, and E. W. Felten, \u201cLarge-step Markov chains for the traveling salesman problem,\u201d manuscript (1989)."},{"key":"34_CR37","doi-asserted-by":"crossref","first-page":"747","DOI":"10.2307\/1427186","volume":"18","author":"D. Mitra","year":"1986","unstructured":"D. Mitra, F. Romeo, and A. Sangiovanni-Vincentelli, \u201cConvergence and finite-time behavior of simulated annealing,\u201d J. Advan. Appl. Prob.18 (1986), 747\u2013771.","journal-title":"J. Advan. Appl. Prob."},{"key":"34_CR38","unstructured":"H. M\u00fchlenbein, \u201cThe dynamics of evolution and learning \u2014 Towards genetic neural networks,\u201d manuscript (1989)."},{"key":"34_CR39","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/0167-8191(88)90098-1","volume":"7","author":"H. M\u00fchlenbein","year":"1988","unstructured":"H. M\u00fchlenbein, M. Gorges-Schleuter, and O. Kr\u00e4mer, \u201cEvolution algorithms in combinatorial optimization,\u201d Parallel Comput.7 (1988), 65\u201385.","journal-title":"Parallel Comput."},{"key":"34_CR40","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0167-6377(87)90002-2","volume":"6","author":"M. Padberg","year":"1987","unstructured":"M. Padberg and G. Rinaldi, \u201cOptimization of a 532-city symmetric traveling salesman problem by branch and cut,\u201d Operations Res. Lett.6 (1987), 1\u20137.","journal-title":"Operations Res. Lett."},{"key":"34_CR41","volume-title":"\u201cA branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems,\u201d Report R. 247","author":"M. Padberg","year":"1988","unstructured":"M. Padberg and G. Rinaldi, \u201cA branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems,\u201d Report R. 247, Istituto di Analisi dei Sistimi ed Informatica del CNR, Rome, 1988."},{"key":"34_CR42","unstructured":"C. H. Papadimitriou, \u201cThe complexity of the Lin-Kernighan heuristic for the traveling salesman problem,\u201d manuscript (1990)."},{"key":"34_CR43","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1137\/0206005","volume":"6","author":"C. H. Papadimitriou","year":"1977","unstructured":"C. H. Papadimitriou and K. Steiglitz, \u201cOn the complexity of local search for the traveling salesman problem,\u201d SIAM J. Comput.6 (1977), 76\u201383.","journal-title":"SIAM J. Comput."},{"key":"34_CR44","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1287\/opre.26.3.434","volume":"26","author":"C. H. Papadimitriou","year":"1978","unstructured":"C. H. Papadimitriou and K. Steiglitz, \u201cSome examples of difficult traveling salesman problems,\u201d Operations Res.26 (1978), 434\u2013443.","journal-title":"Operations Res."},{"key":"34_CR45","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1145\/76359.76361","volume":"36","author":"L. K. Platzman","year":"1989","unstructured":"L. K. Platzman and J. J. Bartholdi, III, \u201cSpacefilling curves and the planar travelling salesman problem,\u201d J. Assoc. Comput. Mach.36 (1989), 719\u2013737.","journal-title":"J. Assoc. Comput. Mach."},{"key":"34_CR46","doi-asserted-by":"crossref","first-page":"563","DOI":"10.1137\/0206041","volume":"6","author":"D. J. Rosenkrantz","year":"1977","unstructured":"D. J. Rosenkrantz, R. E. Stearns, and P. M. Lewis, II, \u201cAn analysis of several heuristics for the traveling salesman problem,\u201d SIAM J. Comput.6 (1977), 563\u2013581.","journal-title":"SIAM J. Comput."},{"key":"34_CR47","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/321958.321975","volume":"23","author":"S. Sahni","year":"1976","unstructured":"S. Sahni and T. Gonzalez, \u201cP-complete approximation problems,\u201d J. Assoc. Comput. Mach.23 (1976), 555\u2013565.","journal-title":"J. Assoc. Comput. Mach."},{"key":"34_CR48","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1145\/42282.46160","volume":"35","author":"G. H. Sasaki","year":"1988","unstructured":"G. H. Sasaki and B. Hajek, \u201cThe time complexity of maximum matching by simulated annealing,\u201d J. Assoc. Comput. Mach.35 (1988), 387\u2013403.","journal-title":"J. Assoc. Comput. Mach."},{"key":"34_CR49","unstructured":"H. S. Stone, private communication (1989)."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0032050.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,5]],"date-time":"2023-05-05T21:20:08Z","timestamp":1683321608000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0032050"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540528261"],"references-count":49,"URL":"https:\/\/doi.org\/10.1007\/bfb0032050","relation":{},"subject":[]}}