Pianificazione del calendario: vincoli del campo home

Sto lavorando su un algoritmo di programmazione round-robin per lo sport.

L'obiettivo dell'algoritmo è pianificare tutti i giochi dati in diverse settimane, nei campi dati e in determinati tempi di gioco. Si tratta in genere di round robin o di campionati a doppio round robin, ma il numero di volte in cui ciascuna squadra gioca l'altro potrebbe non essere lo stesso.

Le leghe sono composte da diversi gruppi o categorie (ad es. Signore, Gentiluomo, Under 18) con diverso numero di squadre e diverso numero di giochi. Gli slot in cui sono programmati i giochi sono condivisi da tutti loro. Un esempio di uno slot può essere Field 3 10am-11am .

Le corrispondenze vengono calcolate in anticipo utilizzando un normale algoritmo round-robin, e quindi l'algoritmo di pianificazione funziona in modo molto diretto. I giochi di ogni settimana sono programmati nel primo spazio idoneo:

for week in weeks:
    for game in games[week]:
        for slot in slots:
            if eligible(game, slot):
                schedule(game, slot)

Una corrispondenza è composta da Home Team vs Away Team . Una squadra è la casa o la squadra in trasferta semplicemente dalla sua posizione nella partita.

Il vincolo del campo home crea un'associazione tra una squadra e un campo e afferma che questa squadra deve giocare i propri giochi casalinghi in quel campo specifico. Dettagli da tenere in considerazione:

• Una squadra può o non può avere un campo casa. Se non lo fanno, possono giocare a casa loro ovunque.
• Una squadra può avere più di un campo casa.
• I campi della casa possono essere condivisi: un campo può essere il campo di casa di più di un gruppo.

Quest'ultimo punto è il tutto che mi dà problemi. Abbiamo un campionato di due mesi con un solo gioco alla settimana, 6pm-7pm on Fridays , il che significa che tutti i giochi sono simultanei. Tutte le squadre del campionato hanno uno o due campi di casa, e sono spesso condivise da un paio di squadre. Questo porta al seguente problema:

home_fields[team1] -> field2
home_fields[team3] -> field2

Stiamo provando a pianificare Team 1 vs Team 2 che è in Week 3 . Come possiamo vedere, dobbiamo programmarlo in uno slot con Field 2 . Tuttavia, risulta che in Week 3 abbiamo già Team 3 vs Team 5 , che deve anche essere pianificato in Field 2 .

Non possiamo semplicemente provare a pianificare Team 1 vs Team 2 in una settimana diversa perché il numero di volte in cui Team 1 (e Team 2 ) viene riprodotto ogni settimana finirebbe per sbilanciarsi. Le squadre devono giocare un numero distribuito uniformemente di partite a settimana.

Abbiamo provato una serie di approcci per risolvere questi conflitti di campi interni. Aiutano, ma solo in una certa misura:

1. Cambiare le posizioni a casa

Questo mira ad affrontare il problema del campo condiviso. Se due squadre condividono lo stesso campo ed entrambi sono la squadra di casa nella stessa settimana, proviamo a cambiare la casa e le posizioni di distanza in uno dei giochi. Ovviamente, questo disturba il conteggio delle partite in casa e in trasferta per entrambe le squadre, quindi prima di rendere l'interruttore efficace, il conteggio deve essere bilanciato.

for unscheduled_game in unscheduled_games:
    for slot in all_slots:
        if not eligible(unscheduled_game, slot, reason=HOME_FIELD):
            switch_home_away(unscheduled_game)
            if balance_home_away():
                if not slot.game or reschedule(slot.game, all_slots, home_away_switch=True):
                    schedule(unscheduled_game, slot)

La funzione reschedule , come puoi presumere, toglie il gioco dallo slot corrente e tenta di riprogrammare una partita in uno qualsiasi degli slot dati. Nota come è abilitato il flag di commutazione casa lontano, in modo che l'algoritmo di riprogrammazione tenti anche un interruttore di home away, fino a un certo limite di profondità.

Questo aiuta a fare un punto, ma a volte non funziona perché il gioco cambiato non può essere programmato da nessuna parte, o perché il tentativo di ristabilire il bilanciamento iniziale non è riuscito.

2. Trasferimento di giochi tra le settimane

Questa procedura funziona solo se i team si giocano l'un l'altro più di una volta. Diciamo che abbiamo Team 1 vs Team 2 in Week 1 che non potremmo pianificare. Poi c'è un gioco Team 2 vs Team 1 pianificato in Week 5 che fa si adatta a uno slot in Week 1 . Inoltre, il gioco non programmato originale si adatta a uno slot in Week 5 . Quindi trasferiamo semplicemente il gioco non programmato da Week 1 a Week 5 e lo pianifichiamo con successo, e riprogrammiamo il gioco programmato da Week 5 a Week 1 .

for unscheduled_game in unscheduled_games:
    for game in [g for g in scheduled_games if g.home_team == unscheduled_game.away_team and g.away_team == unscheduled.game.home_team]
        for slot_week_M in [s for s in slots if s.week == game.week]:
            if eligible(unscheduled_game, slot_week_M):
                for slot_week_N in [s for s in slots if s.week == unscheduled_game.week]:
                    if eligible(game, slot_week_N):
                        schedule(unscheduled_game, slot_week_M)
                        schedule(game, slot_week_N)

Ho idee non formulate che non sono stato in grado di elaborare e utilizzare, o persino di capire se potrebbero essere utili a tutti:

• Trasferimento avanzato a più settimane. Forse c'è un modo più complesso di trasferire più giochi tra più settimane, con più di due squadre coinvolte. Ma non ho un'idea precisa su come farlo o su come ciò potrebbe essere d'aiuto.

• Cambiare gli avversari. Forse un modo per risolvere i conflitti è direttamente cambiare la composizione di una partita. Invece di avere Team 1 vs Team 2 lo renderemmo Team 3 vs Team 2 per sbarazzarci di un blocco di campo home che Team 1 potrebbe avere. Non sono del tutto sicuro che ciò possa essere d'aiuto, e anche se ciò è fattibile, poiché dovremmo cercare di correggere il cambiamento poiché questo lascerebbe il programma non bilanciato ( Team 1 non viene più riprodotto in quella settimana, Team 3 ora ha una partita in più in quella settimana, e il numero di volte in cui le squadre coinvolte si giocano a vicenda potrebbe aver deviato troppo dal numero accettato).

Ho appena finito le idee. Quali altre misure posso provare a risolvere i problemi relativi ai vincoli dei campi domestici e pianificare tutti i giochi?