Problem pokrivanja skupa (covering set problem), najpoznatiji u varijanti izbora lokacija vatrogasnih postaja (fire station location problem), ima mnogobrojne praktične primjene u prometu.

Problem pokrivanja skupa (covering set problem) ima jednostavnu definiciju: u grupi elemenata koji su u nekom odnosu (relaciji) treba naći minimalan broj skupova kojima će biti obuhvaćeni svi elementi po određenom pravilu. Problem pokrivanja skupova je znakovit NP-teški problem u kombinatornoj optimizaciji. Inženjerski problemi mogu se podijeliti u manje probleme (pardon, izazove): disjunktne skupove ili u podskupove s presjecima pa ne treba puno informatičkih resursa (procesorske snage) i vremena za njihovo rješavanje.

Nama inženjerima je puno lakše objasniti primjerom, a najčešće se koristi problem izbora lokacija vatrogasnih postaja. Područje (grad, mjesto) podijeljeno je na 10 zona, a unutar svake zone i između zona poznata su vremena putovanja vatrogasnih vozila. Potrebno je locirati najmanji broj vatrogasnih postaja, a da bude zadovoljen uvjet da vrijeme putovanja od lokacije vatrogasne postaje do bilo koje zone ne bude dulje od 15 minuta. Grupa elemenata su zone, odnosi između zona definirani su vremenom putovanja, a pravilo je ne putovati dulje od 15 minuta. Putovanja se prikazuju matricom. Moguće su situacije različitih vremena putovanja; primjerice, od zone 1 prema 2 putovanje traje 12 minuta, a od 2 prema 1 je 10 minuta. Po definiciji se za putovanje unutar zone stavlja vrijednost nula, jer zona unutar koje bi putovanje trajalo dulje od maksimalno zadane vrijednosti (pravila) nema smisla.

Puno je jednostavnije manipulirati matricom koja će imati manje brojeva. Kreira se binarna matrica koja će imati 0-1 elemente:

pa matrica putovanja [d(i,j)] pokazuje koje relacije se mogu uzeti u obzir u izboru rješenja.

Moramo definirati veličine koje će pokazivati da li se zona uzima u rješenje ili ne.

Model se sada može zapisati i riješiti

u Excel Solver (hr. Rješavač) koji daje rješenje:

Potrebno je izgraditi tri vatrogasne postaje u zonama 2,4 i 8 čime se osigurava vrijeme putovanja od maksimalno 15 minuta. Rješenje nam pokazuje da se zona 9 može doseći unutar 15 minuta iz dvije postaje u zonama 4 i 8. Izbor bi pao na vatrogasnu postaju u zoni 4 jer je vrijeme putovanja jednu minutu kraće. Matematika upućuje, a inženjer odlučuje temeljem analize svih elemenata ugrađenih u model.

Iako to nije prvotna namjera, s ovakvim modelom se inženjer može malo poigrati i dobiti familiju odgovora za različita minimalna vremena putovanja. Grafički prikaz pokazuje da nije moguće postići putovanja kraća od osam minuta i za to je potrebno u svakoj zoni izgraditi vatrogasnu postaju. Ako bi se izgradile dvije postaje (u zonama 1 i 9) moglo bi se jamčiti vrijeme putovanja do 19 minuta.

Problem (EU jezikom: izazov) se može i drugačije postaviti. Umjesto promatranja putovanja od točke prema području, možemo zadati problem gravitacije područja prema nekoj točci. Zamislimo sličnu situaciju područja sa 10 zona u koje moramo smjestiti autobusna stajališta. Cilj je postaviti što manje stajališta koja su dostupna za najviše 250 s pješačenja; pri brzini hoda 1,2 m/s (4,32 km/h) prijeđe se 300 m, a to je udaljenost koja predstavlja visoku kvalitetu ponude javnog prijevoza. Što manje stajališta – manje zaustavljanja – kraće vrijeme putovanja javnim prijevozom. Matrica pokazuje vrijeme pješačenja u sekundama između pojedinih zona. Rješenje je izgraditi stajališta u zonama 1 i 9 što jamči da pješačenje neće biti dulje od 250 s. Rješenje modela pokazuje da su oba stajališta udaljena manje od 300 m za zone: 1, 4, 7, 8 i 9.

Lokacijski problemi nisu tako jednostavni, jednodimenzionalni. Model postaje realniji ako se promatra cijena izgradnje stajališta. Cijene izgradnje su različite zbog (ne)potrebnih: rješavanja imovinsko-pravnih odnosa, izgradnje potpornih zidova/propusta, proširenja ceste, dogradnje nogostupa i dr.. Model se dopunjuje s cijenom izgradnje stajališta.

