Population-Based Simulated Annealing for Traveling Tournaments

Pascal Van Hentenryck, Yannis Vergados

This paper reconsiders the travelling tournament problem, a complex sport-scheduling application which has attracted significant interest recently. It proposes a population-based simulated annealing algorithm with both intensification and diversification. The algorithm is organized as a series of simulated annealing waves, each wave being followed by a macro-intensification. The diversification is obtained through the concept of elite runs that opportunistically survive waves. A parallel implementation of the algorithm on a cluster of workstations exhibits remarkable results. It improves the best known solutions on all considered benchmarks, sometimes reduces the optimality gap by about 60%, and produces novel best solutions on instances that had been stable for several years.

Subjects: 15. Problem Solving; 15.2 Constraint Satisfaction

Submitted: Apr 24, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.