Bára Křížová, Katka Osvaldová: Hledání nejrychlejší cesty napříč dopravními prostředky

Cíl projektu

Projekt, o kterém se chystáte číst, vznikl jako závěrečná práce Katky Osvaldové a Báry Křížové v rámci VI. Běhu Digitální Akademie Czechitas. Před akademií jsme se neznaly a dohromady nás svedla chuť naučit se programovat v Pythonu. Ještě před Meet your mentor jsme měly o našem projektu jen mlhavou představu. Věděly jsme, že se chceme zaměřit na Python a zajímají nás témata jako technologie, ekologie, Smart Cities… Během rozhovorů s mentory začínal náš projekt získávat jasnější obrysy a po rozhovoru s Tomášem Rudoleckým z Honewellu, který nás odrovnal svým nadšením pro náš záměr, jsme si jen přály, aby to klaplo a Tomáš byl naším mentorem. Stalo se a my jsme začaly nad naším projektem přemýšlet trochu usilovněji. Ze všech nápadů se nám nakonec nejvíc líbila myšlenka vytvořit aplikaci, která by uměla vyhledat trasu z místa na místo napříč dopravními prostředky. Tedy tak, aby uživatel zadal odkud a kam chce jít a aplikace už mu řekla, tady jdi 3 minuty pěšky na zastávku autobusu, pak jeď na tuhle zastávku a přesedni na metro, vystup na jiné zastávce a pokračuj 5 minut pěšky. Myšlenka to byla krásná a nadšení bylo ze začátku veliké.

Postup práce

Hned od začátku jsme se s naším mentorem shodli, že budeme používat nejprve data umělá a pokud půjde vše dobře, tak data reálná přidáme později. Začaly jsme tedy vytvořením krásného modelu databáze abychom se na další schůzce s Tomášem usnesli, že je pro naše potřeby složitá a že ho nejspíš vůbec nebudeme potřebovat.



 

   
Začaly jsme tedy znovu a to nakreslením mapky naše modelové města. Mapka sestává z deseti bodů různě propojených dopravními prostředky. Pro začátek jsme zvolily autobus, metro a kolo. Na základě mapky jsme si vytvořily CSV s potřebnými daty a radovánky s Pythonem mohly začít.

Na několik dalších týdnů se naším nejlepším kamarádem stal Google a Stack Overflow. Pracovaly jsme v interaktivním vývojovém prostředí Spyder, kde jsme si vyzkoušely debugging jednotlivých částí kódu. Po pár nezdárných pokusech jsme našly funkci find_shortest_path, která vypadala celkem užitečně a pustily se do upravování, tak aby dělala to co chceme my. Jako první jsme přidaly funkci, která importuje CSV a hodnoty načte jako graf (mapu), jelikož funkce find_shortest_path pracuje s grafem jako vstupním parametrem. Součástí funkce je kód, který načte CSV soubor do seznamu řádků. Další část vynechá první řádek s hlavičkou tabulky. Funkce add_row_to_graph prochází seznam řádek po řádku a přidává je do grafu (mapy).

Funkci pro načítání CSV dat jsme jednoduše upravily tak, aby uživatel mohl zadat start a cíl své cesty. 

Vyhledávací algoritmus find_shortest_path jsme nejprve testovaly  na jednodušším grafu, který jsme si přímo do kódu zadaly ručně. Poté jsme funkci rozšířily o možnost vyhledávání pro různé způsoby dopravy. Výstupem funkce je nejkratší cesta mezi uživatelem zadaným startem a cílem a je popsána pomocí kroků. Krokem je myšlena spojnice sousedních bodů. Krok je reprezentován čtveřicí, která obsahuje start kroku, cíl kroku, délku kroku a způsob dopravy. Výstup ve formě kroků (čtveřic) je důležitý pro funkci print_path.

Funkce print_path má za úkol uživatelsky přívětivě vytisknout  popis nalezené nejkratší cesty formou jednotlivých kroků.

Mapka a vykreslení trasy

Pro závěrečné vykreslení mapky s jednotlivými body jsme použili knihovnu networkx, modul matplotlib. Souřadnice jsme zvolily podle původní mapky navržené v OpenOffice Draw. nx.draw_networkx_nodes vykreslí jendotlivé body podle souřadnic v proměnné pos. nx.draw_networkx_labels pak každému bodu přiřadí název.

  

Na závěr jsme mapku propojily s vystupem funkce print_path použitím

nx.draw_networkx_edges(G,pos,edgelist=node_path, width=8,alpha=0.5,edge_color='b') pro vykreslení doporučené trasy.

Ukázka výpočtu nejrychlejší cesty z bodu A do bodu I a její vykresní v mapce. Nejrychlejší cesta nemusí být zároveň tou nejkratší.

Ukázka vykreslení přímé cesty:

Vize do budoucna

 Cílem projektu nebylo vytvoření "production-ready"aplikace se vším všudy, spíše si vyzkoušet, jak u podobných projektů postupovat. Jedním z nápadů, ke kterým jsme se z časových důvodů nedostaly, bylo propojení kodu s interaktivní mapou reálného města, která by umožnila uživateli jednoduše zadat start a cíl své cesty a zapracování jízdních řádů s ohledem na přestupy a čekání na návaznosti jednotivých spojů.



Poděkování

Velké díky patří našemu mentorovi Tomáši Rudoleckému z Honeywellu za jeho nekonečnou trpělivost a nadšení pro věc a našim partnerům, kteří nás během celého studia podporovali, zejména Blažejovi, který nám pomohl projekt rozdělit na jednotlivé 'must have' a 'nice to have' úkoly a realisticky odhadnout čas potřebný k dotažení projektu do rozumné podoby.
 
Zdroje

Stack Overflow [online]. Stack Exchange, 2017 [cit. 2017-07-23]. Dostupné z: https://stackoverflow.com.

Networkx [online] Dostupné z: https://networkx.github.io/documentation/stable/index.html