A Cooperative Local Search Method for Solving the Traveling Tournament Problem

Abstract

Constrained optimization is the process of optimizing a certain objective function subject to a set of constraints. The goal is not necessarily to find the global optimum. We try to explore the search space more efficiently in order to find a good approximate solution. The obtained solution should verify the hard constraints that are required to be satisfied. In this paper, we propose a cooperative search method that handles optimality and feasibility separately. We take the traveling tournament problem (TTP) as a case study to show the applicability of the proposed idea. TTP is the problem of scheduling a double round-robin tournament that satisfies a set of related constraints and minimizes the total distance traveled by the teams. The proposed method for TTP consists of two main steps. In the first step, we ignore the optimization criterion. We reduce the search only to feasible solutions satisfying the problem's constraints. For this purpose, we use constraints programming model to ensure the feasibility of solutions. In the second step, we propose a stochastic local search method to handle the optimization criterion and find a good approximate solution that verifies the hard constraints. The overall method is evaluated on benchmarks and compared with other well-known techniques for TTP. The computational results are promising and show the effectiveness of the proposed idea for TTP.