Abstrakt: Klasické algoritmy používané pro vyhledávání cest v sítích hromadné dopravy typicky ocˇekávají, že pomeˇrneˇ prˇesneˇ známe délku cesty mezi jednotlivými uzly, i že víme, kdy prˇesneˇ daný spoj odjede a prˇijede. Mnoho lidí z vlastní zkušenosti ví, že tyto výchozí údaje pro vyhledávání spojení mohou být ovlivneˇny celou rˇadou faktor˚u. Dopad vneˇjších vliv˚u lze za urcˇitých podmínek odhadnout z dostupných historických dat.
Spolehlivost naplánovaných tras závisí na dodržování cˇas˚u daných jízdnímrˇádem. Chování reálných dopravních sítí však obsahuje prvek náhodnosti. Co když se spoj, kterým jedeme, zdrží v husté dopraveˇ, stihneme pak prˇestup na další spoj, jak bylo v plánu? Pocˇítal plánovacˇ se zdržením, protože touto denní dobou mají urcˇité spoje v urcˇitém úseku cˇasto zpoždeˇní? Nebo stihneme prˇestoupit jen proto, že interval navazujícího spoje vyšel dostatecˇneˇ daleko od našeho plánovaného cˇasu prˇíchodu na zastávku?
V úvodní cˇásti cˇlánku je popsaná problematika, kterou se budeme zabývat. Dále je rozebrán mechanismus prˇestup˚u. Následuje sekce veˇnující se zpoždeˇní a metodami, které se snaží tento negativní jev ošetrˇit. Cˇlánek prˇedkládá metody jak využít historických provozních dat ke zvýšení spolehlivosti plánování cest. V záveˇru shrnujeme prezentované poznatky a formulujeme cíle pro budoucí práci. 2
Základním úkolem plánovacˇe spojení v meˇstské hromadné dopraveˇ je nalezení nejvhodneˇjší cesty v komplexní dopravní síti. Podoba výsledného spojení je dána volbou prˇepravních prostrˇedk˚u v nástupních a prˇestupních bodech. Cˇ asto to, jak na sebe jednotlivé spoje navazují, ovlivní výbeˇr cesty. Cˇ ím více informací budeme mít o návaznosti jednotlivých spoj˚u, tím kvalifikovaneˇjší rozhodnutí m˚uže ucˇinit plánovacˇ prˇi výbeˇru spojení.
Praktický prˇíklad, cˇást 1: Jan má pracovní sch˚uzku, na kterou by nemeˇl prˇijít pozdeˇ. Sch˚uzka zacˇíná v 15:00. Jan chce mít jistotu, že dorazí vcˇas, tak si nechá 10 minut rezervu. Plánovacˇ nabídne dveˇ cesty. První spojení je tvorˇeno linkou 22 a 18, cesta zacˇíná v 14:37 a v cíli by meˇl Jan být v 14:47. Druhé spojení zacˇí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 drˇíve a také neobsahuje peˇší prˇechod mezi zastávkami. Ucˇinil správné rozhodnutí? Bude Janovi skutecˇneˇ stacˇit relativneˇ velká 10 minutová rezerva pokud neˇjaká cˇást plánu cesty nevyjde?
Netriviální dopravní spojení je realizováno alesponˇ dveˇma r˚uznými prostrˇedky. Prˇestup mezi dveˇma linkami je plánován na základeˇ cˇasu prˇíjezdu prvního spoje, doby potrˇebné pro prˇesun cestujícího mezi zastávkami a cˇasu prˇíjezdu cílového spoje. Jízdní rˇády dávají cestujícímu stabilní informaci o dobeˇ, kterou stráví cˇekáním na zastávce.
Pokud se rˇídíme striktneˇ jízdním rˇádem, spoléháme na to, že každý spoj dané linky je na zastávce vždy v prˇedepsaný okamžik. Pocˇítáme s tím, že 100% spoj˚u je prˇistaveno k zastávkovému ostr˚uvku vcˇas urcˇený jízdním rˇádem. Prˇi výpocˇtu doby pro prˇestup nepocˇítáme s tím, že by se neˇjaké procento spoj˚u opozdilo. Situaci ukazuje obrázek 2.
Pokud dochází k prˇestupu v rámci jednoho ostr˚uvku, pak je cˇas potrˇebný pro výstup z prvního spoje a cˇas potrˇebný pro nástup do dalšího spoje brán jako minimální cˇas pro prˇestup. Pokud bychom uvažovali prˇestup mezi spoji, 22 18
A 2 min 2 min
A 17 3 min 2 min 3 min 2 min B
Obrázek 1: Jan˚uv plán cesty. (na svislé ose jecˇas) které prˇijedou ve stejný okamžik, nebylo by možné zarucˇit porˇadí prˇíjezdu spoj˚u na zastávku ani bezpecˇný prˇestup mezi nimi. Uvažujme 1 minutu jako minimální cˇas potrˇebný pro prˇestup. Celková doba mezi prˇíjezdem tramvaje cˇ.22 a odjezdem tramvaje cˇ.18 jsou 2 minuty. Cestující tedy cˇeká 1 minutu na prˇíjezd tramvaje cˇ.18. 100 80 60 40 20 0 100 80 60 40 20 0 2.2
Doba vyhrazená na zmeˇnu spoje je tvorˇena dobou nutnou pro výstup cestujícího z výchozího spoje a prˇesun mezi zastávkami (tato doba je nutná a nelze ji zkrátit) a dobou strávenou cˇekáním na prˇíjezd cílového spoje.
Ve skutecˇnosti, se cˇasto stává, že se spoj zpozdí a v tom prˇípadeˇ se posouvá cˇasový interval vyhrazený pro prˇestup mezi spoji. S dobou pro prˇesun cestujícího mezi zastávkami se hýbat nedá, ale vzniklé zpoždeˇní spoje lze kompenzovat dobou pro cˇekání na prˇíjezd cílového spoje. Navíc pokud i cílový spoj má zpoždeˇní, vzniká tak další rezerva. Doba, která meˇla být podle plánu cestujícím procˇekána na prˇíjezd cílového spoje, m˚uže být ve skutecˇnosti spotrˇebována jako prˇirozená rezerva pro prˇípadné zpoždeˇní výchozího spoje.
Pokud je odchylka od jízdních rˇád˚u prˇíliš velká nebo pokud spoje navazují prˇíliš teˇsneˇ, m˚uže dojít k tomu, že cestující navazující spoj nestihne a prˇestup se neuskutecˇní podle plánu. V takovém prˇípadeˇ je cestující nucen zmeˇnit zbývající cˇást plánu. To typicky vede k nedodržení požadovaného cˇasu prˇíjezdu, což m˚uže být pro cestujícího znacˇneˇ neprˇíjemné.
Spolehlivost prˇestupu lze nahlížet jako pomeˇr nedodržených naplánovaných prˇestup˚u v˚cˇui všem naplánovaným prˇestup˚um. Zvýšením spolehlivosti prˇestup˚u bychom zvýšili celkovou spolehlivost plánování, zvlášteˇ u plán˚u cest, které sestávají z více r˚uzných úsek˚u. Hlavní rˇpícˇinou selhání prˇestup˚u bývají odchylky od plánovaného provozu. 3
Zpoždeˇní Existuje neˇkolik zp˚usob˚u jak se vyrovnat s nepravidelností provozu hromadné dopravy prˇi plánování spojení. Jeden z jednoduchých prˇístup˚u je jet o jeden spoj drˇíve. Tento prˇístup je cˇasoveˇ neefektivní zvlášteˇ v prˇípadeˇ, kdy spoje mají dlouhý interval.
Prˇidávat rezervu navíc ke každému prˇestupu je nevýhodné. Plánovacˇ by pak uživateli prˇedkládal spojení cˇasoveˇ nárocˇneˇjší, než je ve skutecˇnosti potrˇeba. Prodlužovala by se tak paušálneˇ doba cˇekání a tím i celková délka cesty, což je nežádoucí. Je proto potrˇeba nalézt urcˇitý postup pro vyhodnocení prˇípad˚u, kdy se rezerva vyplatí a jak velká má být.
Pokud máme informaci o možném zpoždeˇní na dané lince, m˚užeme tomu prˇizp˚usobit plán cesty. M˚užeme díky teˇmto znalostem zvolit jinou linku, což m˚uže vést k naplánování zcela odlišné trasy. Obrázek 2: Prˇestup mezi linkami 22 a 18 podle jízdního ˇrádu. (na svislé ose je zpoždeˇní ve vterˇinách, na vodoroné ose je cˇas) 3.1
Plánování spojení je typicky vázáno na jízdní rˇády dané
dopravcem. Nepravidelnosti v jízdních rˇádech jsou dobrˇe
známým jevem, objevují se naprˇícˇ r˚uznými úrovneˇmi
prˇepravní síteˇ hromadné dopravy osob, jak ukazuje [
Rˇ ada dopravc˚u monitoruje pohyb svých prˇepravních
prostrˇedk˚u pomocí systém˚u automatického sledování vozidel
- Automated Vehicle Location(AVL). Pokud systém AVL
pracuje v reálném cˇase, pak je možné tyto informace
využít k aktualizaci plánu spojení. Takto získaná aktuální
provozní data lze využít k predikci odchylek od jízdních
ˇrád˚u v krátkodobém výhledu. Prˇíkladem aplikace tohoto
prˇístupu je [
Nevýhodou tohoto prˇístup˚u je, že zpoždeˇní spoje je možné predikovat až od okamžiku, kdy zpoždeˇní nastalo v drˇíveˇjší cˇásti trasy spoje. To znamená, že plán je nutné meˇnit v okamžiku, kdy je již cˇástecˇneˇ realizován. To s sebou nese výrazná omezení.
Na základeˇ statistického zpracování historie provozních
dat je však možné do jisté míry prˇedvídat chování spoj˚u,
co se týká zpoždeˇní [
V soucˇasné dobeˇ máme k dispozici provozní data tramvajové dopravy v Praze z roku 2008. Data byla získána z AVL systému „DORIS“. Provozní data jsou porovnávána s plánovanými jízdními rˇády tak, aby bylo možné urcˇit odchylky. Každý záznam je datován, lze tedy zpeˇtneˇ rekonstruovat skutecˇný pr˚ubeˇh jízdy každého spoje, který vyjel na trasu. Data zkoumáme již delší dobu. Prˇi rozboru jsme pozorovali výrazné periodicity v odchylkách jednotlivých spoj˚u vázané na denní dobu, zejména v pracovní dny.
Jeden z možných prˇístup˚u jak dosáhnout efektivního využití rezervního cˇasu je pocˇítat s pravdeˇpodobným zpoždeˇním v prˇípadech, kdy si to situace vyžaduje. Jeden z prˇípad˚u, kdy dochází kcˇastému selhání prˇestupu je, když zdrojový spoj jezdí se zpoždeˇním a cílový spoj jezdí pravidelneˇ vcˇas. Prˇedpokládejme, že ve stejnou denní dobu bude zpoždeˇní spoj˚u blízké pr˚umeˇru z minulého období. Pokud predikci zpoždeˇní spoj˚u založenou na provozních datech z minulého období plošneˇ aplikujeme na jízdní rˇády v následujícím období, m˚užeme tak vylepšit výchozí data pro urcˇování prˇestup˚u. Tím se zvýší spolehlivost v daném prˇípadeˇ na 80% až 90%. Konkrétní hodnoty ukazuje tabulka 1.
Spolehlivost prˇestup ˚u podle jízdních rˇád ˚u: dopravce predikovaných po dnech predikovaných po hodinách tram. linky 20-18 12-9 86,91% 72,27% 89,33% 80,63% 89,38% 87,59% Tabulka 1: Spolehlivost predikce pro prˇestupy mezi linkami 20-18 a 12-9 4
Z prˇedchozího je videˇt, že i jednoduchá predikce založená na pr˚umeˇrném zpoždeˇní prˇináší na dané dopravní síti výsledky. Nicméneˇ pro prˇesneˇjší vyhodnocování spolehlivosti prˇestup˚u bychom potrˇebovali jemneˇjší metodu. Prˇedevším potrˇebujeme odhadnout, zda je doba, kterou plánovacˇ prˇiˇradil prˇestupu, dostatecˇná a prˇestup neselže.
Jízdní rˇády rˇíkají, kdy by se daný spoj meˇl vyskytovat na zastávce, rozlišují pouze dva stavy: spoj je na zastávce a spoj není na zastávce. Pokud zaznamenáme prˇedpokládaný výskyt spoje na dané zastávce v daný cˇasový úsek, získáme graf 3. Na základeˇ historických provozních dat jsme pro každou linku schopni rˇíct, kolikrát za urcˇité období prˇijela na danou zastávku vcˇas, kolikrát se zpozdila o minutu, dveˇ, apod. nebo kolikrát prˇijela o minutu drˇíve. Když tato data vyneseme na cˇasovou osu, získáme graf cˇetností zpoždeˇní. 60 50 40 30 20 10 0 Obrázek 4: Rozdeˇlení zpoždeˇní spoj˚u linky 18. (na svislé ose je cˇetnost, na vodoroné ose je zpoždeˇní ve vterˇinách) Graf na obrázku 4 ukazuje v kolika prˇípadech a o kolik se v minulosti opozdil daný spoj na dané zastávce.
Na základeˇ drˇíveˇjších zkušeností víme, že konkrétní spoje se zpoždují pravidelneˇ zejména s vazbou na denní dobu. Dále také víme, že na základeˇ historických provozních dat, lze vytvorˇit použitelnou predikci zpoždeˇní. Pokud tedy budeme prˇedpokládat, že cˇetnost zpoždeˇní bude stejná jako v minulosti, pak lze výskyty v grafu 4 lze použít jako predikci chování spoj˚u dané linky. Prˇedpokládejme, že o stejnou dobu se zpozdí stejné procento spoj˚u. V tom prˇípadeˇ výskyty spoj˚u nebudou odpovídat jízdnímu ˇrádu, ale upravené pravdeˇpodobnostní mapeˇ 5. Takto odhadnuté chování spoj˚u dané linky by meˇlo lépe odpovídat realiteˇ. Obrázek 5: Cˇ etnost výskytu spoj˚u linky 18 odhadnutá podle rozdeˇlení zpoždeˇní. (na svislé ose je cˇetnost, na vodoroné ose je cˇas v minutách)
V prˇípadeˇ spoj˚u, u kterých pravidelneˇ dochází k odchylkám od jízdního rˇádu, m˚uže být výhodné odhadovat zpoždeˇní naprˇíklad pomocí historických provozních dat. Pokud použijeme drˇíveˇjší výskyty zpoždeˇní k vytvorˇení pravdeˇpodobnostní mapy, m˚užeme tak získat relevantní prˇedstavu o chování spoje v kontextu dané zastávky. V tomto prˇípadeˇ se nelze spolehnout na výskyt spoje na zastávce v jeden okamžik. Je potrˇeba spocˇítat pravdeˇpodobnost kombinací výskyt˚u relevantních spoj˚u, které jsou od sebe na cˇasové ose vzdálené alesponˇ minimální dobu potrˇebnou pro prˇestup.
Za prˇedpokladu, že dané linky tramvají jsou na sobeˇ nezávislé, lze pravdeˇpodobnost úspeˇšného prˇestupu odhadnout jako: ∑ p1(t1) ∗ t1
∑ (t1+tm)<=t2 p2(t2) , kde: t1,t2 je cˇas, tm je minimální doba pro prˇestup, p1(t), p2(t) je pravdeˇpodobnost prˇíjezdu spoje 1,2 v cˇase t.
Vezmeˇme stejný prˇestup jako v prˇedchozím prˇípadeˇ, prˇestup mezi linkami 22 a 18 na zastávce „Malostranská“. Minimální doba potrˇebná pro prˇestup v rámci jednoho zastávkového ostr˚uvku z˚ustává - 1 minuta. Obrázek 6 ukazuje pravdeˇpodobnostní mapy obou spoj˚u. Dobu prˇestupu nelze urcˇit jednoznacˇneˇ jako v prˇedchozím prˇípadeˇ. 30 20 10 0
Pokud tramvaj cˇ.22 prˇijede prˇed 14:44 vcˇetneˇ, je zde vysoká pravdeˇpodobnost, že cestující stihne prˇestoupit na linku 18. Veˇtšina výskyt˚u linky 18 je až od 14:45, což je v souladu s jízdním rˇádem. Pokud však tramvaj cˇ.22 prˇijede o 2 a více minut pozdeˇji, než by meˇla podle jízdního rˇádu, tj. 14:45 a pozdeˇji, je pravdeˇpodobnost stihnutí prˇestupu jen 26%. Prˇitom podle cˇetnosti tato možnost prˇedstavuje 52% všech relevantních prˇíjezd˚u tramvaje cˇ.22 v danou dobu. Ukazuje se, že jednou z cest ke zvýšení spolehlivosti plánování spojení, je odhadovat pravdeˇpodobný pr˚ubeˇh prˇestupu. Pokud budeme schopni odhadnout úspeˇšnost každé relevantní varianty prˇestupu, pak bude možné preferovat prˇi plánování spojení ty prˇestupy, které mají vyšší nadeˇji na úspeˇch. To však vyžaduje vícekriteriální algoritmus pro výbeˇr spojení. Výsledkem by mohl být návrh neˇkolika r˚uzných spojení, která jsou cˇasoveˇ málo nárocˇná a prˇitom mají dostatecˇneˇ velkou nadeˇji na úspeˇch. Koncová volba spojení by mohla být prˇenechána uživateli. 5
Záveˇr Plánování spojení v meˇstské hromadné dopraveˇ v sobeˇ skrývá víc než jen úlohu nalézt nejkratší cestu k cíli. Meˇstská dopravní sít’ je úzce svázána s dalšími aspekty moderního života. Je potrˇeba videˇt vyhledávání cest v stále komplexneˇjším meˇrˇítku. Dalo by se rˇíci, že pokud dopravní sít’ dosáhne urcˇitého stupneˇ složitosti, chová se v urcˇitém smyslu charakteristicky. Za tohoto prˇedpokladu lze její chování studovat a získané poznatky úspeˇšneˇ využít pro predikci tohoto chování.
Pomocí popsané metody informovaných prˇestup˚u, jsme schopni odhadnout, které prˇestupy by zarˇazením do plánu cesty mohli zp˚usobit jeho potenciální selhání. M˚užeme zvolit míru pravdeˇpodobnosti, která bude urcˇovat, který prˇestup je pro nás ješteˇ spolehlivý. Jízdní rˇády jsou stále výchozím bodem. Už jen pouhá informace o potenciálním riziku selhání m˚uže být pro cestující užitecˇná.
Praktický prˇíklad, cˇást 2: Janovi záleželo na vcˇasném prˇíjezdu na pracovní sch˚uzku, proto volil rychlejší cestu a dokonce si dal velkou cˇasovou rezervu. Problém je, že použitá linka 22 má v daném úseku cˇasto zpoždeˇní, s cˇímž standartní plánovacˇ nepocˇítá. Konkrétneˇ je pravdeˇpodobnost uskutecˇneˇní prˇestupu mezi linkou 22 a 18 v dané cˇasy odhadnuta na necelých 38%. Situace je podrobneˇ rozebrána na obrázku 6 a d˚usledkem je pozmeˇneˇný itinerárˇ 7 Janovy cesty. Dojde tak s velmi pravdeˇpodobneˇ k nestihnutí prˇestupu a Jan bude nucen cˇekat na další tramvaj linky 18. To ho zdrží natolik, že do cíle dorazí v 15:07, což je hluboko za jeho prvotním ocˇekáváním. Pokud by Jan získal trˇeba jen nápoveˇdu, která trasa je spolehliveˇjší, mohl stihnout svou sch˚uzku.
Pokud metodu informovaných prˇestup˚u použijeme k orˇezávání nespolehlivých prˇestup˚u prˇímo v uzlech prˇi vyhledávání spojení, m˚užeme tak výrazneˇ zvýšit spolehlivost plánovacˇe. Výhodou oproti jiným metodám na zajišteˇní spolehlivosti je, že vznikají cˇasové rezervy jen tam, kde je nejvíce pravdeˇpodobné, že budou spotrˇebovány.
Navíc uvedené postupy lze dobrˇe uplatnit i na straneˇ poskytovatele prˇepravních služeb. Lze naprˇíklad detekovat problematická místa, kde cˇasto dochází k selhání plánovaného prˇestupu a kde cestující zbytecˇneˇ tráví cˇas cˇekáním na další spoj. V prˇípadeˇ okrajových linek lze také detekovat místa, kde naprˇíklad prˇi selhání neˇkterého prˇetupu z˚ustanou cestující izolování bez navazující dopravy.
Naším cílem do budoucna je zacˇlenit uvedenou metodiku do vyhledávacˇe spojení tak, aby byl schopen nalézt spo
A 9
3 min A 17
B 2 min 3 min 2 min
Obrázek 7: Skutecˇný pr˚ubeˇh Janova plánu. lehlivé a prˇitom cˇasoveˇ efektivní spojení. Prˇedložené metody mohou být použity pro multikriteriální vyhledávání k urcˇení paramtru spolehlivosti. Prˇi sestavování pravdeˇpodobnostních map jsou použity cˇetnosti. Jednou z výhod je, že lze snadno prˇidávat noveˇ získaná data.