Detailed Model
Let n ∈ be the number of teams. The following model con- siders the case in which n is even. However, when n is odd, a similar model can be derived with only minor modifica-tions by introducing a dummy team that represents rest slots.
• N{1,2,…,n},thesetofteams;
• M{1,2,…,n−1},thesetofslotstobescheduled;
Copyright By PowCoder代写 加微信 powcoder
• T⊂N,thesetoftopteams;
• ST⊆T,thesetofsupertopteams;
• MW1,MW2⊂M,asetofslotstobeplayedduringwork-
days (i.e., midweek slots), in the first or in the second half, respectively;
• HPr,APr⊆N×M,asetofpreferencesforeachteamto play in a specific slot, home or away, respectively.
• δkij ∈{0,1},ij∈N,k∈M,abinaryvariablewithvalue1 if and only if team i plays at home against team j in slot k during the first half of the tournament;
• Ii ∈ , a slack variable representing the unbalance between home and away matches played during midweek slots for team i;
• DAki ∈,i∈N,k∈M,thetotaldistancetraveledby team i when an away break occurs in slots k and k + 1, where k + 1 is a midweek slot of the first half; for midweek slots of the second half, the variable DHik for home breaks is also defined.
Auxiliary variables
To formulate the objective function and to better describe some constraints, some auxiliary variables can be defined as follows:
• Hik ji δkij ∈ {0,1}, a binary variable that states if teamiplaysathomeinslotk;thevariableAki foraway matches is defined similarly;
• HHik ∈ {0, 1}, a binary variable that states if team i plays at home in both slot k and k+1, that is, it has a break; the variableAAki forawaybreaksisalsodefined;
• APi ∈ {0, 1}, a binary variable that states if team i has an alternating pattern.
Parameters
• Dij, i, j ∈ N, the distance between the home towns of teams i and j normalized in [0,1]; it holds Dij Dji and Dii 0.
Objective function
The function to be minimized is a weighted sum of various penalties:
6 minωrFr,
where ωr is the weight associated with objective r, and
The entire model is based on binary decision variables, which we define as follows:
1 if team i plays at home against team j in slot k, δkij 0 otherwise.
All the variables and the constraints, unless otherwise explic- itly indicated, relate to the first half of a round-robin tourna- ment; we obtain the second half by mirroring the first half.
(F1) Totalnumberofbreaks(homeoraway):
kk F1 (HHi +AAi).
(L2) Notwoconsecutivebreaksareallowed: HHk +HHk+1 ≤1.
(A.12) (A.13)
(A.14) (A.15) (A.16) (A.17)
(F4) Total number of alternating patterns:
F4 APi. i∈N
week slots:
of matches between top teams and super top teams are limited, respec-
(F2) Total number of unbalanced matches for midweek slots:
Sequences HHAHH or AAHAA are forbidden: HHk +HHk+3 ≤1.
HHn−1 +AA3 ≤1. ii
AAk +AAk+3 ≤1. ii
AAn−1 +HH3 ≤1. ii
F2 Ii. i∈N
(F3) Total number of big matches played during midweek slots:
F3 δkij. (A.3) i, j∈T
Constraints (A.15) and (A.17) are imposed to handle border situations between the two halves.
(L4) If the league requires it, a team ı ̄ must play at home against team ̄ in slot k ̄ :
δk ̄ 1. (A.18) ı ̄ ̄
Similarly, a team ıˆ cannot to play at home against team ˆ in slot kˆ:
δkˆ 0. (A.19) ıˆ ˆ
(L5) Thenumberofmatchesinahalfthateachteamplays at home and away must be balanced:
n−1 ≤Hik≤ n−1. (A.20)
(L6) If the tournament stops after slot k ̄ for a specific
period, no away breaks are allowed before, over, and after the stop:
(F5) Total number of unsatisfied home or away preferences:
F5 Aki+ Hik. (A.5) (i, k)∈HPr (i, k)∈APr
(F6) Overall distance term comprising the following com- ponents:
• Total distance covered by away teams on December 26, (denoted by slot k ̄) :
δk ̄D. (A.6) ij ji
• Total distance covered by away teams on unsatisfied home or away preferences:
AAk ̄−10. i
AAk ̄0. i
AAk ̄+10. i
(L ) In each slot k, the number Bk and Bk 7 TST
(A.21) (A.22) (A.23)
DAki + DHik. k∈MW1 i, j∈N k∈MW2 i, j∈N
(L8) The number of matches in a half that each top team i ∈ T plays with another top team at home and away must be balanced:
Round-robin structure constraints
(R1) Eachteammustplayexactlyonegameinaslot: δk +δk 1 ∀i,k.
BTk0, ifk1;
BTk ≤ 2, otherwise.
Bk 0, ifk≤2; ST
(A.9) (R2) Eachteammeetsallotherteamsonceineachhalf:
Bk ≤ 1, otherwise. (A.25) ST
(δij+δji)1 ∀ij.
|T|−1
The rule is also applied for super top teams
AAk +AAk+1 ≤1.
δji ·Dij + δij ·Dij.
(i, k)∈HPr j∈N, ji
• Total distance covered by teams that have breaks in mid-
(i, k)∈APr j∈N, ji
League requirements
k∈M ji, j∈T
(L1) No breaks are allowed at the beginning and at the end of the half:
|ST|−1 k |ST|−1
2 ≤ δij≤ 2 , i∈ST. (A.27)
k∈M ji, j∈ST
HH1 AA1 HHn−2 AAn−2 0. iiii
(L9) There should be balance between the number of mid- week games played at home and those played away. Using
MW k k
Hi Hi+ Ai, (A.28)
where quantities DAki and DHik are summed in the term F6 of the objective function.
Let us consider the first inequality. When A Aki 1 (i.e., an away break occurs in slot k ∈ MW1), the sum of the distances
kk traveled is lower than or equal to DAi . Because DAi is in
the objective function, the equality holds when the optimum is reached. Otherwise, if AAki 0, the inequality is always
satisfied regardless of the value of DAki ; thus, D Aki is forced to be zero at the optimum. Analogous considerations can be made for the second inequality.
(C5) The games on December 26 should be played by teams whose venues are geographically close to avoid lengthy travels on December 25. The overall distance traveled by the teams that play away in that slot has already been reported in the objective function.
k∈MW1 k∈MW2 AMWAk+Hk, (A.29)
iii k∈MW1 k∈MW2
we denote the number of home and away matches in mid- week slots during the whole tournament, respectively; we have the following:
|HMW−AMW|≤I, (A.30) iii
where Ii should be minimum.
(L10) The number of breaks should be as small as possible.
This requirement translates into the term F1 of the objective function.
(L11) Teams with no breaks in their schedule are consid- ered to have an advantage; therefore, this pattern should be avoided. These soft constraints end up in the term F4 of the objective function. In particular, a team i ∈ N has an alternat- ing pattern (i.e., APi 1) if and only if
(HHik +AAki )0; (A.31) k∈M
that is, no breaks exist in the pattern.
(L12) Avoiding playing a big match during midweek slots
is preferable. Total number of big matches during midweek slots has already been reported in the objective function. Club requirements
(C1) Therearespecificslotsinwhichateamı ̄∈Nisforced to play a home game, or a team ıˆ∈ N must play an away game in those slots:
Hı ̄k 1; (A.32) Aıˆk 1. (A.33)
(C2) Iftwoteamsi,j∈Nsharethesamevenue(i.e.,derby) at each slot, one must play at home and the second must play away:
Hik+Hjk1, k∈M. (A.34)
(C3) Each team can express preferences for scheduling home or away games on specific slots. The overall number of unsatisfied preferences was already reported in the objective function.
(C4) If two consecutive away games are scheduled and the two relative slots are temporally close (e.g., in mid- week slots), the overall distance traveled should be as low as possible.
δkD +δk+1D −DAk≤(1−AAk), k∈MW1,i∈N, jiijjiiji i
δkD +δk+1D −DHk≤(1−HHk), k∈MW2,i∈N,
jiijjiiji i ji ji
(A.35) (A.36)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com