de Carvalho, Ozéas Quevedo, authorWhitley, Darrell, authorACM, publisher2025-09-252025-09-252025-07-13Ozéas Quevedo de Carvalho and Darrell Whitley. 2025. Dramatically Faster Partition Crossover for the Traveling Salesman Problem. In Genetic and Evolutionary Computation Conference (GECCO '25), July 14-18, 2025, Malaga, Spain. ACM, New York, NY, USA, 9 pages. https://doi.org/10.1145/3712256.3726465https://hdl.handle.net/10217/242033The Partition Crossover is a deterministic crossover operator for the Traveling Salesman Problem (TSP). It decomposes the union graph of two TSP solutions, A and B, into connected components known as AB-cycles, from which the lower-cost edges are selected and recombined to produce offspring. The operator finds the best offspring within a search space of 2k solutions in linear time, where k is the number of recombining components. We introduce Generalized Partition Crossover 3 (GPX3), a new implementation of Partition Crossover. GPX3 features a new algorithm to quickly find AB-cycles in the union graph. It also identifies additional recombining AB-cycles, expanding the reachable search space. We show that GPX3 runs in O(n) time and is more efficient and effective than previous implementations of Partition Crossover for the TSP.born digitalarticleseng©Ozéas Quevedo de Carvalho, et al. ACM 2025. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in GECCO '25, https://dx.doi.org/10.1145/3712256.3726465.traveling salesman problemcombinatorial optimizationgenetics algorithmscrossover operatorsTexthttps://doi.org/10.1145/3712256.3726465