< Back to previous page
Project
Sports scheduling.
Sport is de voorbije jaren big business geworden. In het Belgisch voetbal wordt er dit jaar opnieuw onderhandeld met Belgacom TV, nu het huidige contract van 12 miljoen euro per jaar voor de uitzendrechten afloopt. In de V.S. worden veelvouden van dit bedrag betaald voor o.a. baseball (>500 miljoen dollar) en basketbal (>600 miljoen dollar). Zelfs die bedragen zijn een peulschil in vergelijking met het budget van 20 miljard dollar voor de Olympische Spelen in Peking, die voor de deur staan. De economische impact van de Spelen op China (en de rest van de wereld) is allicht nog vele malen groter. Het plannen van sportcompetities heeft de voorbije jaren dan ook enorm aan belang gewonnen. De planning van de competitie is een belangrijke taak voor de organisatoren, niet alleen omdat het de resultaten van de wedstrijden zelf kan beïnvloeden, maar ook omdat het een aanzienlijke invloed heeft op de publieke belangstelling en daarmee samenhangend de winstgevendheid van het evenement. Bedrijven die hoge bedragen hebben neergeteld voor uitzendrechten willen immers een kalender die aantrekkelijk is en zoveel mogelijk kijkers of luisteraars weet te bekoren, wat ook voor adverteerders van groot belang is. De mate waarin de organisatoren kunnen tegemoet komen aan de wensen van de media zal een niet geringe invloed hebben op het financiële plaatje. In veel competities heeft de media belang bij een kalender die poogt de competitie spannend te houden tot het einde, zodat de aantrekkingskracht van de competitie op het publiek zo groot mogelijk is. Ook de clubs zelf zien graag een kalender die ervoor zorgt dat ze veel toeschouwers over de vloer krijgen, maar hebben ook sportieve zorgen. Een kalender moet immers fair zijn voor alle deelnemende clubs en mag dus a priori niemand benadelen. Tenslotte wordt ook vaak een beroep gedaan op de overheid om de veiligheid voor de toeschouwers van sportwedstrijden te garanderen. Het spreekt dan ook vanzelf dat een goede kalender onder andere rekening houdt met de beschikbaarheid van politiediensten. Het plannen van een sportcompetitie is dus steeds een afwegen van (veelal tegenstrijdige) economische, sportieve, en veiligheidsaspecten, afkomstig van meerdere betrokken partijen. Doel van het onderzoek Vooraleer begonnen kan worden met het opstellen van een kalender, moet er een beslissing genomen worden over het formaat van de competitie. Hoewel er in dit onderzoeksvoorstel gefocust wordt op round robin tornooien, blijven ook binnen deze categorie nog veel keuzemogelijkheden open, zoals het aantal onderlinge ontmoetingen, het al dan niet spelen van play-offs na afloop van de reguliere competitie, het aantal deelnemers aan de competitie, het aantal degradanten, etc. Elk van deze beslissingen kan een grote invloed hebben op de spankracht en het resultaat van de competitie, en het belang van de individuele wedstrijden. Het is onder meer de bedoeling om in dit onderzoek die invloeden in kaart te brengen, teneinde een gemotiveerde keuze voor een competitieopzet te kunnen maken.
Het plannen van de kalender voor een sportcompetitie die zoveel mogelijk tegemoet komt aan de wensen van alle betrokken partijen is een combinatorisch probleem. Men zou in principe alle mogelijke kalenders kunnen overlopen en er de beste uit kiezen. Zelfs voor heel kleine instanties blijkt dit echter ondoenbaar. In veel sporten (bv. voetbal, hockey, basketbal) komt het plannen van de competitie neer op het uitwerken van een zogenaamd (enkel) round robin tornooi, waar elke ploeg precies één keer tegen elke andere ploeg speelt, of een dubbel round robin tornooi, waar elke ploeg twee keer tegen elke andere ploeg speelt. Het opstellen van een kalender voor een round robin tornooi is op zich eenvoudig. Van zodra er echter extra beperkingen worden opgelegd, zelfs al zijn die van een eenvoudige vorm zoals ploeg x mag niet spelen tegen ploeg y op dag d, wordt het probleem echter moeilijk ([11]). Een aantal andere beperkingen die vaak voorkomen zijn ([7]): plaatsbeperkingen: een ploeg moet thuis of uit spelen op een bepaalde dag complementariteitsbeperkingen: als twee ploegen een stadion delen moet ervoor gezorgd worden dat ze niet op het zelfde moment in hun stadion spelen separatiebeperkingen: in competities waar een ploeg een andere ploeg meer dan eens ontmoet moet er voldoende tijd tussen twee ontmoetingen met dezelfde ploeg zitten. geografische beperkingen: om te vermijden dat alle wedstrijden in eenzelfde klein gebied gespeeld worden, wordt er een geografische spreiding van de wedstrijden opgelegd. In de literatuur zijn een groot aantal voorbeelden uit de praktijk te vinden van tornooien, waarvoor men geprobeerd heeft een kalender op te stellen die voldoet aan een aantal beperkingen van uiteenlopende aard. Dit is onder meer gebeurd voor basketbal ([6]), voetbal ([1], [5], [8]), cricket ([12]) en baseball ([10]). In dit onderzoek zal worden gestreefd naar het ontwikkelen van methoden die toelaten om een kalender op te stellen die door de betrokken clubs als fair wordt aanzien, die tegemoet komt aan sportieve en economische eisen, en ook de veiligheidsvereisten in acht neemt. Bovendien willen wij de traditionele aanpak in de literatuur, die erg probleemspecifiek is, proberen te overstijgen via een model dat toelaat gewichten te plakken op een breed scala van wensen, om dan die kalender te bekomen die voor een zo klein mogelijk totaal gewicht aan wensen schendt. Bij het opstellen van een kalender wordt er vaak aangenomen dat de opeenvolging van tegenstanders bepalend is voor het uiteindelijke resultaat, of dat met andere woorden de wedstrijden niet onafhankelijk van elkaar zijn. In dat opzicht is het voor een ploeg A niet zonder belang tegen welke ploeg C zijn tegenstander B gespeeld heeft in de ronde net voor de wedstrijd tussen A en B. Immers, als B zou verliezen van C, kan A spelen tegen een tegenstander die wellicht verzwakt of met minder vertrouwen aan de start van de wedstrijd komt. Omgekeerd kan A het bij winst van B net moeilijker krijgen, omdat B dan in een winning mood zou kunnen zitten. Men zou dus kunnen zeggen dat ploeg C een effect heeft op het resultaat van A. Hoewel dit effect door trainers al geopperd is als oorzaak van het slecht presteren van een ploeg ([4]), is het nog nooit onderzocht of dit effect in de praktijk bestaat, laat staan hoe belangrijk het is. Wel is er al onderzoek gebeurd naar kalenders die dit effect zoveel mogelijk gelijk spreiden over alle ploegen in de competitie (zie bij voorbeeld [9]). In het algemeen is er nood aan een studie waar uitgezocht wordt of zaken die vaak aangehaald worden met betrekking tot de fairness van een kalender, ook daadwerkelijk een invloed hebben op het resultaat van een competitie. In sommige gevallen moet bij het plannen van een sportcompetitie ook rekening gehouden worden met de afstanden die moeten afgelegd worden door de deelnemende ploegen, teneinde hun wedstrijden te kunnen afwerken. Het doel is dan een (dubbel) round robin tornooi op te stellen zodat de totale gereisde afstand van alle ploegen minimaal is, rekening houdend met een maximaal toegelaten opeenvolgende uit- of thuiswedstrijden. Dit probleem staat bekend als het travelling tournament probleem en komt onder meer voor in de Amerikaanse National Hockey League ([2]). Afstanden zijn ook van belang bij het toewijzen van scheidsrechters aan wedstrijden. Toch is het vaak geen oplossing om gewoon de reisafstanden te minimaliseren, omdat dan een scheidsrechter steeds voor eenzelfde ploeg aangeduid zal worden, wat fair noch wenselijk is. Het toewijzen van scheidsrechters werd onder meer onderzocht voor voetbal ([3]). Motivatie Het valt niet te ontkennen dat sport op veel mensen een enorme aantrekkingskracht heeft. Sport is vaak een manier om mensen dichter bij elkaar te brengen; het maatschappelijk belang van sport kan dan ook moeilijk overschat worden. In zowat elke sporttak is er nood aan een degelijke competitieplanning, of het nu over een topsporter op de Olympische Spelen gaat die zijn medaillekansen zo gaaf mogelijk wil houden, of een recreatieve tennisvereniging die zijn velden zo goed mogelijk wil benutten, of de verplaatsingskosten voor zijn leden zo beperkt mogelijk wil houden. Niet alleen omwille van het frequent voorkomen in de praktijk, maar ook omwille van een aantal theoretische kwesties heeft het plannen van sport competities, en round robin tornooien in het bijzonder, zijn plaats binnen de wetenschappelijke wereld. Eén probleem behelst bijvoorbeeld het vinden van het minimale aantal breaks, of het aantal keer dat een ploeg een opeenvolging heeft van thuis- of uitwedstrijden. Een reeks van thuis- of uitaanduidingen voor een team is wat men noemt een patroon. Een ander open probleem is het zoeken van voldoende voorwaarden waaraan een set van patronen moet voldoen om er een geldig round robin tornooi uit te kunnen genereren. Een andere uitdaging is om dat round robin tornooi dan ook effectief op te stellen. De complexiteit van de vraag of het mogelijk is een round robin tornooi op te stellen gegeven een aantal patronen is na jaren onderzoek nog steeds niet duidelijk. Aanpak en methoden Voor het bepalen van het effect van de competitieopzet op de spankracht en het resultaat van de competitie zien wij heil in een nieuwe norm ter evaluatie van het belang van een wedstrijd. Als we aannemen dat een wedstrijd voor een ploeg nog van belang is, als door het winnen van een wedstrijd een bepaalde doelstelling nog gehaald zou kunnen worden, kunnen we met een IP model het belang van een wedstrijd na gaan. Dit maakt een vergelijking van verschillende competitievormen mogelijk met behulp van simulatie. Wat betreft het opstellen van een kalender voor een sportcompetitie, vinden we in de literatuur een grote diversiteit aan gebruikte methoden terug. Een aantal competities zijn gepland aan de hand van exacte methoden ([5],[6]), maar gezien de complexiteit van het probleem worden ook vaak metaheuristieken gebruikt ([2], [12]). Bij het plannen van de Belgische voetbalkalender is gebleken dat het probleem vereenvoudigd moet worden om in een redelijke tijd oplosbaar te zijn. We hebben aanwijzingen dat het opsplitsen van het probleem in meerdere fases toelaat om betere oplossingen te vinden. Een eerste fase zou kunnen zijn om het patroon van de clubs vast te leggen, terwijl in een tweede fase beslist wordt over de eigenlijke tegenstanders, gegeven dit patroon. Bovendien zouden we graag uitzoeken hoe de gevonden oplossing in fase 2 kan gebruikt worden om het zoekproces in fase 1 te sturen in de richting van een betere oplossing, bijvoorbeeld met een lokaal zoekalgoritme. Een omgeving in een dergelijk lokaal zoekalgoritme zou dan kunnen bestaan uit de kalenders die men kan bekomen door patronen van 2 of meer ploegen om te wisselen of door andere patronen te vervangen. Referenties [1] T. Bartsch, A. Drexl & S. Kroger (2006). Scheduling the professional soccer leagues of Austria and Germany. Computers and Operations Research, 33:1907-1937. [2] D. Costa (1995). An evolutionary tabu search algorithm and the NHL scheduling problem. Information Systems and Operational Research, 33:161-178. [3] A.R. Duarte, C.C. Ribeiro & S. Urrutia (2006). Referee assignment in sports tournaments. Proceedings of the 6th International Conference on the Practice and Theory of Automated Timetabling (PATAT' 06), Brno (Czech Republic), pp. 394-397. [4] J. Geril (2007). Ons budget voor transfers? Nul komma nul euro. Het Nieuwsblad, February 2nd, 2007, VUM. [5] D. Goossens, F. Spieksma (2006). Scheduling the Belgian soccer league, Proceedings of the 6th International Conference on the Practice and Theory of Automated Timetabling (PATAT), Brno (Czech Republic), pp. 420-422. [6] M. Henz (2001). Scheduling a major college basketball conference revisited. Operations Reserach, 49:163-168. [7] R. Rasmussen & M. Trick (2006). Round robin scheduling a survey. Working paper 2006/2, Department of Operations Research, University of Aarhus. [8] C.C. Ribeiro e S. Urrutia (2006). Scheduling the Brazilian soccer championship. Proceedings of the 6th International Conference on the Practice and Theory of Automated Timetabling (PATAT' 06), Brno (Czech Republic), pp. 481-483. [9] K.G. Russell (1980). Balancing carry-over effects in round robin tournaments. Biometrika 67(1):127-131. [10] R.A. Russell & J.M. Leung (1994). Devising a cost effective schedule for a baseball league. Operations Research, 42:614-625. [11] A. Schaerf (1999). Scheduling sport tournaments using constraint logic programming. Constraints, 4:4365. [12] M. Wright (1994). Timetabling county cricket fixtures using a form of tabu search. Journal of the Operations Research Society, 45:758-770.
Het plannen van de kalender voor een sportcompetitie die zoveel mogelijk tegemoet komt aan de wensen van alle betrokken partijen is een combinatorisch probleem. Men zou in principe alle mogelijke kalenders kunnen overlopen en er de beste uit kiezen. Zelfs voor heel kleine instanties blijkt dit echter ondoenbaar. In veel sporten (bv. voetbal, hockey, basketbal) komt het plannen van de competitie neer op het uitwerken van een zogenaamd (enkel) round robin tornooi, waar elke ploeg precies één keer tegen elke andere ploeg speelt, of een dubbel round robin tornooi, waar elke ploeg twee keer tegen elke andere ploeg speelt. Het opstellen van een kalender voor een round robin tornooi is op zich eenvoudig. Van zodra er echter extra beperkingen worden opgelegd, zelfs al zijn die van een eenvoudige vorm zoals ploeg x mag niet spelen tegen ploeg y op dag d, wordt het probleem echter moeilijk ([11]). Een aantal andere beperkingen die vaak voorkomen zijn ([7]): plaatsbeperkingen: een ploeg moet thuis of uit spelen op een bepaalde dag complementariteitsbeperkingen: als twee ploegen een stadion delen moet ervoor gezorgd worden dat ze niet op het zelfde moment in hun stadion spelen separatiebeperkingen: in competities waar een ploeg een andere ploeg meer dan eens ontmoet moet er voldoende tijd tussen twee ontmoetingen met dezelfde ploeg zitten. geografische beperkingen: om te vermijden dat alle wedstrijden in eenzelfde klein gebied gespeeld worden, wordt er een geografische spreiding van de wedstrijden opgelegd. In de literatuur zijn een groot aantal voorbeelden uit de praktijk te vinden van tornooien, waarvoor men geprobeerd heeft een kalender op te stellen die voldoet aan een aantal beperkingen van uiteenlopende aard. Dit is onder meer gebeurd voor basketbal ([6]), voetbal ([1], [5], [8]), cricket ([12]) en baseball ([10]). In dit onderzoek zal worden gestreefd naar het ontwikkelen van methoden die toelaten om een kalender op te stellen die door de betrokken clubs als fair wordt aanzien, die tegemoet komt aan sportieve en economische eisen, en ook de veiligheidsvereisten in acht neemt. Bovendien willen wij de traditionele aanpak in de literatuur, die erg probleemspecifiek is, proberen te overstijgen via een model dat toelaat gewichten te plakken op een breed scala van wensen, om dan die kalender te bekomen die voor een zo klein mogelijk totaal gewicht aan wensen schendt. Bij het opstellen van een kalender wordt er vaak aangenomen dat de opeenvolging van tegenstanders bepalend is voor het uiteindelijke resultaat, of dat met andere woorden de wedstrijden niet onafhankelijk van elkaar zijn. In dat opzicht is het voor een ploeg A niet zonder belang tegen welke ploeg C zijn tegenstander B gespeeld heeft in de ronde net voor de wedstrijd tussen A en B. Immers, als B zou verliezen van C, kan A spelen tegen een tegenstander die wellicht verzwakt of met minder vertrouwen aan de start van de wedstrijd komt. Omgekeerd kan A het bij winst van B net moeilijker krijgen, omdat B dan in een winning mood zou kunnen zitten. Men zou dus kunnen zeggen dat ploeg C een effect heeft op het resultaat van A. Hoewel dit effect door trainers al geopperd is als oorzaak van het slecht presteren van een ploeg ([4]), is het nog nooit onderzocht of dit effect in de praktijk bestaat, laat staan hoe belangrijk het is. Wel is er al onderzoek gebeurd naar kalenders die dit effect zoveel mogelijk gelijk spreiden over alle ploegen in de competitie (zie bij voorbeeld [9]). In het algemeen is er nood aan een studie waar uitgezocht wordt of zaken die vaak aangehaald worden met betrekking tot de fairness van een kalender, ook daadwerkelijk een invloed hebben op het resultaat van een competitie. In sommige gevallen moet bij het plannen van een sportcompetitie ook rekening gehouden worden met de afstanden die moeten afgelegd worden door de deelnemende ploegen, teneinde hun wedstrijden te kunnen afwerken. Het doel is dan een (dubbel) round robin tornooi op te stellen zodat de totale gereisde afstand van alle ploegen minimaal is, rekening houdend met een maximaal toegelaten opeenvolgende uit- of thuiswedstrijden. Dit probleem staat bekend als het travelling tournament probleem en komt onder meer voor in de Amerikaanse National Hockey League ([2]). Afstanden zijn ook van belang bij het toewijzen van scheidsrechters aan wedstrijden. Toch is het vaak geen oplossing om gewoon de reisafstanden te minimaliseren, omdat dan een scheidsrechter steeds voor eenzelfde ploeg aangeduid zal worden, wat fair noch wenselijk is. Het toewijzen van scheidsrechters werd onder meer onderzocht voor voetbal ([3]). Motivatie Het valt niet te ontkennen dat sport op veel mensen een enorme aantrekkingskracht heeft. Sport is vaak een manier om mensen dichter bij elkaar te brengen; het maatschappelijk belang van sport kan dan ook moeilijk overschat worden. In zowat elke sporttak is er nood aan een degelijke competitieplanning, of het nu over een topsporter op de Olympische Spelen gaat die zijn medaillekansen zo gaaf mogelijk wil houden, of een recreatieve tennisvereniging die zijn velden zo goed mogelijk wil benutten, of de verplaatsingskosten voor zijn leden zo beperkt mogelijk wil houden. Niet alleen omwille van het frequent voorkomen in de praktijk, maar ook omwille van een aantal theoretische kwesties heeft het plannen van sport competities, en round robin tornooien in het bijzonder, zijn plaats binnen de wetenschappelijke wereld. Eén probleem behelst bijvoorbeeld het vinden van het minimale aantal breaks, of het aantal keer dat een ploeg een opeenvolging heeft van thuis- of uitwedstrijden. Een reeks van thuis- of uitaanduidingen voor een team is wat men noemt een patroon. Een ander open probleem is het zoeken van voldoende voorwaarden waaraan een set van patronen moet voldoen om er een geldig round robin tornooi uit te kunnen genereren. Een andere uitdaging is om dat round robin tornooi dan ook effectief op te stellen. De complexiteit van de vraag of het mogelijk is een round robin tornooi op te stellen gegeven een aantal patronen is na jaren onderzoek nog steeds niet duidelijk. Aanpak en methoden Voor het bepalen van het effect van de competitieopzet op de spankracht en het resultaat van de competitie zien wij heil in een nieuwe norm ter evaluatie van het belang van een wedstrijd. Als we aannemen dat een wedstrijd voor een ploeg nog van belang is, als door het winnen van een wedstrijd een bepaalde doelstelling nog gehaald zou kunnen worden, kunnen we met een IP model het belang van een wedstrijd na gaan. Dit maakt een vergelijking van verschillende competitievormen mogelijk met behulp van simulatie. Wat betreft het opstellen van een kalender voor een sportcompetitie, vinden we in de literatuur een grote diversiteit aan gebruikte methoden terug. Een aantal competities zijn gepland aan de hand van exacte methoden ([5],[6]), maar gezien de complexiteit van het probleem worden ook vaak metaheuristieken gebruikt ([2], [12]). Bij het plannen van de Belgische voetbalkalender is gebleken dat het probleem vereenvoudigd moet worden om in een redelijke tijd oplosbaar te zijn. We hebben aanwijzingen dat het opsplitsen van het probleem in meerdere fases toelaat om betere oplossingen te vinden. Een eerste fase zou kunnen zijn om het patroon van de clubs vast te leggen, terwijl in een tweede fase beslist wordt over de eigenlijke tegenstanders, gegeven dit patroon. Bovendien zouden we graag uitzoeken hoe de gevonden oplossing in fase 2 kan gebruikt worden om het zoekproces in fase 1 te sturen in de richting van een betere oplossing, bijvoorbeeld met een lokaal zoekalgoritme. Een omgeving in een dergelijk lokaal zoekalgoritme zou dan kunnen bestaan uit de kalenders die men kan bekomen door patronen van 2 of meer ploegen om te wisselen of door andere patronen te vervangen. Referenties [1] T. Bartsch, A. Drexl & S. Kroger (2006). Scheduling the professional soccer leagues of Austria and Germany. Computers and Operations Research, 33:1907-1937. [2] D. Costa (1995). An evolutionary tabu search algorithm and the NHL scheduling problem. Information Systems and Operational Research, 33:161-178. [3] A.R. Duarte, C.C. Ribeiro & S. Urrutia (2006). Referee assignment in sports tournaments. Proceedings of the 6th International Conference on the Practice and Theory of Automated Timetabling (PATAT' 06), Brno (Czech Republic), pp. 394-397. [4] J. Geril (2007). Ons budget voor transfers? Nul komma nul euro. Het Nieuwsblad, February 2nd, 2007, VUM. [5] D. Goossens, F. Spieksma (2006). Scheduling the Belgian soccer league, Proceedings of the 6th International Conference on the Practice and Theory of Automated Timetabling (PATAT), Brno (Czech Republic), pp. 420-422. [6] M. Henz (2001). Scheduling a major college basketball conference revisited. Operations Reserach, 49:163-168. [7] R. Rasmussen & M. Trick (2006). Round robin scheduling a survey. Working paper 2006/2, Department of Operations Research, University of Aarhus. [8] C.C. Ribeiro e S. Urrutia (2006). Scheduling the Brazilian soccer championship. Proceedings of the 6th International Conference on the Practice and Theory of Automated Timetabling (PATAT' 06), Brno (Czech Republic), pp. 481-483. [9] K.G. Russell (1980). Balancing carry-over effects in round robin tournaments. Biometrika 67(1):127-131. [10] R.A. Russell & J.M. Leung (1994). Devising a cost effective schedule for a baseball league. Operations Research, 42:614-625. [11] A. Schaerf (1999). Scheduling sport tournaments using constraint logic programming. Constraints, 4:4365. [12] M. Wright (1994). Timetabling county cricket fixtures using a form of tabu search. Journal of the Operations Research Society, 45:758-770.
Date:1 Oct 2008 → 31 Oct 2013
Keywords:Sports scheduling