基于模擬退火算法的中超賽程編排優化研究

劉寶友，王 濤，馬延龍

(河北科技大學環境科學與工程學院，河北石家莊 050018)

?

基于模擬退火算法的中超賽程編排優化研究

劉寶友，王 濤，馬延龍

(河北科技大學環境科學與工程學院，河北石家莊 050018)

為了促進賽事的公平性、實現人性化的賽程編排設計，同時達到減少出行里程、節約資源、保護環境的目的，采用計算機輔助建模的方法，對中超賽程編排進行優化研究。假設以總體出行里程最短、兼具賽程的公平性和設計的人性化為優化目標，以百度地圖提供的球隊所在城市間的距離數據為依據，通過改進模擬退火算法對2015年中超賽程編排進行優化，運用Matlab求解得到最優方案。結果表明：在最優賽程安排下得到的各支球隊最優出行里程為5.022×105km，相對2015年中超的實際賽程編排總里程減少了12.08%，由此節省燃油14.50 t，減少排放二氧化硫43.9 kg，對大氣中二氧化硫減排的貢獻率為11.11%，節約資金91 467.4元。該結果可以為中超實際主客場賽程編排的優化提供參考。

環境規劃與管理；中超賽程；模擬退火算法；最優化；冷卻進度表

模擬退火算法(simulated annealing algorithm)是一類從局部拓展到全局的隨機性組合系統優化方法[1]，它利用雜交粒子群優化算法中的雜交運算與帶高斯變異粒子群優化算法中的變異運算處理大規模復雜數據的優化問題[2]。與其他方法相比，該算法具有描述簡單、約束較少、使用靈活、運行效率高等優點,適于求解非確定多項式問題(NP)、旅行商問題(TSP)等優化組合問題。改進退火算法的優化性能主要涉及全過程狀態函數與溫度更新函數，這些環節的設計將決定模擬退火算法的快速性、收斂性與魯棒性等[3-4]。

圖1 2015年中超地圖
Fig.1 Geographical map of Chinese Super League in 2015

1 中超賽程現狀及分析

2015年中超聯賽采用主客場雙循環賽制[9]，參賽隊伍是2014年排名前16的球隊(升級隊代替降級隊)。球隊在一個城市進行完一場比賽后乘坐交通工具進入另一個城市參加比賽，所有球隊進行完上半程比賽后回到各自城市休整，下半程與上半程對陣球隊相同但主客場位置調換，所有比賽結束后，各球隊回到各自所在的城市。

在中超賽程中，考慮到旅途勞累與主場優勢等因素，任一球隊不宜連續3次以上(>3)做主場或客場，此時通過建立退火模型進行系統優化，不僅可使賽程編排更為合理，更能確保球隊隊員實力的正常發揮，實現相對公平。各支球隊的地理位置與所在城市之間的距離分別如圖1和表1所示。

表1 2015年不同中超球隊之間的距離

2 中超賽程優化模型的構建

2.1 模型假設

在賽制編排中，將中超賽程所有方案表示為一個有向的賦權圖C=(V，E)[10]，其中V∈(V1,V2,…,V16)，是16支球隊集合中的一支;E∈(E1,E2,…,E16),是不同于V的另一支球隊。最優賽程Z與有向對陣賽程C的關系為

(1)

約束條件如下：

1)任意兩地往返路程相同,即Si,j=Sj,i；

2)交通工具統一為宇通標準55座大巴車，中途不更換其他交通工具；

3)Sa,b=0,a和b為同在一個城市的不同球隊；

4)所有球隊打完上半程后回各自城市進行休整；

5)退火算法參數取舍得當，不會陷入局部最優；

6)兩城市之間的路程精確到整數位。

2.2 模型分析

首先將2014年球隊排名作為2015年各隊的隊號(用a1,a2,…,a16表示，升級隊代替降級隊)，按照抽簽法的原則進行單循環隨機排列，對應到b1,b2,…,b16的位置。對16支球隊的位置進行蛇形編排，即對陣雙方位置為bi?b17-i，固定1號位置不動，2號位置到16號位置(包括位置上的球隊)，順序輪轉，循環一輪后對陣雙方為b1?b2, b3?b16, b4?b15, b5?b14, b6?b13, b7?b12, b8?b11, b9?b10。共可進行15輪循環，此時位置對陣總數U=15輪×8場/輪=120場。

將15輪比賽進行全排列共有15！≈1.3×1012種可能情況，編排情況相對較多，應用模擬退火算法，根據Metropolis接受準則[11-12]，持續進行“產生新解—判斷與目標函數的差距—決定接受或舍棄”的迭代過程，算法法則如下：