Cijena izgradnje stajališta u prvoj zoni je najskuplja i košta 113.000 EUR, a najjeftinija u trećoj zoni sa 40.000 EUR. Ukupno rješenje je drugačije. Zadovoljenje udaljenosti i minimalizacije cijene izgradnje stajališta zahtjeva izgradnju stajališta u zonama 4 i 6. Ukupna cijena izgradnje je 110.000,00 EUR. U ovom rješenju se samo stanovnici u zoni 5 nalaze u dosegu 300 m od oba stajališta.

Prvo rješenje bez uključivanja cijene nudi izgradnju stajališta u zonama 1 i 9 pri čemu stanovnici pet zona imaju dobru dostupnost prema oba stajališta, ali se ta kvaliteta se plaća 199.000,00 EUR. Uključivanjem cijene prolazimo 45 % jeftinije, ali imamo manji komfor stanovnika.

Zadnji model u ovoj temi je nadzor parkirališta. Treba uspostaviti nadzor parkirališta sa što manje kamera koje će nadzirati cijeli prostor. Danas su kamere s punom panoramom (360 stupnjeva) uobičajene. Prije opisa problema, prvo klasičan štos glede optimalnog broja kamera i troškova. Sljedeća slika pokazuje da je najbolje za nadzor sva četiri kvadranta koristiti jednu kameru na mjestu “k2”. Rješenje se mijenja ako znamo da kamera ima troškove izgradnje i eksploatacije 100, a kamere “k1” i “k3” ukupno 70. Osim što je jeftinije imamo i određenu redundanciju jer postoje područja preklapanja video nadzora.

Parkiralište je prikazano na sljedećoj slici. Postoji visoko zelenilo (drveće) koje se ne smije ukloniti. Parkiralište je podijeljeno je na kvadrante (crveno, ukupno 39 kvadranata) i postavljene su moguće lokacije kamera (ukupno 53 kvadranata). Ovo je “školski” primjer pa su definirane i lokacije kamera k8, k15, k22 i k29 iako nisu realne jer se nalaze u prostoru kolnika; stavljene su opcije da ne pokrivaju niti jedan kvadrant i da svaka lokacija košta 99.000 EUR. 

Cijena postavljanja jednog kamernog mjesta (dobava, stup – nosač i ostala oprema, postavljanje, montaža, instalacija, stavljanje u funkciju) je oko 4.000 EUR. Trebalo bi uključiti i troškove servisiranja u amortizacijskom vijeku, ali to je ovdje imanentno jer se radi o identičnoj opremi. Budući drveće zaklanja određene kutove preglednosti postoje određeni troškovi postavljanja kamera na određene lokacije, problem se računa na način da se matricom određuje vidljivost kamere prema određenom kvadrantu i cijena izvođenja kamere na određenoj lokaciji. Zato se u uvjetima na desnoj strani jednadžbe stavi broj za koji smatramo s koliko kamera treba pokriti određeni kvadrant. Matrica u sljedećem grafičkom prikazu pokazuje koja kamera pokriva pojedini kvadrant (1 ako pokriva i 0 ako ne pokriva). S desne strane matrice su nejednadžbe za pojedini kvadrant gdje su za desnu stranu jednadžbe (DS) u slučaju potrebe pokrivanja od strane više kamera stavljeni brojevi veći od 1 (označeni crvenom bojom). Nigdje nije stavljen broj veći od 2, odnosno i kritični kvadranti s više drveća mogu se pokriti s dvije kamere. Problem je malo veći jer ima 39 kvadranata i 53 (49) kamernih mjesta. Rješenje zahtijeva postavljanje 25 kamera. Troškovi su 181.000,00 EUR.

Koliko je problem parkirališta realan? Kako se gleda: i da i ne. Kamere imaju puno veći “domet” od 20-tak metara kako je ovdje prikazano. Zato bi u stvarnom primjeru trebalo 10 – 12 kamera, ako je zadaća nadzor područja parkirališta i slobodnih/zauzetih parkirnih mjesta. Troškovi nosivih konstrukcija bili bi nešto veći jer bi trebalo raditi dodatke konstrukcijama obzirom na drveće i bolje kutove pokrivanja. Ako bi trebalo očitavati i registarske oznake onda bi zaista trebali 20 – 25 kamera različitih namjena.

Ideja ove teme je ionako motivacijska: kako uz ponešto stručnog znanja, malo matematike i zrnca računalne ispomoći u svakom smislu (vremenskom, tehničko-tehnološkom, financijskom, kompromisnom) pronaći najbolje rješenje, a ne putem “stručnih procjena” pobacati opremu i/ili posijati manje-više skupe prometne (i druge) objekte.