Varje år producerar de engelska fotbollsmyndigheterna en uppsättning fixturer för de fyra huvudavdelningarna i England. Under jul- och nyårsperioden måste varje lag spela två fixturer; den ena spelas på deras hemmaplats och den andra på en motståndares plats. Det finns olika andra begränsningar som också måste respekteras med det övergripande målet att minimera det totala avstånd som tillryggalagts av alla lag. I detta dokument definierar jag formellt problemet, diskuterar den datainsamling som jag har genomfört och presenterar algoritmen (som är baserad på djup första sökning, följt av en lokal sökning) Jag har utvecklat. Med hjälp av data från fyra säsonger, visar jag att jag kan producera bättre scheman än de som för närvarande används. Fotboll (kallas fotboll i USA) är det nationella spelet i England. Det finns fyra huvudavdelningar (se bilaga A för de huvudsakliga termer jag använder i detta dokument) som de flesta skulle anse utgöra den "engelska fotbollsligan". Dessa divisioner förvaltas av tre organ, Football Association (FA), Premier League och Football League. Fotbollsföreningen (http://www.thefa.com, senast tillgänglig den 13 mars 2006) är det styrande organet i spelet med ett viktigt mål att utveckla idrotten på alla nivåer. Premier League (http://www.premierleague.com, senast nås den 13 mars 2006), bildades i maj 1992 för att främja den främsta uppdelningen av spelet, har kommersiell självständighet från Football Association och Football League och kan förhandla om sina egna sändnings- och sponsringsavtal. Fotbollsförbundet (http://www.football-league.co.uk, senast tillträtt den 13 mars 2006) tillhandahåller domare för fixturer, producerar fixturprogrammet, administrerar överföringssystemet och letar efter sätt att generera extra intäkter för sina medlemsklubbar. För säsongen [2005][2006] var de fyra största divisionerna kända som "Barclays Premiership", "Coca-Cola Championship", * Korrespondens: G Kendall, School of Computer Science and IT, University of Nottingham, Jubilee Campus, Wollaton Road, Nottingham, Notts NG8 1BB, "Coca-Cola League One" och "Coca-Cola League Two". Namnen på divisionerna ändras i linje med sponsorarrangemangen. Barclays Premiership består av 20 lag, med de andra tre divisionerna vardera med 24 lag. Varje division är fristående, genom att de håller sin egen dubbel runda Robin turnering. Det totala antalet fixturer spelas i Barclays Premiership är 380, med 552 fixturer spelas i de andra tre divisioner, vilket ger totalt 2036 fixturer som måste schemaläggas under en viss säsong. För att producera den nödvändiga dubbel round robin turnering för varje division, kunde jag använda algoritmer hämtade från litteraturen, med en av de vanligaste är polygon konstruktionsmetod (Dinitz et al, 2007). Det är dock osannolikt att denna metod kommer att ta fram en fixturlista som är godtagbar för alla berörda parter (som inkluderar fotbollsmyndigheterna, fotbollsklubbarna, supportrarna, polisen osv.) eftersom algoritmen inte tillgodoser alla de verkliga krav som utgör en godtagbar uppsättning fixturer. Till exempel, parning systemet (se avsnittet Problem Definition) fungerar över divisioner, så att fixturer i en division inte kan schemaläggas utan hänvisning till de andra divisionerna. Ett annat verkligt krav, som inte fångas av metoder som polygon konstruktion, uppstår när schemaläggning fixturer över semesterperioder. Perioden runt jul är en särskilt hektisk tid, med lag som spelar minst två gånger. De datum då fixturerna äger rum under denna period skiljer sig från år till år, och det kan finnas mer än två fixturer för varje lag. Det är dock alltid så att varje lag kommer att spela två relaterade fixturer, med dessa fixturer måste följa den uppsättning begränsningar som diskuteras nedan (Problem Definition avsnitt och i bilaga B). Med tanke på de särskilda kraven för dessa två fixturer, är det vanligt att schemalägga dem först och sedan generera resten av schemat runt dem. Syftet med detta dokument är att undersöka om vi kan skapa fixturer, för dessa två dagar, som följer de olika begränsningarna, men har resor avstånd som är mindre än avstånden för de fixturer som produceras av fotbollsmyndigheterna (Jag hänvisar till de fixturlistor som produceras av fotbollsmyndigheterna som publicerade fixturer). Observera att jag kommer att hänvisa till den första fixturlistan som Boxing Day (26:e december) fixturer och den andra fixturlistan som nyårsdagen (1:a januari) fixturer. Som framgår av tabell 1, är fixturer inte alltid spelas på dessa två datum men det är bekvämt att hänvisa till dem på detta sätt. Detta dokument är organiserat enligt följande. I nästa avsnitt presenterar jag relaterat arbete när det gäller sportplanering. Därefter beskriver jag informellt problemet (en formell definition ges i bilaga B). Efter detta presenterar jag de uppgifter som jag har använt. Därefter beskriver jag det algoritmiska tillvägagångssätt som jag använder. Slutligen visar jag resultaten och sedan presenterar jag mina slutsatser och föreslår framtida riktlinjer för forskning på detta område. Det finns en hel del arbete som har övervägt minimering av resor avstånd för sport scheman. Costa (1995), till exempel, undersökte schemaläggningskraven i National Hockey League, där en av faktorerna var att minimera de tillryggalagda avstånden. Införandet av Travelling Tournament Problem (Easson et al, 2001), med hjälp av avstånd baserade på de road resor som måste genomföras av Major League Baseball lag i USA, har bidragit till att främja forskning intresse för att hitta kortast resavstånd. Easton et al införde ursprungligen sju fall, som innehåller 4, 6, 8, 10, 12, 14 och 16 lag, som har hanterats, med olika metoder. Se till exempel Crauwels och van Oudheusden (2002), Ribeiro och Urrutia (2004), Easton et al (2003) och Araújo et al (2006). De bästa resultaten har rapporterats med hjälp av simulerad glödgning (Anagnostopoulos et al, 2006). En ny uppsättning större fall har nyligen införts (december 2005). Detta omfattar ytterligare nio fall (16, 18, 20, 22, 24, 26, 28, 30 och 32 lag). En aktuell lista över de mest kända lösningarna samt uppgifter om alla fall finns på Michael Tricks webbplats (http://mat.gsia.cmu.edu/TOURN/, senast tillgänglig den 13 mars 2006). Urrutia och Ribeiro (2004) har visat att minimera avstånd och maximering raster (två på varandra följande hemmamatcher (home break) eller två på varandra följande bortamatcher (away break)) är likvärdiga. Detta följde tidigare arbete (de Werra, 1981 Werra,, 1988 Elf et al, 2003) som visade hur man konstruerar scheman med minsta antal raster. Mycket av det tidigare arbetet (särskilt när det gäller problemet Travelling Tournament) bygger på antagandet att lagen går på väg resor. En road trip innebär att ett lag lämnar sin hemstad, reser till sin första motståndare, spelar en fixtur och sedan reser till sin andra motståndare (och möjligen tredje, fjärde,. ..), innan du återvänder hem. Vägresor är vanliga i länder som USA, på grund av de berörda avstånden, men inte vanliga i Storbritannien där lag kommer att lämna sin hemort, spela fixturen och sedan återvända hem. Därför finns det en tydlig skillnad mellan det tidigare arbetet på Travelling Tournament Problem, och det arbete som rapporterats här. För en uppsättning av fixturer, som utgör en hel engelsk fotbollssäsong kan vi inte minimera den totala tillryggalagda sträckan. Mängden resor dikteras av de fixturer som ska spelas eftersom varje lag återvänder hem efter varje fixtur. Men vi kan överväga andra faktorer i fixturlistan för att hjälpa både lagen och supportrarna. Till exempel kan vi försöka och minimera avståndet mellan lag för mitten av veckan fixturer. Vi kan också försöka att minimera antalet raster och, i en idealisk uppsättning av fixturer, varje lag kommer att spela alternativa hem och bort fixturer. Vi kan också försöka schemalägga några fixturer när de är benägna att få mest medieintresse eller vi kan schemalägga fixturer som sannolikt har lågt supporter intresse för att maximera grind kvitton. Den schemaläggning aspekt som jag överväger i detta papper minimerar den tillryggalagda sträckan för två kompletta fixturer (en komplett fixtur definieras som en uppsättning fixturer när varje lag spelar). Dessa två kompletta fixturer kan användas under julen semester när, av en mängd olika skäl, lag vill begränsa antalet resor de gör. Som jag kommer att diskutera senare är dessa armaturer normalt planerade först och de har de lägsta resavstånden för alla kompletta fixturer under säsongen. För att bedöma effektiviteten i mitt tillvägagångssätt, kommer jag att jämföra mina fixturer mot de fixturer som faktiskt användes (som jag kommer att kalla de publicerade fixturer). Läsare som är intresserade av sportschemaläggning hänvisas till följande artiklar som innehåller problem och tillvägagångssätt som är tillämpliga på en rad olika sporter (Campbell och Chen, 1976; G Kendall-Scheduling English football fixturer över semesterperioder 745 Cain, 1977; Bean och Birge, 1980; Ferland och Fleurent, 1991, Wright, 1991, 1994 Schreuder, 1992; Armstrong och Willis, 1993; Russell och Leung, 1994; Willis och Terrill, 1994; Ball and Webster, 1997; Nemhauser and Trick, 1998; Schaerf, 1999; Thompson, 1999; Henz, 2001; Yang et al., 2002; Burke et al., 2004; Henz et al., 2004; Cassady et al., 2005; Coleman, 2005; Bartsch et al., 2006; Drexl och Knust, 2007). En utmärkt översikt över sport schemaläggning finns i (Easson et al., 2004). Problemet definieras formellt i bilaga B. Här ger jag en informell beskrivning. Parningssystemet anger att vissa lag inte bör tillåtas att spela hemma samma dag. Exempel på sådana är Manchester United och Manchester City, Liverpool och Everton samt Chelsea och Fulham. Dessa restriktioner beror vanligtvis på polisiära krav. De parningar som används i detta papper visas i bilaga C. Jag är skyldig att producera två kompletta fixturer, en för boxningsdag och den andra för nyårsdag. Varje komplett fixtur består av 92 lag, vilket resulterar i 46 fixturer. Det övergripande målet är att minimera den totala sträckan tillryggalagd av alla lag, under de två dagarna. Dessutom finns det ett antal begränsningar som måste respekteras. Detta är hårda begränsningar, eftersom de inte kan överträdas. Tabell 3 och A1 ). (5) Det finns en gräns för antalet Londonbaserade klubbar som kan spela hemma vilken dag som helst. På samma sätt finns det gränser för antalet London Premiership klubbar som kan spela hemma samma dag och även antalet större Manchester klubbar som kan spela hemma samma dag. Gränserna för dessa värden visas i bilaga D. Som nämndes i inledningen spelar alla lag (åtminstone) två fixturer under julperioden. Vanligtvis spelas dessa fixturer på boxningsdagen (26 december) och nyårsdagen (1 januari), men de faktiska datumen skiljer sig från år till år. December) följer begränsningen att om ett lag spelade hemma på Boxing Day, det spelar bort den 28/29 december (och vice versa). Därför har varje lag en tre fixtur sekvens av hem/bort/hem eller bort/hem/bort. Den 28/29 december har dock en högre ressträcka (6747 + 839 = 7586) och används därför inte för jämförelseändamål här. Därför har jag i detta dokument tillgång till fyra uppsättningar uppgifter (säsongerna 2002-2003, 2003-2004, 2004-2005 och 2005-2006) och i tabell 2 presenteras bara en av de publicerade fixturerna (Boxdagen, 2004. Fixture och division kolumnerna är självförklarande. Avståndskolumnen är avståndet mellan varje lag och beräknas med hjälp av postkoden (ZIP-koden) för teamen och använder en av Storbritanniens webbplatser för bilhaveritjänster som innehåller en ruttplanerare (http://www.greenflag.co.uk, som nås den 28 december 2005). Avstånden till denna studie var samlade samtidigt (i december 2005). Avstånden kommer faktiskt att förändras över tid på grund av förändringar i väglayouter, byggandet av nya vägar, etc. Med detta i åtanke, Jag har levererat alla de avstånd som används i denna tidning på författarens webbplats (på grund av utrymmesbegränsningar är det för stort för att lista här) (http://www.cs.nott.ac.uk/-gxk/research-data/). Clash kolumnen anger var det finns ett par sammandrabbning i publicerade fixturer. Det vill säga, två lag spelar hemma, när de har definierats som ett par. Till exempel, i tabell 2, både Birmingham och Coventry är hemma och dessa lag har definierats som ett par. Tabell 2 representerar bara ett urval av de publicerade fixturerna. De andra fixturerna finns i Rollin och Rollin (2002), men de viktiga faktorerna, när det gäller det arbete som presenteras här, har sammanfattats i tabell 3. Det finns 92 lag över de fyra divisionerna, så en komplett fixtur består av 46 fixturer. För att skapa fixturer för boxningsdag och nyårsdag, måste jag skapa två kompletta fixturer samtidigt minimera resor avstånd, begränsa antalet par sammandrabbningar och hålla fast vid de andra begränsningar som beskrivs ovan och formellt presenteras i bilaga B. Ett möjligt sätt att generera scheman är att skapa ett komplett sökträd, där varje nod representerar en fixtur och vägen från rotnoden till botten av trädet G Kendall-Scheduling engelska fotbolls fixturer över semesterperioder 747 representerar en komplett fixtur. I detta fall, djupet av sökträdet kommer att vara 45 (förutsatt att rot noden är nivå 0) och grenningsfaktorn är följande. Om jag börjar med Barclays Premiership (20 lag), skulle jag först välja två lag (Jag använder notation C(m, n) för att representera'm välja n). Därför har jag C(20, 2) × 2 = 190 × 2 = 380 noder på nivå 0. Observera att jag multiplicerar med 2, eftersom varje fixtur kan vändas för att byta hem och bort lag. Nästa nivå skulle ha en förgreningsfaktor på C(18, 2) × 2 = 153 × 2 = 306 och så vidare tills jag når C(2, 2) × 2 = 1 × 2 = 2. Detta skulle representera ett sökträd med 10 nivåer och 380 × 306 × · · × 2 noder (2,43 × 10 18 ). När jag har producerat sökträdet för Barclays Premiership, skulle jag nu behöva fortsätta bygga trädet genom att införliva Coca-Cola Championship. Därför, att gå från nivå 9 till nivå 10 skulle ha en förgreningsfaktor på C(24, 2) × 2 = 276 × 2 = 552, med nästa nivå med en förgreningsfaktor på C(22, 2) × 2 = 231 × 2 = 462 noder. När trädet hade utökats till Coca-Cola Championship, skulle jag upprepa processen för de två återstående divisionerna. Storleken på sökträdet för bara en av Coca-Cola divisionerna är av ordningen 6,20 × 10 23. En fullständig uppräkning av ett sökträd för bara en enda division är inte möjlig, för att inte tala om ett kombinerat sökträd för alla divisioner. Därför har jag utvecklat en strategi i två steg. Det första steget bygger ett separat sökträd för varje division, med beskärning för att minska storleken på sökytan. Varje division returnerar den bästa lösningen den finner som är en uppsättning av 10 fixturer (sp. 12) för Barclays Premiership (respektive Coca-Cola-divisionerna). Denna sökning sker två gånger för varje division, en gång för boxningsdag och en gång för nyårsdag. Det finns små skillnader mellan de två sökningarna för de olika dagarna, som jag beskriver nedan. Den andra etappen genomför en lokal sökning i alla divisioner, för båda dagarna, för att hitta en bra och genomförbar lösning. Detaljerna för båda dessa steg beskrivs nedan. Steg 1: Djup Första Sök: Jag producerar initialt en lösning för varje division, för båda dagarna. Jag skapar ett sökträd, beskärning på grenar som antingen inte kan leda till en bättre lösning än en redan genererad eller som kommer att leda till en ogenomförbar lösning. Jag börjar med att ta ett team (på måfå) och generera alla dess möjliga fixturer (både hem och bort). Nästa jag gör en djup första sökning. En nod expanderas genom att generera alla möjliga fixturer. När jag utökar en nod, kontrollerar jag följande. (1) Jag utvidgar inte en nod som skulle leda till att samma lag spelar två gånger i den grenen av trädet, eftersom detta skulle vara ett ogenomförbart schema. (2) Om färdsträckan för två lag är större än 200 miles, Jag genererar inte den söknod. Siffran 200 baseras på det faktum att (i Storbritannien) detta representerar restid på cirka 3 timmar vilket är ungefär det maximum som lag/supportrar skulle vilja resa över semesterperioden. Jag gör ett undantag för Plymouth. På grund av dess läge finns det inte många lag inom 200 miles så jag höjer deras gräns till 250. (3) Om den utvidgade noden skulle leda till en total ressträcka som är större än den bästa lösningen hittills, genererar jag inte den noden. Den bästa lösning som hittills har hittats definieras som en nod som innehåller en fullständig uppsättning av armaturer (dvs. på nivå 9 för Barclays Premiership och nivå 11 för de andra divisionerna) och det totala tillryggalagda avståndet är det minimum som hittills har konstaterats. (4) Jag tillåter inte parade lag att spela varandra. (5) Jag tillåter inte parade lag att båda spela hemma. Jag följer exakt samma förfarande som ovan för att skapa fixturer för nyårsdagen. Dessutom är den fullständiga fixturen ovan indata till detta sökförfarande så att ytterligare kontroller kan utföras. I detta förfarande utför jag dessa ytterligare kontroller när jag skapar nya noder i detta sökträd. (1) Jag slappnar av villkoret (5, ovan) att parade lag inte båda kan vara hemma. Syftet med den lokala sökningen är att minska antalet sammanstötningar mellan par till acceptabla värden (dvs. mindre än eller lika med de offentliggjorda listorna) samt att se till att övriga begränsningar inte överträds. Innan jag beskriver den lokala sökproceduren definierar jag en swapoperation som jag använder i sökningen. Denna operation byter hem och bort team i ett givet schema. Om jag bara övervägde en komplett fixtur, skulle detta vara en enkel operation eftersom att byta lag i en enda fixtur fortfarande skulle leda till en genomförbar tidsplan och dessutom skulle det inte påverka den tillryggalagda sträckan eftersom avstånden antas vara symmetriska. Men där jag Fixture f har två kompletta fixturer, som jag gör här, byta hem och bort laget i ett schema leder till ett ogenomförbart schema som jag nu har samma lag som spelar hemma (eller bort) i båda kompletta fixturer. Därför måste jag utföra bytet i en fixtur och reparera den andra fixturen. Ett exempel visas i figur 1. Figur 1a visar läget för två scheman (f (B) och f (N ) före bytestransaktionen. Den fixtur Chelsea kontra Portsmouth, i f (B), har identifierats som den fixtur där lagen kommer att bytas. Efter bytet (figur 1b ) de två lagen har bytts. Men för att upprätthålla genomförbarheten av de två armaturer, Jag måste lokalisera Chelsea och Portsmouth i f (N ) och byta dem också. Observera att denna andra byte har potential att ändra resavstånd som Chelsea var på väg till Arsenal, men Portsmouth är nu på väg till Arsenal. Fulham reste till Portsmouth men nu reser Fulham till Chelsea. Efter att ha definierat den här bytesoperationen kan jag nu beskriva den lokala sökalgoritmen. Jag ringer följande operatörer 5000 gånger (dvs. totalt 40 000 samtal). Jag använder värdet 5000 efter experiment men det kan enkelt ökas eftersom de lokala sökrörelserna är beräknings billigt (den lokala sökningen tar lite mer än några minuter). (1) Om det finns ett par sammandrabbning i f (B), Jag lokaliserar fixturen som har ett maximalt antal sammandrabbningar, väljer slumpmässigt om det finns mer än en kandidat. Jag byter hem och bort team, gör motsvarande byte i f (N ) för att upprätthålla genomförbarhet. De totala avstånden beräknas genom att lägga ihop boxningsdagen och nyårsresorna. Den procentuella förbättringen av avståndet beräknas som "100-genererat avstånd * 100/publicerat avstånd". (5) Om antalet Barclays Premiership London klubbar som spelar hemma i f (B) överstiger tröskeln, väljer jag (på måfå) en av dessa fixturer och byta hem och bort lag. Jag gör motsvarande byte i f (N ) för att upprätthålla genomförbarhet. (6) Samma som 3 men nu överväger f (N ). Efter var och en av ovanstående, Jag kontrollerar om jag har en ny bästa lösning (dvs minsta resavstånd och inga begränsningar överträdelser). I slutet av den lokala sökfasen genomför jag en efterbehandlingsfas för att se till att en genomförbar lösning återställs. Denna post-search process kontrollerar att jag inte har några back fixturer (lag jag spelar lag j, följt av lag j spelar lag i) och att jag inte har några lokala derbies (två parade lag spelar varandra). Även om dessa två villkor finns, jag utför swap operatör, se till att jag inkluderar en av de team som bidrar till den ogenomförbara lösningen. Utgången från denna fas efter processen är en lösning som inte bryter mot några begränsningar. Med hjälp av ovanstående två steg strategi, Jag kan producera betydande förbättringar över publicerade fixturer (se tabellerna 3 och 4). Tabell 3 visar de förbättringar jag uppnått för varje dag. Dessutom kunde jag nå dessa lösningar med samma, eller färre, par sammandrabbningar jämfört med de publicerade fixturerna. På boxningsdagen, för säsongen [2005][2006], till exempel, klarade jag en distansbesparing på 1246 (4295 − 3049), med två mindre par sammandrabbningar. Den föregående säsongen (2004Den föregående säsongen ( -2005, avståndsbesparing för boxningsdagen är 838 (4563-3725) men nu uppnås med samma antal par sammandrabbningar. Tabell 4 visar den totala sträcka som tillryggalagts under de två kompletta fixturerna för varje säsong. Det märks att de största besparingarna uppnåddes under säsongen 2005-2006. Jag diskuterar de möjliga skälen till detta i mina avslutande kommentarer. Men även om jag tar bort detta år från övervägande, uppnår jag en genomsnittlig total besparing på 24.86% ([29.95+22.15+22.47]/3), med samma antal par sammandrabbningar. Tabell 5 visar en av de kompletta fixturer som genererades. I den här artikeln har jag beskrivit ett problem med sportplanering som inte har rapporterats tidigare i litteraturen. Problemet är att minimera den totala sträckan tillryggalagd av 92 fotbollsliga klubbar över två kompletta fixturer. Vid första anblicken kan det tyckas vara ett liknande problem som problemet Travelling Tournament men, i själva verket, problemen är mycket olika. Syftet med Travelling Tournament Problem är att minimera avstånd genom att hitta en uppsättning av lämpliga road resor, så att när lagen spelar ett antal bort spel, de begränsar mängden resor som utförs. I detta problem, reseavstånd, för ett visst lag under en given säsong, är fast. Istället försöker jag minimera avståndet för två datum så att dessa armaturer kan användas under julperioden. Som framgår av resultaten har jag gjort betydande besparingar jämfört med de publicerade fixturerna. Genom att göra det har jag inte ökat antalet parkrocker och under en av säsongerna har jag faktiskt minskat antalet parkrocker. Dessutom har jag inte tillåtit några parlag att spela varandra. Detta är ibland tillåtet i publicerade fixturer, som kan hjälpa till att minska den totala avståndet som parade lag är ofta nära varandra. Slutligen har jag också sett till att jag inte har mer än ett visst antal lag som spelar i London eller Greater Manchester någon dag. Jag diskuterar för närvarande mina resultat med fotbollsligan. Jag skulle vilja utvidga detta arbete för att försöka ta fram fixturlistor för hela säsongen. Detta kommer att innefatta att man tar hänsyn till många fler begränsningar, och därför skulle jag vilja diskutera problemet med problemägarna, eftersom jag skulle vilja se till att jag löser det problem som de faktiskt står inför och inte någon förenklad abstraktion. När det gäller det arbete som rapporteras i denna rapport ser jag ett antal framtida riktningar som jag skulle kunna följa. Den första är att ge en rättvis jämförelse för säsonger där fyra kompletta fixturer behövs under semestersäsongen. säsong är ett exempel när detta var ett krav. Tabell 1 visar att under semesterperioden för den här säsongen, det fanns faktiskt fyra kompletta fixturer spelade. De två ytterligare kompletta fixturer (spelade den 31 december, 2 januari och 3 januari) också hålla sig till begränsningen att om du spelar hemma på en av dessa dagar, då måste du spela bort på den andra dagen. Också, genom att titta på avstånd (4503+6564+296=11 363) Jag noterar att dessa är också bland de lägsta i säsongen när man överväger alla kompletta fixturer. Detta tyder på att schemaläggare för den här säsongen har varit tvungna att producera två uppsättningar kompletterande fixturer för semesterperioden. Faktum är att detta har rapporterats i pressen och beror på att 2006 är ett världscupår och de engelska fotbollsmyndigheterna försöker schemalägga matcher på ett sådant sätt att det engelska landslaget kan tillbringa mer tid tillsammans som förberedelse inför världscupen. Under den föregående säsongen (2004)(2005) fanns det också fyra fixturer planerade, som också följde hem / borta begränsningar. Avstånden till de alternativa armaturerna är dock höga så jag antar att det inte fanns något krav på att minimera avstånden. Jag skulle också vilja ytterligare undersöka de gränser som jag sätter på mitt djup första sökning. I algoritmavsnittet beskrev jag hur jag kontrollerar om jag expanderar en nod eller inte. Jag har fler idéer om hur jag kan förbättra detta. En idé är att höja 200 milsgränsen (250 för Plymouth) så att jag överväger fler lösningar. Sedan, i den lokala sökningen skulle jag kunna presentera en operatör som tittar på laget som har den högsta ressträckan och utföra ett drag som försöker boka om det laget. En annan idé är att beställa armaturer när man överväger expansionerna. Det vill säga att expandera lägre kostnader (de med lägre avstånd) noder först. Detta kan ha effekten av att minska sökytan eftersom jag sannolikt kommer att överskrida det totala resavståndet (dvs. bästa lösning hittills) högre i sökträdet eftersom vi bör hitta en relativt låg kostnad lösning tidigt i sökningen som kommer att minska antalet expansioner jag måste utföra senare. Det skulle också vara intressant att undersöka om jag kan minska antalet sammandrabbningar, samtidigt som transportavstånden bibehålls till godtagbara nivåer. I denna aktuella studie, satte jag den övre gränsen på antalet par sammandrabbningar till dem som finns i publicerade fixturer. Vilken effekt skulle det ha på lösningarna om jag sänkte dessa gränser? Skulle lösningarna kunna betraktas som bättre av till exempel polisen, för även om lagen skulle behöva resa vidare, skulle det finnas en minskning av de nödvändiga polisresurserna på grund av att färre lag spelar i ett visst geografiskt område? För att undersöka just denna forskningslinje skulle jag behöva tala med polismyndigheter och fotbollsmyndigheter. Detta har varit ett mycket intressant problem att arbeta med och det har potential för betydande ytterligare undersökningar. Denna studie har använt en exakt metod (djup första sökning) i kombination med en lokal sökning. Om jag ska ta itu med problemet med att generera fixturlistor för hela säsongen är det troligt att jag kommer att behöva ta till meta-heuristiska metoder (t.ex. genetiska algoritmer (Goldberg, 1989; Sastry et al, 2005), simulerad annealing (Kirkpatrick et al, 1983; Aarts et al, 2005), hyper-heuristics (Burke et al, 2003a,b; Ross, 2005; Burke et al, 2007) etc.). Men som jag har visat här är det möjligt att bryta ner problemet, och kanske kan hybridiseringen av exakta och metaeuristiska metoder också vara tillämplig på det större problemet. I denna uppsats, för första gången i den akademiska litteraturen, studeras de problem som är förknippade med schemaläggning av fotbollsmatcher i de fyra större engelska divisionerna. I synnerhet studerar jag hur fixturer kan schemaläggas över semesterperioder när resor avstånd måste minimeras. Ett bidrag av detta papper är att generera fixturer som är bättre än publicerade fixturer (dvs de som publiceras och används). Med "bättre" menar jag när man jämför det totala tillryggalagda avståndet, samtidigt som man håller fast vid de begränsningar som krävs. Jag använder en kombination av djup första sökning, följt av en lokal sökning för att hitta genomförbara lösningar. Ett ytterligare bidrag från detta arbete beskriver problemet både på ett beskrivande sätt och presenterar också en formell modell. Man hoppas att detta kommer att främja mer forskning om detta problem. Dessutom beskriver jag den datainsamling som genomfördes för att ge andra forskare tillgång till uppgifterna för att kunna reproducera mina resultat eller utveckla detta arbete ännu mer. De uppgifter som jag lägger fram skulle kunna användas för en rad andra tillämpningar, t.ex. fordonsrouting eller resande säljare. Tack-Jag vill tacka anonyma granskare för deras kommentarer. Detta har lett till ett mycket bättre papper.
Kendall Ref har antagit en strategi i två steg för att ta fram två fullständiga exempel på detta problem.
Scheduling English football fixtures over holiday periods
{'venue': 'Journal of the Operational Research Society', 'journal': None, 'mag_field_of_study': ['Computer Science']}