基于禁忌搜索算法的聯(lián)賽調(diào)度問(wèn)題求解研究

趙玉明

（肇慶學(xué)院 計(jì)算機(jī)學(xué)院，廣東 肇慶 526061）

0 引言

許多聯(lián)賽（例如足球，籃球，乒乓球）主管部門必須要面對(duì)參賽隊(duì)伍的調(diào)度問(wèn)題.這些調(diào)度問(wèn)題一般含有相互沖突的約束和不同的優(yōu)化目標(biāo).例如：旅行距離最小[1]，每隊(duì)每天只有1場(chǎng)比賽，特殊日期體育場(chǎng)不能使用，主場(chǎng)比賽與其所對(duì)應(yīng)的客場(chǎng)比賽之間天數(shù)最少，等等.求解滿足上述條件和優(yōu)化目標(biāo)的問(wèn)題從而得到滿意的調(diào)度非常困難.

許多研究者為解決這類調(diào)度問(wèn)題做了很多研究，提出了很多方法同時(shí)也取得了不同程度的成功，例如整數(shù)線性規(guī)劃[2]、約束規(guī)劃[3]、局部搜索（模擬退火算法[4]，禁忌搜索算法[5]，混合算法等）.

本文要解決的是一類特殊的聯(lián)賽調(diào)度問(wèn)題（SLSP），McAloon等[6]研究過(guò)這類問(wèn)題.他們使用整數(shù)線性規(guī)劃得到的結(jié)果很不理想；之后嘗試采用約束規(guī)劃，得到了較好的結(jié)果；最后用局部搜索算法得到和約束規(guī)劃相同的結(jié)果，但前者的計(jì)算時(shí)間要少得多.

Gomes 等[7]使用確定完整搜索的隨機(jī)版本求解SLSP 問(wèn)題，取得的結(jié)果比使用約束規(guī)劃得到的結(jié)果要好，并且能解決參賽隊(duì)數(shù)目較大的問(wèn)題.

Regin[8-9]提出2種使用約束規(guī)劃解決SLSP問(wèn)題的方法.第1種方法使用強(qiáng)有力的過(guò)濾算法，得到的結(jié)果在執(zhí)行時(shí)間和魯棒性方面都比文獻(xiàn)[6]和文獻(xiàn)[7]好.第2種方法是第1種方法的改進(jìn)，這種改進(jìn)基于問(wèn)題的轉(zhuǎn)換.Regin通過(guò)引入一個(gè)隱式約束，把SLSP問(wèn)題轉(zhuǎn)化成一個(gè)等價(jià)問(wèn)題，然后使用一個(gè)啟發(fā)式的特殊過(guò)濾算法改進(jìn)了其自己的結(jié)果.

本文的研究旨在提出一種基于禁忌搜索的局部搜索算法求解SLSP問(wèn)題.

本文結(jié)構(gòu)安排如下：第2 部分正式表述SLSP 問(wèn)題；第3 部分為SLSP 問(wèn)題建立約束滿足問(wèn)題模型；第4部分提出我們的禁忌搜索算法；第5部分給出比較測(cè)試結(jié)果；第6部分總結(jié)全文并得出結(jié)論.

1 問(wèn)題的描述

本文后面部分都使用下列約束和定義.

|T|支參賽隊(duì)，|T|為偶數(shù)，T 是所有參賽隊(duì)的集合；

所有參賽隊(duì)相互比賽且僅比賽1次；

整個(gè)賽季持續(xù)|T|-1個(gè)星期；

每支參賽隊(duì)每星期必須進(jìn)行1次比賽；

每星期有|T|/2局比賽，一場(chǎng)比賽可以被安排在任一局比賽；

整個(gè)賽季1支參賽隊(duì)出現(xiàn)在同一局里面最多2次；

