The traveling tournament problem is a difficult sports league scheduling problem introduced by

Easton, K., Nemhauser, G., Trick, M.: The traveling tournament problem description and benchmarks. In: International Conference on Principles and Practice of Constraint Programming. LNCS, vol. 2239, pp. 580–584. Springer (2001)

The problem description, benchmark problem instances, and currently best known lower and upper bounds can be found on Michael Trick's TTP page and more recently at the RobinX repository.

This repository contains a Julia implementation of a beam search approach as presented in [1].

The code has been tested with Julia 1.10.2 and DataStructures.jl 0.18.20. Google OR-Tools 9.9 with Python 3.12 are interfaced via PyCall.jl.

Installation of dependencies assuming a python3 with ortools installed in the path:

julia --project=. -e "import Pkg; Pkg.instantiate(verbose=true)"

PYTHON=`which python3` julia --project=. -e 'using Pkg; Pkg.build("PyCall")'

To precalculate the lower bounds for teams' states of an instance (aka disjoint pattern database, similar as done by [2,3]), to be saved into a pickled and bz2 compressed numpy array:

julia --project=. ttp_bounds_precalculation.jl insts/circ/circ14.txt 3 data/circ14_cvrph.pkl.bz2 true

To subsequently call the randomized beam search approach with shuffled team ordering and relative noise of 0.001:

julia --project=. ttp_beam_search.jl insts/circ/circ14.txt 3 true data/circ14_cvrph.pkl.bz2 10000 true random 0.001 -1 false

A final feasible local search using the TTSA neighborhoods [4] can be activated by setting the last parameter to true.

There is also a parallel beam search implementation for the TTP also faster in single threaded mode.

Alternatively, Google OR-Tools can be used to solve the arising capacitated vehicle routing problems (CVRPs) on the fly used as guidance for the beam search and keep already solved problems in a cache:

julia --project=. ttp_beam_search_ortools.jl insts/circ/circ14.txt 3 true 16384 true lexicographic none 0.0 false -1 false

For the latter, there is also an iterative variant, which increases the beam width by a factor every number of runs until either a time or maximum beam width is hit:

julia --project=. ttp_beam_search_ortools_iter.jl insts/NL/nl10.txt 3 true 3600 128 32768 2 true random none 0.001 2 true -1

[ks^-1] are thousands of nodes explored per second, lce [log] represents a log cache efficiency by a cache miss fraction (e.g., -3 means every 1000th CVRP calculation needed to be performed from scratch, the remaining were retrieved from cache), tph [ms] is the average time per such a CVRP calculation in milliseconds.

[1]

Frohner, N., Neumann, B., and Raidl, G. R. (2020). A beam search approach to the traveling tournament problem. In Paquete, L. and Zarges, C., editors, Evolutionary Computation in Combinatorial Optimization – 20th European Conference, EvoCOP 2020, Held as Part of EvoStar 2020, volume 12102 of LNCS, pages 67–82, Sevilla, Spain. Springer.

[2]

David C Uthus, Patricia J Riddle, and Hans W Guesgen. DFS* and the traveling tournament problem. In International Conference on AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems volume 5547 of LNCS, pages 279–293. Springer, 2009.

[3]

David C Uthus, Patricia J Riddle, and Hans W Guesgen. Solving the traveling tournament problem with iterative-deepening A*. Journal of Scheduling, 15(5): 601–614, 2012.

[4]

Aris Anagnostopoulos, Laurent Michel, Pascal Van Hentenryck, and Yannis Vergados. A simulated annealing approach to the traveling tournament problem. Journal of Scheduling, 9(2):177–193, 2006.