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

赵玉明

（肇庆学院 计算机学院，广东 肇庆 526061）

0 引言

许多联赛（例如足球，篮球，乒乓球）主管部门必须要面对参赛队伍的调度问题.这些调度问题一般含有相互冲突的约束和不同的优化目标.例如：旅行距离最小[1]，每队每天只有1场比赛，特殊日期体育场不能使用，主场比赛与其所对应的客场比赛之间天数最少，等等.求解满足上述条件和优化目标的问题从而得到满意的调度非常困难.

许多研究者为解决这类调度问题做了很多研究，提出了很多方法同时也取得了不同程度的成功，例如整数线性规划[2]、约束规划[3]、局部搜索（模拟退火算法[4]，禁忌搜索算法[5]，混合算法等）.

本文要解决的是一类特殊的联赛调度问题（SLSP），McAloon等[6]研究过这类问题.他们使用整数线性规划得到的结果很不理想；之后尝试采用约束规划，得到了较好的结果；最后用局部搜索算法得到和约束规划相同的结果，但前者的计算时间要少得多.

Gomes 等[7]使用确定完整搜索的随机版本求解SLSP 问题，取得的结果比使用约束规划得到的结果要好，并且能解决参赛队数目较大的问题.

Regin[8-9]提出2种使用约束规划解决SLSP问题的方法.第1种方法使用强有力的过滤算法，得到的结果在执行时间和鲁棒性方面都比文献[6]和文献[7]好.第2种方法是第1种方法的改进，这种改进基于问题的转换.Regin通过引入一个隐式约束，把SLSP问题转化成一个等价问题，然后使用一个启发式的特殊过滤算法改进了其自己的结果.

本文的研究旨在提出一种基于禁忌搜索的局部搜索算法求解SLSP问题.

本文结构安排如下：第2 部分正式表述SLSP 问题；第3 部分为SLSP 问题建立约束满足问题模型；第4部分提出我们的禁忌搜索算法；第5部分给出比较测试结果；第6部分总结全文并得出结论.

1 问题的描述

本文后面部分都使用下列约束和定义.

|T|支参赛队，|T|为偶数，T 是所有参赛队的集合；

所有参赛队相互比赛且仅比赛1次；

整个赛季持续|T|-1个星期；

每支参赛队每星期必须进行1次比赛；

每星期有|T|/2局比赛，一场比赛可以被安排在任一局比赛；

整个赛季1支参赛队出现在同一局里面最多2次；

此调度问题就是在满足上述约束的基础上调度安排所有参赛队.为了说明上述问题我们在表1中给出一个有8支参赛队参赛，赛季长达7个星期，每个星期进行4局比赛的联赛调度问题的可行调度.8支参赛队以A～H作为标号.

表1 含有8支参赛队的一个可行调度

从表1可以看出，赛程的安排可以用二维数组表示，行用来表示第n 个星期，列用来表示赛局.每一列满足基数约束，即每支参赛队仅出现1次.在每行中每支参赛队最多出现2次.另外每场比赛仅出现1次，即表1中所有比赛不同.

2 将问题公式化

我们把SLSP问题看作一个约束满足问题，并使用约束规划描述它.

2.1 约束满足问题（CSP）

约束满足问题用一个三元组（X,D,C）定义.

X 是含有n 个变量的有限集：X={X1,…,Xn};

D 是相关域的集合：D={D1,…,Dn}，每一个Di是由Xi的所有可能的取值组成的有限集.

C 是p 个约束组成的集合：C={C1,…,Cp}，每个约束定义在一个变量集合上，同时确定哪些取值组合与变量取值一致.

给定上述三元组后，CSP问题本质上是在所有变量取值范围内寻找满足所有约束的全部变量值，这些变量值被称为符合CSP问题.所有变量取值的集合定义成域的笛卡尔积D1×…×Dn，求解CSP问题意味着在巨大数目的可能变量取值里寻找一个特殊的满足约束的变量值.

2.2 SLSP问题公式化成CSP问题

使用下列符号将SLSP问题描述成CSP问题：

P:局集合，|P|=|T|/2;

W:星期集合，|W|=|T|-1;

tn:第n 个参赛队编号，tn∈T,1≤n≤|T||;

x(tm,tn):tm—tn比赛的调度变量，其值的形式为(pm,n,wm,n)，意味着此次比赛被安排到wm,n星期pm,n局.