此調(diào)度問(wèn)題就是在滿足上述約束的基礎(chǔ)上調(diào)度安排所有參賽隊(duì).為了說(shuō)明上述問(wèn)題我們?cè)诒?中給出一個(gè)有8支參賽隊(duì)參賽，賽季長(zhǎng)達(dá)7個(gè)星期，每個(gè)星期進(jìn)行4局比賽的聯(lián)賽調(diào)度問(wèn)題的可行調(diào)度.8支參賽隊(duì)以A～H作為標(biāo)號(hào).

表1 含有8支參賽隊(duì)的一個(gè)可行調(diào)度

從表1可以看出，賽程的安排可以用二維數(shù)組表示，行用來(lái)表示第n 個(gè)星期，列用來(lái)表示賽局.每一列滿足基數(shù)約束，即每支參賽隊(duì)僅出現(xiàn)1次.在每行中每支參賽隊(duì)最多出現(xiàn)2次.另外每場(chǎng)比賽僅出現(xiàn)1次，即表1中所有比賽不同.

2 將問(wèn)題公式化

我們把SLSP問(wèn)題看作一個(gè)約束滿足問(wèn)題，并使用約束規(guī)劃描述它.

2.1 約束滿足問(wèn)題（CSP）

約束滿足問(wèn)題用一個(gè)三元組（X,D,C）定義.

X 是含有n 個(gè)變量的有限集：X={X1,…,Xn};

D 是相關(guān)域的集合：D={D1,…,Dn}，每一個(gè)Di是由Xi的所有可能的取值組成的有限集.

C 是p 個(gè)約束組成的集合：C={C1,…,Cp}，每個(gè)約束定義在一個(gè)變量集合上，同時(shí)確定哪些取值組合與變量取值一致.

給定上述三元組后，CSP問(wèn)題本質(zhì)上是在所有變量取值范圍內(nèi)尋找滿足所有約束的全部變量值，這些變量值被稱為符合CSP問(wèn)題.所有變量取值的集合定義成域的笛卡爾積D1×…×Dn，求解CSP問(wèn)題意味著在巨大數(shù)目的可能變量取值里尋找一個(gè)特殊的滿足約束的變量值.

2.2 SLSP問(wèn)題公式化成CSP問(wèn)題

使用下列符號(hào)將SLSP問(wèn)題描述成CSP問(wèn)題：

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

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

tn:第n 個(gè)參賽隊(duì)編號(hào)，tn∈T,1≤n≤|T||;

