Reitti(polku)-analyysi Tässä yhteydessä reitti-analyysin tapauksessa lähdeaineisto on rasterimuotoinen. Vektorimuotoisen aineiston yhteydessä puhutaan verkosto-analyysistä.
Reitti-analyysiä varten tarvitaan:
lähderasteri, jossa vain lähdesolut sisältävät dataa. Optimaalisen polun löytäminen tapahtuu suhteessa näihin soluihin
kustannusrasteri, jossa märitellään kustannus (tai vastus) liittyen kyseisen solun läpi kulkemiseen. Kustannus muodostuu usein useamman komponentin summana. Kustannukset voivat olla absoluuttisia (mitattavissa esim. rahamäärällä) tai suhteellisia. Viimeisiä voidaan käyttää esim. luonnolle aiheutuvien haittojen määrittelemisen yhteydessä.
Yleensä optimaalisen polun löytäminen tapahtuu askeleittain niin että yksi askel käsittää aina vierekkäisiä soluja:
tai
Least Accumulative Cost - analyysi Optimaalisen polun löytämisessä perusmenetelmiin kuuluu ns. Least Accumulative Cost – analyysi. Analyysin tuloksena voidaan tuottaa ainakin kolme eri rasteria:
Least Accumulative Cost – rasteri
suunta-rasteri (osoittaa optimaalisen polun sunnan jokaisesta solusta )
allokaatio-rasteri (jakaa alueen lähdepisteiden välillä optimaalisen polun mukaan)
Esimerkki!
Todellisuudessa polun kustannus on usein anisotrooppinen (kustannus eri suunnissa kulkemiseen on erilainen).
Polun kustannusten laskemisessa käytetään lisäksi seuraavia määritelmiä:
etäisyys pinnan mukaan
pystysuuntainen komponentti (vertical factor)
vaakasuuntainen komponentti (horizontal factor)
Verkosto Verkosto koostuu vektorimuotoisista komponenteista. Esimerkkejä verkostoista ovat
tieverkosto
jokiverkosto
julkisen liikenteen verkosto
Verkosto perustuu topologiaan, esimerkiksi:
verkoston viivat kohtaavat risteysalueilla
viivoissa ei saa olla ’aukkoja’
viivoilla on suunta
Tieverkosto: linkki, liittymä, käännösimpedanssi Tieverkosto koostuu linkeistä (link), joille on määritelty impedanssi (=vastus, kustannus). Impedanssi voi määräytyä yksinomaan linkin pituudella. Hyödyllisempi impedanssin mitta on kuitenkin linkin päästä päähän kulkemiseen tarvittava aika. Aika voi vaihdella riippuen kulkemisen suunnasta tai kellonajasta.
Linkkien risteyskohdissa on määritelty liittymä (junction). Liittymää kuvaa sen käännösimpedanssi (turn impedance), joka kertoo, kuinka paljon aikaa kyseisellä liittymällä kääntyminen er isuuntiin vie. Käännösimpedanssi riippuu usein käännöksen suunnasta, jolloin sen kuvaamiseen tarvitaan käännöstaulukko (turn table).
Esimerkiksi 4-suuntaisessa risteyksessä mahdollisia käännöksiä on yhteensä 12 (ellei lasketa U-käännöksiä). Käännöstaulukko sisältää rivin jokaista mahdollista käännöstä kohtaan.
Tieverkosto: sovelluksia Tieverkostoon merkitään myös tieto yksisuuntaisista ja suljetuista teistä.
Tieverkoston luominen käsittää:
verkoston osia kuvaavien piirteiden syöttämistä paikkatietojärjestelmään
topologian määrittäminen
ominaisuustiedon määrittäminen (esim. yksisuuntaisuus, nopeusrajoitukset, kulkuaika, käännöstaulukot)
Tärkeimpiä tieverkoston sovelluksia on nopeimman reitin analyysi. Yksi vaihtoehto siihen on aikaisemmin esitelty Least Accumulative Cost – menetelmä
Esimerkki!
Tunnettu kauppamatkustajan ongelma on erikoistapaus nopeimman reitin analyysistä, jossa 1) kauppamatkustajan on kuljettava läpi kaikkien solmujen 2) kauppamatkustaja voi aloittaa mistä solmusta tahansa mutta hänen täytyy lopulta palata samaan solmuun
Allokaatio Nopeimman reitin analyysin eräs sovellus on ns. lähimmän palvelupisteen löytämisen ongelma. Ongelma voidaan ratkaista euklidisen etäisyyden mukaan, mutta realistisempi tulos saadaan käyttäen verkosto-analyysiä.
Allokaatio-ongelma koskee esim. alueen jakamista palvelujen saantinopeuden mukaan (esim. kaupungin alueen jakaminen paloasemien välillä vasteajan perusteella). Jos tässä yhteydessä palvelujen saatavuutta täytyy parantaa, voidaan verkosto-analyysin avulla löytää uusille palvelupisteille optimaaliset sijainnit. Tätä ongelmaa kutsutaan location-allocation – ongelmaksi.
Location-allocation ongelma Location-allocation – ongelman ratkaisemisessa tarvitaan tieto:
tarjonnasta
kysynnästä
etäisyysmitasta
Tunnetuimpia algoritmeja ongelman ratkaisemiseksi ovat:
minimietäisyys-algoritmi (minimum distance model); minimoi kokonaismatkan kaikista kysyntäpisteistä lähimpään palvelupisteeseen
parhaan kattavuuden algoritmi (maximum covering model); maksimoi palvelualueeseen jäävien asiakkaiden määrän tietyn etäisyyden tai vasteajan puitteissa
Lisäksi voidaan määritellä ehtoja kuten esimerkiksi suurin sallittu etäisyys minimietäisyys-algoritmin yhteydessä.
Usein asiakkaiden määrä on liian suuri käsitelläkseen niitä erikseen; tällöin asiakkaiden sijainniksi voidaan märitellä esim. korttelien keskipisteet ja liittää siihen ominaisuustietona kunkin korttelin aiakasnmäärän
Comments