{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,23]],"date-time":"2025-12-23T10:00:09Z","timestamp":1766484009262},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540425601"},{"type":"electronic","value":"9783540448082"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44808-x_3","type":"book-chapter","created":{"date-parts":[[2007,5,3]],"date-time":"2007-05-03T20:32:08Z","timestamp":1178224328000},"page":"32-59","source":"Crossref","is-referenced-by-count":63,"title":["The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests"],"prefix":"10.1007","author":[{"given":"Jill","family":"Cirasella","sequence":"first","affiliation":[]},{"given":"David S.","family":"Johnson","sequence":"additional","affiliation":[]},{"given":"Lyle A.","family":"McGeoch","sequence":"additional","affiliation":[]},{"given":"Weixiong","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,9,11]]},"reference":[{"key":"3_CR1","first-page":"645","volume":"ICM III","author":"D. Applegate","year":"1998","unstructured":"D. Applegate, R. Bixby, V. Chvatal, and W. Cook. On the solution of traveling salesman problems. Doc. Mathemat-ica J. der Deutschen Mathematiker-Vereinigung, ICM III:645\u2013656, 1998. The Concorde code is available from the website http:\/\/www.keck.caam.rice.edu\/concorde.html","journal-title":"Doc. Mathemat-ica J. der Deutschen Mathematiker-Vereinigung"},{"key":"3_CR2","unstructured":"D. Applegate, W. Cook, and A. Rohe. Chained Lin-Kernighan for large traveling salesman problems. To appear. A postscript draft is currently available from the website http:\/\/www.caam.rice.edu\/~bico\/"},{"issue":"4","key":"3_CR3","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1145\/212066.212081","volume":"21","author":"G. Carpaneto","year":"1995","unstructured":"G. Carpaneto, M. Dell\u2019Amico, and P. Toth. Exact solution of large-scale, asymmetric traveling salesman problems. ACM Trans. Mathematical Software, 21(4):394\u2013409, 1995.","journal-title":"ACM Trans. Mathematical Software"},{"key":"3_CR4","doi-asserted-by":"crossref","first-page":"736","DOI":"10.1287\/mnsc.26.7.736","volume":"26","author":"G. Carpaneto","year":"1980","unstructured":"G. Carpaneto and P. Toth. Some new branching and bounding criteria for the asymmetric traveling salesman problem. Management Science, 26:736\u2013743, 1980.","journal-title":"Management Science"},{"key":"3_CR5","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1002\/net.3230120103","volume":"12","author":"A. M. Frieze","year":"1982","unstructured":"A. M. Frieze, G. Galbiati, and F. Maffioli. On the worst-case performance of some algorithms for the asymmetric traveling salesman problem. Networks, 12:23\u201339, 1982.","journal-title":"Networks"},{"key":"3_CR6","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/BF01585701","volume":"53","author":"M. Fischetti","year":"1992","unstructured":"M. Fischetti and P. Toth. An additive bounding procedure for the asymmetric travelling salesman problem. Math. Programming A, 53:173\u2013197, 1992.","journal-title":"Math. Programming A"},{"key":"3_CR7","doi-asserted-by":"crossref","first-page":"1520","DOI":"10.1287\/mnsc.43.11.1520","volume":"43","author":"M. Fischetti","year":"1997","unstructured":"M. Fischetti and P. Toth. A polyhedral approach to the asymmetric traveling salesman problem. Management Sci., 43:1520\u20131536, 1997.","journal-title":"Management Sci."},{"key":"3_CR8","doi-asserted-by":"publisher","first-page":"846","DOI":"10.1287\/opre.42.5.846","volume":"42","author":"M. Fischetti","year":"1994","unstructured":"M. Fischetti, P. Toth, and D. Vigo. A branch and bound algorithm for the capacitated vehicle routing problem on directed graphs. Operations Res., 42:846\u2013859, 1994.","journal-title":"Operations Res."},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"F. Glover, G. Gutin, A. Yeo, and A. Zverovich. Construction heuristics for the asymmetric TSP. European J. Operations Research. to appear.","DOI":"10.1016\/S0377-2217(99)00468-3"},{"key":"3_CR10","unstructured":"R. Giancarlo. Personal communication, September 2000."},{"issue":"2","key":"3_CR11","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/BF00247211","volume":"2","author":"F. Glover","year":"1996","unstructured":"F. Glover. Finding a best traveling salesman 4-opt move in the same time as a best 2-opt move. J. Heuristics, 2(2):169\u2013179, 1996.","journal-title":"J. Heuristics"},{"key":"3_CR12","unstructured":"G. Gutin and A. Zverovich. Evaluation of the contract-or-patch heuristic for the asymmetric TSP. Manuscript, 2000."},{"key":"3_CR13","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. The traveling salesman problem and minimum spanning trees. Operations Res., 18:1138\u20131162, 1970.","journal-title":"Operations Res."},{"key":"3_CR14","doi-asserted-by":"publisher","first-page":"6","DOI":"10.1007\/BF01584070","volume":"1","author":"M. Held","year":"1971","unstructured":"M. Held and R. M. Karp. The traveling salesman problem and minimum spanning trees: Part II. Math. Prog., 1:6\u201325, 1971.","journal-title":"Math. Prog."},{"key":"3_CR15","unstructured":"D. S. Johnson, J. L. Bentley, L. A. McGeoch, and E. E. Rothberg. Near-Optimal Solutions to Very Large Traveling Salesman Problems. Monograph, to appear."},{"key":"3_CR16","first-page":"215","volume-title":"Local Search in Combinatorial Optimization","author":"D. S. Johnson","year":"1997","unstructured":"D. S. Johnson and L. A. McGeoch. The traveling salesman problem: A case study in local optimization. In E. H. L. Aarts and J. K. Lenstra, editors, Local Search in Combinatorial Optimization, pages 215\u2013310. John Wiley and Sons, Ltd., Chichester, 1997."},{"key":"3_CR17","first-page":"341","volume-title":"Proc. 7th Ann. ACM-SIAM Symp. on Discrete Algorithms","author":"D. S. Johnson","year":"1996","unstructured":"D. S. Johnson, L. A. McGeoch, and E. E. Rothberg. Asymptotic experimental analysis for the Held-Karp traveling salesman bound. In Proc. 7th Ann. ACM-SIAM Symp. on Discrete Algorithms, pages 341\u2013350. Society for Industrial and Applied Mathematics, Philadelphia, 1996."},{"issue":"4","key":"3_CR18","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1137\/0208045","volume":"8","author":"R. M. Karp","year":"1979","unstructured":"R. M. Karp. A patching algorithm for the nonsymmetric traveling-salesman problem. SI AM J. Comput., 8(4):561\u2013573, 1979.","journal-title":"SI AM J. Comput."},{"key":"3_CR19","first-page":"171","volume-title":"The Art of Computer Programming, Volume 2: Seminumer-ical Algorithms","author":"D. E. Knuth","year":"1981","unstructured":"D. E. Knuth. The Art of Computer Programming, Volume 2: Seminumer-ical Algorithms (2nd Edition). Addison-Wesley, Reading, MA, 1981. See pages 171\u2013172.","edition":"2nd Edition"},{"issue":"5","key":"3_CR20","doi-asserted-by":"crossref","first-page":"1066","DOI":"10.1287\/opre.28.5.1086","volume":"28","author":"P. C. Kanellakis","year":"1980","unstructured":"P. C. Kanellakis and C. H. Papadimitriou. Local search for the asymmetric traveling salesman problem. Oper. Res., 28(5):1066\u20131099, 1980.","journal-title":"Oper. Res."},{"key":"3_CR21","first-page":"181","volume-title":"The Traveling Salesman Problem","author":"R. M. Karp","year":"1985","unstructured":"R. M. Karp and J. M. Steele. Probabilistic analysis of heuristics. In E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B Shmoys, editors, The Traveling Salesman Problem, pages 181\u2013205. John Wiley and Sons, Chichester, 1985."},{"key":"3_CR22","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. An effective heuristic algorithm for the traveling salesman problem. Operations Res., 21:498\u2013516, 1973.","journal-title":"Operations Res."},{"key":"3_CR23","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0167-6377(92)90028-2","volume":"11","author":"O. Martin","year":"1992","unstructured":"O. Martin, S. W. Otto, and E. W. Felten. Large-step Markov chains for the TSP incorporating local search heuristics. Operations Res. Lett., 11:219\u2013224, 1992.","journal-title":"Operations Res. Lett."},{"key":"3_CR24","doi-asserted-by":"crossref","unstructured":"D. L. Miller and J. F. Pekny. Exact solution of large asymmetric traveling salesman problems. Science, 251:754\u2013761, 15 September 1996.","DOI":"10.1126\/science.251.4995.754"},{"issue":"4","key":"3_CR25","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1287\/ijoc.3.4.376","volume":"3","author":"G. Reinelt","year":"1991","unstructured":"G. Reinelt. TSPLIB-A traveling salesman problem library. ORSA J. Comput., 3(4):376\u2013384, 1991. The TSPLIB website is http:\/\/www.iwr.uni-heidelberg.de\/iwr\/comopt\/software\/TSPLIB95\/ .","journal-title":"ORSA J. Comput."},{"key":"3_CR26","series-title":"Lect Notes Comput Sci","volume-title":"The Traveling Salesman: Computational Solutions of TSP Applications","author":"G. Reinelt","year":"1994","unstructured":"G. Reinelt. The Traveling Salesman: Computational Solutions of TSP Applications. LNCS 840. Springer-Verlag, Berlin, 1994."},{"key":"3_CR27","unstructured":"B. W. Repetto. Upper and Lower Bounding Procedures for the Asymmetric Traveling Salesman Problem. PhD thesis, Graduate School of Industrial Administration, Carnegie-Mellon University, 1994."},{"key":"3_CR28","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1007\/3-540-61310-2_24","volume-title":"Integer Programming and Combinatorial Optimization: Proc. 5th Int. IPCO Conference","author":"N. Simonetti","year":"1996","unstructured":"N. Simonetti and E. Balas. Implementation of a linear time algorithm for certain generalized traveling salesman problems. In Integer Programming and Combinatorial Optimization: Proc. 5th Int. IPCO Conference, LNCS 840, pages 316\u2013329, Berlin, 1996. Springer-Verlag."},{"key":"3_CR29","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1016\/0167-6377(92)90068-E","volume":"12","author":"D. Williamson","year":"1992","unstructured":"D. Williamson. Analysis of the Held-Karp lower bound for the asymmetric TSP. Operations Res. Lett., 12:83\u201388, 1992.","journal-title":"Operations Res. Lett."},{"key":"3_CR30","doi-asserted-by":"crossref","unstructured":"Young, D. S. Johnson, D. R. Karger, and M. D. Smith. Near-optimal intraprocedural branch alignment. In Proceedings 1997 Symp. on Programming Languages, Design, and Implementation, pages 183\u2013193. ACM, 1997.","DOI":"10.1145\/258916.258932"},{"key":"3_CR31","unstructured":"W. Zhang. Truncated branch-and-bound: A case study on the asymmetric TSP. In Proc. of AAAI 1993 Spring Symposium on AI and NP-Hard Problems, pages 160\u2013166, Stanford, CA, 1993."},{"key":"3_CR32","unstructured":"W. Zhang. Depth-first branch-and-bound versus local search: A case study. In Proc. 17th National Conf. on Artificial Intelligence (AAAI-2000), pages 930\u2013935, Austin, TX, 2000."}],"container-title":["Lecture Notes in Computer Science","Algorithm Engineering and Experimentation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44808-X_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,27]],"date-time":"2019-04-27T14:17:00Z","timestamp":1556374620000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44808-X_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540425601","9783540448082"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/3-540-44808-x_3","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}