1995 Volume 10 Issue 3 Pages 464-467
Given two tours of n cities, a pair of subtours of these tours consisting of the same set of cities is called a common subtour. The operation of subtour exchange crossover used in the genetic algorithm of Yamamura, et al. [山村92] is based on such common subtours. In this note, we present an O(n^2) time algorithm to enumerate all common subtours, and show that the expected number of common subtours for two random tours is at most 4+o(1).