(2)

利用概率算子min{1,exp(-Δf/Tk)}>random[0,1]選擇性接受可行解，以概率exp(-Δf/Tk)選擇性接受劣質解[13-15]。通過迭代算子Tk+1=CTk，k←k+1，其中C∈(0,1)進行迭代運算，則速度與位置更新公式如下：

vi,j(k+1)=χ[vi,j(k)+c1r1(pi,j(k)-xi,j(k))+c2r2(pg,j(k)-xi,j(k))],

(3)

xi,j(k+1)=xi,j(k)+vi,j(k+1),(j=1,…,n),

(4)

(5)

在運行算法過程中，性能相對較好的編排結果應該被賦予更高的選中率，若用f代表目標函數，可用式(6)為概率Pi選擇合適的取值。

(6)

為了提升賽程的相對公平性，任一球隊不宜連續3次以上(>3)做主場或客場，則模型設計基本原則如下：

1)任一球隊如果本輪打主場則下一輪優先考慮打客場；

2)任一球隊如果本輪打客場則下一輪優先考慮打主場。

設定第1輪比賽對陣雙方主客場隨機選取，從第2輪到第15輪主客場受限程度依次遞增，首先窮舉第1輪所有可能主客場情況并利用dgr_flag與wish_host分別提供危險標志和希望標志(初始值為零)，數據結構如下:

dgr_flg=zeros(1,TEAM_NUM);%每個球隊提供一個危險標志

wish_host=zeros(1,TEAM_NUM);%每個球隊希望打主場標志。

2.3 算法尋優步驟

16支球隊分為8組對陣，每組對陣有2種主客場情況，則共28=256種主客場情況，選取其中1種進行完整的15輪循環，此時尋優步驟如下：

1)在256種主客場編排中隨機選取1種情況進行蛇形編排與順序輪轉，得到完整的15輪循環過程；

2)利用模擬退火算法進行種群尋優并判斷每組對陣的2支球隊是否已經連續做了3次主場(或客場)[18-19]，如果對陣的2支球隊都已經做了3次主場(或客場)且下一場希望相同，則結束進程返回步驟1)重新隨機選取；

圖2 算法的總體流程圖Fig.2 Flow diagram of algorithm

3)如果對陣的2支球隊都已經連續3次做了主場(或客場)，但2支球隊對待下一場比賽希望做主場還是客場的情況相反，此時可以完成循環并輸出最優解；

4)如果對陣的2支球隊下一場都想做主場(或者客場)，但只有其中1支隊伍已經連續3次做了主場(或客場)，則此隊擁有優先選擇權，完成循環并輸出最優解；

5)如果對陣的2支球隊下一場都想做主場(或客場)，但是2支球隊都沒有連續3次做主場(或客場)，則可根據隊號大小決定，隊號大的優先選擇，完成循環并輸出最優解。

圖3 利用模擬退火算法的全局尋優結果Fig.3 Global optimization results by stimulated annealing algorithm

該算法的總體流程見圖2。在中超聯賽中，下半程賽程完全翻轉上半程賽程，即對陣雙方、主客場安排與輪次順序完全確定。本文從中超聯賽實際情況出發，在上半程對陣雙方與主客場安排確定的情況下利用退火算法對下半程進行尋優，將優化后的上、下半程的賽程之和作為中超比賽整體的賽程，則此賽程即為最優的全局編排方案[20]。

3 結果分析與討論

3.1 結果分析

按照模擬退火算法初始值設置的一般原則，經過多次嘗試，選取初始退火溫度T0=500 000,在終止條件Tk+1=CTk中令C=0.95，通過運行Matlab程序，可得到全局尋優的模擬退火圖，如圖3所示。

運行時長2 990.91s，隨機選取種類超過25萬種，最終得到表2所示的運行結果。從表2可以得到每支球隊出行的具體路線，同時計算出16支球隊最短的出行里程為5.022×105km。

由于氣候等不可抗因素對賽程編排具有一定的影響，某些球隊所在城市在特定時段內不適宜做主場。以某支球隊在前3場不適宜做主場為例，在利用算法尋找最優結果之前，人為賦予該球隊主場危險標志，即默認此球隊在前3輪比賽之前已經做主場參加了3場比賽，此時在進行前3輪比賽中該球隊始終擁有優先選擇主客場的權利，此時在算法尋優過程中該球隊始終處于客場狀態，可得到在賽程前3場中此隊做客場的最優情況。通過合理使用危險標志與期望標志，可使優化的中超聯賽賽程更趨人性化設計，可有效避免一些不可抗因素對球賽的干擾，有利于球員各自水平的正常發揮。

