A Simulated Annealing Approach to the Travelling Tournament Problem

A Simulated Annealing Approach to the Travelling Tournament Problem

A. Anagnostopoulos, L. Michel, P. Van Hentenryck, and Y. Vergados

Brown University, Box 1910, Providence, RI 02912

Abstract

Automating the scheduling of sport leagues has re­ ceived considerable attention in recent years. This paper considers the traveling tournament problem (TTP) proposed in [8; 4] to abstract the salient features of major league baseball (MLB) in the United States. It proposes a simulated annealing algorithm (TISA) for the TIP that produces sig­ nificant improvements over previous approaches.

Introduction The scheduling of sport leagues has become an important class of combinatorial optimization applications in recent years since they represent significant sources of rev­ enue and generate extremely challenging optimization prob­ lems. This paper considers the travelling tournament problem (TTP) proposed in [4] to abstract the salient features of Ma­ jor League Baseball (MLB) in the United States. The key to the MLB schedule is a conflict between minimizing travel distances and feasibility constraints on the home/away pat­ terns. Travel distances are a major issue in MLB because of the number of teams and the fact that teams go on "road trips" to visit several opponents before returning home. The feasibility constraints in the MLB restricts the number of suc­ cessive games that can be played at home or away.

The TIP is an abstraction of the MLB intended to stimu­ late research in sport scheduling. A solution to the TIP is a double round-robin tournament which satisfies sophisticated feasibility constraints (e.g., no more than three away games in a row) and minimizes the total travel distances of the teams. [4) argues that, without an approach to the TTP, it is unlikely that suitable schedules can be obtained for the MLB. The TTP has raised significant interest in recent years since the chal­ lenge instances were proposed. [4] describes both constraint and integer programming approaches to the TIP which gen­ erate high-quality solutions. [I] explores a Lagrangian relax­ ation approach (together with constraint programming tech­ niques) which improves some of the results. Other lower and upper bounds are given in [8], although the details of how they are obtained does not seem to be available.

Problem Description The problem was introduced by Eas­ ton, Nemhauser and Trick [8; 4], which contains many inter­ esting discussion on sport scheduling. An input consists of n teams (n even) and ann x n symmetric matrix d, such that dij represents the distance between the homes of teams Ti and Ti. A solution is a schedule in which each team plays with each other twice, once in each team's home. Such a schedule is called a double round-robin tournament. It should be clear that a double round-robin tournament has 2n - 2 rounds. For a given scheduleS, the cost of a team as the total distance that it has to travel starting from its home, playing the scheduled games in S, and returning back home. The cost of a solution is defined as the sum of the cost of every team.

The goal is to find a schedule with minimum cost satisfy­ ing the following two constraints: (I) Atmost Constraints: No more than three consecutive home or away games are allowed for any team. (2) Norepeat Constraints: A game of Ti at Tj 's home cannot be followed by a game of Tj at Ti 's home. As a consequence, a double round-robin schedule is feasible if it satisfies the atmost and norepeat constraints and is infeasible otherwise. A schedule is conveniently represented by a table indicating the opponents of the teams. Each line corresponds to a team and each column corresponds to a round. The opponent of team Ti at round r k is given by the absolute value of element (i, k) . If (i, k) is positive, the game takes place at T/s home, otherwise at Ti 's opponent home. Consider for instance the schedule S for 6 teams (and thus 10 rounds) .

ScheduleS specifies that team T1 has the following schedule. It successively plays against teams T6 at home, T2 away, T4 at home, T3 at home, T5 away, T4 away, T3 away, T5 at home, T2 at home, T6 away. The travel cost of team T1 is

Observe that long stretches of games at home do not con­ tribute to the travel cost but are limited by the atmost con­ straints. This kind of tension is precisely why this problem is hard to solve in practice.

The Local Search This paper proposes an advanced sim­ ulated annealing algorithm (TTSA) for the TTP. As usual, the algorithm starts from an initial configuration. Its basic step moves from the current configuration c to a configu­ ration in the neighborhood of c. TTSA is based on four main design decisions. (I) Constraints are separated into two groups: hard constraints, which are always satisfied by the configurations, and soft constraints, which may or may not be violated. The hard constraints are the round-robin con­ straints, while the soft constraints are the no-repeat and at­ most constraints. In other words, all configurations in the search represents a double round-robin tournament, which may or may not violate the no-repeat and atmost constraints. Exploring the infeasible region seems to be particularly im­ portant for this problem. Obviously, to drive the search to­ ward feasible solutions, TTSA modifies the original objec­ tive function to include a penalty term. (2) TTSA is based on a large neighborhood of size O(n 3 ), where n is the num­ ber of teams. Some of these moves can be regarded as a form of ejection chains which is often used in tabu search [6; 7]. (3) TTSA dynamically adjusts the objective function to balance the time spent in the feasible and infeasible regions. This adjustments resembles the strategic oscillation idea [5] successfully in tabu search to solve generalized assignment problems [3], although the details differ since simulated an­ nealing is used as the meta-heuristics. (4) TTSA also uses re­ heats (e.g., [2]) to escape local minima at low temperatures. The "reheats" increase the temperature again and divide the search in several phases.

The Neighborhood The neighborhood consists of four dif­ ferent moves. Among them, partial swaps of rounds and teams are critical to find high-quality solutions. Consider the move PartialSwapRounds(S, Ti, rk, r 1). This move considers team Ti and swaps its games at rounds Tk and r 1. Then the rest of the schedule for rounds rk and r1 is updated (in a de­ terministic way) to produce a double round-robin tournament. Consider the schedule S

and the move PartialSwapRounds(S, T2 , r2 , r9 ). Obviously swapping the game in rounds r 2 and r9 would not lead to a round-robin tournament. It is also necessary to swap the games of team I, 4, and 6 in order to obtain:

This move can thus be regarded as a form of ejection chain [6; 7]. Finding which games to swap is not difficult: it suffices to find the connected component which contains the games of Ti in rounds r 2 and r1 in the graph where the vertices are the teams and where an edge contains two teams if they play against each other in rounds rk and r1. All the teams in this component must have their games swapped. Note that there are O(n 3 ) such moves.

Experiments TTSA was applied to the National League benchmark described in [4; 8] . Over the course of this re­ search, TTSA was able to match the best solutions for NL4, NL6, and NL8, and to improve the solutions for NLI 0, NL12, NL14, and NL16 significantly. The best existing solutions were those in [8] and were the best to our knowledge at the time of writing. The last update was on November I, 2002. TISA is the first algorithm to go lower than 200,000 for 14 teams and 280,000 for I6 teams. The results are summa­ rized Table I. Observe that even our worst results on these instances improve the previous best solutions.

Acknowledgements This work is partially supported by by NSF ITR Awards DMI-OI2I495 and ACI-OI2I497.