{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,30]],"date-time":"2025-03-30T12:07:22Z","timestamp":1743336442370},"reference-count":18,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":7223,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1987,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A method for accelerating the computational performance of branch exchange heuristics for symmetric traveling salesman problems (TSP's) is presented. The improvement in performance is obtained by considering only exchanges that have a good chance of producing a better solution. In the instance of the 3\u2013optimal heuristic, the approach reduces the number of operations required to obtain a good solution to a TSP with <jats:italic>N<\/jats:italic> nodes from <jats:italic>O(N<jats:sup>3<\/jats:sup>)<\/jats:italic> to <jats:italic>O(N<jats:sup>2<\/jats:sup>)<\/jats:italic>, without a corresponding degradation in the quality of the solution. Most of the results are produced for Euclidean TSP's, but evidence is presented that indicates that thes results apply equally well if not more strongly to the general symmetric TSP.<\/jats:p>","DOI":"10.1002\/net.3230170405","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T22:50:26Z","timestamp":1178923826000},"page":"423-437","source":"Crossref","is-referenced-by-count":12,"title":["Accelerated branch exchange heuristics for symmetric traveling salesman problems"],"prefix":"10.1002","volume":"17","author":[{"suffix":"Jr.","given":"William R.","family":"Stewart","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(84)90004-3"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1969.75"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1969.101"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1972.79"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.6.6.791"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.26.5.495"},{"key":"e_1_2_1_8_2","unstructured":"S.Eilon C.Watson\u2010Gandy andN.Christofides Distribution Management Griffin London (1971)."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.28.3.694"},{"key":"e_1_2_1_10_2","volume-title":"The empirical analysis of TSP heuristics","author":"Golden B.","year":"1985"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/362588.362593"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1965.tb04146.x"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.21.2.498"},{"key":"e_1_2_1_14_2","unstructured":"I.Or Traveling salesman\u2010type combinatorial problems and their relation to the logistics of blood banking. Ph.D. Thesis Department of Industrial Engineering and Management Sciences Northwestern University (1976)."},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(83)90099-1"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.25.3.517"},{"key":"e_1_2_1_17_2","unstructured":"K.SteiglitzandP.Weiner Some improved algorithms for computer solution of the traveling salesman problem. Proc. of the 6th Annual Allerton Conf. on Circuit and Systems Theory (1968)814\u2013821."},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(84)90050-X"},{"key":"e_1_2_1_19_2","unstructured":"C.Tovey Hill climbing with multiple local optima. Siam J. Disc. Alg. Meth. in press."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230170405","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230170405","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,21]],"date-time":"2023-10-21T03:53:56Z","timestamp":1697860436000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230170405"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,1]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1987,1]]}},"alternative-id":["10.1002\/net.3230170405"],"URL":"https:\/\/doi.org\/10.1002\/net.3230170405","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[1987,1]]}}}