基于禁忌搜索算法的联赛调度问题求解研究

Study of Sports League Scheduling Problem Based on Tabu Search Algorithm

本文提出一种基于禁忌搜索算法求解联赛调度问题(SLSP)的方法.约束满足问题(constraint satisfaction problem)表达形式是此方法的基础.为验证该方法的有效性,做了很多测试,可求解的最复杂的例子包含40个参赛队,780个整数变量,每个整数变量有780个值.实验结果表明,该方法在求解能力方面超过了一些现有方法,是解决此类问题最有前途的方法之一.

In this paper, we present a tabu method for a formulation of the Sports League Scheduling Problem. The method is based on a formulation of the problem as a Constraint Satisfaction Problem（CSP）. Many tests were performed on problem instances, among which the most complicated solvable instance involves up to40 teams representing 780 integer variables with 780 values per variable. Numerical results demonstrate that this method outperforms some existing approaches and is one of the most promising methods for solving problems of this type.