🏈 A hybrid local search and MIP-heuristic for the traveling tournament problem.
This python package contains a simple hybrid local search and MIP-heuristic for the traveling tournament problem. In detail, it uses a modified algorithm variant of the original approach described here, which is due to M. Goerigk and S. Westphal.
The definition of the TTP is as follows: Let a set of n teams and a distance matrix D be given. Here, D[i,j] is the distance from team i to team j. One wants to find a feasible double round robin tournament of the teams satisfying the following conditions:
- the length of any home stand is at most
max_k. - the length of any road trip is at most
max_k. - the two games between any two teams do not follow immediately.
- the sum of the distances traveled by the teams is minimized.
Starting from a canonical feasible solution, the algorithm uses a greedy local search to improve the solution (Phase I). As soon as we are stuck at a local minimum, the algorithm then tries to escape the local minimum by a MIP-heuristic (Phase II). Here, it optimizes the home-away patterns and the team matchups in alternation as long as it is not possible to improve the previous solution. Then, it switches back to Phase I and repeats. It terminates if neither Phase I nor Phase II can further improve the current best solution.
The local search is written in Cython and thus guarantees a high performance. Since most of the algorithm runtime is spent in Phase II, it's possible to set a custom MIP Gap. This can reduce the runtime dramatically but will lead to worse solutions in most cases. However, there are some cases where a higher MIP Gap gives better solutions, which in turn indicates that the neighborhoods used by the local search are not fully connected.
After installing Cython and a C++ compiler with C++17 support, this package can be installed via
pip3 install git+https://github.com/jhelgert/pyTTPimport numpy as np from pyTTP import solve, print_schedule team_names = ["ATL", "NYM", "PHI", "MON"] distances = np.array([[0, 745, 665, 929], [745, 0, 80, 337], [665, 80, 0, 380], [929, 337, 380, 0]], dtype=np.int32) objval, schedule = solve(distances, max_k=3) print_schedule(schedule, team_names)gives the optimal schedule
Slot ATL NYM PHI MON 0 @MON PHI @NYM ATL 1 @NYM ATL @MON PHI 2 @PHI @MON ATL NYM 3 NYM @ATL MON @PHI 4 MON @PHI NYM @ATL 5 PHI MON @ATL @NYM with objective value 8276.