Practical Route Planning Algorithms
Ondrej Moriš · 2012
Cestni siť je možne modelovat prostřednictvim orientovaneho multigrafu s ohodnocenim hran reprezentujicim zvolenou metriku. Výsledkem tedy je, že problem planovani cest se da formulovat jako varianta velmi dobře znameho problemu hledani nejkratsi cesty v grafech reprezentujicich skutecne světove cestni sitě. Neformalně řeceno, (řidici) jsou dany dva vrcholy (GPS souřadnice) v grafu (cestni siť) a cilem je najit optimalni tah (nejlepsi cestu) z jednoho vrcholu do druheho vzhledem k daným kriteriim optimality. Bohužel, zakladni algoritmy resici tento problem nejsou vhodne pro obrovske cestni sitě s mnoha dalsimi atributy. Dizertacni prace se bude zabývat praktickými aspekty planovani cest ve světových cestnich sitich. Nas výzkum bude zaměřený na teoreticky a zaroveň i prakticky efektivni a korektni algoritmy davajici požadovane zrychleni za cenu pouze maleho množstvi prepocitaných dat. Budeme zkoumat predevsim kvalitu cest jako napriklad komfort ci smysluplnost, zformulujem prakticky motivovane kriteria optimality. Ty pote využijeme pro navrh dokazatelně optimalnich planovacich algoritmů. Chceme, aby nove algoritmy co nejvice zodpovidali lidske intuici při planovani cest.