Útkeresési eljárás a városi közforgalmú közlekedés szimulációjához

Útkeresési eljárás a városi közforgalmú közlekedés szimulációjához Prileszky István [email protected]

Pusztai Pál [email protected]

Útkeresési eljárás

Számítástechnikai megvalósítás

Bemenő és eredmény adatok Hálózat és menetrend

Utazási igények

Útkeresési paraméterek

Útkeresés

A kielégíthetetlen utazási igények



A kielégíthető utazási igények útvonaltervei

Egyéb eredmények

Jellemzők  

Az útkeresést a szimulációtól függetlenül futtatható Windows alkalmazás végzi. Az adatok tárolása, a szimulációval való kommunikáció szövegfájlokkal történik.

Győr, 2015.03.26-27

Közlekedéstudományi Konferencia, Széchenyi Egyetem

2



Bemenő adatok 

Hálózati adatok 

Megállók   



Azonosító Megnevezés Gyűjtőmegálló azonosítója

Gyűjtőmegállók   

Azonosító Koordináták, méret A gyűjtőmegállóhoz tartozó megállók azonosítói

Győr, 2015.03.26-27


3



Bemenő adatok 

Hálózati adatok 

Vonalak   

Azonosító Megnevezés A jármű által (sorban) érintett

 úthálózati élek azonosító  megállók mindegyikére: azonosító, elérési idő (percben)

Győr, 2015.03.26-27


4



Bemenő adatok 

Menetrendi adatok 

Járatok   

Azonosító Indulási idő (óra, perc) A járat vonalának azonosítója

Győr, 2015.03.26-27


5



Bemenő adatok 

Utazási igények 

Egy-egy személyre vonatkozóan    

Azonosító Időpont (óra, perc) Kezdő gyűjtőmegálló azonosítója Cél gyűjtőmegálló azonosítója

Győr, 2015.03.26-27


6



Bemenő adatok 

Egyéb adatok 

Útkeresési paraméterek   

Az egy viszonylatban meghatározandó legrövidebb utak maximális száma (1-10) A maximális eltérés a legjobb eljutáshoz képest (0-60) Az egy utazás során megtehető átszállások maximális száma (0-5)

Győr, 2015.03.26-27


7



Teszthálózat 1

Győr, 2015.03.26-27


8



Teszthálózat 2 

Adatok száma    

Megállók: 434 Gyűjtőmegállók: 221 Vonalak: 124 Járatok: 555 



Győr, 2015.03.26-27

Időszak: 4.28 – 9.56

Utazási igények: 21656


9



Eredmény adatok 

Kielégíthetetlen utazási igények 

Az utazási igények formátumában

Győr, 2015.03.26-27


10




Kielégíthető utazási igények 

Az utazási igények és a hozzájuk tartozó fák azonosítója



A különböző fák/útvonaltervek

Győr, 2015.03.26-27


11




Egyéb eredmények 

Információk a megtalált legrövidebb utakról  

Járatokat, megállókat, gyűjtőbeli eléréseket tartalmazó utak Vonalakat, gyűjtőbeli első megállókat tartalmazó utak

Győr, 2015.03.26-27


12



A legrövidebb út Dijkstra ( Járatok, Vonalak, Megállók, Gyűjtők, Kp, Vp, IIdő, T, C, B ) /* Kezdőállapot */ for az összes i megállóra /* Egyik megálló sem elérhető */ T[i] ← Végtelen; C[i] ← NincsCímke; B[i] ← NincsCímke; Akt[i] ← hamis /* Az aktív pontok halmaza */ A ← {} /* Kp gyűjtőjében való megállók beállítása * for az összes y megállóra Kp gyűjtőjében T[y] ← IIdő; C[y] ← Kp if y ≠ Kp B[y] ← GyűjtőbeliElérés /* y hozzávétele az aktív pontokhoz (A) */ A ← A + {y}; Akt[y] ← igaz /* Javító lépések */ …

Győr, 2015.03.26-27


13



A legrövidebb út /* Javító lépések */ Vége ← hamis while A ≠ {} And Not Vége x ← Legyen A minimális távolságú (T) eleme if x = Vp Vége ← igaz else /* x törlése A-ból */ A ← A − {x}; Akt[x] ← hamis /* Rövidítés x-beli átszállással */ for az összes j járaton indulási idő szerinti sorrendben v ← a j járat vonala if v még nem vizsgált /* Egy vonalat csak egyszer vizsgáljunk meg */ if Megáll-e x-ben a j járat és az érkezés x-be ≥ T[x] /* x-beli átszállással rövidítünk a j járattal az x-t követő megállókban */ for az x utáni összes y megállóra a v vonalon idő ← az y-ba való érkezés ideje if idő < T[y] /* y gyűjtőjében lévő megállók elérhetőségének módosítása */ …