很明显X={x(tm,tn),1≤m≤n≤|T|},并且所有的域都等于D={(pm,n,wm,n),pm,n∈p,1≤pm,n≤|P|,wm,n∈W,1≤wm,n≤|W|};∀x ∈X,Dx=Do.约束集C 包含下列3种约束：

唯一性约束，即每支参赛队每星期只进行1 场比赛.Constraint 1(tn)⇔wm,n≠wq,n,∀(m,q)∈[1；|T|]2,m≠n,q≠n,m≠q;

每支参赛队在同一局不能多于1 场比赛约束.Constraint 2(tn)⇔|pm,n=pqn,(m,q)∈[1；|T|]2,m≠n,q≠n,m≠q}|≤1；

所有比赛不同约束.Constraint 3(tm,tn)⇔tm,tn≠tq,tr,∀tq,tr∈T2,tq≠tr.

3 使用禁忌搜索求解SLSP问题

3.1 搜索空间

赛程安排就是域D={(pm,n,wm,n,pm,n∈p,1≤pm,n≤|P|,wm,n∈W,1≤wm,n≤|W|}中的元素对变量集合X={x(tm,tn),1≤m＜n≤|T|}中所有变量进行完全赋值.因此赛程安排是一个大小为|W|×|P|的二维表，表中元素是二元组(m,n),1≤m＜n≤|T|.对于有40个参赛队的SLSP问题有780个变量，每个变量有780个值.

一共有|T|/2×(|T|-1)场比赛需要调度，每个调度可以看成是对所有比赛的一个排列.有|T|个参赛队的SLSP问题，其搜索空间的大小是(|T|/2×(|T|-1))!.

3.2 初始赛程安排

初始赛程安排用来指定搜索空间的起点，可以随意指定一个满足Constraint 3的赛程安排作为搜索空间的起点，然后随意为每个二元组(w,p)安排1场比赛，w ∈W,p ∈P.受文献[10]的启发，笔者采用另一种方式构建初始赛程安排.限于篇幅构建过程省略，具体步骤可参见文献[10].笔者所构造的初始赛程安排满足Constraint 1和Constraint 3.

3.3 邻域

设s 为一来自搜索空间S 的赛程安排，s 的邻域N(s)定义如下：

N(s)={s′|s′∈S,s和s′只有一对变量值不同,并且s和s′中至少有一个不满足约束}.s 的邻域可以通过交换当前s 中任意不满足约束的2 个变量的当前值得到.我们可以用二元组表示从赛程安排s 到s的邻域s′ 的一次移动，也就是交换2 场比赛.另外，为了保证满足Constraint 2，交换比赛应在同一个星期进行.

3.4 评估函数

为了比较赛程安排的质量，定义一个评估函数f(s).令Happ Ps(p,tn)为赛程安排s 中参赛队tn出现在赛局p 的次数.f(s)为所有参赛队在所有赛局里出现次数最多的总和.

解SLSP问题本质上就是找到一个赛程安排ξ ∈S，使得f(ξ)=0 成立.

3.5 禁忌表管理

禁忌表是特殊的短期记忆，包含由曾经遇到的赛程安排或这些赛程安排的有关属性，是禁忌搜索的基本组成部分.设立禁忌表的目的是避免陷入死循环和跳出局部最优状态.禁忌期限对禁忌算法的性能有很大影响，期限过长会限制对没有探索的赛程安排的访问，并且禁忌算法探索邻域的能力会减弱；期限过短会使禁忌算法限于局部最优的状态.

在尝试了不同的禁忌期限后，笔者选择使用随机禁忌期限.赛程安排s 的禁忌期限定义如下：ks=rand(g)，rand(g)是一个[1;g]之间的随机整数，g ∈[10;80]，s ∈S.用|X|×|X|的矩阵实现禁忌表，矩阵的每个元素对应于一次移动，并且存储了当前迭代次数和禁忌期限.使用这种数据结构，通过简单的当前迭代次数比较就可以知道一个移动是否是合法的.

3.6 通用算法

本文所提出的TS-SLSP 算法以构建满足Constraint 1 和Constraint 3 的搜索空间初始赛程安排作为开端，而后沿着邻域继续迭代访问一系列局部最好的赛程安排.在每次迭代中，最好的移动即使不能改善当前赛程安排的评估函数值，也会被用于当前赛程安排.如果f(x)=0,即找到一个最优的调度或者移动次数达到给定的限制，算法停止.TS-SLSP算法的伪代码如下：

输入：||T；

输出：最优赛程安排或者找不到最优赛程安排；

f 为评估函数，f′为该评估函数的当前最优值；

c 为当前赛程安排，c′为迄今所遇到的最好赛程安排；

第1步：初始化禁忌表为空；

第2步：产生初始赛程安排c；

第3步：c′=c;

第4步：f′=f(c);

第5步：如果满足算法停止条件，到第11步；

第6步：对c 做最好的移动m,把m 添加到禁忌列表；

第7步：如果f(s)＜f′,c′=c,f′=f(c),到第5步;否则到第8步；

第8步：如果f′在足够时间内没有被改善，c=c′,禁忌表清空，去第5步；

第9步：如果f′=0，找到最优赛程安排，到第11步；

第10步：输出：找不到最优赛程安排；

第11步：算法终止.

4 计算结果

将本文提出的禁忌算法同文献[9]中的算法进行比较测试，结果如表2所示.测试在Windows XP操作系统下进行，系统配置3.33 Gb内存，3.39 MHz.测试用例从14个参赛队到41个参赛队.本文提出的TS-SLSP算法允许进行2 000万次迭代.

从表2可以看出，同文献[9]中的算法相比，本文提出的算法有如下优点：第一，具有很强的求解能力.在参赛队数目大于28时，文献[9]中的算法在2 h内已经不能找到解，而TS-SLSP算法在参赛队数目高达40的情况下仍然可以找到最优赛程安排，尽管运行时间延长很多.第二，具有很高的成功率.在参赛队数目小于25时，本文提出的算法成功率都大于85%，甚至达到100%.从表2也可看到本文提出算法存在的不足：第一，在参赛队数目小于28时，本文提出的算法比文献[9]中算法运行的时间长；第二，在参赛队数目为41时，本文提出的算法在2 h内迭代2 000万次的情况下找不到解；第三，算法的成功率随着参赛队数目的增加而降低.

表2 比较测试结果

5 结论

本文中，笔者为联赛调度问题提出一种禁忌算法（TS-SLSP），该算法基于SLSP问题的CSP形式且具有以下特性：简单的交换邻域，便于快速邻域搜索的高效数据机构，动态禁忌期限等.测试结果表明TS-SLSP算法在求解能力方面优于文献[9]中的算法，尽管文献[9]中的算法组合了约束传递算法和原始问题的非平凡形式.同时，我们注意到TS-SLSP算法的运行时间远大于文献[9]中的算法，这也说明本文提出的算法有很大的改进空间.例如：可以将约束传递技术同禁忌搜索结合起来提高算法的效率，这将是今后的研究方向之一.

本文的工作再一次证明了高效数据结构对禁忌搜索算法性能的重要性，同时也证实了参数的设置对于获得高质量的解具有关键性作用.可以将TS-SLSP算法做一些调整以解决其他的运动调度优化问题，例如最小化主客场比赛时间间隔.所有这些研究表明，元启发式算法（禁忌搜索算法，模拟退火算法等）对解决各种计划和调度问题具有较好的潜力.

[1]BEAN J C,Brige J R.Reducing traveling costs and player fatigue in the national basketball association[J].Interfaces,1980,10(3):98-102.

[2]FERLAND J A,FLEURENT C.Allocating games for the NHL using integer programming[J].Operations Research,1996,41(4):649-654.

[3]HENZ M.Scheduling a major college basketball conference[J].Operations Research,2001,49(1):649-654.

[4]TERRI B J,Willis R J.Scheduling the australian state cricket season using simulated annealing[J].Journal of the Operational Research society,1994,45(3):276-280.

[5]WRIGHT M.Timetabling county cricket fixtures using a form of tabu search[J].Journal of the Operational Research Society,1994,45(7):758-770.

[6]MCALOON K,TRETKOFF C,WETZEL G.Sports league scheduling[C]//Proceedings of the Third ILOG Optimization Suite International Users’Conference.1997.

[7]GOMES C P,SELMAN B,KAUTZ H A.Boosting combinatorial search through randomization[C]//Proceedings of the Fifteenth National Conference on Artificial Intelligence.Madison:AAAI Press,1998:431-437.

[8]REGIN J C.Modeling and solving sports league scheduling with constraint programming[C]//First Congress of the French Operational Research Society.1998.

[9]REGIN J C,Sports scheduling and constraint programming[C]//INFORMS.1999.

[10]SCHREUDER J A M.Constructing timetables for sport competitions[J].Mathematical Programming Study,1980,13:58-67.