A Simulated Annealing with Hill Climbing Algorithm for the Traveling Tournament Problem

Publication Type

Journal Article

Publication Date

2006

Abstract

The Traveling Tournament Problem (TTP) [E. Easton, G. Nemhauser, M. Trick, The traveling tournament problem description and benchmarks, in: Proceedings of the 7th International Conference on Principles and Practice of Constraint Programming, CP 2001, 2001, pp. 580–584; M. Trick, Challenge Traveling Tournament Problems, 2004] schedules a double round-robin tournament to minimize the total distance traveled by competing teams. It involves issues of feasibility and optimality and is a challenge to constraint and integer programming. In this work, we divide the search space and use simulated annealing (SA) to search a timetable space and hill-climbing to explore a team assignment space. The SA component mutates timetables using conditional local jumps to find timetables which lead to better schedules while hill-climbing is enhanced by pre-computation and dynamic cost updating to provide fast and efficient search. Computational experiments using this hybrid approach on benchmark sets give results comparable to or better than current best known solutions.

Keywords

Tournament, Scheduling, Heuristics

Discipline

Operations and Supply Chain Management

Research Areas

Operations Management

Publication

European Journal of Operational Research

Volume

174

Issue

3

First Page

1459

Last Page

1478

ISSN

0377-2217

Identifier

10.1016/j.ejor.2005.02.065

Publisher

Elsevier

Additional URL

https://doi.org/10.1016/j.ejor.2005.02.065

Link to Full Text

Share

COinS