Győr, 2015.03.26-27


14



A legrövidebb út /* y gyűjtőjében lévő megállók elérhetőségének módosítása */ for az összes z megállóra y gyűjtőjében /* A z megálló elérhetőségének módosítása */ T[z] ← idő if z = y /* Járattal történő elérés */ C[z] ← x; B[z] ← j else /* Gyűjtőbeli elérés */ C[z] ← y; B[z] ← GyűjtőbeliElérés /* Ha z még nem aktív, akkor hozzávesszük A-hoz */ if Not Akt[z] A ← A + {z}; Akt[z] ← igaz

Győr, 2015.03.26-27


15



A legrövidebb utak – egy segédeljárás 

Feladat 



Egy elérhetőség (időben rendezett) bejegyzése egy adott megállónál.

Paraméterek 

Input      



Akt_T: az elérés ideje (napon belüli percben) Akt_C: az előző megálló (ahol a felszállás történt a járatra) azonosítója Akt_B: az elérést biztosító járat azonosítója Akt_D: a járaton töltött utazási idő (percben) Hol: az a megálló (amelynek az elérést adminisztráljuk) IdőLimit: az az időhatár (napon belüli percben), amelyen belül még adminisztrálunk

Input/Output 

T, C, B, D: az eléréseket tároló változók (minden megállóhoz több elérés tartozhat)

Beszúr ( Akt_T, Akt_C, Akt_B, Akt_D, Hol, IdőLimit, T, C, B, D ) if Akt_T ≤ IdőLimit if Még nem szerepel ez az elérhetőség a Hol megállónál Felvesszük az új elérhetőséget (Akt_T, Akt_C, Akt_B, Akt_D) a Hol megállónál

Győr, 2015.03.26-27


16



A legrövidebb utak – az elérések meghatározása Dijkstra-K ( Járatok, Vonalak, Megállók, Gyűjtők, Kp, IIdő, IdőLimit, T, C, B, D ) /* Kezdőállapot */ for az összes i megállóra /* Egyik megálló sem elérhető */ T[i][0] ← Végtelen; C[i][0] ← NincsCímke; B[i][0] ← NincsCímke; D[i][0] ← NincsCímke; Akt[i] ← 0 /* Az aktív pontok halmaza */ A ← {} /* Kp gyűjtőjében való megállók beállítása * for az összes y megállóra Kp gyűjtőjében if y ≠ Kp /* Azonos gyűjtőbeli elérés */ Beszúr ( IIdő, Kp, GyűjtőbeliElérés, 0, y, IdőLimit, T, C, B, D ) else Beszúr ( IIdő, Kp, NincsCímke, 0, y, IdőLimit, T, C, B, D ) /* y hozzávétele az aktív pontokhoz (A) */ A ← A + {y}; Akt[y] ← 1 /* Javító lépések */ …

Győr, 2015.03.26-27


17



A legrövidebb utak – az elérések meghatározása /* Javító lépések */ Vége ← hamis while A ≠ {} And Not Vége x ← Legyen A minimális távolságú (T) eleme if T[x] ≥ IdőLimit Vége ← igaz else /* x törlése A-ból */ A ← A − {x}; Akt[x] ← 2 /* Rövidítés x-beli átszállással */ for az összes j járaton indulási idő szerinti sorrendben v ← a j járat vonala if Megáll-e x-ben a j járat és az érkezés x-be ≥ T[x] /* x-beli átszállással rövidítünk a j járattal az x-t követő megállókban */ for az x utáni összes y megállóra a v vonalon idő ← az y-ba való érkezés ideje utazás ← az x-ből y-ba való utazás ideje /* y gyűjtőjében lévő megállók elérhetőségének módosítása */ …

Győr, 2015.03.26-27


18



A legrövidebb utak – az elérések meghatározása /* y gyűjtőjében lévő megállók elérhetőségének módosítása */ for az összes z megállóra y gyűjtőjében if z = y /* Járattal történő elérés */ Beszúr ( IIdő, x, j, utazás, z, IdőLimit, T, C, B, D ) else /* Gyűjtőbeli elérés */ Beszúr ( IIdő, y, GyűjtőbeliElérés, 0, z, IdőLimit, T, C, B, D ) /* Ha z-t most értük el, akkor hozzávesszük A-hoz */ if Akt[z] = 0 A ← A + {z}; Akt[z] ← 1

Győr, 2015.03.26-27


19



A legrövidebb utak – az elérések meghatározása 

Egy járatot miért vizsgálunk meg többször a rövidítések során? 

M1-M3 viszonylatban  