x(tm,tn):tm—tn比賽的調(diào)度變量，其值的形式為(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種約束：

唯一性約束，即每支參賽隊(duì)每星期只進(jìn)行1 場(chǎng)比賽.Constraint 1(tn)?wm,n≠wq,n,?(m,q)∈[1；|T|]2,m≠n,q≠n,m≠q;

每支參賽隊(duì)在同一局不能多于1 場(chǎng)比賽約束.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問(wèn)題

3.1 搜索空間

賽程安排就是域D={(pm,n,wm,n,pm,n∈p,1≤pm,n≤|P|,wm,n∈W,1≤wm,n≤|W|}中的元素對(duì)變量集合X={x(tm,tn),1≤m＜n≤|T|}中所有變量進(jìn)行完全賦值.因此賽程安排是一個(gè)大小為|W|×|P|的二維表，表中元素是二元組(m,n),1≤m＜n≤|T|.對(duì)于有40個(gè)參賽隊(duì)的SLSP問(wèn)題有780個(gè)變量，每個(gè)變量有780個(gè)值.

一共有|T|/2×(|T|-1)場(chǎng)比賽需要調(diào)度，每個(gè)調(diào)度可以看成是對(duì)所有比賽的一個(gè)排列.有|T|個(gè)參賽隊(duì)的SLSP問(wèn)題，其搜索空間的大小是(|T|/2×(|T|-1))!.

3.2 初始賽程安排

初始賽程安排用來(lái)指定搜索空間的起點(diǎn)，可以隨意指定一個(gè)滿足Constraint 3的賽程安排作為搜索空間的起點(diǎn)，然后隨意為每個(gè)二元組(w,p)安排1場(chǎng)比賽，w ∈W,p ∈P.受文獻(xiàn)[10]的啟發(fā)，筆者采用另一種方式構(gòu)建初始賽程安排.限于篇幅構(gòu)建過(guò)程省略，具體步驟可參見(jiàn)文獻(xiàn)[10].筆者所構(gòu)造的初始賽程安排滿足Constraint 1和Constraint 3.

3.3 鄰域

設(shè)s 為一來(lái)自搜索空間S 的賽程安排，s 的鄰域N(s)定義如下：

N(s)={s′|s′∈S,s和s′只有一對(duì)變量值不同,并且s和s′中至少有一個(gè)不滿足約束}.s 的鄰域可以通過(guò)交換當(dāng)前s 中任意不滿足約束的2 個(gè)變量的當(dāng)前值得到.我們可以用二元組表示從賽程安排s 到s的鄰域s′ 的一次移動(dòng)，也就是交換2 場(chǎng)比賽.另外，為了保證滿足Constraint 2，交換比賽應(yīng)在同一個(gè)星期進(jìn)行.

3.4 評(píng)估函數(shù)

為了比較賽程安排的質(zhì)量，定義一個(gè)評(píng)估函數(shù)f(s).令Happ Ps(p,tn)為賽程安排s 中參賽隊(duì)tn出現(xiàn)在賽局p 的次數(shù).f(s)為所有參賽隊(duì)在所有賽局里出現(xiàn)次數(shù)最多的總和.

解SLSP問(wèn)題本質(zhì)上就是找到一個(gè)賽程安排ξ ∈S，使得f(ξ)=0 成立.

3.5 禁忌表管理

禁忌表是特殊的短期記憶，包含由曾經(jīng)遇到的賽程安排或這些賽程安排的有關(guān)屬性，是禁忌搜索的基本組成部分.設(shè)立禁忌表的目的是避免陷入死循環(huán)和跳出局部最優(yōu)狀態(tài).禁忌期限對(duì)禁忌算法的性能有很大影響，期限過(guò)長(zhǎng)會(huì)限制對(duì)沒(méi)有探索的賽程安排的訪問(wèn)，并且禁忌算法探索鄰域的能力會(huì)減弱；期限過(guò)短會(huì)使禁忌算法限于局部最優(yōu)的狀態(tài).

在嘗試了不同的禁忌期限后，筆者選擇使用隨機(jī)禁忌期限.賽程安排s 的禁忌期限定義如下：ks=rand(g)，rand(g)是一個(gè)[1;g]之間的隨機(jī)整數(shù)，g ∈[10;80]，s ∈S.用|X|×|X|的矩陣實(shí)現(xiàn)禁忌表，矩陣的每個(gè)元素對(duì)應(yīng)于一次移動(dòng)，并且存儲(chǔ)了當(dāng)前迭代次數(shù)和禁忌期限.使用這種數(shù)據(jù)結(jié)構(gòu)，通過(guò)簡(jiǎn)單的當(dāng)前迭代次數(shù)比較就可以知道一個(gè)移動(dòng)是否是合法的.

3.6 通用算法

本文所提出的TS-SLSP 算法以構(gòu)建滿足Constraint 1 和Constraint 3 的搜索空間初始賽程安排作為開(kāi)端，而后沿著鄰域繼續(xù)迭代訪問(wèn)一系列局部最好的賽程安排.在每次迭代中，最好的移動(dòng)即使不能改善當(dāng)前賽程安排的評(píng)估函數(shù)值，也會(huì)被用于當(dāng)前賽程安排.如果f(x)=0,即找到一個(gè)最優(yōu)的調(diào)度或者移動(dòng)次數(shù)達(dá)到給定的限制，算法停止.TS-SLSP算法的偽代碼如下：

輸入：||T；

輸出：最優(yōu)賽程安排或者找不到最優(yōu)賽程安排；

f 為評(píng)估函數(shù)，f′為該評(píng)估函數(shù)的當(dāng)前最優(yōu)值；

c 為當(dāng)前賽程安排，c′為迄今所遇到的最好賽程安排；

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

第2步：產(chǎn)生初始賽程安排c；

第3步：c′=c;

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

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

第6步：對(duì)c 做最好的移動(dòng)m,把m 添加到禁忌列表；

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

第8步：如果f′在足夠時(shí)間內(nèi)沒(méi)有被改善，c=c′,禁忌表清空，去第5步；

第9步：如果f′=0，找到最優(yōu)賽程安排，到第11步；

第10步：輸出：找不到最優(yōu)賽程安排；

第11步：算法終止.

4 計(jì)算結(jié)果

將本文提出的禁忌算法同文獻(xiàn)[9]中的算法進(jìn)行比較測(cè)試，結(jié)果如表2所示.測(cè)試在Windows XP操作系統(tǒng)下進(jìn)行，系統(tǒng)配置3.33 Gb內(nèi)存，3.39 MHz.測(cè)試用例從14個(gè)參賽隊(duì)到41個(gè)參賽隊(duì).本文提出的TS-SLSP算法允許進(jìn)行2 000萬(wàn)次迭代.

從表2可以看出，同文獻(xiàn)[9]中的算法相比，本文提出的算法有如下優(yōu)點(diǎn)：第一，具有很強(qiáng)的求解能力.在參賽隊(duì)數(shù)目大于28時(shí)，文獻(xiàn)[9]中的算法在2 h內(nèi)已經(jīng)不能找到解，而TS-SLSP算法在參賽隊(duì)數(shù)目高達(dá)40的情況下仍然可以找到最優(yōu)賽程安排，盡管運(yùn)行時(shí)間延長(zhǎng)很多.第二，具有很高的成功率.在參賽隊(duì)數(shù)目小于25時(shí)，本文提出的算法成功率都大于85%，甚至達(dá)到100%.從表2也可看到本文提出算法存在的不足：第一，在參賽隊(duì)數(shù)目小于28時(shí)，本文提出的算法比文獻(xiàn)[9]中算法運(yùn)行的時(shí)間長(zhǎng)；第二，在參賽隊(duì)數(shù)目為41時(shí)，本文提出的算法在2 h內(nèi)迭代2 000萬(wàn)次的情況下找不到解；第三，算法的成功率隨著參賽隊(duì)數(shù)目的增加而降低.

表2 比較測(cè)試結(jié)果

5 結(jié)論

本文中，筆者為聯(lián)賽調(diào)度問(wèn)題提出一種禁忌算法（TS-SLSP），該算法基于SLSP問(wèn)題的CSP形式且具有以下特性：簡(jiǎn)單的交換鄰域，便于快速鄰域搜索的高效數(shù)據(jù)機(jī)構(gòu)，動(dòng)態(tài)禁忌期限等.測(cè)試結(jié)果表明TS-SLSP算法在求解能力方面優(yōu)于文獻(xiàn)[9]中的算法，盡管文獻(xiàn)[9]中的算法組合了約束傳遞算法和原始問(wèn)題的非平凡形式.同時(shí)，我們注意到TS-SLSP算法的運(yùn)行時(shí)間遠(yuǎn)大于文獻(xiàn)[9]中的算法，這也說(shuō)明本文提出的算法有很大的改進(jìn)空間.例如：可以將約束傳遞技術(shù)同禁忌搜索結(jié)合起來(lái)提高算法的效率，這將是今后的研究方向之一.

本文的工作再一次證明了高效數(shù)據(jù)結(jié)構(gòu)對(duì)禁忌搜索算法性能的重要性，同時(shí)也證實(shí)了參數(shù)的設(shè)置對(duì)于獲得高質(zhì)量的解具有關(guān)鍵性作用.可以將TS-SLSP算法做一些調(diào)整以解決其他的運(yùn)動(dòng)調(diào)度優(yōu)化問(wèn)題，例如最小化主客場(chǎng)比賽時(shí)間間隔.所有這些研究表明，元啟發(fā)式算法（禁忌搜索算法，模擬退火算法等）對(duì)解決各種計(jì)劃和調(diào)度問(wèn)題具有較好的潛力.

[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.