En række består af $N$ hold. Med en målpuljestørrelse på $H = 7$ hold pr. pulje dannes $K = \lceil N / H \rceil$ puljer $P_1, \ldots, P_K$.
Køretiden mellem to hold $i$ og $j$ betegnes $d(i, j)$ og er hentet fra OSRM — en åben routingtjeneste der beregner reelle bilkøretider på vejnettet.
Trin 1 — Initialisering: Grådig fordeling
1a. Frø-udvælgelse (Farthest-First Traversal)
For at sikre at puljernes “centre” er geografisk spredte, udvælges $K$ frøhold $s_1, \ldots, s_K$ via en grådig farthest-first traversal på de geografiske koordinater $x_i$:
$$s_{k+1} = \arg\max_{i \notin S_k} \min_{s \in S_k} | x_i - x_s |_2$$
hvor $S_k = {s_1, \ldots, s_k}$. Klubber med mere end 4 hold bidrager med 2 forudvalgte frø, så store klubber altid initialiserer separate puljer.
1b. Grådig puljefyldning
Frøholdene sorteres efter faldende total køretid til alle andre hold — holdet med de “fjerneste” naboer vælger sin pulje-modstander først. Herefter tilføjes hold rundenom én ad gangen: hvert frøhold udvælger det nærmeste ledige hold $j^*$ fra ledige hold $\mathcal{L}$, under hensyntagen til klubbegrænsningen:
$$j^* = \arg\min_{j \in \mathcal{L},; c(j) \notin C(P_k)} d(s_k, j)$$
hvor $c(j)$ er holdet $j$‘s klub og $C(P_k) = {c(i) : i \in P_k}$ er mængden af klubber allerede repræsenteret i pulje $k$. Resthold, der ikke kan placeres uden klubkonflikt, fordeles til den pulje der giver færrest klubkonflikter.
Trin 2 — Forbedring: 2-opt byttealgoritme
Potentialfunktionen
Lad den gennemsnitlige køretid for hold $i$ i pulje $P_k$ være:
$$d_{\text{hold}}(i, P_k) = \frac{1}{|P_k| - 1} \sum_{j \in P_k \setminus {i}} d(i, j)$$
Den gennemsnitlige køretid i pulje $P_k$ er da:
$$\bar{d}(P_k) = \frac{1}{|P_k|} \sum_{i \in P_k} d_{\text{hold}}(i, P_k)$$
og det globale gennemsnit på tværs af alle puljer:
$$\bar{d}(\mathcal{P}) = \frac{1}{K} \sum_{k=1}^{K} \bar{d}(P_k)$$
Den globale potentialfunktion $\Phi$ kombinerer gennemsnitlig køretid og variansen mellem puljer i ét mål:
$$\Phi(\mathcal{P}) = (1 - \alpha)\cdot \bar{d}(\mathcal{P}) ;+; \alpha \cdot \frac{\operatorname{Var}!\left(\bar{d}(P_1), \ldots, \bar{d}(P_K)\right)}{\bar{d}(\mathcal{P})}$$
hvor $\alpha \in [0,1]$ er fairnessfaktoren. Vi anvender $\alpha = 0.3$, hvilket giver en overvægt til at minimere gennemsnitlig køretid mens variansen holdes i skak. Variansen normaliseres med $\bar{d}(\mathcal{P})$ for at gøre de to led skalamæssigt sammenlignelige.
Bytte-operationer
Et 2-opt bytte af hold $i \in P_a$ og $j \in P_b$ giver de opdaterede puljer:
$$P_a’ = (P_a \setminus {i}) \cup {j}, \qquad P_b’ = (P_b \setminus {j}) \cup {i}$$
Et bytte accepteres kun hvis begge nedenstående betingelser er opfyldt:
Betingelse 1 — Klubbegrænsning: Ingen pulje må have mere end $m = 2$ hold fra samme klub efter byttet. Denne betingelse lempes hvis hold $i$ eller $j$ er et outlier-hold, eller hvis pulje $P_a$ eller $P_b$ er en outlier-pulje (defineret nedenfor).
Betingelse 2 — Potentialforbedring:
$$\Phi(P_1, \ldots, P_a’, \ldots, P_b’, \ldots, P_K) < \Phi(P_1, \ldots, P_a, \ldots, P_b, \ldots, P_K) - \varepsilon$$
hvor $\varepsilon = 10^{-6}$ forhindrer numerisk støj i at trigge unødvendige bytter.
Outlier-definitioner
Hold $i \in P_k$ kaldes et outlier-hold med faktor $\beta = 1.5$ hvis:
$$d_{\text{hold}}(i, P_k) > \beta \cdot \frac{1}{|P_k| - 1} \sum_{j \in P_k \setminus {i}} d_{\text{hold}}(j, P_k)$$
dvs. holdet har markant længere gennemsnitlig køretid end de øvrige hold i sin pulje.
Pulje $P_k$ kaldes en outlier-pulje hvis:
$$\bar{d}(P_k) > \beta \cdot \frac{1}{K-1} \sum_{l \neq k} \bar{d}(P_l)$$
Outlier-undtagelsen tillader algoritmen at løse geografisk skæve situationer, selv når et rent bytte ville introducere en klubkonflikt.
Konvergens
Algoritmen itererer over alle par $(P_a, P_b)$ og alle mulige bytter $(i, j)$. Første accepterede bytte appliceres øjeblikkeligt og søgningen genstartes. Algoritmen terminerer når ingen bytte-operation opfylder begge betingelser — dvs. ved et lokalt minimum for $\Phi$.