Revision [105]
This is an old revision of RoutingProposal made by NickN17 on 2008-03-21 12:50:29.
Priatelia, ja som si naivne myslel, že to najprv trochu porozoberáme, či som si to vymyslel použiteľne a nie že všetci začnete kodovať o dušu :)
Routing Proposal
Ú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.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.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ý
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