Routino

A routino egy útvonaltervező, mely OSM adatok alapján képes a legrövidebb, vagy a leggyorsabb utat kiszámítani két pont között.

Telepítés

Előfeltételek A program előfeltételeit célszerű telepíteni először

apt-get install gcc make libc6-dev libz-dev libbz2-dev
apt-get install libwww-perl liburi-perl libjson-pp-perl #These are optional

Telepítés A telepítéshez ez után le kell töltenünk a Routino weboldaláról a forráskódot, majd azt kibontva, le kell fordítanunk, majd be kell másolni az Apache webszerver mappájába.

make
cp -a web /var/www/routino
chown -R www-data:www-data /var/www/routino

Ezek után az OSM adatokat fel kell dolgozni:

cd /var/www/routino/data
../bin/planetsplitter --errorlog [Tetszőleges OSM fájl neve].osm.bz2

Miután megvolt, válasszuk ki, hogy OpenLayers vagy Leaflet felületen szeretnénk-e használni a Routino-t, és futtassuk ezt le:

cd /var/www/routino/www/[openlayers vagy leaflet]
sh -x install.sh

Ezek után még egy lépés hátra van, az apache /etc/apache2/sites-enabled/000-default fájljába ezeket a sorokat hozzá kell adni:

<Directory /var/www/routino>
    AllowOverride Options=MultiViews,ExecCGI FileInfo Limit
</Directory>

Konfigurálás Szerkesszük az alábbi fájlt: /var/www/routino/www/routino/mapprops.js

• A library változó értékével tudjuk módosítani, hogy az OpenLayers vagy a Leaflet felületet próbálja-e meg betölteni.
• A westedge eastedge southedge northedge zoomout zoomin változókkal értelemszerűen a térkép mozgásterét tudjuk korlátozni, illetve a minimum és a maximum zoom értékeket.
• A mapdata változóban tudjuk megadni, hogy melyik Tileserver-ről szedje le a térkép Tile-okat. Az alapértelmezett Tileserver jelenleg megfelelő lesz.

Algoritmusok

Előfeldolgozás

Ahhoz, hogy kellően gyors, és hatékony legyen az útvonalkeresés, az OSM adatokat feldolgozzuk, és eltároljuk egy lokális adatbázisban. A csomópontok közül a legtöbbet töröljük, és az érdekes csomópontokat hagyjuk meg. Ezután az izolált területeket töröljük.

A csomópontok megtartásának szabályai:

• 3 vagy több útvonalszakaszt köt össze.
• 2 útvonalszakaszt köt össze, de a két útvonalszakasznak más tulajdonságai vannak.
• 2 útvonalszakaszt köt össze, de az útvonalszakaszok közt megváltoztak az útvonaltervezési korlátozások.

A fentebbi szabályokat felhasználva a csomópontok törlését annyiszor ismételhetjük, amíg csak a legfontosabb csomópontok maradnak már csak meg. Ezeket a csomópontokat szuper-csomópontnak nevezzük, és a szuper-csomópontokat szuper-utak kötik össze.

Útkeresés

1. A kezdőponttól útvonalat keresünk a legközelebbi szuper-csomóponthoz.
2. A végponttól útvonalat keresünk a legközelebbi szuper-csomóponthoz.
3. Az 1. és a 2. szuper-csomópont közt megkeressük a szuper-útvonalat.
4. A 3. pontban talált szuper-útvonalak mindegyikére megkeresi a legrövidebb utat a szuper-útvonal kezdő és végpontja között.

Az útvonal keresési algoritmust az A* algoritmussal (vagy legalábbis egy ehhez nagyon hasonlító algoritmussal) oldották meg. Ez az algoritmus a kezdő csomóponttól a legkisebb érték (legrövidebb, vagy leggyorsabb út) kiszámítására törekszik minden csomóponthoz.

A 4. pontban lévő útvonalakat viszont a Dijkstra algoritmussal keresi meg.