Fair-fixture: Minimizing carry-over effects in football leagues

Dilek Günneç; Ezgi Demir

doi:10.3934/jimo.2018110

Article Contents

2019, Volume 15, Issue 4: 1565-1577. Doi: 10.3934/jimo.2018110

This issue Previous Article CP and MIP approaches for soccer analysis Next Article Optimal pricing of perishable products with replenishment policy in the presence of strategic consumers

Fair-fixture: Minimizing carry-over effects in football leagues

Dilek Günneç^1, , and
Ezgi Demir^2,

1.
Department of Industrial Engineering, Özyeğin University, Istanbul, 34794, Turkey
2.
BSH Home Appliances Corporation, Istanbul, 34771, Turkey

* Corresponding author: Dilek Günneç
* Corresponding author: Dilek Günneç

Received: December 2016

Revised: January 2018

Early access: July 2018

Published: July 2019

Abstract / Introduction Full Text(HTML) Figure(0) / Table(7) Related Papers Cited by

Abstract

We study a sports scheduling problem with the objective of minimizing carry-over effects in round robin tournaments.In the first part, focusing on tournaments that allow minimum number of breaks (at most one) for each team, we formulate an integer programming model and provide an efficient heuristic algorithm to solve this computationally expensive problem. We apply the algorithm to the current Turkish Professional Football League and present an alternative scheduling template. In the second part, we discuss how the carry-over effects can be further decreased if the number of breaks is allowed to be of slightly larger value and numerically represent this trade-off.

Keywords:

Mathematics Subject Classification: Primary: 80M50; Secondary: 90C27.

Citation:

Full Text(HTML)

Table 1. Pattern set for a league of 8 teams

		Week
		1	2	3	4	5	6	7
Pattern	1	A	H	A	H	A	H	A
	2	A	H	H	A	H	A	H
	3	A	H	A	A	H	A	H
	4	A	H	A	H	H	A	H
	5	A	H	A	H	A	A	H
	6	H	A	H	A	H	A	H
	7	H	A	A	H	A	H	A
	8	H	A	H	H	A	H	A
	9	H	A	H	A	A	H	A
	10	H	A	H	A	H	H	A

| Show Table

DownLoad: CSV

Table 2. Coe values of TPFL between 2012 and 2016

Season	Coe
2012-13	3666
2013-14	3818
2014-15	3707
2015-16	3820
Average	3752.75

| Show Table

DownLoad: CSV

Table 3. Results of our heuristic

Number of teams	Coe Value (1-Break)	Time (min)
8	104	0.20
10	192	0.44
12	318	2.73
14	446	2.73
16	626	6.30
18	944	23.90

| Show Table

DownLoad: CSV

Table 4. Coe values and number of breaks for the heuristic with the BRK model. ($n = 18$)

Break (Each)	Random		Canonical		TPFL
Break (Each)	Coe	Break	Coe	Break	Coe	Break
$x=1$	944	16	3876	16	3707	16
$1\leq x \leq2$	650	31	698	29	580	32
$2\leq x \leq3$	544	45	502	42	466	45
$2\leq x \leq4$	544	45	502	42	466	45

| Show Table

DownLoad: CSV

Table 5. Coe values and number of breaks when break distribution among teams is not considered

Break (Each)	10 Teams		12 Teams		14 Teams		16 Teams		18 Teams
Break (Each)	Coe	Break	Coe	Break	Coe	Break	Coe	Break	Coe	Break
$x \leq 1$	192	8	318	10	446	12	626	14	944	16
$x \leq 2$	144	12	212	18	344	26	472	30	646	30
$x \leq 3$	144	12	212	16	302	24	396	34	556	40

| Show Table

DownLoad: CSV

Table 6. Comparison of our heuristic with three real league schedules for season 2015-16

	Num. of teams	Coe	Breaks (Each)	Break	Coe (H)	Break (H)	Decrease (%)
Czech Rep.	16	742	$x=1$	16	626	14	15.63
Germany	18	1056	$0\leq x \leq1$	16	944	16	10.60
France	20	719	$0\leq x \leq4$	45	530	56	26.28

| Show Table

DownLoad: CSV

Table 7. Template for an 18-team league

