Eötvös Loránd Tudományegyetem Informatikai Kar Algoritmusok és Alkalmazásaik Tanszék
A Dijkstra-algoritmus alkalmazása városi útvonaltervezésre
Dr. Fekete István egyetemi docens
Kustra László Zsolt programtervező informatikus BSc
Budapest, 2011
A projekt az Európai Unió támogatásával, az Európai Szociális Alap társfinanszírozásával valósul meg (a támogatás száma TÁMOP 4.2.1./B-09/1/KMR-2010-0003).
1. fejezet Bevezetés Jelen szakdolgozat témája a Dijkstra-algoritmus felhasználása városi útvonaltervezésre. Amikor útvonaltervezésről beszélünk, akkor egy valamilyen szempontok alapján optimális útvonal kiválasztására gondolunk két végpont között egy térképen, „városi” alatt pedig azt értjük, hogy utunk során a tömegközlekedést is igénybe vesszük. A városi útvonaltervezés egy praktikus, jól megfogható és viszonylag könnyen definiálható feladatkör. Praktikus, mert időről időre bárki hasznát látja egy útvonaltervezőnek, aki városban él és nem ismeri teljesen a helyi tömegközlekedést. Jól megfogható, mert egy útvonaltervezés eredményéről bárki, előképzettség nélkül is meg tudja mondani, hogy optimális-e vagy sem. Egy informatikus számára továbbá a felmerülő feladatok gráfelméleti fogalmak segítségével viszonylag könnyen definiálhatóak, amint ezt a későbbiekben látni fogjuk. A megoldáshoz viszont a használt algoritmusok mély megértése, az optimális működéshez pedig sokszor azok jelentős átalakítása szükséges. Jelen szakdolgozatban a célunk az, hogy egy valós városon – jelen esetben Budapesten – működő használható algoritmust tervezzünk és implementáljunk, valamint az algoritmus és az implementáció is legyen áttekinthető, egyértelmű, továbbgondolható és kiterjeszthető. Nem célunk minden felmerülő ötletet megvalósítani, vagy akár matematikai formalizmusokba önteni. Az ötletek egy részét csak említés szintjén közöljük, ezek átgondolásra és megvalósításra várnak. Az elkészült szellemi termék jó alap a további ötletek kipróbálására vagy egy komplett programcsomag elkészítésére. Éppen ezért fontosnak tartjuk, hogy egy új ötletet vagy hibajavítást gyorsan kipróbálhassunk valós adatok segítségével és az eredményt azonnal láthassuk. Ennek érdekében az algoritmus teszteléséhez egy egyszerű webes felületet is elkészítünk, ahol a tervezett útvonalakat térképen, könnyen érthető formában elemezhetjük. A megvalósítást kompakt, független formára hozzuk, ami semmilyen külső szolgáltatást vagy weboldalt nem igényel működés közben és akár internet-elérés nélkül is működik.
1
2. fejezet Felhasználói dokumentáció 2.1. Webes felület A dRouteEngine alkalmazás egy webes felületen keresztül tesztelhető. Ez bármilyen modern böngészővel megtekinthető, más alkalmazás telepítését nem igényli a kliensoldalon. A 2.1. ábrán látható a felület felépítése.
2.1. ábra. dRouteEngine Web
2
2. FEJEZET. FELHASZNÁLÓI DOKUMENTÁCIÓ
3
Az útvonaltervezéshez megadható adatok és jelentésük: – Start/arrive time: a felhasználó által megadott időpont értelmezését határozza meg. Start time esetén a megadott időpontot az indulási helyen az útvonal indulási időpontjának, arrive time esetén viszont az érkezési helyen az útvonal érkezési időpontjának tekintjük. – User date és time: az indulási vagy érkezési időpont. – Optimize: a használt optimalizáció fajtáját adja meg. Shortest route beállításnál a lehető leggyorsabb útvonalat keressük, least walk distance esetén pedig a lehető legkevesebb gyaloglással járó útvonalat. – START és ARRIVE: az indulási és érkezési helyek. A mezőket kézzel szerkeszteni nem lehet, térképen kattintással jelöljük ki a pontokat. A pontok kiírása az egységes országos vetületi rendszerben (EOV) történik. – Walk speed: a gyalogos közlekedésnél használt haladási sebesség. – Use low floor vehicles only : ha bejelöljük, akkor kizárólag alacsonypadlós járműveket választ ki az útvonaltervező. – Maximum walk distance when transferring : a járműves utazás nélkül egyszerre megtehető maximális gyalogos távolság, méterekben mérve. Ha nem létezik olyan útvonal, ami a korlátozást figyelembe tudná venni, akkor az ehhez legközelebbi útvonalat választja a tervezőmotor. – Maximum time of wait at a station : a várakozás maximális ideje egy megállóban, másodpercekben mérve. – Transfer ratio: idő/átszállás arány, másodpercekben mérve. A tervezőmotor a maximum transfer ratio másodperccel hosszabb útvonalat preferálja egy rövidebb, de eggyel több átszállást tartalmazó útvonallal szemben. – Send: erre a gombra kattintva kezdődik el az útvonaltervezés. Az útvonaltervezés eredménye a térképen jelenik meg egy felrajzolt útvonal formájában. A felrajzolt szakaszok felbukkanó paneleken szolgáltatnak további információt magukról: – Segment name: a szakasz neve. Ez gyalogos szakasz esetén az utca neve, járműves szakasz esetén pedig a jármű típusa és az indulási, illetve érkezési megállók nevei.
2. FEJEZET. FELHASZNÁLÓI DOKUMENTÁCIÓ
4
2.2. ábra. dRouteEngine Web – egy útvonalterv – Segment type: a szakasz típusa. Lehetséges értékei: street, travel-bus, travel-metro, ... – Segment length in seconds/meters: a szakasz hossza időben és távolságban. A távolság itt gyaloglással megtett távolságot jelent, a járműveken megtett utat csak időben mérjük. – Start time: az útvonal aktuális ideje a szakasz elején. Ez az érték az útvonal legelső szakaszánál megegyezik a felhasználó által megadott időponttal, ha azt indulási időnek értelmezzük. – Arrive time: az útvonal aktuális ideje a szakasz végén. Ez az érték az útvonal legutolsó szakaszánál megegyezik a felhasználó által megadott időponttal, ha azt érkezési időnek értelmezzük. Egy újabb útvonaltervezés automatikusan törli az előző útvonalat a térképről. Ha a szolgáltatás valamilyen okból nem elérhető (például mert az útvonaltervezési kérés elküldésének időpontjában még nincsenek betöltve az adatok a tervezéshez), akkor egy üzenetablakban kapunk hibaüzenetet.
2. FEJEZET. FELHASZNÁLÓI DOKUMENTÁCIÓ
2.3. ábra. dRouteEngine Web – egy útvonalterv
5
2. FEJEZET. FELHASZNÁLÓI DOKUMENTÁCIÓ
6
2.2. Telepítés Ebben a fejezetben áttekintjük azokat a külső alkalmazásokat, amik a dRouteEngine szerveroldali futtatásához szükségesek. Ahol a külső alkalmazás speciális telepítési lépéseket igényel a dRouteEngine támogatásához, ott azt külön jelezzük. Minden más esetben az alkalmazás hivatalos dokumentációja szerinti alaptelepítést várjuk el. A fejezet leírásai Windows operációs rendszert feltételeznek.
2.2.1. Oracle Java SE 6 JDK A Java SE 6 JDK a GlassFish alkalmazásszerver futtatásához szükséges. Honlap és letöltési lehetőség: http://www.oracle.com/us/technologies/java/index.html
2.2.2. PostgreSQL 8.4 A PostgreSQL adatbázis-kezelő letölthető a http://www.postgresql.org/ címről. A telepítés végén elindul az Application Stack Builder Wizard, amiben további kiegészítőket választhatunk ki telepítésre. Válasszuk ki a Database Drivers kategóriában a pgJDBC elemet és a Spatial Extensions kategóriában a PostGIS 1.5 elemet, ahogy az a 2.4. ábrán látszik.
2.4. ábra. Application Stack Builder Wizard
2. FEJEZET. FELHASZNÁLÓI DOKUMENTÁCIÓ
7
A továbbiakban pg−install jelöli azt a könyvtárat, ahova a PostgreSQL telepítésre került. (Ez általában a C:\Program Files\PostgreSQL könyvtár.)
2.2.3. GlassFish Server 3 A GlassFish alkalmazásszerver („Full Platform”) letölthető a http://www.oracle. com/technetwork/java/javaee/overview/index.html címről. A továbbiakban gf−install jelöli azt a könyvtárat, ahova a GlassFish telepítésre került és gf-url azt a címet, ahol böngészővel elérhetjük a kiszolgált tartalmat. Ez lokális gépre történő telepítés esetén jellemzően localhost :8080. Keressük meg a pgJDBC nevű PostgreSQL kiegészítő telepítési könyvtárában (általában pg−install\pgJDBC) a postgresql−8.4−driververzio.jdbc4.jar fájlt. Fontos, hogy jdbc4 legyen a név utolsó előtti tagja. A driververzio rész változhat. Ezt a fájlt ezután másoljuk át a gf−install\glassfish\lib könyvtárba. A következő lépésben indítsuk el a gf−install\bin\asadmin programot. A megjelenő konzolablakban írjuk be az alábbi parancsokat: 1 2 3 4 5 6 7 8
A parancsok kimenete a 2.5. ábrán láthatóhoz hasonló kell, hogy legyen.
2.2.4. GeoServer 2.1 A GeoServer („Web Archive”) letölthető a http://geoserver.org/ címről. Ezt az alkalmazást használjuk a raszteres térkép generálására a webes felület számára. A letöltött zip fájlt tömörítsük ki, majd az így kapott geoserver.war fájlt telepítsük a GlassFish alkalmazásszerver alá, a következő parancs kiadásával: 1
> gf - install \ bin \ asadmin deploy -- contextroot geoserver geoserver . war
2. FEJEZET. FELHASZNÁLÓI DOKUMENTÁCIÓ
8
2.5. ábra. GlassFish asadmin példa kimenet
2.2.5. Osm2pgsql Az osm2pgsql letölthető a http://wiki.openstreetmap.org/wiki/Osm2pgsql címről. Ez a segédprogram szolgál az OpenStreetMap XML formátumú adatainak betöltésére az általunk használt PostgreSQL adatbázisba. Telepítője nincs, a letöltött fájlt egyszerűen tömörítsük ki egy mappába. A továbbiakban osm2pgsql−install jelöli azt a könyvtárat, ahova az osm2pgsql kitömörítésre került.
2.3. Adatbázis Ebben a fejezetben létrehozzuk a dRouteEngine szerveroldali futtatásához szükséges adatbázist és betöltjük a tervezéshez és a raszteres térkép generálásához szükséges adatokat.
2. FEJEZET. FELHASZNÁLÓI DOKUMENTÁCIÓ
9
2.3.1. Létrehozás A PostgreSQL adatbázis létrehozásához jelentkezzünk be az adatbázis-kezelőbe az alábbi paranccsal: 1
> psql -U postgres -W A postgres felhasználóhoz tartozó jelszót telepítés közben kellett megadnunk. Sikeres bejelentkezés esetén új promptot kapunk, ide írjuk be az alábbi parancsokat:
2
3
postgres =# CREATE ROLE drouteengine LOGIN ENCRYPTED PASSWORD ’ drouteengine_password ’; postgres =# CREATE DATABASE drouteengine WITH OWNER = drouteengine TEMPLATE = template_postgis ENCODING = ’UTF -8 ’; Ha az alábbi hibaüzenetet kapjuk, az azt jelenti, hogy a PostGIS kiegészítőt kézzel kell bekapcsolnunk egy üres adatbázisban: ERROR : template database " template_postgis " does not exist Ebben az esetben az üres adatbázis létrehozása így néz ki:
3
postgres =# CREATE DATABASE drouteengine WITH OWNER = drouteengine ENCODING = ’UTF -8 ’; A PostGIS kézi bekapcsolásáról ebben az adatbázisban további információ a kiegészítő honlapján érhető el. (Lsd. [8]) Végül adjuk ki az alábbi parancsokat:
4 5
6
7
postgres =# \ q > psql -U drouteengine -W -d drouteengine -f pg - install \8.4\ share \ contrib \ hstore . sql > psql -U drouteengine -W -d drouteengine -f pg - install \8.4\ share \ contrib \ _int . sql > psql -U drouteengine -W -d drouteengine Sikeres bejelentkezés esetén ismét új promptot kapunk. Ide írjuk be az alábbi parancsokat:
8 9
drouteengine =# CREATE SCHEMA osm ; drouteengine =# \ q
2. FEJEZET. FELHASZNÁLÓI DOKUMENTÁCIÓ
10
2.3.2. Betöltés és frissítés OpenStreetMap adatok Az OpenStreetMap adatbázis letölthető a projekt weboldaláról. (Lsd. [12]) A szakdolgozathoz nem a teljes adatbázist használjuk fel, hanem csak a Magyarországra vonatkozó részt, ami egy hungary.osm.bz2 nevű fájlként érhető el. (További információk a weboldalon.) Letöltés után adjuk ki a következő parancsokat: 1 2
3 4
5 6
7
> psql -U drouteengine -W -d drouteengine drouteengine =# ALTER DATABASE drouteengine SET search_path = osm , public ; drouteengine =# \ q > osm2pgsql - install \ osm2pgsql . exe -U drouteengine -W -d drouteengine -p drouteengine -S osm2pgsql - install \ default . style -s -k -u hungary . osm . bz2 > psql -U drouteengine -W -d drouteengine drouteengine =# ALTER DATABASE drouteengine SET search_path = public , osm ; drouteengine =# \ q Ezután hozzuk létre a dRouteEngine által használt nézeteket az OpenStreetMap adataiból – ezt a lépést csak egyszer, a legelső betöltés során szükséges megtenni:
8
> psql -U drouteengine -W -d drouteengine -f drouteengine . pgdump A drouteengine.pgdump fájl megtalálható a szakdolgozathoz mellékelt segédanyagok között. Menetrend adatok Menetrend adatok elérhetőek a szakdolgozathoz mellékelt segédanyagok között, a bpm.pgdump fájlban. Töltsük be a következő paranccsal:
1
> psql -U drouteengine -W -d drouteengine -f bpm . pgdump A mellékelt bpm.pgdump fájl 2011. április 29. és 2011. május 29. között szolgáltat adatokat. Friss adatok betöltéséhez a 3.3.2. fejezetben található segítség. Ezen kívül létezik egy alternatív kezdeményezés a tömegközlekedés leírására az OpenStreetMap keretein belül, lsd. [9].
2. FEJEZET. FELHASZNÁLÓI DOKUMENTÁCIÓ
11
2.4. Konfigurálás Ebben a fejezetben áttekintjük a dRouteEngine telepítését és beállítását.
2.4.1. GeoServer 2.1 A GeoServer felelős a raszteres térkép generálásáért a webes felület számára. A generálás az OpenStreetMap adataiból történik. Ennek beállításához először hozzunk létre egy JDBC adatforrást az adatbázishoz: 1
2
> gf - install \ bin \ asadmin create - jdbc - connection - pool -- datasourceclassname = org . postgresql . ds . PGSimpleDataSource -- restype = javax . sql . DataSource -- ping = true -- property " ServerName = localhost : PortNumber =5432: User = drouteengine : Password = drouteengine_password : DatabaseName = drouteengine " drouteengine / pool > gf - install \ bin \ asadmin create - jdbc - resource -- connectionpoolid drouteengine / pool jdbc / drouteengine Ezután navigáljunk egy böngészővel a http ://gf-url/geoserver/web/ címre és jelentkezzünk be a megjelenő adminisztrációs felületen. (Részletes leírás a felületről: [6]) Az alapértelmezés szerinti felhasználónév és jelszó: admin/geoserver. A következő beállításokat végezzük el: 1. A WMS oldalon megjelenő űrlapon állítsuk be az alábbi adatokat: Enable WMS Max rendering memory (KB)
igen 524288
Beállítás után kattintsunk a Submit gombra. 2. A Workspaces oldalon válasszuk ki az Add new workspace funkciót és töltsük ki a megjelenő űrlapon a következő adatokat: Name Namespace URI Default Workspace
drouteengine http://ludens.elte.hu/~kl223/drouteengine/ igen
Kitöltés után kattintsunk a Submit gombra.
2. FEJEZET. FELHASZNÁLÓI DOKUMENTÁCIÓ
12
3. A Stores oldalon válasszuk ki az Add new Store, majd a megjelenő oldalon a PostGIS (JNDI) funkciót. A megjelenő űrlapon töltsük ki a következő adatokat: Workspace Data Source Name Description dbtype jndiReferenceName schema
drouteengine drouteengine_osm OpenStreetMap layer for drouteengine postgis jdbc/drouteengine osm
Kitöltés után kattintsunk a Save gombra. 4. Másoljuk át a szakdolgozathoz mellékelt geoserver−osm−styles\symbols mappát a gf−install\glassfish\domains\domain1\applications\geoserver\ data\styles\ könyvtárba. Ezután a Styles oldalon adjuk hozzá a geoserver− −osm−styles mappában lévő style_osm_line.sld, style_osm_polygon.sld és style_osm_poi.sld stílusfájlokat. A mellékelt stílusfájlok forrásai: [3] és [2]. 5. A Layers oldalon válasszuk ki az Add a new resource funkciót, majd a megjelenő oldalon a drouteengine :drouteengine_osm adatforrást. A megjelenő listából a drouteengine_polygon, a drouteengine_line és a drouteengine_point réteget kell közzétenni. A beállítások – a megjelenítési stílus kivételével – minden rétegnél ugyanazok: Data Data Data Data Data
EPSG:900913 EPSG:900913 Force declared Compute from data Compute from native bounds
A Publishing lapon állítsuk be a megjelenítési stílust (Default Style) a három réteghez a következő értékekre: drouteengine_polygon drouteengine_line drouteengine_point Kitöltés után kattintsunk a Save gombra.
style_osm_polygon style_osm_line style_osm_poi
2. FEJEZET. FELHASZNÁLÓI DOKUMENTÁCIÓ
13
6. A Layer Groups oldalon válasszuk ki az Add new layer group funkciót, majd az Add Layer... funkcióval adjuk hozzá először a drouteengine_polygon, majd a drouteengine_line, végül a drouteengine_point réteget. Ezután töltsük ki az alábbi mezőket: Name Bounds
drouteengine Generate Bounds
Kitöltés után kattintsunk a Save gombra. Ezen a ponton a raszteres térképek generálásának beállítása készen van. A beállításokat tesztelni tudjuk a Layer Preview oldalon, a drouteengine rétegcsoport kiválasztásával.
2.4.2. dRouteEngine A dRouteEngine telepítéséhez először hozzá kell adnunk az alkalmazás saját konfigurációját a GlassFish alkalmazásszerverhez. Ez a konfiguráció a szakdolgozathoz mellékelt sun−resources.xml fájlban található. Természetesen szintén a szakdolgozat része az alkalmazás binárisa, ami drouteengine.ear néven található meg. Telepítsük ezeket a fájlokat: 1 2
> gf - install \ bin \ asadmin add - resources sun - resources . xml > gf - install \ bin \ asadmin deploy drouteengine . ear Telepítés után a http ://gf-url/drouteengine/ címen érhető el a dRouteEngine webes felülete.
3. fejezet Fejlesztői dokumentáció 3.1. Algoritmus Ebben a fejezetben áttekintjük az útvonaltervezéshez használt módosított Dijkstraalgoritmust és a felépített gráf struktúráját. Az eredeti algoritmusból kiindulva több teszteseten át javítjuk az algoritmust és a gráfot, egészen az optimális eredmény eléréséig.
3.1.1. Feladat Bemenet – VÁROS: a város utcatérképe, geometriailag egyenes szakaszdarabokból felépítve. Oszlop
Típus
Leírás
indulás érkezés utcanév
pont pont szöveges
Az indulási pont koordinátái. A végpont koordinátái. A leírt egyenes utcaszakasz neve.
Egy A szakasz folytatása egy B szakasz, ha A.érkezés ≈ B.indulás. Egymást metsző szakaszok metszéspontja nem minősül csatlakozási pontnak. – HELY: a járművek által használt megállók listája.
Oszlop
Típus
Leírás
pont megnevezés
pont szöveges
A megálló koordinátái. A megálló szöveges megnevezése, ahogyan az utasok ismerik.
14
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
15
– MENETREND: a járművek útvonalai a megállók között.
Oszlop
Típus
Leírás
indulás_hely érkezés_hely hossz
szám szám szám
vonal ágazat
szöveges szöveges
Az indulási megálló. Az érkezési megálló. A két megálló közötti menetidő másodpercekben. A vonal neve, például 7E, 6 stb. Az ágazat neve, például busz, metró stb.
Ezen kívül feltételezzük az alábbi kifejezések érvényességét: •
INDULÁS ∈ HELY × vonal × időÉ =⇒ időI
Adott HELY megállóban megadja egy adott vonal első indulási idejét az adott időÉ után. Ha KÉRÉS.alacsonypadlós = igaz, akkor az időI időpontban induló jármű biztosan alacsonypadlós. •
ÉRKEZÉS ∈ HELY × vonal × időI =⇒ időÉ
Adott HELY megállóban megadja egy adott vonal utolsó érkezési idejét az adott időI előtt. Ha KÉRÉS.alacsonypadlós = igaz, akkor az időÉ időpontban érkező jármű biztosan alacsonypadlós. A kifejezések értékének kiszámítása az adatok reprezentációjától függ. – KÉRÉS: a felhasználó által megadott tervezési kérés adatai.
Oszlop
Típus
Leírás
idő
idő
idő_mód indulás érkezés alacsonypadlós
felsorolás pont pont logikai
gyaloglás_sebesség optimalizálás
szám felsorolás
A felhasználó által megadott időpont. Jelentését az idő_mód paraméter adja meg. {INDULÁSI_IDŐ, ÉRKEZÉSI_IDŐ} A tervezés indulási pontja. A tervezés végpontja. Ha értéke igaz, akkor mozgássérült emberek számára is akadálymentes útvonal kerül tervezésre. A gyaloglás sebessége. (m/s) {SEBESSÉG, GYALOGLÁS, ...}
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
16
Kimenet Az algoritmus kimenete VÁROS és MENETREND típusú adatok kevert sorozata, ami – folytonos: az egymás után következő adatok a hozzájuk rendelt kezdő- és végkoordinátáiknál fogva értelemszerűen kapcsolódnak egymáshoz. Továbbá egy MENETREND adat járművét sem késsük le az útvonalban. – minimális költségű: KÉRÉS.optimalizálás = SEBESSÉG esetén a lehető legkorábbi megérkezést biztosítja, KÉRÉS.optimalizálás = GYALOGLÁS esetén pedig a lehető legkevesebbet gyalogol az útvonal megtétele közben. – KÉRÉS.indulás-ban kezdődik és KÉRÉS.érkezés-be jut el. – KÉRÉS.idő_mód = INDULÁSI_IDŐ esetén KÉRÉS.idő után indul KÉRÉS.indulásból, KÉRÉS.idő_mód = ÉRKEZÉSI_IDŐ esetén pedig KÉRÉS.idő előtt érkezik KÉRÉS.érkezés-be. – akadálymentes, ha szükséges: KÉRÉS.alacsonypadlós = igaz esetén csak akadálymentes járműveken utazik.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
17
3.1.2. A Dijkstra-algoritmus Források: [1] és [4].
∀v ∈ SZOMSZÉD(u)\KÉSZ d[v] > d[u] + c(u, v) A d[v] := d[u] + c(u, v) Helyreállít(minQ) P [v] := u
SKIP
– G = (V, E, c): a bemeneti gráf. – n= |G.V |, a csúcsok számossága. – s ∈ G.V : a kezdőcsúcs. – d[1..n]: az algoritmus futása során a kezdőcsúcsból a többi csúcsba eddig megtalált legrövidebb út hossza. – P [1..n]: az algoritmus futása során a gráf csúcsaihoz vezető legrövidebb utak előző elemei. (P [s] = NIL.) – KÉSZ : az algoritmus futása során már feldolgozott csúcsok halmaza. – minQ: kupac, ami a d tömb alapján rendezi sorba a gráf csúcsait. – SZOMSZÉD(u) : {v ∈ G.V | (u, v) ∈ G.E} Az algoritmus egy irányított, élsúlyozott (nemnegatív élsúlyú) gráfban keres egy kezdőcsúcsból kiinduló legrövidebb utakat. Az algoritmus „mohó”, ezért ha egy v1 , v2 , . . . , vn vertexsorozat egy megtalált legrövidebb út, akkor a ∀i ∈ [2..n] : : v1 , . . . , vi prefixek is legrövidebb utak kell, hogy legyenek a v1 –vi vertexek között. A bemenetből felépíthető gráfok esetén az algoritmus átlagosan n · logn műveletigénnyel fut.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
18
3.1.3. Korlátozott elérhetőségű élek A probléma Építsük fel a bemenet elemeiből a következő gráfot: G = (V, E, c), ahol idő
c : E → R az élek élsúlyai
V =K ∪
[
{x.pont}
x∈HELY
∪
[
{x.indulás, x.érkezés}
x∈VÁROS
K = {KÉRÉS.indulás, KÉRÉS.érkezés}
E = MENETREND ∪ VÁROS
Azaz a gráf csúcsai koordinátapontok, élei pedig ezen csúcsok között definiáltak, a következőképpen:
∀e ∈ G.E : e.forrás_csúcs =
∀e ∈ G.E : e.cél_csúcs =
e.indulás_hely.pont , ha e.MENETREND e.indulás , ha e.VÁROS
e.érkezés_hely.pont , ha e.MENETREND e.érkezés , ha e.VÁROS
e.hossz , ha e.MENETREND ke.érkezés − e.indulásk2 , ha e.VÁROS KÉRÉS.gyaloglás_sebesség
Az így definiált gráfot a továbbiakban „bemeneti gráfnak” fogjuk hívni, éleit pedig „menetrend éleknek”, illetve „város éleknek”. Az algoritmus futása során a menetrend élek élsúlya (illetve egyáltalán a léte vagy nem léte) függ attól, hogy az útvonal mikor „ér oda” az élhez. Tekintsük a 3.1. ábrát. (A zölddel megjelölt él az optimális választás, a pirossal megjelölt pedig a jelenlegi algoritmus által választott. Ezek jó algoritmus esetén megegyeznek.) Az „A” csúcsból indulva három menetrend él közül választhatunk. A legrövidebb (1 perces)
2009-07-11 12:00:00 INDULÁSI_IDŐ (az „A” megálló) (a „B” megálló) SEBESSÉG 1m/s hamis
3.1. ábra. Bemenet példa menetrend él járműve azonban már odaérkezésünk előtt 4 perccel elment. A második legrövidebb (4 perces) él járműve viszont több órával az odaérkezés után indul. Az optimális megoldás ebben az esetben a 9 perc hosszúságú él lesz. Ebből a példából jól látszik, hogy a menetrend éleket elsősorban nem a hosszuk, hanem az érkezési idejük jellemzi, továbbá figyelnünk kell arra, hogy már érvénytelen (lekésett) éleket ne próbáljunk meg igénybe venni. A város élek esetén használható a szokványos megközelítés, melyek – a gyaloglás sebességének függvényében – konstans élsúllyal rendelkeznek és odaérkezésünk idejétől függetlenül mindig használhatóak.
Figyeljük meg, hogy a megtalált optimális útvonal költsége egyenlő az útvonal érkezési idejével. Ezt használjuk ki, amikor eldöntjük futás közben, hogy egy menetrend élet igénybe vehetünk-e. A Dijkstra-algoritmus a belső ciklusában már nem csúcsok közötti relációkat vizsgál, hanem egy adott csúcsból kiinduló élek listáján megy végig. Ez azért szükséges, mert a bemeneti gráf szomszédos csúcsai között létezhetnek párhuzamos élek.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
21
3.1.4. Átszállások A probléma A jelenlegi bemeneti gráf járműves utazás során nem tesz különbséget az átszállással, illetve az átszállás nélkül (ugyanazon a járművön maradva) továbbutazás között. Tekintsük a 3.2. ábrát. (Ami már a probléma megoldását is mutatja.) Az ábrán jelzett megtalált útvonal járművet vált menet közben, pedig ebből nem származik előnye, mire eléri a „D” megállót. A probléma oka a Dijkstra-algoritmus „mohó” tulajdonságában keresendő; az algoritmus az optimális útvonal minden kezdőrészletét is optimalizálja. Ugyanez a probléma jelentkezhet akkor is, ha nem ugyanabban a megállóban szállunk át, hanem az átszálláshoz át kell gyalogolni néhány város élen. (Például mert egy tér másik felére kell átmenni.) A megoldás Módosítsuk a bemeneti gráf felépítését úgy, hogy a járműves utazás során a Dijkstraalgoritmus ne dönthessen minden köztes megállóban a több párhuzamos vonal között, csak a járműről leszállásnál. Ennek érdekében a gráfon egy egyszerű átalakítást hajtunk végre, ami a HELY bemenet elemeit, azaz a megállókat érinti. Az átalakítás lényegét a 3.2. ábra szemlélteti. (A város élek és a csak város élek által érintett csúcsok nem változnak.) Az átalakítás után kapott gráf definíciója az alábbi: G = (V, E, c), ahol c : E → ÉLSÚLY az élek élsúlyai
V = K ∪ MV ∪
[
{(x.indulás, város), (x.érkezés, város)}
x∈VÁROS
K = {(KÉRÉS.indulás, város) (KÉRÉS.érkezés, város)}
MH = {(m.indulás_hely, m.vonal), (m.érkezés_hely, m.vonal) | m ∈ MENETREND} MV = {(h1 .pont, h2 ) | h ∈ MH}
LFF = {(hely, város, v2 ) | (hely, v2 ) ∈ MH} (felszállás élek) Azaz a gráf minden csúcsa egy rendezett pár, és egyedi csúcsok vannak minden HELY minden ott megálló különböző vonalához rendelve. Ezen felül definiáltunk ún. leszállás és felszállás éleket a gráfba, amik a város élekkel való összeköttetést
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
22
biztosítják az újonnan generált csúcsoknak. (Lsd. ábra.) A leszállás- és felszállás-élek térképen ábrázolva 0 méter hosszúságúak, mivel ugyanazon ponthoz tartozó 2 csúcs között futnak. Ezt tükrözi típusuk is: minden ilyen él (hely, v1 , v2 ) típusú, ahol „hely” jelöli a(z egyetlen) ponthoz tartozó megállót, v1 jelöli az él kiindulási vonalát és v2 jelöli a célvonalat. A fenti definícióban „város” a létező vonalak halmazának egy extremális eleme. A fenti definíció alapján: ∀e ∈ G.E :
(e.indulás_hely.pont, e.vonal) , ha e.MENETREND
e.forrás_csúcs =
(e.indulás, város) , ha e.VÁROS
∀e ∈ G.E : e.cél_csúcs =
(e.hely.pont, e.v1 ) , ha e.LF
(e.érkezés_hely.pont, e.vonal) , ha e.MENETREND (e.érkezés, város) , ha e.VÁROS
(e.hely.pont, e.v2 ) , ha e.LF
Az élek élsúlyainak definíciója:
∀e ∈ G.E : c(e) =
(e.hossz, 0) , ha e.MENETREND ke.érkezés − e.indulásk2 ,0 KÉRÉS.gyaloglás_sebesség
, ha e.VÁROS
(0, 1) , ha e.LFF (0, 0) , ha e.LFL
Definiáljuk az alábbi műveleteket az élsúlyokkal: idő
ÉLSÚLY = R ×
felszállások
N
a, b ∈ ÉLSÚLY
a + b = (aidő + bidő , afelszállások + bfelszállások ) w1 : ÉLSÚLY → R
w1 (a) = aidő + afelszállások · átszállás_arány
a < b ⇔ w1 (a) < w1 (b)
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
23
Az átszállás_arány érték másodpercekben értendő és átváltást biztosít az átszállások száma és az útvonal hossza között: az algoritmus az egy átszállással kevesebbet tartalmazó útvonalat fogja választani, akkor is, ha az maximum átszállás_arány másodperccel hosszabb. Az optimális érték változhat, jelen szakdolgozat írója számára a 180 másodperces érték hozta a legelfogadhatóbb útvonalakat. Az élsúlyokat számoló programrészlet legyen a következő:
ind := INDULÁS(e.indulás_hely, e.vonal, forrás_súlyidő ) cél_súly := forrás_súly cél_súlyidő := ind cél_súly := cél_súly + c(e) return cél_súly
return true
return forrás_súly + c(e)
Egy továbbfejlesztési lehetőség lehet a sebesség_arány értéket az útvonal hosszától függővé tenni. Egy konstans érték, legyen bárhogy beállítva, nem fog minden esetben optimális útvonalakat eredményezni: ha túl kicsi, akkor nem lesz észrevehető hatása a hosszabb útvonalak tervezésekor, ha viszont túl nagy, akkor túlzottan befolyásolja a rövidebb útvonalak tervezését.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
L
leszállás él felszállás él város él (valamilyen hosszú) menetrend él optimális útvonal az algoritmus által megtalált útvonal
2009-07-11 12:00:00 INDULÁSI_IDŐ (az „A” megálló) (a „D” megálló) SEBESSÉG 1m/s hamis
3.2. ábra. Bemenet példa
• D0
1000m L
L
L
• D7
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
25
3.1.5. Párhuzamos gyaloglás A probléma A Dijkstra-algoritmus mohó, ezért a bemeneti gráf minden csúcsába optimális útvonalat tervez, nem csak a célcsúcsba. Ez – emberi szemmel nézve – nem teljesen optimális útvonalakat eredményez, amikor egy járműre a megállóban hosszabb időt kell várakozni. A 3.3. ábrán két különböző, de másodpercre pontosan ugyanolyan hosszú útvonalat láthatunk (zölddel és pirossal jelölve). A piros útvonalon az utas azon jármű útvonala mellett gyalogol, amelyikre később fel is száll. Teszi mindezt azért, mert így a B7E és B0 csúcsokba gyorsabban jut el, mintha az A megállóban várakozna 10 percet. (Azaz a zöld útvonalat választaná.) Valójában azonban az utas számára a B megálló elérésének ideje lényegtelen. És ha már nem számít, akkor nem szeret gyalogolni. Nevezzük el ezt a problémát párhuzamos gyaloglás problémának. (7E ; 12:10:00→12:12:00)
2009-07-11 12:00:00 INDULÁSI_IDŐ (az „A” megálló) (a „C” megálló) SEBESSÉG 1m/s hamis 180s
3.3. ábra. Bemenet példa
A megoldás A megállóban várakozást ne az első menetrend él élsúlyában írjuk jóvá, hanem a felszállás él élsúlyában. Továbbá, az élsúlyokban tartsuk számon a gyalog megtett távolságot is, és az időben azonos hosszúságú útvonalak esetén a gyalog megtett távolság döntsön két élsúly között. Vagy formálisan leírva, a 3.1.4 fejezet jelöléseit használva:
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
idő
ÉLSÚLY = R ×
felszállások
N
×
26
távolság
R
∀e ∈ VÁROS : dm(e) = ke.érkezés − e.indulásk2 ∀e ∈ VÁROS : ds(e) =
ind := INDULÁS(e.hely,e.cél_csúcs2 , forrás_súlyidő ) cél_súly := forrás_súly cél_súlyidő := ind cél_súly := cél_súly + c(e) return cél_súly
return true
return forrás_súly + c(e)
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
27
3.1.6. Konnektor élek A probléma A megállók nem feltétlenül esnek pont egy város él valamelyik végére. Ugyanez igaz a KÉRÉS.indulás és KÉRÉS.érkezés bemeneti adatokra is. Emiatt előfordulhat, hogy a gráf különálló város és menetrend komponensekre szakad, illetve hogy a KÉRÉS.indulás-ból elindulni sem tudunk, vagy épp egyetlen él sem vezet a KÉRÉS.érkezés-be. A megoldás Az útvonal tervezése előtt – akár futási időben – hozzá lehet adni minden megálló (pont, város) alakú csúcsához illetve a KÉRÉS.indulás-hoz és a KÉRÉS.érkezéshez is néhány speciális város élet, amikkel „bekötjük” őket a legközelebbi város élek valamelyik végéhez. A bekötés kétirányú (oda- és visszafelé is generálunk egy konnektor élet) és mindig egy geometriailag egyenes szakasszal történik. Ezeket a speciális város éleket hívjuk konnektor éleknek. A konnektor élek futási idejű generálása során felmerül a kérdés, hogy milyen algoritmus szerint tudjuk kiválasztani egy adott (p) ponthoz, hogy melyik már létező város élek végeihez kössük be a gráfban. Néhány lehetőség: – Ötlet : vegyük a pont pár száz méteres környezetében lévő város éleket és azoknak a végeihez kössük be p-t. Hiba : Túl kicsi környezet esetén lesznek olyan pontok, amikhez egyetlen város élet sem találunk majd. (Például nagy terek közepéről induló útvonalak esetén a KÉRÉS.indulás.) Túl nagy környezet esetén pedig lesznek konnektor élek, amik keresztülgyalogolnak más város éleken, folyókon, vasúti síneken, épületeken. . . – Ötlet : vegyük a p-hez legközelebbi város-élvéget, és abba kössük be a konnektor éleket. Hiba : Ha az útvonaltervezés által megtalált legrövidebb útvonal a bekötött egyetlen konnektor éllel ellentétes irányba menne tovább, akkor egy ideig visszafelé kell gyalogolnunk. Ez akár nagyon sok is lehet. – Ötlet : vegyük a pont pár száz méteres környezetében lévő város éleket és azoknak a végeihez kössük be p-t, amiknek a bekötő szakasza nem keresztezne egy másik város élet és előre definiált kerítést sem. A kerítések legyenek a város élekkel egyező struktúrájú bemenő adatok, amik a folyókat, vasúti síneket, autópályákat, esetleg a nagyobb épületek körvonalait stb. tartalmazzák. Hiba : a megoldásnak nincs ismert hibája.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
28
Megjegyezzük, hogy a bemeneti gráf a memóriában általában sok helyet foglal el, viszont a gyakorlatban csak naponta egyszer, vagy még ritkábban változik. Útvonaltervezésből ennél jóval több várható (mondjuk, másodpercenként 2). Érdemes ezért arra törekedni, hogy egyetlen, konstans példányt tároljunk belőle, és azon több párhuzamos tervezést is futtathassunk. Ekkor nem lehetséges tervezésenként egyedi éleket generálni a gráfhoz. A megállók konnektor éleit a gráf felépítésekor (egyszer) legenerálhatjuk, viszont a KÉRÉS.indulás és a KÉRÉS.érkezés minden tervezésnél máshol van. Ezt a két csúcsot ezért érdemes a gráf felépítésekor, koordináták nélkül felvenni, majd az összes lehetséges módon bekötni őket a városrétegbe. A gráf definíciója tehát egy gyakorlati alkalmazás során így nézne ki: G = (V, E, c), ahogy a 3.1.4. fejezetben definiáltuk, ezen kívül V = V ∪ {(NIL, indulás), (NIL, érkezés)} E = E ∪ BE ∪ KI
BE = {(be, pont) | (pont, város) ∈ V } KI = {(ki, pont) | (pont, város) ∈ V }
A „be” élek a (NIL, indulás) csúcsból futnak a (pont, város) alakú csúcsokba. A KÉRÉS.indulás pont konkrét helyétől függően minden tervezés során csak néhány „be” él lesz elérhető. (Lsd. az elérhető függvényt a struktogramokban.) Hasonlóan a „ki” élekre is: minden „ki” él a hozzá tartozó (pont, város) csúcsból indul és a (NIL, érkezés) csúcsba érkezik. A KÉRÉS.érkezés pont konkrét helyétől függően minden tervezés során csak néhány „ki” él lesz elérhető. Ezen elérhető „be” és „ki” élek hosszát futási időben számoljuk, geometriai távolsággal mérve (azaz egyenes úton haladva), a város élek élsúlyának kiszámításához hasonlóan. Ezen élekkel a dokumentum további részében nem foglalkozunk, hanem feltételezzük, hogy valamilyen módon be tudtuk kötni a KÉRÉS.indulás-t és a KÉRÉS.érkezés-t a gráfba.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
29
3.1.7. Korlátozott gyaloglás A probléma Egy járműves útvonaltervező algoritmust írunk. Szeretnénk, ha meg lehetne szabni, hogy járműves utazás nélkül az utas maximum mennyit gyalogolhat. Ez a limit viszont szükség esetén feloldható kell, hogy legyen. (Azon esetekben, amikor vagy ahol nem olyan sűrű a járműközlekedés, például éjszaka vagy külvárosi részeken.) Jelöljük ezt a limitet max_séta néven. (A mértékegysége legyen méter.) A megoldás A max_séta mellett vezessünk be egy másik hasonló korlátozást is, az egy megállóban történő várakozás maximális idejére. Jelöljük ezt a korlátozást max_várakozás néven. (A mértékegysége legyen másodperc.) A második korlátozás szükségességének megértéséhez tekintsük a 3.4. ábrát: a pirossal jelzett útvonal valóban betartja a max_séta korlátozását, viszont körülbelül 8 órával hosszabb a zöld útvonalnál. Ez emberi szemmel nézve nem optimális. (973 ; 00:00:00→00:01:00)
•B0 2009-07-11 16:00:00 INDULÁSI_IDŐ (az „A” megálló) (a „B” megálló) GYALOGLÁS 1m/s hamis 180s 100m
3.4. ábra. Bemenet példa Adjunk hozzá új komponenseket az élsúly-értékekhez: 1. séta_tilosban ∈ R az útvonal során eddig „tilosban”, azaz a max_séta távolságon túl gyalog, járműves utazás nélkül megtett távolság. 2. séta_legutóbb ∈ R az útvonal eleje vagy a legutóbbi leszállás óta „legálisan” gyalogosan megtett távolság.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
30
3. várakozás_tilosban ∈ R az útvonal során eddig „tilosban”, azaz a megállónként max_várakozás időn túl történt várakozás időtartama. Az élsúlyok elsődleges rendezése a séta_tilosban és várakozás_tilosban komponensek összege szerint történjen, a pontos definíciót lsd. lentebb. Formálisan leírva, a 3.1.5. fejezet jelöléseit használva: idő
ÉLSÚLY = R ×
felszállások
N
×
távolság
R
×
séta_tilosban
R
×
séta_legutóbb
R
×
várakozás_tilosban
R
∀e ∈ VÁROS : dm(e) = ke.érkezés − e.indulásk2
dm(e) KÉRÉS.gyaloglás_sebesség
∀e ∈ VÁROS : ds(e) =
∀e ∈ G.E : nulláz(e) = −d[e.forrás_csúcs]séta_legutóbb c : E → ÉLSÚLY
3.1.8. Legkevesebb gyaloglásra optimalizálás A probléma A legkorábbi megérkezés mellett szeretnénk legkevesebb gyalogosan megtett útra és megállóban várakozásra optimalizált útvonalakat is tervezni. Szeretnénk továbbá azt is megadni, hogy egy átszállás elkerülése érdekében mennyit vagyunk hajlandóak gyalogolni, hasonlóan a 3.1.4. fejezetben definiált átszállás_arány értékhez. A megoldás Definiáljuk az élsúlyok közötti összehasonlítási relációt az alábbi módon, a 3.1.7. fejezet jelöléseit használva: a, b ∈ ÉLSÚLY
A legkevesebb gyaloglásra optimalizálással a dokumentum további részében az egyszerűség kedvéért nem foglalkozunk, de a szakdolgozathoz készített referencia implementáció képes a használatára. (Lsd. 2.1. fejezet.)
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
32
3.1.9. Érkezési időre tervezés A probléma Szeretnénk olyan útvonalterveket készíteni, amiknél nem az indulási időt adjuk meg, hanem az érkezési ponthoz érkezés idejét. Az ilyen tervezéseket ugyanazon a bemeneti gráfon szeretnénk futtatni, mint amin a normál, KÉRÉS.idő_mód = INDULÁSI_IDŐ tervezések is futnak. A megoldás Az alábbiakban módosítsuk az algoritmus működését: – Transzponáljuk a bemeneti gráfot, azaz fordítsuk meg az élek irányítását. Egy szomszédsági gráfról konstans időben készíthető olyan transzponált nézet, ami az eredeti gráfot használja, tehát ez könnyen megoldható. – Cseréljük fel a felszállás és a leszállás élek élsúlyának számolási módját. – Használjuk az alábbi műveleteket az élsúlyokkal: a, b ∈ ÉLSÚLY
3.2. Fejlesztői környezet A felhasználói dokumentációban említett alkalmazásokon kívül (lsd. 2.2. fejezet) az alábbi programok szükségesek a dRouteEngine továbbfejlesztéséhez: – Netbeans 7 a forráskód szerkesztéséhez és a fordítással kapcsolatos feladatok elvégzéséhez: http://netbeans.org/ – FireBug a webes felület fejlesztéséhez.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
34
3.3. Adatbázis A dRouteEngine által használt adatbázis 4 sémát tartalmaz: Séma
Leírás
public
osm bpm drouteengine
A globálisan használható táblákat és tárolt eljárásokat tárolja. Ennél az adatbázisnál ez a PostGIS, hstore és _int kiegészítők tábláit és tárolt eljárásait jelenti. Az osm2pgsql által betöltött OpenStreetMap adatbázis sémája. A járműves utazás adatait tartalmazó séma. A dRouteEngine futtatásához és az útvonaltervezéshez szükséges táblákat és nézeteket tartalmazó séma.
3.3.1. OpenStreetMap Az OpenStreetMap adatbázis egyed-kapcsolat diagramja a 3.5. ábrán látható. <<schema>> osm
<
>
<<schema>> drouteengine
<
>
drouteengine_point <>
street <> street_orig_id: integer street_name: text <> street_part_id: integer point_from_x: double point_from_y: double point_to_x: double point_to_y: double
<> osm_id: integer (osm tags)*: text z_order: integer tags: hstore way: point
drouteengine_polygon <> osm_id: integer (osm keys)*: text z_order: integer way_area: real tags: hstore way: polygon
cél 1
3.5. ábra. Az adatbázis felépítése (osm és drouteengine)
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
35
osm.drouteengine_line Az összes vonal-típusú adatot tartalmazó tábla. Ezt a táblát felhasználjuk a raszteres térkép generálásához. Az oszlopok jelentése: Oszlop osm_id (osm tags)
z_order tags way
Leírás Az OpenStreetMap saját egyedi azonosítója a vonalhoz. A gyakran használt tagek kiemelve a tags-ből. Az oszlopok neve a tag nevével egyezik meg, értéke pedig a tag értéke vagy NULL, ha az adott tag nem volt definiálva az adott vonalra. Egymást keresztező vagy fedő vonalak esetén az objektumok megjelenítési sorrendjét meghatározó adat. Asszociatív tömb a vonalhoz tartozó egyedi tagekkel. A gyakran használt tagekért és jellemző értékeikért lsd. [10]. A vonal, a PostGIS saját adattípusában.
osm.drouteengine_road A drouteengine_line egy részét tartalmazó tábla. Ide kerülnek be a járható utak. A tábla oszlopai közül hiányzik a z_order, de ezen kívül megegyezik a drouteengine_line felépítésével. osm.drouteengine_point A pont-típusú adatokat tartalmazza. Ezt a táblát felhasználjuk a raszteres térkép generálásához. A tábla felépítése a PostGIS tároló típusától eltekintve megegyezik a drouteengine_line felépítésével. osm.drouteengine_polygon A terület-típusú adatokat tartalmazó tábla. Ezt a táblát felhasználjuk a raszteres térkép generálásához. A tábla felépítése a PostGIS tároló típusától eltekintve megegyezik a drouteengine_line felépítésével. drouteengine.street Az útvonaltervezés utca-adatbázisát tartalmazó nézet. A drouteengine_line táblából képezzük a highway tag következő értékeit kiválasztva1 : primary, primary_link, secondary, secondary_link, tertiary, residential, unclassified, road, living_street, service, track, pedestrian, path, footway, briddleway, steps, mini_roundabout, crossing, roundabout, turning_circle, construction. 1
Leírás az értékekről : [10]
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
36
Minden sor egy egyenes szakaszt ír le, aminek hossza a két végpontja közötti geometriai távolság. (A nézetben szereplő koordináták egységes országos vetületi rendszerben (EPSG 23700) értendők.) Minden drouteengine_line-beli sor egy töröttvonalat ír le, ezért általában egy drouteengine_line-beli sorból több streetbeli sor is készül. Oszlop street_orig_id street_name street_part_id point_from_x point_from_y point_to_x point_to_y
Leírás Az OpenStreetMap saját egyedi azonosítója a vonalhoz, amiből az adott szakaszt képezzük. A szakaszhoz tartozó közterület-név. Az azonos street_orig_id-hez (vagyis az azonos utcához) tartozó szakaszok közötti sorrend. A szakasz kiinduló pontjának eovx koordinátája. A szakasz kiinduló pontjának eovy koordinátája. A szakasz végpontjának eovx koordinátája. A szakasz végpontjának eovy koordinátája.
Segédtáblák Az osm.drouteengine_nodes, osm.drouteengine_ways és osm.drouteengine_rels táblákat az osm2pgsql hozza létre betöltés közben egy köztes lépésként a végleges táblák generálása előtt. (További információk a létrehozott táblák szerkezetéről: [11]) A táblákat a betöltésen és a frissítésen kívül másra nem használjuk.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
37
3.3.2. Menetrend A menetrend-adatbázis egyed-kapcsolat diagramja a 3.6. ábrán látható. <<schema>> bpm
<
>
<
>
<
>
bpm_stop
bpm_line
bpm_transport
<> stop_id: integer eovx: double eovy: double <> line_id: integer stop_idx: integer <> line_part_id: text stop_delay: integer name: text
<> line_id: integer <> transport_id: integer name: text
<>
<>
<> transport_id: integer name: text type: text transfer_distance: double UNIQUE (name,type)
bpm.bpm_transport A létező vonaltípusokat tartalmazó tábla. Oszlop transport_id name type transfer_distance
Leírás Egyedi azonosító a vonaltípushoz. A vonaltípus neve, például 7E, 76, 6, ... Az ágazat neve, például bus, troley, tram, ... A vonalhoz tartozó átlagos felszállási és leszállási távolság. Ez az az út, amit pluszban meg kell tennünk gyalog, hogy elérjük a járművet. Metrók esetén például itt jelezzük az aluljárókban és a mozgólépcsőn megtett távolságot.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
38
bpm.bpm_line A létező vonalakat tartalmazó tábla. Oszlop line_id transport_id name
Leírás Egyedi azonosító a vonalhoz. A vonaltípus egyedi azonosítója. A vonal belső használatra szánt neve, ami jellemzően a végállomások neveit tartalmazza.
bpm.bpm_line_part A létező jármű-vonalvezetéseket tartalmazó tábla. Egy vonalvezetés egy jármű útvonalát írja le a térképen két megálló között. Oszlop
Leírás
line_part_id sorrend eovx eovy basex basey
Egyedi azonosító a vonalvezetéshez. Sorrend a vonalvezetés pontjai között. Bekötő EOVX koordináta a ponthoz. (A megállótól.) Bekötő EOVY koordináta a ponthoz. (A megállótól.) EOVX koordináta a ponthoz. EOVY koordináta a ponthoz.
bpm.bpm_stop A megállókat leíró tábla. Minden megálló egyértelműen hozzárendelhető egy vonalhoz, azaz több megálló is lehet ugyanazon a ponton. Oszlop stop_id eovx eovy line_id stop_idx line_part_id stop_delay name
Leírás Egyedi azonosító a megállóhoz. EOVX koordináta a megállóhoz. EOVY koordináta a megállóhoz. A megállóhoz tartozó vonal egyedi azonosítója. A vonalon belül a megálló egyedi sorrendje. A jármű vonalvezetése a következő megállóig. A megállóhoz érkezés ideje percekben mérve, a vonal kezdőállomásától számolva. A megálló neve.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
39
bpm.bpm_schedule_set A menetrendeket leíró fejtábla. Egy sor a táblában egy napi menetrendet jelent egy vonal számára. Oszlop schedule_set_id name
Leírás Egyedi azonosító a menetrendhez. A menetrend belső használatra szánt neve, például hétköznap 7E, 2011 húsvét M2, ...
bpm.bpm_frequency Óránkénti indulási gyakoriságot kifejező adat egy vonal menetrendjében. Oszlop frequency_id schedule_set_id hour
frequency low_floor
Leírás Egyedi azonosító a táblához. A menetrend egyedi azonosítója, amihez az adat tartozik. Az óra, amiben érvényes az indulási gyakoriság. Ez az adat 032-ig terjedhet, mert az éjszakai menetrendek az előző naphoz tartoznak. Az indulási gyakoriság percekben mérve. Értéke igaz, ha az induló járművek alacsonypadlósak. Egyébként hamis.
bpm.bpm_unique_time Pontos, a kezdőállomásból történő egyszeri indulási időpontot kifejező adat egy vonal menetrendjében. Oszlop unique_time_id schedule_set_id hour minute low_floor
Leírás Egyedi azonosító a táblához. A menetrend egyedi azonosítója, amihez az adat tartozik. Az indulási óra. Ez az adat 0-32-ig terjedhet, mert az éjszakai menetrendek az előző naphoz tartoznak. Az indulási perc. Értéke igaz, ha az induló jármű alacsonypadlós. Egyébként hamis.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
40
bpm.bpm_unique_time_skip Egy pontos indulási időponthoz tartozó kihagyott megállókat tartalmazó tábla. Oszlop unique_time_id stop_idx
Leírás A pontos indulási időpont egyedi azonosítója, amihez az adat tartozik. A kihagyott megálló sorszáma a vonalon belül. (Lsd. bpm.bpm_stop.stop_idx)
bpm.bpm_calendar A vonalakat és a menetrendeket összekötő tábla. Egy vonalhoz több menetrendet is rendelhetünk, például egy menetrendet egész évre, és több kisebbet az egyes ünnepekre. Ha egy vonalhoz és időponthoz több menetrend is tartozhat, akkor az a menetrend lesz érvényes, ami teljesen a többin belül helyezkedik el. Oszlop calendar_id start end
day_type schedule_set_id line_id
Leírás Egyedi azonosító a táblához. Az érvényesség első napja. Az érvényesség vége; az első nap, amikor a menetrend már nem a teljes napra szól, hanem csak az éjszakai járatok menetrendjét tartalmazza. A hét azon napjai, amikor a menetrend érvényes. 1 jelenti a vasárnapot, 2 a hétfőt és így tovább. A használt menetrend egyedi azonosítója. Az érintett vonal egyedi azonosítója.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
41
3.4. Referencia implementáció A szakdolgozat része a 3.1. fejezetben definiált algoritmus egy implementációja. Az implementáció Java nyelven íródott és tartalmazza a megfelelő modulokat a Java EE 6 környezetbe való beillesztéshez, ahogy az a 3.7. ábrán látszik. Kliensoldal
útvonaltervezés
térképgenerálás
GlassFish
dRouteEngine
GeoServer
Java EE modulok
Általános modulok
war
client_connector
graph-connector
ejb
graph-simple
PostgreSQL
drouteengine adatbázis
bpm (menetrend)
osm (OpenStreetMap)
3.7. ábra. A modulok függőségei A szakdolgozat része egy webes felület, ami a Java EE 6 modulokkal működik együtt és az algoritmus tesztelésére használható. Az útvonaltervezés adatbázishátterét Budapest utcatérképe és menetrend-adatai szolgáltatják, ahogy azt a 3.3. fejezetben leírtuk. A webes felület által megjelenített raszteres térképet a GeoServer generálja. (Az ehhez szükséges beállításokat a 2.4.1. fejezetben tárgyaltuk.) Telepítés után a teljes alkalmazás képes internet-elérés nélkül – például egy belső hálózaton – működni. Megjegyezzük, hogy ha a megfelelő menetrend-adatok rendelkezésre állnak, akkor az implementáció más városokon is használható. A továbbiakban egyenként áttekintjük az implementáció még nem dokumentált moduljait.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
42
3.4.1. client_connector A client_connector modul tartalmazza az útvonaltervezési kérések és a kész útvonalak egységes reprezentációjára használható osztályokat. A modul osztálydiagramja a 3.8. ábrán látható. Az osztálydiagramon nem tüntettük fel a triviális getter és setter metódusokat. java.util :Point <>
Comparable
client-connector
Request
Point
-startPoint: Point -startBaseDistance: double -arrivePoint: Point -arriveBaseDistance: double -timeMeans: TimeMeans -userTime: Date -optimize: String -walkSpeed: double -lowFloorNeeded: boolean -maxWalk: double -maxWait: boolean -transferRatio: double +toString(): String
Reply
-x: Double -y: Double +Point() +Point(x:double,y:double) +distanceAd2(p:Point): double +distance(p:Point): double +compareTo(p:Point): int +equals(o:Object): boolean +hashcode(): int +toString(): String
ReplyEdge -edgeClass: String -edgeName: String -startTime: Date -arriveTime: Date -meters: double -seconds: double -points: List +toString(): String
3.8. ábra. A client_connector modul
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
43
Point A Point osztály egy síkbeli pontot reprezentál, két koordinátával. Az osztály szerializálható és rendelkezik JAXB-annotációkkal. Leírás x, y distanceAd2(p)
distance(p) compareTo(p)
equals(o)
hashCode() toString()
Koordináták. Az aktuális pont és egy másik pont közötti távolság számértékének négyzetét adja meg. Ez a metódus optimalizációként szolgál, a síkbeli koordinátarendszereknél jellemző gyökvonás elkerülésére, amikor arra nincs szükség. Az aktuális pont és egy másik pont közötti távolságot adja meg, méterekben mérve. Az aktuális pont és egy másik pont összehasonlítása. Az összehasonlítás az x koordináták, vagy egyenlőség esetén az y koordináták alapján történik. Az aktuális pont és egy másik pont ekvivalencia-vizsgálatára szolgáló metódus. Az x és y koordináták alapján történik a vizsgálat. Hash-érték számolás az x és y koordináták alapján. Visszaadja az aktuális pont formázott, szöveges reprezentációját, belső használatra.
ReplyEdge A ReplyEdge osztály egy logikailag egybetartozó útszakaszt reprezentál a kész útvonalban. Ez jellemzően két szomszédos megálló közötti útvonalat jelent járműves utazás esetén, vagy ugyanazon (nevű) utcán való gyaloglást. Az osztály szerializálható és rendelkezik JAXB-annotációkkal. Leírás edgeClass edgeName startTime arriveTime meters seconds points toString()
Rövid kódnév az útszakasz azonosításához, például street, travel-bus, travel-metro stb. Az útszakasz neve, például az utca neve vagy a két érintett megálló. Az útszakasz kezdetéhez érkezés ideje. Az útszakasz végéhez érkezés ideje. Az útszakasz sétálva megtett távolsága. Az útszakasz másodpercekben mért hossza. Az útszakaszt a térképen leíró töröttvonal. Visszaadja az aktuális útszakasz formázott, szöveges reprezentációját, belső használatra.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
44
ReplyDumpHelper A ReplyDumpHelper egy segédosztály, ami Reply objektumok feltöltésére szolgál. Szerepe az, hogy összevonja az egymás után következő, azonos edgeClass és edgeName értékekkel rendelkező útszakaszokat, akkor is, amikor az ilyen összetartozó részeket a program több független részben kezeli. A város élek például geometriailag egyenes szakaszok, egy utca pedig általában nem teljesen egyenes, ezért egy utcát több város él ír le az útvonaltervezés során. A kész útvonalban ennek ellenére utcánként csoportosítva szeretnénk látni az útvonal gyalog megtett részeit. Leírás request reply current next(...)
A Request objektum, amivel egy kliens az útvonaltervezést kérte. A Reply objektum, amit fel szeretnénk tölteni. Az aktuálisan használt útszakasz a feltöltés során. A metódus egy új útszakasz kezdetét jelzi. Ha a forceNew paraméter értéke igaz, akkor a metódus új útszakaszt kezd. Egyébként, ha az eddig a current adattagban hivatkozott útszakasz edgeClass és edgeName értékei megegyeznek a paraméterként kapott értékekkel, akkor a metódus nem kezd új útszakaszt, ellenkező esetben igen. Lezárja a current útszakaszt és hozzáadja az útvonalhoz. Hatása megegyezik a next(null, null, true) híváséval. Új térképi pontot ad hozzá az útszakaszt leíró töröttvonalhoz. A current adattag delegált metódusa. Továbbítja a kérést a current adattag számára, ha az új indulási idő korábbi, mint a már beállított. A current adattag delegált metódusa. Továbbítja a kérést a current adattag számára, ha az új érkezési idő későbbi, mint a már beállított. A current adattag delegált metódusa. Hozzáadja a kapott időtartamot az útszakasz eddigi seconds értékéhez. A current adattag delegált metódusa. Hozzáadja a kapott hosszt az útszakasz eddigi meters értékéhez. A current adattag delegált metódusa. (Csak getter !) A current adattag delegált metódusa. (Csak getter !)
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
45
Request A Request osztály reprezentál egy útvonaltervezési kérést. Az osztály szerializálható és rendelkezik JAXB-annotációkkal. A KÉRÉS értékeket a 3.1.1. fejezetben írtuk le; a max_várakozás és max_séta értékeket a 3.1.7. fejezetben, a sebesség_arány értéket pedig a 3.1.4. fejezetben vezettük be. Leírás startPoint arrivePoint timeMeans userTime optimize walkSpeed lowFloorNeeded maxWalk maxWait transferRatio startBaseDistance arriveBaseDistance toString()
KÉRÉS.indulás KÉRÉS.érkezés KÉRÉS.idő_mód KÉRÉS.idő KÉRÉS.optimalizálás KÉRÉS.gyaloglás_sebesség KÉRÉS.alacsonypadlós max_séta max_várakozás sebesség_arány Az indulási pont és a hozzá legközelebbi város élvég maximális távolsága, ahova még beköthetjük. Az érkezési pont és a hozzá legközelebbi város élvég maximális távolsága, ahova még beköthetjük. Visszaadja a kérés formázott, szöveges reprezentációját, belső használatra.
Reply A Reply osztály egy teljes útvonalat reprezentál. Ilyen objektumokat kapnak vissza a kliensek. Az osztály szerializálható és rendelkezik JAXB-annotációkkal. Leírás status edges time
Az útvonaltervezéssel kapcsolatos hibaüzenet. Ha nem történt hiba, akkor az értéke OK. Az útvonal, mint ReplyEdge útszakaszok listája. Az útvonaltervezés végrehajtásának kimért ideje a szervergépen, nanomásodpercekben mérve.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
46
3.4.2. graph_connector A graph_connector modul egy a program többi részétől független, saját készítésű gráfkezelő könyvtár. Felépítését a Boost Graph Library2 ihlette, de jelen szakdolgozathoz csak a Dijkstra-algoritmust és a hozzá kapcsolódó részeket készítettük el. A modul osztálydiagramja a 3.9. ábrán látható. Az osztálydiagramon nem tüntettük fel a triviális getter és setter metódusokat. graph-connector :Vertex :Edge
A használt generikus paraméterek leírása: Paraméter Vertex Edge Weight Distance Key Property
Leírás Tetszőleges típus egy csúcs reprezentálásra egy gráfban. Tetszőleges típus egy irányított él reprezentálására egy gráfban. A Dijkstra-algoritmus futása során egy csúcshoz rendelhető tetszőleges súlytípus. Az élek élsúlytípusa. Tetszőleges típus, jellemzően a Vertex vagy Edge értékét kapja. Tetszőleges típus.
Graph A Graph interfész egy szomszédsági gráf csak olvasható hozzáférését biztosítja a könyvtárban definiált algoritmusok számára. Leírás getVertices() getOutEdges(v) getInEdges(v) getStartVertex(e) getArriveVertex(e)
Visszaadja a gráfhoz tartozó csúcsok gyűjteményét. Visszaadja egy adott csúcshoz a csúcsból induló élek gyűjteményét. Visszaadja egy adott csúcshoz a csúcsba érkező élek gyűjteményét. Visszaadja egy adott élhez az indulási csúcsot. Visszaadja egy adott élhez az érkezési csúcsot.
InverseGraph Az InverseGraph osztály konstans időben képezi egy Graph implementáció transzponáltját. Leírás inner getVertices() getOutEdges(v) getInEdges(v) getStartVertex(e) getArriveVertex(e)
A Graph implementáció, amit transzponálunk. Az inner adattag delegált metódusa. inner.getInEdges(v) inner.getOutEdges(v) inner.getArriveVertex(e) inner.getStartVertex(e)
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
48
PropertyMap A PropertyMap osztály egy tetszőleges egyedi mezőt csatol a gráf csúcsaihoz vagy éleihez. Leírás get(k) put(k,p)
Egy adott kulcshoz (azaz csúcshoz vagy élhez) rendelt egyedi mező lekérdezése. Egy új egyedi mezőérték hozzárendelése az adott kulcshoz.
HashPropertyMap Egy PropertyMap implementáció, ami a HashMap könyvtári osztályt használja az egyedi mező tárolásához. WeightComparator A WeightComparator interfész lehetővé teszi a Weight típusú értékek összehasonlítását a Dijkstra-algoritmus futása során. Leírás createZeroWeight() createInfWeight()
compare(a,b)
Egy minimális Weight objektum generálása, ami a kezdőcsúcshoz hozzárendelhető a Dijkstra-algoritmus során. Egy maximális Weight objektum generálása, ami „végtelen-értékként” használható a Dijkstra-algoritmus során, azaz bármilyen más nem-végtelen értéknél nagyobb. Két Weight objektum összehasonlítása a Comparator interfész szabályai szerint.
WeightCombine A WeightCombine interfész lehetővé teszi egy (a gráf csúcsához rendelt) Weight érték és egy (a gráf éléhez rendelt) Distance érték „kombinálását”, például összeadását. Jellemzően egy csúcs értékét és a csúcsból kiinduló egyik él súlyát kombináljuk, hogy az így kapott értéket az él érkezési csúcsához rendeljük. Leírás combine(sourceWeight, edgeDistance)
sourceWeight + edgeDistance előállítása és visszaadása.
DijkstraVisitor A DijkstraVisitor interfész a Dijkstra-algoritmus futása során használható az algoritmus működésének kiegészítésére. Jellemző használata az előző élek folyamatos
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
49
nyilvántartása: minden, a kezdőcsúcsból elérhető csúcshoz a hozzá vezető legrövidebb útvonal előző élének tárolása. Leírás initializeVertex(v) examineVertex(v)
examineEdge(e)
edgeRelaxed(e) edgeNotRelaxed(e) finishVertex(v)
Ez a metódus egyszer hívódik meg a gráf minden csúcsára a Dijkstra-algoritmus inicializációja során. Ez a metódus a kiterjesztése előtt hívódik meg a v csúcsra, közvetlenül az előtt, hogy a csúcs kimenő éleire meghívnánk az examineEdge(e) metódust. Ez a metódus minden kiterjesztés alatt álló csúcs összes elérhető kimenő élére meghívódik, mielőtt az él súlyát kiszámolnánk. Ha az él célcsúcsának súlyát csökkenteni tudtuk az élen keresztül, akkor ez a metódus hívódik meg. Ha az él célcsúcsának súlyát nem tudtuk csökkenteni az élen keresztül, akkor ez a metódus hívódik meg. Ez a metódus a kiterjesztése után hívódik meg a v csúcsra, azaz miután az összes kimenő élét feldolgoztuk.
Dijkstra A Dijkstra osztály tartalmazza a Dijkstra-algoritmus kódját és referenciát tárol az algoritmus végrehajtásához szükséges összes bemeneti adatra. Leírás A bemeneti gráf, amin az algoritmust szeretnénk végrehajtani. A tervezés indulási csúcsa. A tervezés érkezési csúcsa, aminek a kiterjesztése előtt leállíthatjuk az algoritmust. weightCombine A használandó WeightCombine implementáció. A használandó WeightComparator implementáció. weightComp dijkstraVisitor A használandó DijkstraVisitor implementáció. weightMap A csúcsokhoz az algoritmus során rendelt élsúlyösszegek. distanceMap Az élekhez rendelt élsúlyok. Ezt a PropertyMap implementációt csak olvassuk az algoritmus során. edgePredicate Az élek elérhetőségének eldöntéséhez használt PropertyMap. (Csak olvassuk az algoritmus során.) Egy nem elérhető él olyan, mintha ott sem lenne, azaz egyszerűen kihagyjuk a feldolgozását az algoritmus során. colorMap A csúcsokhoz rendelt feldolgozottsági állapot az algoritmus során. search() Az algoritmus futtatása. g start arrive
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
50
3.4.3. graph_simple A graph_simple modul szolgál a PostgreSQL adatbázis, a graph_connector modul és a client_connector modul összekapcsolására. A modul osztálydiagramjai a 3.10., 3.11., 3.12. és 3.13. ábrán láthatók. Az osztálydiagramokon nem tüntettük fel a triviális getter és setter metódusokat. graph-connector :Vertex :Edge <>
SimpleGraph A modul által használt Graph implementáció, ami a szintén a modulban lévő Vertex és Edge osztályokat használja a csúcsok és az élek reprezentálására. Leírás addEdge(e)
Egy új él hozzáadása a gráfhoz. Ha az indulási vagy érkezési csúcsok még nem lennének a gráf részei, akkor automatikusan hozzáadódnak.
Vertex A modul által használt osztály a csúcsok reprezentációjára. Leírás point type equals(o) hashCode() toString()
A csúcshoz rendelt térképi pont. Egyéb szöveges infó, az azonos térképi ponton lévő csúcsok megkülönböztetéséhez. Az aktuális csúcs és egy másik csúcs ekvivalencia-vizsgálatára szolgáló metódus. A point és type adattagok alapján történik a vizsgálat. Hash-érték számolás a point és type adattagok alapján. Visszaadja az aktuális csúcs formázott, szöveges reprezentációját, belső használatra.
Edge A modul által használt absztrakt osztály az élek általános leírására. Leírás start arrive isAvailable(...) computeWeight(...)
dumpProduction(...)
updateReplyDumpHelper(...)
Az él kiindulási csúcsa. Az él érkezési csúcsa. Igaz értéket ad vissza, ha az él elérhető a gráfbejárása során a Dijkstra-algoritmus számára. Kiszámolja az él súlyát, majd hozzáadja azt a paraméterként kapott sourceWeight érték másolatához és visszaadja a másolatot. Ezzel a metódussal konvertálódnak az útvonaltervezés után a legrövidebb útvonal élei a client_connector modulban definiált formába. Segédmetódus a ReplyEdge osztály seconds, meters, startTime és arriveTime értékeinek beállításához. A metódus a Dijkstra-algoritmus során kiszámolt Weight értékeket használja fel.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
52
GraphManager Az osztály a modul szolgáltatásait teszi elérhetővé a program többi része számára. A gráf betöltését az adatbázisból, ami akár hosszabb ideig is eltarthat, külön szálban végzi. Leírás appConfig
graph run() dijkstra(...)
A program üzemeltetője által módosítható konfigurációs beállítások. Innen olvassuk ki például a gráf betöltéséhez használt SQL utasításokat. Az aktuálisan használt, teljesen betöltött gráfra mutató referencia, vagy null, ha még nincsen gráf betöltve. A gráf betöltését és frissítését végző szál kódja. Egy útvonaltervezés végrehajtása a gráfon, majd az eredmény visszaadása a hívó félnek. Ha még nincs betöltött gráf, akkor is azonnal visszatér egy hibaüzenettel. (Lsd. Reply.status mező.)
graph-connector
:Weight <>
WeightComparator
:Weight :Weight <>
WeightCombine
graph-simple
ForwardWeightComparator -dijkstraCtx: DijkstraContext +createInfWeight(): Weight +createZeroWeight(): Weight +compare(a:Weight,b:Weight): int
ReverseWeightComparator -dijkstraCtx: DijkstraContext +createInfWeight(): Weight +createZeroWeight(): Weight +compare(a:Weight,b:Weight): int
Weight -seconds: Double -meters: Double -metersExtra: Double -metersExtraLocal: Double -metersFrame: Double -transferCount: int -waitExtra: Double -skipStops: Set -transport: Transport +equals(o:Object): boolean +hashCode(): int +clone(): Weight +toString(): String
Weight A modul által használt osztály az élsúlyok reprezentálására. Vegyük észre, hogy az osztály nem definiál természetes rendezést! A rendezési reláció pontos megvalósítása függhet a Request értékétől, ezért a lehetséges rendezéseket több WeightComparator implementációban rögzítettük és futási időben választunk közülük. Leírás seconds meters metersExtra metersExtraLocal metersFrame
transferCount waitExtra skipStops
transport
equals(o)
hashCode() toString()
Unix timestamp érték, másodpercekben mérve. Gyalogosan megtett távolság, méterekben mérve. A Request.maxWalk értéken túl, járműves utazás nélkül, egyszerre megtett gyalogos távolság. A legutóbbi járműves utazás (vagy az útvonal eleje) óta a Request.maxWalk alatt megtett gyalogos távolság. Az indulási és érkezési pontok bekötőszakaszának megtett gyalogos távolságai. Minden esetben ez a mező az élsúlyok elsődleges rendezési szempontja, hogy a lehető legrövidebb bekötőszakaszokat válassza a Dijkstra-algoritmus. A felszállások száma. A Request.maxWait értéken túli megállóban várakozás ideje másodpercekben. A menetrend élek között az aktuálisan használt jármű által kihagyott megállók listája. Város éleknél a mező értéke null. Ez az információ az adatbázisból jön és az élsúly-értékeket használjuk arra, hogy propagáljuk a Dijkstra-algoritmus futása során. A menetrend élek között az aktuálisan használt vonal leírója. Város éleknél a mező értéke null. Ez az információ az adatbázisból jön és az élsúly-értékeket használjuk arra, hogy propagáljuk a Dijkstra-algoritmus futása során. Az aktuális élsúly és egy másik élsúly ekvivalenciavizsgálatára szolgáló metódus. A vizsgálat a skipStops és a transport mezőkön kívül minden adattagot figyelembe vesz. Hash-érték számolás, az equals(o) metódushoz illeszkedve. Visszaadja az aktuális élsúly formázott, szöveges reprezentációját, belső használatra.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
54
ForwardWeightComparator Az indulási időre tervezés során használt WeightComparator implementáció. Az összehasonlítási szempontok, sebességre optimalizálás esetén: Irány 1. 2.
< <
3. 4.
< <
Kifejezés Weight.metersFrame Weight.metersExtra + Weight.waitExtra Request.walkSpeed Weight.seconds+Weight.transferCount·Request.transferRatio Weight.meters
Gyaloglásra optimalizálás esetén: Irány 1. 2.
< <
3.
<
4.
<
Kifejezés Weight.metersFrame Weight.metersExtra + Weight.waitExtra Request.walkSpeed Weight.meters Request.walkSpeed
+ Weight.transferCount · Request.transferRatio
Weight.seconds
ReverseWeightComparator Az érkezési időre tervezés során használt WeightComparator implementáció. Az összehasonlítási szempontok, sebességre optimalizálás esetén: Irány 1. 2.
< <
3. 4.
> <
Kifejezés Weight.metersFrame Weight.metersExtra + Weight.waitExtra Request.walkSpeed Weight.seconds−Weight.transferCount·Request.transferRatio Weight.meters
Gyaloglásra optimalizálás esetén: Irány 1. 2.
< <
3.
<
4.
>
Kifejezés Weight.metersFrame Weight.metersExtra + Weight.waitExtra Request.walkSpeed Weight.meters Request.walkSpeed
+ Weight.transferCount · Request.transferRatio
Weight.seconds
SimpleWeightCombine A modul által használt WeightCombine implementáció. Leírás combine(sW, edgeDistance)
Mindig az edgeDistance-t adja vissza. (Lsd. Edge.computeWeight(...))
3.12. ábra. A graph_simple modul - az élek SimpleEdgePredicate Csak olvasható PropertyMap implementáció, ami a kapott él Edge.isAvailable(...) metódusának visszatérési értékét adja vissza. EdgeDistanceMap Csak olvasható PropertyMap implementáció, ami a kapott él Edge.computeWeight(...) metódusának visszatérési értékét adja vissza. Transport Egy vonal globális információit tartalmazó osztály. Az adatbázisból kerül feltöltésre.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
56
BpmCalendar Egy időintervallum menetrendjét reprezentáló osztály egy vonal számára, egy irányba. Ezt az osztályt használjuk a 3.1.1. fejezetben deklarált INDULÁS(...) és ÉRKEZÉS(...) kifejezések értékeinek kiszámolására. Az adatbázisból kerül feltöltésre. WalkEdge A gyalogos, geometriailag egyenes szakaszt bejáró élek közös ősosztálya. Leírás getWalkDistance(...) computeWeight(...) getEdgeClass() getEdgeName() dumpProduction(...)
Absztrakt metódus a szakasz hosszának kiszámolására. Az él súlyának kiszámolása a getWalkDistance(...) segítségével. Absztrakt metódus, ami az él kliensoldal felé szánt rövid azonosítójával tér vissza, ami az él típusára utal. Absztrakt metódus, ami az él kliensoldal felé szánt teljes nevével tér vissza. (Pl. az utca neve.) Virtuális metódus, ami elvégzi az él átalakítását a kliensoldal felé, a térképi pontok átadását kivéve. Azt a gyerekosztályokra hagyja.
TransferEdge A felszállás- és leszállás éleket reprezentáló osztály. Leírás transport stopDelay stopIdx calendars computeWeight(...)
dumpProduction(...)
Az él által érintett megállóhoz tartozó vonal leírója. Az él által érintett megálló távolsága a vonal kezdőállomásától, másodpercekben mérve. Az él által érintett megálló sorszáma a vonalon. Az összes érvényes BpmCalendar listája, ami az él által érintett vonalra vonatkozik. Kiszámolja az él súlyát, majd hozzáadja azt a paraméterként kapott sourceWeight érték másolatához és visszaadja a másolatot. Ezzel a metódussal konvertálódnak az útvonaltervezés után a legrövidebb útvonal élei a client_connector modulban definiált formába.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
57
TravelEdge A menetrend éleket reprezentáló osztály. Leírás length points
computeWeight(...)
dumpProduction(...)
Az él hossza, másodpercekben mérve. A jármű vonalvezetése az él által érintett két megálló között. A dumpProduction(...) metódusban kerül felhasználásra. Kiszámolja az él súlyát, majd hozzáadja azt a paraméterként kapott sourceWeight érték másolatához és visszaadja a másolatot. Ezzel a metódussal konvertálódnak az útvonaltervezés után a legrövidebb útvonal élei a client_connector modulban definiált formába.
3.13. ábra. A graph_simple modul - a gyalogos élek
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
58
StreetEdge A város éleket reprezentáló osztály. Leírás edgeName getWalkDistance(...) getEdgeClass() dumpProduction(...)
Az utca neve. A start és arrive csúcsok pontjai közötti távolságot adja vissza. A "street" stringet adja vissza. Ezzel a metódussal konvertálódnak az útvonaltervezés után a legrövidebb útvonal élei a client_connector modulban definiált formába.
ConnectorEdge A konnektor éleket, azaz a megállókat és a városréteget összekötő éleket reprezentáló osztály. Leírás getEdgeClass()
A "connector" stringet adja vissza.
StartEdge Az indulási pontot és a városréteget összekötő éleket reprezentáló osztály. Leírás isAvailable(...)
getWalkDistance(...) computeWeight(...)
getEdgeClass() getEdgeName() dumpProduction(...)
Igazat ad vissza, ha az él célcsúcsa (ami egy város csúcs) a Request.startPoint ponttól maximum Request.startBaseDistance távolságra van. A Request.startPoint és az arrive csúcs pontja közötti távolságot adja vissza. Az él súlyának kiszámolása a getWalkDistance(...) segítségével, majd az él hosszának hozzáadása a Weight.metersFrame mezőhöz is. A "start" stringet adja vissza. A "start" stringet adja vissza. Ezzel a metódussal konvertálódnak az útvonaltervezés után a legrövidebb útvonal élei a client_connector modulban definiált formába.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
59
ArriveEdge A városréteget és az érkezési pontot összekötő éleket reprezentáló osztály. Leírás isAvailable(...)
getWalkDistance(...) computeWeight(...)
getEdgeClass() getEdgeName() dumpProduction(...)
Igazat ad vissza, ha az él indulási csúcsa (ami egy város csúcs) a Request.arrivePoint ponttól maximum Request.arriveBaseDistance távolságra van. A start csúcs pontja és a Request.arrivePoint közötti távolságot adja vissza. Az él súlyának kiszámolása a getWalkDistance(...) segítségével, majd az él hosszának hozzáadása a Weight.metersFrame mezőhöz is. Az "arrive" stringet adja vissza. Az "arrive" stringet adja vissza. Ezzel a metódussal konvertálódnak az útvonaltervezés után a legrövidebb útvonal élei a client_connector modulban definiált formába.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
60
3.4.4. ejb EJB modul az algoritmus Java EE környezetbe illesztéséhez. A modul az alábbi beaneket tartalmazza: Bean GraphBean
RouteBean
Leírás Lokális singleton session bean. Feladata az alkalmazás konfigurációs beállításainak betöltése és a graph_simple modul GraphManager osztályából egy példány tárolása és lokális kiszolgálása. (A GraphManager osztály a teljes betöltött bemeneti gráfra tartalmaz referenciákat, ezért akár nagyon sok memóriát is elfoglalhat. Ezt az osztályt nem célszerű távoli eljáráshívás paramétereként vagy visszatérési értékeként használni.) Remote stateless session bean. Feladata az útvonaltervezési kérések kiszolgálása, amihez a GraphBean által tárolt GraphManager objektum dijkstra(...) metódusát delegálja. Ez a metódus egy Request típusú paraméterrel és Reply típusú visszatérési értékkel rendelkezik, tehát alkalmas távoli eljáráshívásra.
3.4.5. war WAR modul az algoritmus teszteléséhez használt webes felülettel. (Leírás a 2.1. fejezetben.) A modul tartalmaz egy RESTful web service-t RouteService néven, ami a RouteBean metódusait delegálja. JSP vagy JSF oldalak nincsenek, a kliensoldal statikus HTML (és CSS) lapokból és Javascript szkriptekből áll.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
61
3.5. Tesztelés 3.5.1. Fehér doboz tesztelés A 3.1. fejezet alfejezetei – az első kettő kivételével – egy-egy fehér doboz teszteléssel felfedezett problémát mutatnak be az algoritmus működésében és annak lehetséges megoldásait fejtik ki. Ezen kívül az alábbi, a referencia implementációhoz kapcsolódó teszteseteket nézzük végig: – Unit tesztek a program osztályainak és moduljainak elvárás szerinti működésének tesztelésére. Tapasztalat: az összes unit teszt hiba nélkül lefut. – A dRouteEngine indítása PostgreSQL adatbázisháttér indítása nélkül. Tapasztalat: a dRouteEngine néhány másodpercenként megpróbálja felvenni a kapcsolatot az adatbázisháttérrel. Amint ez megtörténik, sikeresen betölti a bemeneti gráfot. – A PostgreSQL adatbázisháttér leállítása a bemeneti gráf betöltése után. Tapasztalat: az útvonaltervezések gond nélkül kiszolgálásra kerülnek a korábban betöltött gráf használatával. – Útvonaltervezési kérés küldése, mielőtt a gráf betöltődött volna. Tapasztalat: a böngésző felbukkanó ablakban értesít arról, hogy a gráf még nincs betöltve. – Útvonaltervezési kérés küldése Szegedről Sopronba, illetve bármilyen utcától 750 méternél távolabbról vagy távolabbra. Tapasztalat: a böngésző felbukkanó ablakban értesít róla, hogy nem tudott útvonalat tervezni. – Útvonaltervezési kérés küldése egy olyan napra, amihez nincsen menetrend adatbázis betöltve. Tapasztalat : a kapott útvonalak járművek használata nélkül, gyalogosan teszik meg az utat.
3.5.2. Fekete doboz tesztelés – Hibás vagy értelmezhetetlen kérés küldése. (Megjegyezzük, hogy ez „jóindulatú” tesztelés során nem fordulhat elő, mert a webes felületen minden bemeneti adathoz kitöltési segédletek vannak.) Tapasztalat: a böngésző felbukkanó ablakban értesít róla, hogy hiba történt a tervezés során.
3. FEJEZET. FEJLESZTŐI DOKUMENTÁCIÓ
62
– Tömeges tesztelés véletlenszerű indulási és érkezési pontok használatával, a 3.1.1. fejezetben az útvonaltervezés kimenetére megfogalmazott megszorítások teljesülésének ellenőrzése. Az ellenőrzés könnyen szkriptelhető, mivel az útvonaltervezés egy RESTful web service-en – azaz egy speciális HTTP POST kérésen – keresztül történik, ezért a webes felületet nem kötelező használni hozzá. Tapasztalat: a tesztelés fényt derített néhány adatbázis-hibára a menetrend adatok között, amik jellemzően negatív élek felbukkanását eredményezték a gráfban. Ez nem folytonos útvonalakat eredményezett: a tervezett útvonalak néhány fix pontban mindig megszakadtak és a gráf egy másik, látszólag független pontjában folytatódtak. A megoldás egyrészt az adatbázis megtisztítása volt, másrészt egy ellenőrzés beépítése a Dijkstra-algoritmusba, ami egy hibaüzenettel leállítja a tervezést, ha negatív élet talál. – Hatékonysági és terheléses tesztek futtatása. Tapasztalat: a kliensoldal bármilyen modern böngészőn futtatható. (A tesztelt böngészők listáját lsd. lentebb.) Gépigénye megegyezik a böngészők átlagos gépigényével. A szerveroldal futtatásához legalább 4GB RAM szükséges és ajánlott legalább 5GB lemezterületet biztosítani a működés közben legenerált térképcsempék cache-e számára. A térképcsempék generálása helyben, kérésre történik, ezért ha olyan helyre és zoom szintre navigál egy felhasználó, ahol még senki nem járt, akkor érezhetően lassabb lehet a térkép kiszolgálása. Több párhuzamos útvonaltervezés érezhetően lassít a kiszolgáláson; ez több gép felhasználásával a Java EE architektúra skálázhatóságának köszönhetően rendszerüzemeltetői szinten orvosolható. – A webes felület működésének tesztelése több böngészőn. Tapasztalat : a webes felület megjelenése és működése helyes és megközelítőleg azonos az alábbi böngészőkön: •
Mozilla Firefox 1.5 — 4.0
•
Internet Explorer 6 — 8
•
Safari 4.0.5
•
Google Chrome 11.0
4. fejezet Összegzés 4.1. Továbbfejlesztés A dRouteEngine alkalmazás jelenlegi formájában több irányba is továbbfejleszthető. A következő részben néhány ilyen irányt veszünk számba.
4.1.1. Egy város tömegközlekedésének vizsgálata A Dijkstra-algoritmus egy indulási pontból a gráf összes többi pontjába tervez útvonalat. Ez felhasználható olyan várostérképek készítésére, amik a magassági vagy a meteorológiai (hőmérsékleti) térképekhez hasonlóan megmondják, hogy egy fix kezdőpontból mennyi idő alatt lehet eljutni a város többi részébe. Az ilyen térképek felhasználhatóak egy város tömegközlekedésének vizsgálatára és javítására, vagy akár lakásvásárlás előtt a környék felmérésére stb.
4.1.2. Mobil felület A mobil eszközök támogatásához a webes felületet alkotó két fontos programkönyvtár, a jQuery és az OpenLayers mobil változatát kell használni. (Egy működő példa: [7]) Más változtatás nem szükséges.
4.1.3. Offline működés Az alkalmazás offline történő, jellemzően mobil eszközökről való működtetéséhez egy új gráfbetöltő modult és új felhasználói felületet kell írni. A jelenleg használt modul PostgreSQL-t használ a betöltéshez, ami egy mobil eszközön nem lesz elérhető. Az új modul betöltheti a gráfot például deszerializációval, egy lokálisan tárolt bináris fájlból. Ekkor a bináris fájlt a fejlesztőnek kell legenerálnia és eljuttatnia a felhasználókhoz. Az alkalmazás többi modulja módosítás nélkül használható az új környezetben. (A Java EE kötések természetesen nem szükségesek.) 63
4. FEJEZET. ÖSSZEGZÉS
64
4.1.4. Több város támogatása Egy telepítés akár több különböző város számára is nyújthatna útvonaltervezési szolgáltatásokat. Ehhez el kell különíteni egymástól a független városokat az OpenStreetMap adatok és a menetrend kezelésénél és szükséges lehet egy webes adminisztrációs felület megírása is.
4.1.5. Útvonaltervezés járműveknek Egy városban üzemeltetett járatok útvonalának megtervezéséhez és adminisztrálásához hasznos segítséget nyújthat egy pontos útvonaltervező. Ehhez további térképi adatok szükségesek: – Irányítási adatok az utcákhoz, hogy a tervező figyelembe tudja venni az egyirányú utcákat. – Kanyarodási szabályok a kereszteződésekhez, hogy csak megfelelő módon kanyarodhasson az útvonal. – Maximális (vagy átlagos) haladási sebességek az utcákhoz, esetleg napszakra lebontva. – Egyéb megszorítások, például járművekre vonatkozó súly- vagy magasságszabályozások.
4.1.6. Kerítések Az útvonaltervezések GPS koordinátapárok között történnek, amiket az útvonal legelején és legvégén „bekötünk” egy közeli utcához. Ez a módszer nem tökéletes, mivel nem veszi figyelembe az esetleges átjárhatatlan akadályokat, például folyóvizek, vasutak, autópályák, épületek stb. Megoldás lehet az ilyen akadályok ellenőrzése és egy akadálymentes bekötő szakasz kiválasztása.
4.1.7. Részletes statisztikák A jelenlegi, teszteléshez használható webes felület helyett egy komplett útvonaltervező webes felületét lehetne kialakítani. Ehhez az útvonaltervezők szokásos funkcióit kell megvalósítani: részletes statisztikák a webes felületen vagy PDF formátumban, jármű-ágazatok ki- és bekapcsolásának lehetősége stb.
Irodalomjegyzék [1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Új algoritmusok. Scolar Kiadó, 2003. ISBN 963-9193-90-9. [2] FlorentDotMe. OSM Styles for GeoServer. Website, May 2011. https://github. com/FlorentDotMe/OSM−Styles−for−GeoServer. [3] OSM in a Box. Wiki. Website, May 2011. ch/redmine/projects/osminabox/wiki.
http://dev.ifs.hsr.
[4] Dr. Fekete István. Algoritmusok és adatszerkezetek II. Website, February 2011. http://people.inf.elte.hu/fekete/docs_2/grafalg/grafalg.htm# dijkstra. [5] Boost C++ Libraries. The Boost Graph Library. Website, May 2011. http: ://www.boost.org/doc/libs/1_46_1/libs/graph/doc/index.html. [6] OpenGeo. GeoServer Users Manual. Website, February 2011. http://docs. geoserver.org/stable/en/user/webadmin/index.html. [7] OpenLayers. OpenLayers with jQuery Mobile. Website, May 2011. http: ://openlayers.org/dev/examples/mobile−jq.html. [8] Refractions Research. PostGIS 1.5.2 Manual. Website, February 2011. http: ://postgis.org/documentation/manual−1.5/. [9] OpenStreetMap Wiki. Budapest. Website, February 2011. http://wiki. openstreetmap.org/wiki/Budapest. [10] OpenStreetMap Wiki. Budapest. Website, February 2011. http://wiki. openstreetmap.org/wiki/Map_Features. [11] OpenStreetMap Wiki. Osm2pgsql schema. Website, May 2011. http://wiki. openstreetmap.org/wiki/Osm2pgsql/schema. [12] OpenStreetMap Wiki. Planet.osm. Website, February 2011. http://wiki. openstreetmap.org/wiki/Planet.osm. 65
