ITAT 2013 Proceedings, CEUR Workshop Proceedings Vol. 1003, pp. 29–34 http://ceur-ws.org/Vol-1003, Series ISSN 1613-0073, c 2013 V. Martínek, M. Žemlička Spolehlivost přestupů Vladislav Martínek1 a Michal Žemlička2 1 Dept. of Software Engineering Charles University in Prague Prague, Czech Republic martinek@ksi.mff.cuni.cz 2 Network and Labs Management Center Charles University in Prague Prague, Czech Republic zemlicka@sisal.mff.cuni.cz Abstrakt: Klasické algoritmy používané pro vyhledávání 2 Přestupy cest v sítích hromadné dopravy typicky očekávají, že po- měrně přesně známe délku cesty mezi jednotlivými uzly, i Základním úkolem plánovače spojení v městské hromadné že víme, kdy přesně daný spoj odjede a přijede. Mnoho lidí dopravě je nalezení nejvhodnější cesty v komplexní do- z vlastní zkušenosti ví, že tyto výchozí údaje pro vyhle- pravní síti. Podoba výsledného spojení je dána volbou pře- dávání spojení mohou být ovlivněny celou řadou faktorů. pravních prostředků v nástupních a přestupních bodech. Dopad vnějších vlivů lze za určitých podmínek odhadnout Často to, jak na sebe jednotlivé spoje navazují, ovlivní vý- z dostupných historických dat. běr cesty. Čím více informací budeme mít o návaznosti V tomto příspěvku nahlédneme na plánování cest v jednotlivých spojů, tím kvalifikovanější rozhodnutí může hromadné dopravě z pravděpodobnostního hlediska. Uká- učinit plánovač při výběru spojení. žeme, jak určit spolehlivost přestupů a předneseme vy- Praktický příklad, část 1: Jan má pracovní schůzku, braná praktická využití. na kterou by neměl přijít pozdě. Schůzka začíná v 15:00. Jan chce mít jistotu, že dorazí včas, tak si nechá 10 minut rezervu. Plánovač nabídne dvě cesty. První spojení je tvořeno linkou 22 a 18, cesta začíná v 14:37 1 Úvod a v cíli by měl Jan být v 14:47. Druhé spojení za- číná v 14:38 a v cíli je v 14:48, používá linky 9 a 17. Jan vybere první spojení, protože je v cíli dříve a také neobsahuje pěší přechod mezi zastávkami. Učinil V prostředí velkých měst mají lidé často na výběr vedle správné rozhodnutí? Bude Janovi skutečně stačit re- individuálních způsobů přepravy také rozsáhlou sít’ hro- lativně velká 10 minutová rezerva pokud nějaká část madné přepravy. Ve druhém případě může být spojení plá- plánu cesty nevyjde? nováno na základě jízdních řádů vydaných dopravcem. Při cestování se většinou snažíme nalézt nejkratší nebo jinak výhodnou cestu. To nám ulehčují různé plánovače spojení, které na základě jízdních řádů hledají nejkratší cesty vět- 2.1 Přestup podle jízdního řádu šinou s malým počtem přestupů. Netriviální dopravní spojení je realizováno alespoň dvěma Spolehlivost naplánovaných tras závisí na dodržování různými prostředky. Přestup mezi dvěma linkami je pláno- časů daných jízdním řádem. Chování reálných dopravních ván na základě času příjezdu prvního spoje, doby potřebné sítí však obsahuje prvek náhodnosti. Co když se spoj, kte- pro přesun cestujícího mezi zastávkami a času příjezdu cí- rým jedeme, zdrží v husté dopravě, stihneme pak přestup lového spoje. Jízdní řády dávají cestujícímu stabilní infor- na další spoj, jak bylo v plánu? Počítal plánovač se zdrže- maci o době, kterou stráví čekáním na zastávce. ním, protože touto denní dobou mají určité spoje v určitém Pokud se řídíme striktně jízdním řádem, spoléháme na úseku často zpoždění? Nebo stihneme přestoupit jen proto, to, že každý spoj dané linky je na zastávce vždy v přede- že interval navazujícího spoje vyšel dostatečně daleko od psaný okamžik. Počítáme s tím, že 100% spojů je přista- našeho plánovaného času příchodu na zastávku? veno k zastávkovému ostrůvku v čas určený jízdním řá- V úvodní části článku je popsaná problematika, kterou dem. Při výpočtu doby pro přestup nepočítáme s tím, že se budeme zabývat. Dále je rozebrán mechanismus pře- by se nějaké procento spojů opozdilo. Situaci ukazuje ob- stupů. Následuje sekce věnující se zpoždění a metodami, rázek 2. které se snaží tento negativní jev ošetřit. Článek předkládá Pokud dochází k přestupu v rámci jednoho ostrůvku, metody jak využít historických provozních dat ke zvýšení pak je čas potřebný pro výstup z prvního spoje a čas po- spolehlivosti plánování cest. V závěru shrnujeme prezen- třebný pro nástup do dalšího spoje brán jako minimální čas tované poznatky a formulujeme cíle pro budoucí práci. pro přestup. Pokud bychom uvažovali přestup mezi spoji, 30 V. Martínek, M. Žemlička 2.2 Rezerva při přestupu 14:35 A Doba vyhrazená na změnu spoje je tvořena dobou nutnou A pro výstup cestujícího z výchozího spoje a přesun mezi zastávkami (tato doba je nutná a nelze ji zkrátit) a dobou 22 strávenou čekáním na příjezd cílového spoje. 6 min 9 3 min Ve skutečnosti, se často stává, že se spoj zpozdí a v tom 14:40 případě se posouvá časový interval vyhrazený pro přestup mezi spoji. S dobou pro přesun cestujícího mezi zastáv- 2 min kami se hýbat nedá, ale vzniklé zpoždění spoje lze kom- penzovat dobou pro čekání na příjezd cílového spoje. Na- víc pokud i cílový spoj má zpoždění, vzniká tak další re- 2 min 3 min zerva. Doba, která měla být podle plánu cestujícím proče- 14:45 kána na příjezd cílového spoje, může být ve skutečnosti 18 2 min spotřebována jako přirozená rezerva pro případné zpož- 17 dění výchozího spoje. 2 min B B 2.3 Selhání přestupu 14:50 Pokud je odchylka od jízdních řádů příliš velká nebo po- kud spoje navazují příliš těsně, může dojít k tomu, že ces- tující navazující spoj nestihne a přestup se neuskuteční podle plánu. V takovém případě je cestující nucen změ- nit zbývající část plánu. To typicky vede k nedodržení po- Obrázek 1: Janův plán cesty. (na svislé ose je čas) žadovaného času příjezdu, což může být pro cestujícího značně nepříjemné. které přijedou ve stejný okamžik, nebylo by možné zaru- čit pořadí příjezdu spojů na zastávku ani bezpečný pře- 2.4 Spolehlivost přestupu stup mezi nimi. Uvažujme 1 minutu jako minimální čas potřebný pro přestup. Celková doba mezi příjezdem tram- Spolehlivost přestupu lze nahlížet jako poměr nedodrže- vaje č.22 a odjezdem tramvaje č.18 jsou 2 minuty. Cestu- ných naplánovaných přestupů vůči všem naplánovaným jící tedy čeká 1 minutu na příjezd tramvaje č.18. přestupům. Zvýšením spolehlivosti přestupů bychom zvý- šili celkovou spolehlivost plánování, zvláště u plánů cest, které sestávají z více různých úseků. Hlavní příčinou se- lhání přestupů bývají odchylky od plánovaného provozu. 100 80 60 40 3 Zpoždění 20 0 14:42 14:43 14:44 14:45 14:46 14:47 14:48 14:49 14:50 14:51 Existuje několik způsobů jak se vyrovnat s nepravidelností provozu hromadné dopravy při plánování spojení. Jeden 100 z jednoduchých přístupů je jet o jeden spoj dříve. Tento 80 60 přístup je časově neefektivní zvláště v případě, kdy spoje 40 mají dlouhý interval. 20 0 Přidávat rezervu navíc ke každému přestupu je nevý- 14:42 14:43 14:44 14:45 14:46 14:47 14:48 14:49 14:50 14:51 hodné. Plánovač by pak uživateli předkládal spojení ča- sově náročnější, než je ve skutečnosti potřeba. Prodlužo- vala by se tak paušálně doba čekání a tím i celková délka 1 min 1 min cesty, což je nežádoucí. Je proto potřeba nalézt určitý po- stup pro vyhodnocení případů, kdy se rezerva vyplatí a jak velká má být. Obrázek 2: Přestup mezi linkami 22 a 18 podle jízdního Pokud máme informaci o možném zpoždění na dané řádu. (na svislé ose je zpoždění ve vteřinách, na vodoroné lince, můžeme tomu přizpůsobit plán cesty. Můžeme díky ose je čas) těmto znalostem zvolit jinou linku, což může vést k naplá- nování zcela odlišné trasy. Spolehlivost přestupů 31 3.1 Nepravidelnost provozu zdrojový spoj jezdí se zpožděním a cílový spoj jezdí pra- videlně včas. Předpokládejme, že ve stejnou denní dobu Plánování spojení je typicky vázáno na jízdní řády dané bude zpoždění spojů blízké průměru z minulého období. dopravcem. Nepravidelnosti v jízdních řádech jsou dobře Pokud predikci zpoždění spojů založenou na provozních známým jevem, objevují se napříč různými úrovněmi pře- datech z minulého období plošně aplikujeme na jízdní řády pravní sítě hromadné dopravy osob, jak ukazuje [1]. Na v následujícím období, můžeme tak vylepšit výchozí data zpoždění vznikající v dopravní síti může být nahlíženo pro určování přestupů. Tím se zvýší spolehlivost v daném různě. Existuje celá řada statistických ohodnocení. Yetis- případě na 80% až 90%. Konkrétní hodnoty ukazuje ta- kul a Senbil [2] se zabývají distribucí dojezdových časů bulka 1. během dne s ohledem na geografické oblasti města An- kara. Olson a Haugland [3] rozdělují zpoždění na hlavní a Spolehlivost přestupů tram. linky vedlejší. Primární jsou způsobena přímým vlivem doprav- podle jízdních řádů: 20-18 12-9 ních prostředků, zatímco ta sekundární jsou zavlečena ze dopravce 86,91% 72,27% spojů, na které se čeká. predikovaných po dnech 89,33% 80,63% predikovaných po hodinách 89,38% 87,59% 3.2 Plánování spojení s pomocí AVL dat Tabulka 1: Spolehlivost predikce pro přestupy mezi lin- Řada dopravců monitoruje pohyb svých přepravních pro- kami 20-18 a 12-9 středků pomocí systémů automatického sledování vozidel - Automated Vehicle Location(AVL). Pokud systém AVL pracuje v reálném čase, pak je možné tyto informace vy- 4 Pravděpodobnostní mapy užít k aktualizaci plánu spojení. Takto získaná aktuální provozní data lze využít k predikci odchylek od jízdních Z předchozího je vidět, že i jednoduchá predikce zalo- řádů v krátkodobém výhledu. Příkladem aplikace tohoto žená na průměrném zpoždění přináší na dané dopravní síti přístupu je [4, 5]. výsledky. Nicméně pro přesnější vyhodnocování spolehli- Nevýhodou tohoto přístupů je, že zpoždění spoje je vosti přestupů bychom potřebovali jemnější metodu. Pře- možné predikovat až od okamžiku, kdy zpoždění nastalo v devším potřebujeme odhadnout, zda je doba, kterou plá- dřívější části trasy spoje. To znamená, že plán je nutné mě- novač přiřadil přestupu, dostatečná a přestup neselže. nit v okamžiku, kdy je již částečně realizován. To s sebou nese výrazná omezení. Na základě statistického zpracování historie provozních 4.1 Plánovaný výskyt spoje dat je však možné do jisté míry předvídat chování spojů, Jízdní řády říkají, kdy by se daný spoj měl vyskytovat na co se týká zpoždění [6]. Máme tak možnost počítat s prav- zastávce, rozlišují pouze dva stavy: spoj je na zastávce děpodobnými odchylkami už ve fázi prvotního plánování. a spoj není na zastávce. Pokud zaznamenáme předpoklá- Cestující tak dostane do ruky plán spojení, který ho pře- daný výskyt spoje na dané zastávce v daný časový úsek, dem informuje o rezervách, které byly přidány kvůli prav- získáme graf 3. děpodobnému zpoždění spoje. Zajímavý přístup jak reali- zovat predikci zpoždění pomocí neuronové sítě byl testo- ván Mazloumi et al. [7]. Na základě predikce je pak možné 100 počítat s pravděpodobnou hodnotou zpoždění a sestavit 80 60 podle toho požadované spojení. 40 20 0 3.3 Průměrné zpoždění v Praze 00 05 10 15 20 25 30 35 40 45 50 55 V současné době máme k dispozici provozní data tram- vajové dopravy v Praze z roku 2008. Data byla získána z Obrázek 3: Četnost výskytu spojů linky 18 podle jízdního AVL systému „DORIS“. Provozní data jsou porovnávána řádu. (na svislé ose je četnost, na vodoroné ose je čas v s plánovanými jízdními řády tak, aby bylo možné určit od- minutách) chylky. Každý záznam je datován, lze tedy zpětně rekon- struovat skutečný průběh jízdy každého spoje, který vyjel na trasu. Data zkoumáme již delší dobu. Při rozboru jsme 4.2 Četnost zpoždění pozorovali výrazné periodicity v odchylkách jednotlivých spojů vázané na denní dobu, zejména v pracovní dny. Na základě historických provozních dat jsme pro každou Jeden z možných přístupů jak dosáhnout efektivního linku schopni říct, kolikrát za určité období přijela na da- využití rezervního času je počítat s pravděpodobným nou zastávku včas, kolikrát se zpozdila o minutu, dvě, zpožděním v případech, kdy si to situace vyžaduje. Jeden apod. nebo kolikrát přijela o minutu dříve. Když tato data z případů, kdy dochází k častému selhání přestupu je, když vyneseme na časovou osu, získáme graf četností zpoždění. 32 V. Martínek, M. Žemlička   60 ∑ p1 (t1 ) ∗ ∑ p2 (t2 ) , t1 (t1 +tm )<=t2 50 40 kde: 30 20 10 t1 ,t2 je čas, 0 -1 0 1 2 3 4 5 tm je minimální doba pro přestup, p1 (t), p2 (t) je pravděpodobnost příjezdu spoje 1,2 v čase t. Obrázek 4: Rozdělení zpoždění spojů linky 18. (na svislé ose je četnost, na vodoroné ose je zpoždění ve vteřinách) Vezměme stejný přestup jako v předchozím případě, přestup mezi linkami 22 a 18 na zastávce „Malostranská“. Minimální doba potřebná pro přestup v rámci jednoho za- Graf na obrázku 4 ukazuje v kolika případech a o kolik se stávkového ostrůvku zůstává - 1 minuta. Obrázek 6 uka- v minulosti opozdil daný spoj na dané zastávce. zuje pravděpodobnostní mapy obou spojů. Dobu přestupu Na základě dřívějších zkušeností víme, že konkrétní nelze určit jednoznačně jako v předchozím případě. spoje se zpoždují pravidelně zejména s vazbou na denní dobu. Dále také víme, že na základě historických provoz- ních dat, lze vytvořit použitelnou predikci zpoždění. Po- 30 kud tedy budeme předpokládat, že četnost zpoždění bude 20 stejná jako v minulosti, pak lze výskyty v grafu 4 lze po- p1 10 užít jako predikci chování spojů dané linky. Předpoklá- dejme, že o stejnou dobu se zpozdí stejné procento spojů. 0 14:42 14:43 14:44 14:45 14:46 14:47 14:48 14:49 14:50 14:51 V tom případě výskyty spojů nebudou odpovídat jízdnímu řádu, ale upravené pravděpodobnostní mapě 5. Takto od- 80 hadnuté chování spojů dané linky by mělo lépe odpovídat 60 realitě. 40 p2 20 0 100 14:42 14:43 14:44 14:45 14:46 14:47 14:48 14:49 14:50 14:51 80 60 40 20 0 1 min 00 05 10 15 20 25 30 35 40 45 50 55 Obrázek 5: Četnost výskytu spojů linky 18 odhadnutá Obrázek 6: Informovaný přestup mezi linkami 22 a 18. (na podle rozdělení zpoždění. (na svislé ose je četnost, na vo- svislé ose je četnost, na vodoroné ose je čas) doroné ose je čas v minutách) Pokud tramvaj č.22 přijede před 14:44 včetně, je zde vysoká pravděpodobnost, že cestující stihne přestoupit na linku 18. Většina výskytů linky 18 je až od 14:45, což je v 4.3 Informovaný přestup souladu s jízdním řádem. Pokud však tramvaj č.22 přijede V případě spojů, u kterých pravidelně dochází k odchyl- o 2 a více minut později, než by měla podle jízdního řádu, kám od jízdního řádu, může být výhodné odhadovat zpož- tj. 14:45 a později, je pravděpodobnost stihnutí přestupu dění například pomocí historických provozních dat. Po- jen 26%. Přitom podle četnosti tato možnost představuje kud použijeme dřívější výskyty zpoždění k vytvoření prav- 52% všech relevantních příjezdů tramvaje č.22 v danou děpodobnostní mapy, můžeme tak získat relevantní před- dobu. stavu o chování spoje v kontextu dané zastávky. V tomto případě se nelze spolehnout na výskyt spoje na zastávce v 4.4 Aplikace jeden okamžik. Je potřeba spočítat pravděpodobnost kom- binací výskytů relevantních spojů, které jsou od sebe na Ukazuje se, že jednou z cest ke zvýšení spolehlivosti plá- časové ose vzdálené alespoň minimální dobu potřebnou nování spojení, je odhadovat pravděpodobný průběh pře- pro přestup. stupu. Pokud budeme schopni odhadnout úspěšnost každé Za předpokladu, že dané linky tramvají jsou na sobě ne- relevantní varianty přestupu, pak bude možné preferovat závislé, lze pravděpodobnost úspěšného přestupu odhad- při plánování spojení ty přestupy, které mají vyšší naději nout jako: na úspěch. To však vyžaduje vícekriteriální algoritmus pro Spolehlivost přestupů 33 výběr spojení. Výsledkem by mohl být návrh několika růz- 14:35 ných spojení, která jsou časově málo náročná a přitom mají dostatečně velkou naději na úspěch. Koncová volba A spojení by mohla být přenechána uživateli. A 5 Závěr 22 9 min 9 3 min 14:40 Plánování spojení v městské hromadné dopravě v sobě skrývá víc než jen úlohu nalézt nejkratší cestu k cíli. Měst- 2 min ská dopravní sít’ je úzce svázána s dalšími aspekty moder- ního života. Je potřeba vidět vyhledávání cest v stále kom- plexnějším měřítku. Dalo by se říci, že pokud dopravní sít’ dosáhne určitého stupně složitosti, chová se v urči- 3 min tém smyslu charakteristicky. Za tohoto předpokladu lze 14:45 její chování studovat a získané poznatky úspěšně využít pro predikci tohoto chování. 2 min 17 2 min Pomocí popsané metody informovaných přestupů, jsme schopni odhadnout, které přestupy by zařazením do plánu cesty mohli způsobit jeho potenciální selhání. Můžeme B 14:50 zvolit míru pravděpodobnosti, která bude určovat, který přestup je pro nás ještě spolehlivý. Jízdní řády jsou stále výchozím bodem. Už jen pouhá informace o potenciálním 18 2 min riziku selhání může být pro cestující užitečná. Praktický příklad, část 2: Janovi záleželo na včas- ném příjezdu na pracovní schůzku, proto volil rychlejší B cestu a dokonce si dal velkou časovou rezervu. Pro- blém je, že použitá linka 22 má v daném úseku často zpoždění, s čímž standartní plánovač nepočítá. Kon- Obrázek 7: Skutečný průběh Janova plánu. krétně je pravděpodobnost uskutečnění přestupu mezi linkou 22 a 18 v dané časy odhadnuta na necelých 38%. Situace je podrobně rozebrána na obrázku 6 a dů- lehlivé a přitom časově efektivní spojení. Předložené me- sledkem je pozměněný itinerář 7 Janovy cesty. Dojde tody mohou být použity pro multikriteriální vyhledávání tak s velmi pravděpodobně k nestihnutí přestupu a Jan k určení paramtru spolehlivosti. Při sestavování pravděpo- bude nucen čekat na další tramvaj linky 18. To ho zdrží dobnostních map jsou použity četnosti. Jednou z výhod je, natolik, že do cíle dorazí v 15:07, což je hluboko za že lze snadno přidávat nově získaná data. jeho prvotním očekáváním. Pokud by Jan získal třeba jen nápovědu, která trasa je spolehlivější, mohl stih- nout svou schůzku. Poděkování Pokud metodu informovaných přestupů použijeme k Tento článek byl vytvořen za podpory projektu číslo ořezávání nespolehlivých přestupů přímo v uzlech při vy- 157710 Grantové agentury univerzity Karlovy hledávání spojení, můžeme tak výrazně zvýšit spolehlivost a za podpory grantu SVV-2013-267312. plánovače. Výhodou oproti jiným metodám na zajištění spolehlivosti je, že vznikají časové rezervy jen tam, kde je nejvíce pravděpodobné, že budou spotřebovány. Reference Navíc uvedené postupy lze dobře uplatnit i na straně poskytovatele přepravních služeb. Lze například detekovat [1] P. Rietveld, F. Bruinsma, and D. van Vuuren, “Coping with problematická místa, kde často dochází k selhání plánova- unreliability in public transport chains: A case study for ného přestupu a kde cestující zbytečně tráví čas čekáním Netherlands,” Transportation Research Part A: Policy and na další spoj. V případě okrajových linek lze také dete- Practice, vol. 35, no. 6, pp. 539 – 559, 2001. kovat místa, kde například při selhání některého přetupu [2] E. Yetiskul and M. Senbil, “Public bus transit travel- zůstanou cestující izolování bez navazující dopravy. time variability in Ankara (Turkey),” Transport Policy, vol. 23, pp. 50–59, 2012. [Online]. Available: http://www. sciencedirect.com/science/article/pii/S0967070X12000789 5.1 Plány do budoucna [3] N. O. Olsson and H. Haugland, “Influencing factors on train Naším cílem do budoucna je začlenit uvedenou metodiku punctuality-results from some norwegian studies,” Transport do vyhledávače spojení tak, aby byl schopen nalézt spo- Policy, vol. 11, pp. 387–397, 2004. 34 V. Martínek, M. Žemlička [4] D. N. Tien, T. MacDonald, and Z. Xu, “TDplanner: Public transport planning system with real-time route updates based on service delays and location tracking,” in IEEE Vehicular Technology Conference, 2011. [5] A. Karbassi and M. Barth, “Vehicle route prediction and time of arrival estimation techniques for improved trans- portation system management,” in IEEE IV2003: Intelligent Vehicles Symposium, Proceedings. IEEE Intelligent Trans- portat Syst, 2003, pp. 511–516, 4th Intelligent Vehicles Sym- posium, Columbus, OH, Jun 09-11, 2003. [6] M. Hickman, “Robust passenger itinerary planning using transit AVL data,” in Intelligent Transportation Systems, 2002. Proceedings. The IEEE 5th International Conference on, 2002, pp. 840–845. [7] E. Mazloumi, G. Currie, and G. Rose, “Using traffic flow data to predict bus travel time va- riability through an enhanced artificial neural ne- twork.” [Online]. Available: http://intranet.imet.gr/Portals/0/ UsefulDocuments/documents/03377.pdf