Week 1	Week 2	Week 3	Week 4	Week 5	Week 6	Week 7	Week 8	Week 9
1-11	18-1	1-8	12-1	1-14	2-1	1-17	4-1	1-5
6-2	2-7	16-2	2-9	3-2	8-3	15-2	2-11	18-2
3-14	12-3	3-13	10-3	7-4	4-6	3-4	5-3	3-17
17-4	4-5	9-4	4-16	6-5	5-9	16-5	7-6	15-4
5-10	13-6	17-5	5-7	9-8	17-7	6-8	8-18	6-9
7-13	8-17	6-12	17-6	15-10	10-11	9-7	17-9	16-7
16-8	10-9	7-10	8-15	11-13	12-15	18-10	10-16	11-8
9-12	11-15	11-18	14-11	18-12	13-16	11-12	12-14	14-10
15-18	14-16	15-14	13-18	16-17	14-18	14-13	13-15	12-13

Week 10	Week 11	Week 12	Week 13	Week 14	Week 15	Week 16	Week 17
9-1	1-7	16-1	1-6	3-1	15-1	1-10	13-1
2-13	14-2	2-12	10-2	2-8	2-5	17-2	2-4
7-3	3-6	9-3	3-16	4-13	11-3	3-15	18-3
4-18	11-4	4-14	12-4	5-12	10-4	4-8	8-5
5-11	15-5	5-18	14-5	6-14	18-6	5-13	10-6
6-16	12-8	6-15	18-7	7-15	8-7	6-11	14-7
8-14	16-9	7-11	13-8	9-18	13-9	7-12	11-9
10-12	13-10	8-10	15-9	17-10	12-16	9-14	12-17
17-15	18-17	17-13	11-17	16-11	14-17	16-18	15-16

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	I. Anderson, Balancing carry-over effects in tournaments, Chapman and Hall/CRC Research Notes in Mathematics Series, 403 (1999), 1-16.
[2]	D. De Werra, Geography, games and graphs, Discrete Applied Mathematics, 2 (1980), 327-337. doi: 10.1016/0166-218X(80)90028-1.
[3]	D. De Werra, Scheduling in sports, Studies on Graphs and Discrete Programming, 11 (1981), 381-395.
[4]	D. De Werra, L. Jacot-Descombes and P. Masson, A constrained sports scheduling problem, Discrete Applied Mathematics, 26 (1990), 41-49. doi: 10.1016/0166-218X(90)90019-9.
[5]	F. Della Croce and D. Oliveri, Scheduling the Italian football league: An ILP-based approach, Computers & Operations Research, 33 (2006), 1963-1974.
[6]	T. Flatberg, E. J. Nilssen and M. Stolevik, Scheduling the topmost football leagues of Norway, in Book of abstracts of the 23rd European Conference on Operational Research, Bonn, Germany, (2009), p240.
[7]	D. Goossens and F. Spieksma, Does the carry-over effect exist?, in Book of abstracts of the 23rd European Conference on Operational Research, Bonn, Germany, (2009), p288.
[8]	D. Goossens and F. Spieksma, Soccer schedules in Europe: An overview, Journal of Scheduling, 15 (2012), 641-651.
[9]	A. Guedes and C. Ribeiro, A heuristic for minimizing weighted carry-over effects in round robin tournaments, Journal of Scheduling, 14 (2011), 655-667. doi: 10.1007/s10951-011-0244-y.
[10]	M. Henz, Scheduling a major college basketball conference-revisited, Operations Research, 49 (2001), 163-168. doi: 10.1287/opre.49.1.163.11193.
[11]	M. P. Kidd, A tabu-search for minimising the carry-over effects value of a round-robin tournament, Journal of the Operations Research Society of South Africa, 26 (2010), 125-141. doi: 10.5784/26-2-91.
[12]	E. Lambrechts, A. M. C. Ficker, D. Goossens and F. Spieksma, Round-robin tournaments generated by the circle method have maximum carry-over, Proceedings of the International Conference on Integer Programming and Combinatorial Optimization, 9682 (2016), 178-189. doi: 10.1007/978-3-319-33461-5_15.
[13]	R. Miyashiro and T. Matsui, Minimizing the carry-over effects value in a round robin tournament, Proceedings of the International Conference on the Practice and Theory of Automated Timetabling, (2006), 460-463.
[14]	M. C. Roboredo, L. Aizemberg, A. A. Pessoa and J. C. Mello, Scheduling the Brazilian football league minimizing extended carry-over effects associated to strength groups, Engevista, 16 (2014), 102-110.
[15]	K. G. Russell, Balancing carry-over effects in round robin tournaments, Biometrika, 67 (1980), 127-131. doi: 10.1093/biomet/67.1.127.
[16]	M. Trick, A schedule-then-break approach to sports timetabling, in Proceedings of the International Conference on the Practice and Theory of Automated Timetabling, (2000), 242-253. doi: 10.1007/3-540-44629-X_15.