V posledních letech je k dispozici stále více dat vhodných jako podklad pro výpočet dopravních intenzit, ale softwarové nástroje pro tvorbu velkých modelů z těchto dat nejsou dostupné. Cílem této práce je analyzovat, navrhnout a otestovat implementaci transportních modelů ve škálovatelném paralelním výpočetním prostředí. Práce se především zaměřuje na odhad matice přepravních vztahů a na přidělování zátěže na síť. Vhodné paralelní algoritmy jsou popsány, vyhodnoceny a implementovány ve výpočetním prostředí typu MapReduce (pro tento účel je používán Apache Spark). Implementované metody jsou testovány na datech o různé velikosti. Výsledky těchto testů ukazují, že pomocí vyvinutého frameworku lze vytvořit velké modely (například model celé Evropy, který obsahuje milióny hran) v řádu desítek hodin.
Anotace v angličtině
Nowadays, a lot of transport-related data for a traffic modeling are available, but present software tools that can process such data volume and compute large models are still lacking. The aim of this thesis is to analyse, design and test an implementation of the transport models in the scalable parallel computing environment. More particularly, the work is primarily focused on the Origin-Destination matrix estimation and the traffic assignment, which are the essential parts for traffic volume modeling. Parallel algorithms that are suitable for such a problem are described, evaluated and implemented into the Map-Reduce computing model (Apache Spark is used for such a purpose). Implemented methods are tested on various-sized datasets and the test results are demonstrated . Experiments have shown, that the proposed solution is capable of processing a large-scale model (e.g. a model of whole Europe consisting of millions of edges) within a time frame of tens of hours.
Klíčová slova
Map-Reduce, odhad matice přepravních vztahů, přidělování zátěže na síť, distribuované výpočetní prostředí, Apache Spark, intenzity dopravy, paralelní výpočty
V posledních letech je k dispozici stále více dat vhodných jako podklad pro výpočet dopravních intenzit, ale softwarové nástroje pro tvorbu velkých modelů z těchto dat nejsou dostupné. Cílem této práce je analyzovat, navrhnout a otestovat implementaci transportních modelů ve škálovatelném paralelním výpočetním prostředí. Práce se především zaměřuje na odhad matice přepravních vztahů a na přidělování zátěže na síť. Vhodné paralelní algoritmy jsou popsány, vyhodnoceny a implementovány ve výpočetním prostředí typu MapReduce (pro tento účel je používán Apache Spark). Implementované metody jsou testovány na datech o různé velikosti. Výsledky těchto testů ukazují, že pomocí vyvinutého frameworku lze vytvořit velké modely (například model celé Evropy, který obsahuje milióny hran) v řádu desítek hodin.
Anotace v angličtině
Nowadays, a lot of transport-related data for a traffic modeling are available, but present software tools that can process such data volume and compute large models are still lacking. The aim of this thesis is to analyse, design and test an implementation of the transport models in the scalable parallel computing environment. More particularly, the work is primarily focused on the Origin-Destination matrix estimation and the traffic assignment, which are the essential parts for traffic volume modeling. Parallel algorithms that are suitable for such a problem are described, evaluated and implemented into the Map-Reduce computing model (Apache Spark is used for such a purpose). Implemented methods are tested on various-sized datasets and the test results are demonstrated . Experiments have shown, that the proposed solution is capable of processing a large-scale model (e.g. a model of whole Europe consisting of millions of edges) within a time frame of tens of hours.
Klíčová slova
Map-Reduce, odhad matice přepravních vztahů, přidělování zátěže na síť, distribuované výpočetní prostředí, Apache Spark, intenzity dopravy, paralelní výpočty
Provedení rešerše v oblasti modelování dopravních intenzit a dostupného software pro tyto účely
Implementace vhodných algoritmů v prostředí Apache Spark
Provedení testování implementovaného řešení
Zásady pro vypracování
Provedení rešerše v oblasti modelování dopravních intenzit a dostupného software pro tyto účely
Implementace vhodných algoritmů v prostředí Apache Spark
Provedení testování implementovaného řešení
Seznam doporučené literatury
Jan T. Lundgren, Anders Peterson, A heuristic for the bilevel origindestination-matrix estimation problem, Transportation Research Part B: Methodological, Volume 42, Issue 4, May 2008, Pages 339-354, ISSN 0191-2615, http://dx.doi.org/10.1016/j.trb.2007.09.005.
Spiess, H. (1990) A gradient approach for the OD matrix adjustment problem, CRT Pub. No 693, Centre de Recherche sur les Transports, Universit de Montral, Montreal, Canada.
Peterson, A. (2007) The origin-destination matrix estimation problem : Analysis and computations.
Bera, S., Rao, K.V.K. (2011) Estimation of origin-destination matrix from traffic counts: the state of the art
DEAN, J.; GHEMAWAT, S.: MapReduce: simplified data processing on large clusters. Communications of the ACM, ročník 51, č. 1, 2004: s. 107113.
Seznam doporučené literatury
Jan T. Lundgren, Anders Peterson, A heuristic for the bilevel origindestination-matrix estimation problem, Transportation Research Part B: Methodological, Volume 42, Issue 4, May 2008, Pages 339-354, ISSN 0191-2615, http://dx.doi.org/10.1016/j.trb.2007.09.005.
Spiess, H. (1990) A gradient approach for the OD matrix adjustment problem, CRT Pub. No 693, Centre de Recherche sur les Transports, Universit de Montral, Montreal, Canada.
Peterson, A. (2007) The origin-destination matrix estimation problem : Analysis and computations.
Bera, S., Rao, K.V.K. (2011) Estimation of origin-destination matrix from traffic counts: the state of the art
DEAN, J.; GHEMAWAT, S.: MapReduce: simplified data processing on large clusters. Communications of the ACM, ročník 51, č. 1, 2004: s. 107113.