Optimizacija taksi dispečera Voronoj dijagramima
Svaki prazan kilometar taksija je novac koji dispečer nikad neće videti. Standardni pristup je surova računska sila — proveriti svako vozilo, jedno po jedno, za svakog putnika. Hteo sam da vidim da li postoji brži, elegantniji način — jedan koji dolazi iz geometrije, ne iz brute-force koda.
januar 2026
$ git clone github.com/Rudic21302/VoronojTaxi
"Najbliže" vozilo nije uvek i "dostupno" vozilo.
Image from Pexels by Artem Velychko
Uvod
Ekonomska efikasnost taksi dispečera najviše zavisi od jedne stvari — minimizacije praznog hoda, vremena kad vozilo vozi bez putnika. Cilj ovog projekta je da primenom Voronoj dijagrama optimizujem dodelu vožnji, tako da svaki putnik dobije najbliže moguće vozilo. Idealno rešenje bi bio takozvani "prostorno-vremenski Voronoj dijagram" (STVD), koji bi uzeo u obzir i realan saobraćaj i vreme — ali to izlazi iz okvira ovog rada. Ovde se fokusiram na jednostavniji, statički model, koji služi kao osnova za dalji razvoj ka tom cilju.
Model
Da bi ovo uopšte funkcionisalo, prostor grada tretiram kao pojednostavljenu dvodimenzionalnu ravan, gde se blizina meri standardnom Euklidskom distancom — vazdušnom linijom. Na ovim pravilima počiva i sama konstrukcija Voronoj dijagrama: Voronoj ćelija jednog vozila nije ništa drugo do presek svih njegovih pojedinačnih "pobeda" nad ostalim vozilima u sistemu. Ovo je direktna varijanta klasičnog "problema pošte" iz računarske geometrije — umesto da se za svakog korisnika iznova računa udaljenost do svakog vozila, dovoljno je znati u kojoj se zoni nalazi, čime se spora aritmetika pretvara u brzu geometrijsku pretragu.
Implementacija: pristup:
Za samu konstrukciju Voronoj dijagrama koristim "plane-sweep" tehniku — metod pokretne linije koji postiže optimalnu vremensku složenost O(n log n), uz DCEL (Doubly Connected Edge List) kao standardnu strukturu za čuvanje planarnih grafova. Implementacija je urađena u Python-u; iako je Python sporiji od recimo C++ ili Jave, taj nedostatak nestaje upotrebom NumPy i SciPy biblioteka za vektorizovane operacije. Jedan detalj mi je bio posebno važan: korišćenje fiksnog semena (seed) za generator slučajnih brojeva. Raspored vozila jeste slučajan, ali uz fiksni seed svako pokretanje programa daje identičan raspored i oblik zona — što znači da mogu tačno da proverim kako sistem donosi odluku o dodeli vozila, bez buke koju bi uneli uvek novi, nasumični podaci.
Ovih par linija definiše ceo scenario simulacije — veličina grada, broj vozila, broj putnika, i seed za generator slučajnih brojeva. Menjanjem samo ovih brojeva mogu da testiram sistem u potpuno drugačijim uslovima — od 3 vozila i par putnika, do 24 vozila i 12 putnika u gužvi — bez diranja ijedne linije logike ispod.
# Constants
GRID_SIZE = 10
NUM_TAXIS = 24
NUM_CUSTOMERS = 12
SEED = 35Ove dve linije pokreću dva paralelna procesa. Voronoi klasa (preko Fortune-ovog algoritma) deli grad na zone odgovornosti — to je vizuelni sloj, ono što se crta na mapi. KDTree radi nešto inženjerski važnije: slaže iste koordinate u strukturu optimizovanu za brzu pretragu po nivoima, umesto sporog poređenja "jednog po jednog" vozila. Rezultat je sistem koji u isto vreme ima sliku za čoveka i brzu strukturu za računar — dva različita prikaza istih podataka, svaki optimizovan za svoju svrhu.
# Core Logic
vor = Voronoi(taxi_points)
tree = KDTree(taxi_points)Svaka obojena zona na mapi pripada tačno jednom vozilu — granice su izračunate tako da je svaka tačka unutar zone bliža tom vozilu nego bilo kom drugom. Kad se pojavi novi putnik, sistem ne mora da proveri svih 24 vozila pojedinačno — dovoljno je da pogleda u kojoj se zoni putnik nalazi, i aritmetička pretraga postaje geometrijska.
Umesto da se za svakog putnika posebno pretražuje lista vozila, KD-stablu se prosleđuje kompletna matrica koordinata svih putnika odjednom. Rezultat su dva niza — udaljenost i indeks najbližeg vozila za svakog putnika — izračunata u deliću sekunde, čak i kad ima stotine zahteva istovremeno.
# Query - Find nearest taxi for ALL customers
distances, indices = tree.query(customer_points)
nearest_taxis = taxi_points[indices] # Array of nearest taxi coordinatesMatematički, zone na ivici grada nemaju kraj — pružaju se u beskonačnost. Funkcija voronoi_finite_polygons_2d rešava taj problem tako što izračuna gde bi se ivica "trebala" završiti i zatvori oblik u validan poligon. Drugi deo istog problema je da ti poligoni onda štrče daleko van granica mape — za to koristim Sutherland-Hodgman algoritam za sečenje, koji poligon secira duž svake ivice mape dok ne ostane samo deo koji stvarno pripada gradu. Rezultat je čist, zatvoren mozaik zona bez ijedne vizuelne greške.
# --- Helper Functions for Finite Voronoi Regions ---
def voronoi_finite_polygons_2d(vor, radius=None):
"""
Reconstruct infinite voronoi regions in a 2D diagram to finite
polygons.
"""
if vor.points.shape[1] != 2:
raise ValueError("Requires 2D input")
new_regions = []
new_vertices = vor.vertices.tolist()
center = vor.points.mean(axis=0)
if radius is None:
radius = vor.points.ptp().max() * 2
# Construct a map between point index and all ridges
# (point index, point index) -> [ridge index, ridge index, ...]
all_ridges = {}
for (p1, p2), (v1, v2) in zip(vor.ridge_points, vor.ridge_vertices):
all_ridges.setdefault(p1, []).append((p2, v1, v2))
all_ridges.setdefault(p2, []).append((p1, v1, v2))
# Reconstruct infinite regions
for p1, region_idx in enumerate(vor.point_region):
vertices = vor.regions[region_idx]
if all_ridges.get(p1) is None:
continue
ridges = all_ridges[p1]
new_region = [v for v in vertices if v >= 0]
for p2, v1, v2 in ridges:
if v2 = 0:
# finite ridge: already in the region
continue
# Compute the missing endpoint of an infinite ridge
t = vor.points[p2] - vor.points[p1] # tangent
t /= np.linalg.norm(t)
n = np.array([-t[1], t[0]]) # normal
midpoint = vor.points[[p1, p2]].mean(axis=0)
direction = np.sign(np.dot(midpoint - center, n)) * n
far_point = vor.vertices[v2] + direction * radius
new_region.append(len(new_vertices))
new_vertices.append(far_point.tolist())
# Sort vertices counterclockwise
vs = np.asarray([new_vertices[v] for v in new_region])
c = vs.mean(axis=0)
angles = np.arctan2(vs[:,1] - c[1], vs[:,0] - c[0])
new_region = np.array(new_region)[np.argsort(angles)]
new_regions.append(new_region.tolist())
return new_regions, np.asarray(new_vertices)Linije koje povezuju putnike sa dodeljenim vozilima nikad se ne ukrštaju sa granicom tuđe zone — to je vizuelni dokaz da matematika iza sistema radi kako treba. Za svakog putnika program računa udaljenost vazdušnom linijom tačno na dve decimale, u proseku za par milisekundi. To znači da sistem može da obradi stotine zahteva istovremeno bez ikakvog zastoja.
Zaključak
Ovaj rad potvrđuje da Voronoj dijagrami imaju realnu primenu kao alat za podelu teritorije — transformacija mape u zone uticaja pravi podatke razumljive čoveku, što smanjuje kognitivno opterećenje dispečera: umesto čitanja tabela, odluka postaje pogled na mapu. Arhitektura se pokazala kao prava odluka — razdvajanje vizuelnog sloja (Voronoj za prikaz) od računarskog sloja (KD-stablo za pretragu) je ono što sistemu omogućava da radi u realnom vremenu bez kašnjenja, čak i na većim skupovima podataka.
Ipak, ovo je solidna statička osnova, ne gotov proizvod. Da bi postao komercijalno upotrebljiv alat, sistemu nedostaje: red čekanja, dinamičko ažuriranje statusa vozila, prelazak sa vazdušne linije na realnu putnu mrežu (generalizovani mrežni Voronoj dijagrami), vremenska komponenta, i povezivanje sa API servisima poput Google Maps-a. Put od akademske demonstracije do alata sa realnim potencijalom u privredi je jasan — samo nije još prehodan.
Dev Log
- v1.0 · Jan 2026 Osnovni Voronoj model + KD-stablo za pretragu najbližeg vozila
- v1.1 · Jan 2026 Rešen problem beskonačnih regiona (voronoi_finite_polygons_2d)
- v1.2 · Jan 2026 Dodato sečenje poligona na granice mape (Sutherland–Hodgman)
Treba vam developer u timu?
Dostupan sam za saradnju kao developer — za stalnu poziciju ili pojačanje na projektu.
Budite u toku!
Novi postovi, projekti i alati — direktno na Vas email.