表2 全局優化后的中超賽程安排

注:表中各個球隊均以隊名中的后2個字作為簡稱，例如“上海申鑫”簡寫為“申鑫”。

3.2 結果討論

根據中國汽車燃料消耗量網(the website of automobile fuel consumption of China)的信息可知，標準宇通55座大巴車的百公里耗油量為25 L，0號柴油5.3元/L，GB 252—2015規定0號柴油含硫量不高于0.2%(質量分數，下同)，此處按0.15%計算。相對2015年中超實際編排方案，優化后編排里程減少69 032 km，燃油量減少了14.50 t，節約資金91 467.4元，同時減少二氧化硫排放43.9 kg。實際應用中，由于出行里程縮短而使道路通暢率上升，百公里耗油量隨之降低，最終節能效果更加明顯。

根據2015-09-07人民網環保部報道，2015年上半年中國二氧化硫總體排放量為989.1萬t，機動車排放量約占總排放量的6%，即59.346×104t。由以上數據計算可知，優化后賽程編排對二氧化硫排放貢獻率由4.5×10-8減少為4.0×10-8，貢獻率減少了11.11%。因此，對賽程進行優化編排對改善空氣質量具有一定的作用。

4 模型評價

優化后的模型通過合理嵌套模擬退火算法全局尋優，可以快速尋找到中超比賽最優的主客場賽程方案和各隊的行程路線，程序簡單且可操作性強；在中超賽程下半程對陣雙方和主客場確定的情況下利用模擬退火算法優化輪次，相比于中超目前下半程輪次與上半程相同的情況而言，具有更高的實用價值。

優化后的模型通過抽簽法隨機編排位置號，智能編排減少人工干預，且充分考慮部分參賽城市因不確定因素某時段不適合做主場的情況，體現賽事的公平性和更好的人性化安排。

優化后的模型易于理解且具有很強的自適應性和推廣價值，可應用在足球、籃球和羽毛球等各類體育賽事中。

5 結 語

優化思想可為賽程編排問題提供解決方法與手段，合理優化路徑使大量無序態的賽程安排趨于有序化，通過尋求最優賽程方案使比賽更趨合理公平，并可節約資源、保護環境。與2015年中超實際賽程相比，應用該模型后比賽里程減少69 032 km，節省開支91 467.4元，燃油量減少了14.50 t，減少二氧化硫排放43.9 kg。本研究可為主客場賽程安排分析求解提供參考，并對進一步有效保護環境、提升空氣質量提供思路。

[1] 劉浩, 韓晶. MATLAB R2014a 完全自學一本通[M]. 北京:電子工業出版社, 2015.

[2] 余勝威. MATLAB優化算法案例分析與應用[M]. 北京:清華大學出版社, 2014.

[3] 吳意樂, 何慶. 基于改進遺傳模擬退火算法的WSN路徑優化算法[J]. 計算機應用研究, 2016, 33(10): 53-58.

WU Yile, HE Qing. WSN path optimization algorithm based on improved genetic simulated annealing algorithm[J]. Application Research of Computers, 2016, 33(10): 53-58.

[4] MISEVICIUS A. A modified simulated annealing algorithm for the quadratic assignment problem[J]. Informatica, 2003, 14(4):497-514.

[5] 史峰, 王輝, 郁磊, 等. MATLAB智能算法30個案例分析[M]. 北京:北京航空航天大學出版社, 2011.

[6] 趙文紅, 張紅斌. 一種改進的粒子群優化算法[J]. 河北科技大學學報, 2006, 27(4): 317-320.

ZHAO Wenhong, ZHANG Hongbin. An improved basic particle swarm optimization algorithm[J]. Journal of Hebei University of Science and Technology,2006, 27(4)：317-320.

[7] 郭亞軍. 綜合評價理論與方法[M]. 北京: 科學出版社, 2002.

[8] MANTAWY A H, ABDEL-MAGID Y L, SELIM S Z. A simulated annealing algorithm for unit commitment[J]. IEEE Transactions on Power Systems, 1998,13(1):197-204.

[9] 梁廣輝. 中超聯賽可持續發展的SWOT分析[D]. 北京: 北京體育大學, 2011.

LIANG Guanghui. SWOT Analysis of Chinese Super League of Sustainable Development[D]. Beijing: Beijing Sport University, 2011.

[10]孫士平, 吳建軍. 直接搜索模擬退火算法的自適應改進[J]. 計算機工程與應用, 2015, 51(23):31-37.

