The timetable constrained distance minimization problem |
| |
Authors: | Rasmus V Rasmussen and Michael A Trick |
| |
Institution: | (1) Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA 15213, USA |
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|