Abstract
We define the timetable constrained distance minimization problem (TCDMP) which is a sports scheduling problem applicable for tournaments where the total travel distance must be minimized. The problem consists of finding an optimal home-away assignment when the opponents of each team in each time slot are given. We present an integer programming, a constraint programming formulation and describe two alternative solution methods: a hybrid integer programming/constraint programming approach and a branch and price algorithm. We test all four solution methods on benchmark problems and compare the performance. Furthermore, we present a new heuristic solution method called the circular traveling salesman approach (CTSA) for solving the traveling tournament problem. The solution method is able to obtain high quality solutions almost instantaneously, and by applying the TCDMP, we show how the solutions can be further improved.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Anagnostopoulos, A., Michel, L., Van Hentenryck, P., & Vergados, Y. (2003). A simulated annealing approach to the traveling tournament problem. In Proceedings CPAIOR’03, Montreal.
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998). Branch-and-price: Column generation for huge integer programs. Operations Research, 46, 316–329.
Benoist, T., Laburthe, F., & Rottembourg, B. (2001). Lagrange relaxation and constraint programming collaborative schemes for traveling tournament problem. In Proceedings CPAIOR’01, Wye College (Imperial College), Ashford, Kent, UK.
Della Croce, F., & Oliveri, D. (2006). Scheduling the Italian football league: an ILP-based approach. Computers and Operations Research, 33(7), 1963–1974.
Easton, K., Nemhauser, G., & Trick, M. (2001). The traveling tournament problem: description and benchmarks. In Lecture notes in computer science: Vol. 2239. Proceedings CP’01 (pp. 580–585). Berlin: Springer.
Easton, K., Nemhauser, G., & Trick, M. (2003). Solving the traveling tournament problem: a combined integer programming and constraint programming approach. In E. Burke & P. De Causmaecker (Eds.), Lecture notes in computer science: Vol. 2740. PATAT 2002 (pp. 100–109). Berlin: Springer.
Elf, M., Jünger, M., & Rinaldi, G. (2003). Minimizing breaks by maximizing cuts. Operations Research Letters, 31, 343–349.
Henz, M. (2001). Scheduling a major college basketball conference—revisited. Operations Research, 49, 163–168.
Henz, M. (1999). Constraint-based round robin tournament planning. In D. De Schreye (Ed.), Proceedings of the international conference on logic programming (pp. 545–557) Las Cruces, NM. Cambridge: MIT Press.
Henz, M., Müller, T., & Thiel, S. (2004). Global constraints for round robin tournament scheduling. European Journal of Operational Research, 153, 92–101.
Inc. ILOG. (2003). ILOG OPL Studio 3.7, language manual.
Inc. ILOG. (2003). CPLEX 9.0 user manual.
Inc. ILOG. (2000). ILOG Solver 5.0 User’s manual and reference manual.
Lim, A., Rodrigues, B., & Zhang, X. (2006). A simulated annealing and hill-climbing algorithm for the traveling tournament problem. European Journal of Operational Research, 174(3), 1459–1478.
Miyashiro, R., & Matsui, T. (2006). Semidefinite programming based approaches to the break minimization problem. Computers and Operations Research, 33(7), 1975–1982.
Nemhauser, G. L., & Trick, M. A. (1998). Scheduling a major college basketball conference. Operations Research, 46(1), 1–8.
Rasmussen, R. V., & Trick, M. A. (2007). A Benders approach for the constrained minimum break problem. European Journal of Operational Research, 177(1), 198–213.
Régin, J.-C. (2001). Minimization of the number of breaks in sports scheduling problems using constraint programming. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 57, 115–130.
Régin, J.-C., & Puget, J.-F. (1997). A filtering algorithm for global sequencing constraints. In Lecture notes in computer science: Vol. 1330. Proceedings CP’97. Berlin: Springer.
Ribeiro, C. C., & Urrutia, S. (2008, in press). Heuristics for the mirrored traveling tournament problem. European Journal of Operational Research.
Schaerf, A. (1999). Scheduling sport tournaments using constraint logic programming. Constraints, 4, 43–65.
Trick, M. (2001). A schedule-then-break approach to sports timetabling. In E. Burke & W. Erben (Eds.), Lecture Notes in Computer Science: Vol. 2079. PATAT 2000 (pp. 242–252). Berlin: Springer.
Trick, M. A. (2006). Michael Trick’s guide to sports scheduling. URL http://mat.tepper.cmu.edu/sports/Instances/.
Van Hentenryck, P., & Vergados, Y. (2006). Traveling tournament scheduling: a systematic evaluation of simulated annealing. In J. C. Beck & B. M. Smith (Eds.), Lecture notes in computer science: Vol. 3990 (pp. 167–181). Berlin: Springer.
van Hoeve, W.-J., Pesant, G., Rousseau, L.-M., & Sabharwal, A. (2006). Revisiting the sequence constraint. In Lecture notes in computer science: Vol. 4204. Proceedings CP’06. Berlin: Springer.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Rasmussen, R.V., Trick, M.A. The timetable constrained distance minimization problem. Ann Oper Res 171, 45–59 (2009). https://doi.org/10.1007/s10479-008-0384-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-008-0384-4