SUN Shiping, WU Jianjun. Adaptive improvement of direct search simulated annealing algorithm[J]. Computer Engineering and Applications, 2015,51(23):31-37.

[11]陳華根, 李麗華, 許惠平,等. 改進的非常快速模擬退火算法[J]. 同濟大學學報(自然科學版)，2006,34(8):1121-1125.

CHEN Huagen, LI Lihua, XU Huiping, et al. Modified very fast simulated annealing algorithm[J]. Journal of Tongji University(natural science)，2006, 34(8):1121-1125.

[12]HERSHBERGER J, SURI S, BHOSLE A M. On the difficulty of some shortest path problems[J].ACM Transactions on Algorithms, 2007, 2607(1):343-354.

[13]CLERC M, KENNEDY J. The particle swarm-explosion, stability and convergence in a multidimensional complex space[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(1): 58-73.

[14]胡運權. 運籌學基礎及應用[M]. 北京：高等教育出版社, 2008.

[15]吳受章. 最優控制理論與應用[M]. 北京：機械工業出版社, 2008.

[16]胡大偉, 朱志強, 胡勇. 車輛路徑問題的模擬退火算法[J]. 中國公路學報，2006, 19(4): 123-126.

HU Dawei, ZHU Zhiqiang, HU Yong. Simulated annealing algorithm of vehicle routing problem[J]. China Journal of Highway and Transport,2006, 19(4):123-126.

[17]MEISSNER M, SCHMUKER M, SCHNEIDER G. Optimized particle swarm optimization (OPSO) and its application to artificial neural network training[J]. BMC Bioinformatics, 2006(7): 125-135.

[18]陸平靜, 李寶, 易任嬌, 等. 一種基于改進模擬退火算法的程序性能優化參數搜索算法[J]. 計算機工程與科學, 2015, 37(7): 1227-1232.

LU Pingjing, LI Bao, YI Renjiao,et al. An improved simulated annealing algorithm for program optimization parameters search[J]. Computer Engineering and Science, 2015, 37(7):1227-1232.

[19]陳華根，吳健生，王家林,等．模擬退火算法機理研究[J].同濟大學學報( 自然科學版)，2004，32(6):802-805．

CHEN Huagen, WU Jiansheng, WANG Jialin, et al. Mechanism study of simulated annealing algorithm[J]. Journal of Tongji University(Natural Science)， 2004, 32(6):802-805.

[20]張銀蒲. 遺傳算法在組播路由優化中的應用[J]. 河北科技大學學報, 2011,32(3):261-264.

ZHANG Yinpu. Application of genetic algorithm to optimization of multicast routing[J]. Journal of Hebei University of Science and Technology, 2011,32(3):261-264.

Study of Chinese Super League schedule optimization based on simulated annealing algorithm

LIU Baoyou, WANG Tao, MA Yanlong

(School of Environmental Science and Engineering, Hebei University of Science and Technology, Shijiazhuang, Hebei 050018, China)

To optimizethe scheduleof Chinese Super League by establishing the mathematical model can not onlypromotefairness, obtain the humanization designation, but also achieve the aim of savingmileages, resources and protecting environment effectively.Assuming the distance between any two cities was the Baidu map of direct distance, promoting fairness and humanization as well as pursuing the shortest mileage. Wholetraveling distance of 2015 Chinese Super League schedule was optimized based on the improved simulated annealing algorithm and the model was established by Matlab. The results indicated that the whole traveling distance of optimized tournament is 5.022×105km, which reduced 12.08% compared with that of actual schedule of 2015 Chinese Super League. Furthermore, 14.5 tons of fuel can be saved, 43.9 kg of sulfur dioxide emissions can be reduced, SO2contribution can be reduced to 11.11% and 91 467.4 yuan can be saved in the optimized designation.

environmental planning and management; Chinese Super League schedule; simulated annealing algorithm; optimization; cooling schedule

1008-1542(2016)05-0497-06

10.7535/hbkd.2016yx05011

2016-03-10；

2016-04-08；責任編輯：王海云

劉寶友(1973—)，男，河北盧龍人，教授，博士，主要從事綠色化學、環境規劃與管理方面的研究。

E-mail:lby7150@sina.com

X32;O224;TP301.6

A

劉寶友，王 濤，馬延龍.基于模擬退火算法的中超賽程編排優化研究[J].河北科技大學學報,2016,37(5):497-502.

LIU Baoyou, WANG Tao, MA Yanlong.Study of Chinese Super League schedule optimization based on simulated annealing algorithm[J].Journal of Hebei University of Science and Technology,2016,37(5):497-502.