M1

Megtalált út: M1 J1 M3 Nem megtalált út: M1 J2 M2 J1 M3

M2

J1

7.00

7.15

7.05

7.10

M3 7.30

J2



M1-M2 viszonylatban  

Megtalált út: M1 J1 M2 Nem megtalált út: M1 J1 M3 J2 M2

M1

M2

7.00

7.10

J2

M3 7.25 7.20

7.30 J1 M4

Győr, 2015.03.26-27

7.40


20



A legrövidebb utak – az utak összerakása Összerak ( T, C, B, D, Kp, Vp, K, Átsz, Elsőhívás, Idő, Ut, Utak, UtakDb, Vége ) if Not Vége AktUtDb ← Ut.UtDb if (Vp = Kp) And (C[Vp][0] = Kp) /* A kezdőponthoz értünk, van egy újabb út */ Ut1 ← az Ut megfordítva Ut1 ← az Ut1 úgy, hogy az egymás melletti járatokat összevonjuk if Nincs még ilyen járatokból álló út az Utak között UtakDb ← UtakDb + 1 Vegyük fel az Utak közé az Ut1 utat if UtakDb = K Vége ← igaz else /* Még nem a Kp-nál vagyunk, vegyük (időrendben) Vp megfelelő elérhetőségeit */ …

Győr, 2015.03.26-27


21



A legrövidebb utak – az utak összerakása /* Még nem a Kp-nál vagyunk, vegyük (időrendben) Vp megfelelő elérhetőségeit */ Db ← Vp elérhetőségeinek száma i←0 while (i ≤ Db – 1) And (Elsőhívás Or Not Elsőhívás And (T[Vp][i] ≤ Idő)) Jó ← igaz /* Két egymást követő GyűjtőbeliElérés-t tartalmazó utat nem építünk */ if B[Vp] = GyűjtőbeliElérés if Az Ut utolsó járata = GyűjtőbeliElérés Jó ← hamis /* Kört tartalmazó utat nem építünk */ if Jó And Vp benne van az eddig épített Ut-ban Jó ← hamis if Jó And B[Vp][i] ≠ GyűjtőbeliElérés if B[Vp][i] benne van az eddig épített Ut-ban Jó ← hamis /* A maximális átszállásszámot ne haladjuk meg */ JDb ← Az Ut valódi (nem gyűjtőbeli elérést jelentő) járatainak száma if JDb − 1 > Átsz Jó ← hamis …

Győr, 2015.03.26-27


22



A legrövidebb utak – az utak összerakása if Jó if Elsőhívás /* Az út hosszának beállítása */ Ut.UtH ← T[Vp][i] – Idő /* Az Ut bővítése */ Ut ← az Ut kibővítve az út végén a Vp ponttal és a B[Vp][i] járattal /* Rekurzív hívás */ Összerak ( T, C, B, D, Kp, C[Vp][i], K, Átsz, hamis, T[Vp][i] – D[Vp][i], Ut, Utak, UtakDb, Vége ) /* Az Ut visszaállítása */ Ut.UtDb ← AktUtDb Ut ← az Ut elemeinek (UtP, UtJ) számát csökkentsük Ut.UtDb-ra */ i←i+1

Győr, 2015.03.26-27


23



A legrövidebb utak – a k db legrövidebb út előállítása 

Feladat 



Egy gyűjtőmegálló viszonylatban adott indulási idővel (IIdő) meghatározni az adott feltételeknek (K, Átsz, Eltérés) eleget tévő legrövidebb utakat.

Paraméterek  

Input: az output paraméterek kivételével mindegyik Output: Utak, UtakDb

GyUt ( Járatok, Vonalak, Megállók, Gyűjtők, KGy, VGy, IIdő, K, Átsz, Eltérés, Utak, UtakDb ) UtakDb ← 0 Kp ← a KGy gyűjtőmegálló első megállója Vp ← a VGy gyűjtőmegálló első megállója Dijkstra ( Járatok, Vonalak, Megállók, Gyűjtők, Kp, Vp, IIdő, T, C, B ) if T[Vp] < Végtelen IdőLimit ← T[Vp] + Eltérés Dijkstra-K ( Járatok, Vonalak, Megállók, Gyűjtők, Kp, IIdő, IdőLimit, T2, C2, B2, D2 ) /* Az Összerak hívás előtti kezdőértékek */ Ut ← egy üres út Vége ← hamis Összerak ( T2, C2, B2, D2, Kp, Vp, K, Átsz, igaz, IIdő, Ut, Utak, UtakDb, Vége )

Győr, 2015.03.26-27


24

Útkeresési eljárás a városi közforgalmú közlekedés szimulációjához

Recommend Documents