{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T16:45:46Z","timestamp":1781109946291,"version":"3.54.1"},"reference-count":64,"publisher":"IGI Global Scientific Publishing","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,7]]},"abstract":"<jats:p>In this article, the new crossover operator BBX for Evolutionary Algorithms (EAs) for traveling salesman problems (TSPs) is introduced. It uses branch-and-bound to find the optimal combination of the (directed) edges present in the parent solutions. The offspring solutions created are at least as good as their parents and are only composed of parental building blocks. The operator is closer to the ideal concept of crossover in EAs than existing operators. This article provides the most extensive study on crossover operators on the TSP, comparing BBX to ten other operators on the 110 instances of the TSPLib benchmark set in EAs with four different population sizes. BBX, with its better ability to reuse and combine building blocks, surprisingly does not generally outperform the other operators. However, it performs well in certain scenarios. Besides presenting a novel approach to crossover on the TSP, the study significantly extends and refines the body of knowledge on the field with new conclusions and comparison results.<\/jats:p>","DOI":"10.4018\/ijcini.2019070101","type":"journal-article","created":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T11:52:45Z","timestamp":1559821965000},"page":"1-18","source":"Crossref","is-referenced-by-count":2,"title":["A Branch-and-Bound-Based Crossover Operator for the Traveling Salesman Problem"],"prefix":"10.4018","volume":"13","author":[{"given":"Thomas","family":"Weise","sequence":"first","affiliation":[{"name":"Institute of Applied Optimization, Hefei, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yan","family":"Jiang","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Qi","family":"Qi","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China, Hefei, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Weichen","family":"Liu","sequence":"additional","affiliation":[{"name":"University of Science and Technology of China, Hefei, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"2432","reference":[{"key":"IJCINI.2019070101-0","doi-asserted-by":"publisher","DOI":"10.1287\/opre.45.2.226"},{"key":"IJCINI.2019070101-1","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(99)00067-2"},{"key":"IJCINI.2019070101-2","first-page":"21","article-title":"On the history of combinatorial optimization (till 1960).","volume":"12","author":"S.Alexander","year":"2005","journal-title":"Handbooks in Operations Research and Management Science: Discrete Optimization"},{"key":"IJCINI.2019070101-3","author":"D. L.Applegate","year":"2007","journal-title":"The traveling salesman problem: A computational study"},{"key":"IJCINI.2019070101-4","doi-asserted-by":"publisher","DOI":"10.1007\/BF00203625"},{"key":"IJCINI.2019070101-5","doi-asserted-by":"publisher","DOI":"10.1287\/opre.19.2.278"},{"key":"IJCINI.2019070101-6","author":"N.Biggs","year":"1976","journal-title":"Graph theory, 1736-1936"},{"key":"IJCINI.2019070101-7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78295-7"},{"key":"IJCINI.2019070101-8","unstructured":"Bock, F. (1958). An algorithm for solving \u201ctraveling-salesman\u201d and related network optimization problems. Presented at the 14th ORSA National Meeting."},{"key":"IJCINI.2019070101-9","unstructured":"Boddy, M. S., & Dean, T. L. (1989, February). Solving time-dependent planning problems. Brown University, Providence, RI. Department of Computer Science. Retrieved from ftp:\/\/ftp.cs.brown.edu\/pub\/techreports\/89\/cs89-03.pdf"},{"key":"IJCINI.2019070101-10","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.26.7.736"},{"key":"IJCINI.2019070101-11","unstructured":"Cook, W. J. (2003, December). Results of Concorde for TSPLib benchmark. Atlanta, GA, USA: Georgia Institute of Technology, H. Milton Stewart School of Industrial and Systems Engineering. Retrieved from http:\/\/www.tsp.gatech.edu\/concorde\/benchmarks\/bench99"},{"key":"IJCINI.2019070101-12","doi-asserted-by":"crossref","unstructured":"Cotta, C., & Troya, J. M. (2003, March). Embedding branch and bound within evolutionary algorithms. Applied Intelligence, 18(2), 137\u2013153. Retrieved from http:\/\/atarazanas.sci.uma.es\/docs\/articulos\/16644025.doi:10.1023\/A:1021934325079","DOI":"10.1023\/A:1021934325079"},{"key":"IJCINI.2019070101-13","doi-asserted-by":"publisher","DOI":"10.1287\/opre.6.6.791"},{"key":"IJCINI.2019070101-14","first-page":"162","article-title":"Applying adaptive algorithms to epistatic domains.","volume":"Vol. 1","author":"L.Davis","year":"1985","journal-title":"Proceedings of the 9th international joint conference on artificial intelligence (IJCAI\u201985)"},{"key":"IJCINI.2019070101-15","doi-asserted-by":"publisher","DOI":"10.1287\/opre.4.1.61"},{"key":"IJCINI.2019070101-16","doi-asserted-by":"publisher","DOI":"10.1007\/BF00202901"},{"key":"IJCINI.2019070101-17","author":"D. E.Goldberg","year":"1989","journal-title":"Genetic algorithms in search, optimization, and machine learning"},{"key":"IJCINI.2019070101-18","first-page":"154","article-title":"Alleles, loci and the TSP.","author":"D. E.Goldberg","year":"1985","journal-title":"Proceedings of the 1st international conference on genetic algorithms and their applications (ICGA\u201985)"},{"key":"IJCINI.2019070101-19","first-page":"42","article-title":"Incorporating problem specific knowledge into genetic algorithms","author":"J. J.Grefenstette","year":"1987","journal-title":"Genetic algorithms and simulated annealing"},{"key":"IJCINI.2019070101-20","doi-asserted-by":"publisher","DOI":"10.1007\/BF01415960"},{"key":"IJCINI.2019070101-21","doi-asserted-by":"publisher","DOI":"10.1007\/b101971"},{"key":"IJCINI.2019070101-22","unstructured":"Hansen, N., Auger, A., Finck, S., & Ros, R. (2012, March 24). Real-parameter black-box optimization benchmarking: Experimental setup. Orsay, France: Universit\u00e9 Paris Sud, INRIA Futurs, \u00c9sssquipe TAO."},{"key":"IJCINI.2019070101-23","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-009-0004-6"},{"key":"IJCINI.2019070101-24","author":"J. H.Holland","year":"1975","journal-title":"Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence"},{"key":"IJCINI.2019070101-25","first-page":"238","article-title":"Evaluating Las Vegas algorithms \u2013 pitfalls and remedies.","author":"H. H.Hoos","year":"1998","journal-title":"Proceedings of the 14th conference on uncertainty in artificial intelligence (UAI\u201998)"},{"key":"IJCINI.2019070101-26","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(00)00139-9"},{"key":"IJCINI.2019070101-27","doi-asserted-by":"publisher","DOI":"10.1137\/0208045"},{"key":"IJCINI.2019070101-28","first-page":"181","article-title":"Probabilistic analysis of heuristics","author":"R. M.Karp","year":"1985","journal-title":"The traveling salesman problem: A guided tour of combinatorial optimization"},{"key":"IJCINI.2019070101-29","doi-asserted-by":"publisher","DOI":"10.1023\/A:1006529012972"},{"key":"IJCINI.2019070101-30","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018553211613"},{"key":"IJCINI.2019070101-31","author":"E. L. G.Lawler","year":"1985","journal-title":"The traveling salesman problem: A guided tour of combinatorial optimization"},{"key":"IJCINI.2019070101-32","doi-asserted-by":"publisher","DOI":"10.2307\/3008306"},{"key":"IJCINI.2019070101-33","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1965.tb04146.x"},{"key":"IJCINI.2019070101-34","unstructured":"Little, J. D. C., Murty, K. G., Sweeny, D. W., & Karel, C. (1963, March). An algorithm for the traveling salesman problem. Cambridge, MA: Massachusetts Institute of Technology (MIT), Sloan School of Management. Retrieved from http:\/\/dspace.mit.edu\/bitstream\/handle\/1721.1\/46828\/algorithmfortrav00litt"},{"key":"IJCINI.2019070101-35","doi-asserted-by":"publisher","DOI":"10.1166\/jctn.2016.5189"},{"key":"IJCINI.2019070101-36","author":"S.Martello","year":"2011","journal-title":"Surveys in combinatorial optimization"},{"issue":"4","key":"IJCINI.2019070101-37","first-page":"297","article-title":"Memetic algorithms for the traveling salesman problem.","volume":"13","author":"P.Merz","year":"2001","journal-title":"Complex Systems"},{"key":"IJCINI.2019070101-38","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03315-9"},{"key":"IJCINI.2019070101-39","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.59.4667"},{"key":"IJCINI.2019070101-40","first-page":"157","article-title":"Memetic algorithms","author":"P.Moscato","year":"2002","journal-title":"Handbook of applied optimization"},{"key":"IJCINI.2019070101-41","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(88)90098-1"},{"key":"IJCINI.2019070101-42","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1120.0506"},{"key":"IJCINI.2019070101-43","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1977.1674939"},{"key":"IJCINI.2019070101-44","first-page":"224","article-title":"A study of permutation crossover operators on the traveling salesman problem.","author":"I. M.Oliver","year":"1987","journal-title":"Proceedings of the second international conference on genetic algorithms and their applications (ICGA\u201987)"},{"key":"IJCINI.2019070101-45","doi-asserted-by":"publisher","DOI":"10.1109\/CIPLS.2013.6595203"},{"key":"IJCINI.2019070101-46","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.3.4.376"},{"key":"IJCINI.2019070101-47","unstructured":"Reinelt, G. (1995). TSPLIB 95. Universit\u00e4t Heidelberg, Institut f\u00fcr Mathematik, Heidelberg, Germany. Retrieved from http:\/\/comopt.ifi.uni-heidelberg.de\/software\/TSPLIB95\/DOC.PS"},{"key":"IJCINI.2019070101-48","unstructured":"Syswerda, G. (1991, January). Schedule optimization using genetic algorithms. In L. Davis (Ed.), Handbook of genetic algorithms (pp. 332\u2013349). Stamford, CT: Thomson Publishing Group, Inc."},{"key":"IJCINI.2019070101-49","doi-asserted-by":"publisher","DOI":"10.1145\/2576768.2598245"},{"key":"IJCINI.2019070101-50","doi-asserted-by":"crossref","unstructured":"Tompkins, D. A. D., & Hoos, H. H. (2004). Ubcsat: An implementation and experimentation environment for sls algorithms for sat and max-sat. In Revised selected papers from the seventh international conference on theory and applications of satisfiability testing (SAT\u201904), Vancouver, Canada, May 10-13 (pp. 306\u2013320). Springer.","DOI":"10.1007\/11527695_24"},{"key":"IJCINI.2019070101-51","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2011.07.049"},{"key":"IJCINI.2019070101-52","doi-asserted-by":"publisher","DOI":"10.1109\/ICSMC.2009.5346283"},{"key":"IJCINI.2019070101-53","unstructured":"Weise, T. (2009). Global optimization algorithms \u2013 theory and application. it-weise.de. Retrieved from http:\/\/www.it-weise.de\/projects\/book.pdf"},{"key":"IJCINI.2019070101-54","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-012-1274-4"},{"key":"IJCINI.2019070101-55","doi-asserted-by":"publisher","DOI":"10.1109\/MCI.2014.2326101"},{"key":"IJCINI.2019070101-56","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2013.2251885"},{"key":"IJCINI.2019070101-57","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-016-0417-5"},{"key":"IJCINI.2019070101-58","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15844-5"},{"key":"IJCINI.2019070101-59","doi-asserted-by":"publisher","DOI":"10.1145\/1569901.1570026"},{"key":"IJCINI.2019070101-60","unstructured":"Whitley, L. D., Starkweather, T., & Fuquay, D. (1989). Scheduling problems and traveling salesman: The genetic edge recombination operator. In J. D. Schaffer (Ed.), Proceedings of the third international conference on genetic algorithms (ICGA\u201989), Fairfax, VA, June 4-7 (pp. 133-140). San Francisco, CA: Morgan Kaufmann Publishers Inc."},{"key":"IJCINI.2019070101-61","unstructured":"Whitley, L. D., Starkweather, T., & Shaner, D. (1991, January). The travelling salesman and sequence scheduling: Quality solutions using genetic edge recombination. In L. Davis (Ed.), Handbook of genetic algorithms (pp. 350\u2013372). Stamford, CT: Thomson Publishing Group, Inc."},{"key":"IJCINI.2019070101-62","doi-asserted-by":"publisher","DOI":"10.1145\/2908961.2909001"},{"key":"IJCINI.2019070101-63","unstructured":"Zhang, W. (1999). Truncated and anytime depth-first branch and bound: A case study on the asymmetric traveling salesman problem. In W. Zhang & S. K\u00f6nig (Eds.), AAAI spring symposium series: Search techniques for problem solving under uncertainty and incomplete information, Palo Alto, CA, March 22- 24 (pp. 148\u2013155). Palo Alto, CA: AAAI Press."}],"container-title":["International Journal of Cognitive Informatics and Natural Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.igi-global.com\/viewtitle.aspx?TitleId=231497","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,5,6]],"date-time":"2022-05-06T04:03:13Z","timestamp":1651809793000},"score":1,"resource":{"primary":{"URL":"http:\/\/services.igi-global.com\/resolvedoi\/resolve.aspx?doi=10.4018\/IJCINI.2019070101"}},"subtitle":[""],"short-title":[],"issued":{"date-parts":[[2019,7]]},"references-count":64,"journal-issue":{"issue":"3"},"URL":"https:\/\/doi.org\/10.4018\/ijcini.2019070101","relation":{},"ISSN":["1557-3958","1557-3966"],"issn-type":[{"value":"1557-3958","type":"print"},{"value":"1557-3966","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7]]}}}