Final published version
Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - A combined local search and integer programming approach to the traveling tournament problem
AU - Goerigk, Marc
AU - Westphal, Stephan
PY - 2016/4
Y1 - 2016/4
N2 - The traveling tournament problem is a well-known combinatorial optimization problem with direct applications to sport leagues scheduling, that sparked intensive algorithmic research over the last decade. With the Challenge Traveling Tournament Instances as an established benchmark, the most successful approaches to the problem use meta-heuristics like tabu search or simulated annealing, partially heavily parallelized. Integer programming based methods on the other hand are hardly able to tackle larger benchmark instances. In this work we present a hybrid approach that draws on the power of commercial integer programming solvers as well as the speed of local search heuristics. Our proposed method feeds the solution of one algorithm phase to the other one, until no further improvements can be made. The applicability of this method is demonstrated experimentally on the galaxy instance set, resulting in currently best known solutions for most of the considered instances.
AB - The traveling tournament problem is a well-known combinatorial optimization problem with direct applications to sport leagues scheduling, that sparked intensive algorithmic research over the last decade. With the Challenge Traveling Tournament Instances as an established benchmark, the most successful approaches to the problem use meta-heuristics like tabu search or simulated annealing, partially heavily parallelized. Integer programming based methods on the other hand are hardly able to tackle larger benchmark instances. In this work we present a hybrid approach that draws on the power of commercial integer programming solvers as well as the speed of local search heuristics. Our proposed method feeds the solution of one algorithm phase to the other one, until no further improvements can be made. The applicability of this method is demonstrated experimentally on the galaxy instance set, resulting in currently best known solutions for most of the considered instances.
KW - Integer programming
KW - Sports scheduling
KW - Tabu search
KW - Traveling tournament problem
U2 - 10.1007/s10479-014-1586-6
DO - 10.1007/s10479-014-1586-6
M3 - Journal article
AN - SCOPUS:84897346383
VL - 239
SP - 343
EP - 354
JO - Annals of Operations Research
JF - Annals of Operations Research
SN - 0254-5330
IS - 1
ER -