Neka je $I=\{1,2,..n\}$ skup korisnika, a $J=\{1,2,...m\}$ skup potencijalnih lokacija uslužnih centara. Neka je sa $c_{ij}$ označeno rastojanje od korisnika $i$ do centra $j$. Zadatak je naći lokacije tačno $p$ centara kojima se minimizuje maksimalno rastojanje svih korisnika do njima najbilžeg otvorenog centra. Uvodimo sledeći skup promenljivih:
$$ x_{ij}=\left\{\begin{matrix} 1, \text{korisnik } i\in I \text{ je pridružen centru } j\in J\\ 0, \text{inače} \end{matrix}\right. $$
$$ y_{j}=\left\{\begin{matrix}1, \text{centar je uspostavljen na lokaciji } j\in J\\ 0, \text{inače}\end{matrix}\right. $$
$W$ - promenljiva koja predstavlja maksimalno rastojanje korisnika do njima najbližeg otvorenog uslužnog centra.
Formulacija problema:
$$ \begin{aligned} \min\ &W,\\\text{pod ograničenjima: } &\sum_{j\in J}x_{ij}=1,\ \forall i\in I, \\&x_{ij}-y_j\leq0,\ \forall i\in I,\ j\in J, \\&\sum_{j\in J}y_{j}=p, \\&\sum_{j\in J}c_{ij}x_{ij}-W\leq0,\ \forall i\in I\\&x_{ij}\in\{0,1\},y_{j}\in\{0,1\} \end{aligned} $$
Prvim skupom ogranicenja se zahteva da svaki korisnik bude pridružen tačno jednom uslužnom centru (nemamo ograničenje na kapacitet centra, pa može ovako). Drugi skup ograničenja obezbeđuje da nijedan korisnik ne sme biti pridružen centru koji nije uspostavljen. Treće ograničenje zahteva uspostavljanje tačno $p$ uslužnih centara. Četvrti skup ograničenja zahteva da rastojanje svakog korisnika $i\in I$ do njemu najbližeg centra mora biti manje od $W.$
Instancu zadajemo u sledećem formatu:
$$ \begin{aligned}&n\\&m\\&p\\&c_{11},....,c_{1m}\\&c_{21},....,c_{2m}\\&\vdots\\&c_{n1},....,c_{nm}\\&\text{check}\end{aligned} $$
Primer:
Kod:
Lokacijski problem maksimalnog pokrivanja (The maximal covering location problem, MCLP) podrazumeva nalaženje jednog ili više (p) čvorova na mreži ( lokacije snabdevača), takvih da se iz njih za neko unapred zadato rastojanje (ili vreme putovanja, troškove) pokriva najveći broj (tražnja) korisnika.