Problem: Wytyczanie najszybszej drogi z punktu A do punktu B w mieście zakładając, że niektóre ulicę są tymczasowo zamknięte. Opis: Wykorzystanie algorytmu Dijkstry w modelowaniu samochodowego ruchu miejskiego, z uwzględnieniem czasowego wyłączenia ulic. Problem projektu sprowadza się do wyznaczania optymalnych obwodnic/ tras alternatywnych w mieście. Założono niejednorodność gęstości sieci ulic oraz prędkości samochodów.
Projekt został zrealizowany wykorzystując:
- Python
- Dash - to platforma typu open source do budowania interfejsów wizualizacji danych.
- OSMNX - pakiet Pythona, który umożliwia pobieranie danych geoprzestrzennych z OpenStreetMap oraz modelowanie, projektowanie, wizualizowanie i analizowanie rzeczywistych sieci ulic i wszelkich innych geometrii geoprzestrzennych. do wyznaczania najkrótszej trasy wykorzystaliśmy algorytm Dijkstry który zaimplementowano w funkcji Dijkstras_Shortest_Path klasy Graph:
Kod projektu znajduje się w repozytorium github: https://github.com/Barthomieu/Dijkstra_best_path.git
Strona startowa projektu prezentuje się następująco,
domyślnie pola Północ, Wschód, Południe, Zachód są ustalone na współrzędne Katowic
jednak można je zmienić wchodząc na stronę https://www.openstreetmap.org/ jest to
interfejs który współpracuje z biblioteką OSMNX. Po ustaleniu wycinka mapy który nas
interesuje, klikamy Eksport, który pokaże nam potrzebne współrzędne(pola zaznaczone na
zielono):
w podobny sposób należy określić punkt startowy i punkt końcowy. Współrzędne punktów również można określić przy pomocy portalu https://www.openstreetmap.org/ klikając PPM- >pokaż adres w określonym punkcie
Po uzupełnieniu wszystkich pól i kliknięciu przycisku “Szukaj najkrótszej trasy” przy pomocy
pakietu OSMNX zostanie wygenerowany graf którego wierzchołkami będa miejsca
przecięcie ulic:
dodatkowo w pliku json zwracane są dane wierzchołków oraz odcinków które je łączą. Poniżej fragment zwracanego pliku JSON w którym każdy wierzchołek jest opisany w następujący sposób: {"type": "node", "id": 26310253, "lat": 50.2500417, "lon": 19.0022881}, natomiast każda krawędź będąca połączeniem wierzchołków w następujący sposób
{"type": "way", "id": 29729269, "nodes": [3109781806, 2003201137, 2137893310, 3109781794, 327480519], "tags": {"highway": "residential", "lanes": "1", "name": "1 Maja", "oneway": "yes", "surface": "asphalt"}}
Przy pomocy algorytmu Dijkstry zostaje wytyczona najkrótsza trasa
jako początkowy ustalona Budynek CNTI a jako punkt końcowy ustalono Budynek N.
w efekcie otrzymujemy najkrótszą trasę która wynosi 3990m
aby zaznaczyć zamkniętą ulicę, należy wpisać jej nazwę w polu “wprowadź nazwę
zamkniętej ulicy” a następnie kliknąć przycisk “Szukaj nowej trasy”
na poniższym screenie występuje trasa przy założeniu zamknięcia ulicy 1 Maja, trasa
wydłużyła sie do 4449 metrów
Fragment pierwotnej trasy
Fragment nowej trasy: