Revision [576]
This is an old revision of RoutingProposal made by JozefVince on 2008-12-16 00:11:04.
Úložisko routing dát
pre rýchly štart som si vybral SQLite, perl na predspracovanie a prípravu dát... ak uvidim, že to vedie k nejakému výsledku, možno sa zamyslím nad nejakým binárnym storage formátom.Existuje postgis čo je GIS nadstavba na PostgreSQL. Import z osm je cez osm2pgsql. - ano ale uvazoval som sqlite kvoli tomu, ze na mobile skor rozchodim sqlite kniznicu ako cely postgis)
Spracovanie OSM dát
- načítať slovakia.osm do osm.db (SQLite databazy)
- zrušiť všetky neroutovatelné data (lesy, voda, landuse...) - tu pripomínam sám sebe, že landuse može byť potrebné pre spočítanie maxspeed pre cesty vramci landuse, zatiaľ však ignorujme túto "drobnosť"
- nájsť všetky RoutingNodes. to sú tie, ktoré sú na začiatku a na konci každej cesty, a body, v ktorých sa spájajú dve alebo viac ciest
- rozbiť všetky cesty na RoutingSegments - to sú také úseky ciest, ktoré medzi jednotlivými RoutingNodes
- spojiť lineárne segmenty ciest druhu do jedného RoutingSegments (napr. ulica-most-ulica je z hľadiska routovania jeden segment)
- pre každý RoutingSegment spočítať PenaltyVector / RoutingFeatureWeightVector [w1,w2,...wN] - vyjadruje, že pre RoutingSegment(rsX) tvorený RoutingNode(rnA) a RoutingNode(rnB) sú vybrané RoutingFeatures [rf1,rf2,...rfN] zastúpené príslušnou váhou - dobre zvolené RoutingFeatures a dobre zvolené výpočty RoutingFeatureWeightVector su predpokladom dobrého vyhľadávania cesty podľa zvolených RoutingProfile -ov
- treba poriešiť jednosmenky - t.j. bude si povieme, že RoutingSegment(rsX1) [ RoutingNode(rnA) , RoutingNode(rnB) ] je iný ako RoutingSegment(rsX2) [ RoutingNode(rnB) , RoutingNode(rnA) ], pritom RoutingSegment(rsX1) a RoutingSegment(rsX2) môžu mať rozdielne váhy pre RoutingFeatureWeightVector (napriklad kvoli tomu, že jeden smer je z kopca a druhý do kopca - súhlasím, že zachádzam do extrému, ale ja to rád)
- musím ešte spomenúť RoutingProfile [ c1,c2,...cN ] - vyjadrujúci ktorý faktor z RoutingFeatureWeightVector -a má aký vplyv na výber trasy
Kolo druhé
Ak uvažujem o možnosti plánovať cestu "easy", a neskôr samozrejme TurnRestrictions (až bude OSM rozhodnute, ako si želá modelovať zákazy odbočenia), je potrebné brať do úvahy aj vzájomné vzťahy medzi RoutingSegments, ktoré majú spoločný RoutingNode. Napr. je viac easy odbočiť z hlavnej cesty na vedlajšiu ako naopak, zabočiť doprava je jednoduchšie ako zabočiť doľava (ak nie si v Anglicku).Všeobecne je možné uvažovať aj o RoutingFeatureWeightVector-e
- pri prechode cez RoutingNode bez ohľladu na to, z ktorého do ktorého RoutingSegment -u
- pri prechode cez RoutingNode z jedného RoutingSegment-u na druhý
Routovanie neaút
Okrem aút routovanie používajú aj iné subjekty, ktoré majú iné potreby (chodci, bicykle, člny). Tieto majú niekedy iné požiadavky a možnosti- môžu chodiť po peších zónach a v protismere jednosmeriek
- môžu používať turistické chodníky
- nejazdia po dialniciach
- nejazdia po cestách prvej triedy (ak ich úspora z ich použitia nie je viac ako x%)
- preferujú tichšie cesty (ak nie sú "oveľa" dlhšie)
- do výslednej ceny cesty vstupuje aj celkové prevýšenie (ideálne aj zobrazenie celkového profilu)
- môžu používať hromadnú dopravu, lanovky, ...
- cesta z kopca a do kopca má úplne inú a subjektívnu rýchlosť (profil užívateľa?)
- postupom času rýchlosť človeka klesá (ak nemal obed a primeranú prestávku)
Takže RoutingFeatureWeightVector môže byť veľmi dlhá téma. Ale čas raz príde.
Tu prichadza na scenu moja druha myslienka, ze pre jednotlive ukazovatele vah vytvarat separatne subory (nieco ako car_motorway.db, car_primary.db, .... pedestrian_uphill.db, pedestrian_downhill.db ) - kde budu dvojice (segment_id, predpocitana_vaha) pripadne trojice (segment_1_id, segment_2_id, predpocitana_vaha) pre "odbocenia" ... je treba udrziavat konzistente id vsetkeho okolo ...ale dava to volnost v tom, ze si na kartu stiahnes len to co pouzivas, a soft ktory by stym mal/mohol vediet pocitat by mal databazu pre RoutingProfiles - a pouzival by vahy len z dostupnych *.db suborov ) - ked sebou nezoberies pedestrian_downhill.db, nebude ti optimalizovat cestu na idenie dolu kopcom lebo nebudu vahy...
Routing Algorithm
o Algoritme A* teda veľa neviem, len toľko, že sa podobá na Dijkstra, len používa nejakú heuristiku na odhad z aktuálnej pozície do cieľa. Nesnaži sa generovať všetky možné trasy naraz, ale vylešpuje vždy tú, ktorá dáva najmenší súčet prejdenej cesty + heuristika do ciela.O heuristike
- najjednoduchšia a naj naivnejšia je euklidova vzdialenosť do cieľa, len nemám zatiaľ premyslené, ako do tej heuristiky pretaviť hodnoty RoutingFeatureWeightVector.- podmienkou je aby heuristika podcenovala cestu z aktuálneho bodu do cieľa
RoutingFeatureWeightVector
keby ste chceli, mohli by sme pozbierať komponenty toho nášho RoutingFeatureWeightVector -a- pravdepodobne s najväčšou váhou vstupuje vzdialenosť
- druhou v poradí je asi typ cesty (po diaľnici sa ide určite pohodlnejšie (možno ekomonickejšie) ako po ceste 2. triedy)
- rýchlosť na danom úseku (tá je ale podmienená aj RoutingProfile a ako tak uvažujem, možno to bude treba rozbiť na viac faktorov, MaxSpeed, AverageSpeed... )
- čas potrebný na prechod RoutingSegment -om (všeobecne môže byť odvodený od vzdialenosti a AverageSpeed , no určite nie od MaxSpeed)
- výškový profil RoutingSegment (píšem to tu preto, lebo môžeme uvažovať aj o plánovaní cesty pre turistiku, kde je toto podstatná informácia, pravdepodobne v uvádzať ako dva parametre, suma stúpaní a suma klesaní na danom RoutingSegment )
- doplňte...
Yo... celková prejdená trasa je SUMA ( RoutingProfile [ c1,c2,...cN ] x RoutingFeatureWeightVector(RoutingSegment, [w1,w2,...wN]) ) + Heuristika - a táto sa minimalizuje