Parhaimmassa tapauksessa reittioptimoinnilla kyetään vastaamaan jokaiseen otsikossa esitetyistä kysymyksistä. Tässä blogissa pääset tutustumaan niin reittioptimoinnin, mallinnuksen, graafien, QGISin, PostGISin, CPLEXin kuin yleisen (ohjelmointi)logiikankin maailmoihin – lukuiloa!

Johdanto

Matemaattista optimointia voi osuvimmin kuvata parhaan ratkaisun etsimiseksi olemassaolevien vaihtoehtojen joukosta. Tyypillisesti etsitään sellaista ratkaisua, joka minimoi / maksimoi kohdefunktioksi kutsuttavan, vaihtoehtojen paremmuutta vertaavan kriteerin arvon. Optimoitavaa suuretta kutsutaan päätösmuuttujaksi. Päätösmuuttujien arvoja muuttamalla pyritään saavuttamaan mahdollisimman hyvin asetetun optimointiongelman tavoitteet. Optimointiongelman tavoitetta kutsutaan kohdefunktioksi. Kohdefunktiot koostuvat päätösmuuttujista, parametreista, vakioista sekä niiden välisistä relaatioista. Parametrien voidaan ajatella kuvaavan kyseessä olevan systeemin ominaisuuksia. Vakiot puolestaan voidaan nähdä parametreja muuttumattomampina, universaaleina ominaisuuksina.

Optimointimallia muodostettaessa tulee ottaa kohdefunktion lisäksi huomioon myös päätöksiä rajoittavat ehdot. Tällaisia ehtoja kutsutaan rajoitteiksi. Usein malleihin liittyy luonnollisia rajarajoitteita, jotka aiheutuvat päätösmuuttujalla kuvattavan suureen ominaisuuksista. Jos esimerkiksi yritetään minimoida aikaa, joka romaanin kirjoittamiseen tulee kulumaan, päivässä käytettävien työtuntien määrää kuvaavalle päätösmuuttujalle x täytyy asettaa alaraja x ≥ 0. Vuorokaudessa ei nimittäin ole mahdollista työskennellä negatiivista määrää tunteja. Rajoitefunktioiden avulla voidaan kuvata monimutkaisempia rajoitteita. Esimerkkinä tällaisesta voisi toimia vaikkapa rajoite, joka vaatii, että jokaista vuorokaudessa työskenneltävää kolmea tuntia kohti täytyy pitää yksi kahvitunti, nukkumiseen täytyy varata ainakin kuusi tuntia, ja näiden kolmen päätösmuuttujan summa ei saa ylittää 24 tuntia. Kahvitunnin pitämisestä ja nukkumisesta saatava hyöty voidaan kuvata kohdefunktiossa päätösmuuttujien välisenä relaationa. Kyseiseen relaatioon voi liittyä sekä parametrejä että vakioita, joiden avulla pystytään kuvaamaan monimutkaisempia vuorovaikutussuhteita.

Merkitään symbolilla N optimointimalliin liittyvien päätösmuuttujien lukumäärää. Mikäli päätösmuuttujien arvoista koostuva N-ulotteinen vektori toteuttaa kaikki optimointimallin rajoitteet, ollaan löydetty sallittu ratkaisu. Minimointi-tyyppisen optimointiongelman optimaaliseksi ratkaisuksi kutsutaan sellaista sallittua pistettä, jossa kohdefunktio saa pienimmän arvonsa.

Reittioptimointi on eräs optimoinnin alakategorioista. Reittioptimointi voidaan nähdä tieteenalana, jonka tavoitteena on löytää systemaattisia tapoja tunnistaa nopein / kustannustehokkain tapa järjestää jonkin resurssin kuljetus. Reittioptimoinnin keinoin voidaan reititysratkaisujen etsimisen lisäksi pyrkiä vastaamaan myös laajempiin yritysmaailman tavoitteisiin (esim. parantamaan asiakastyytyväisyyttä, vähentämään toiminnan kustannuksia tai optimoimaan työsuunnittelua). Yksi perinteisimmistä reittioptimoinnin ongelmista on Kauppamatkustajan ongelma (Travellling Salesman Problem), jossa tavoitteena on löytää pienimmän kustannuksen omaava reitti, joka kulkee usean kaupungin / kohteen kautta ja palaa takaisin lähtöpisteen [4]. Tässä blogissa tulemme kuitenkin etsimään vastausta hieman erityyppiseen reittioptimointi-ongelmaan, jota pääsimme tutkimaan yhteistyössä Tampereen Infra Oy:n kanssa.

Aurausongelman mallinnus

Toteutuneen hankkeen aikana tutkittiin monia tapoja mallintaa aura-auton ajoreitin valitsemiseen liittyvää problematiikkaa. Reittioptimointi yhdessä mielessä hyvin erityinen analysointitapa; on aivan samantekevää onko meillä käytettävissä aineistoa esimerkiksi aura-autojen liikkeistä. Sillä, miten asia on tavattu tehdä, ei ole juurikaan vaikutusta siihen, miten se oikeasti kannattaisi tehdä. Tässä työssä hyödynnettiin lähtöaineistoina ainoastaan Digiroadin tarjoamaa tieverkostodataa, tarkasteltavan alueen määrittävää aluerajausta ja tietoa kunnossapitoajoneuvojen varikon sijainnista. Haasteelliseksi optimoinnin tekee se, että tutkittava ilmiö onnistutaan mallintamaan realistisesti. Optimointi on aina tasapainoilua kehitetyn mallin validiteetin ja ratkeavuuden välillä.

Ihan ensimmäiseksi muokkasimme Digiroadin tieverkkoaineiston sellaiseen muotoon, jonka päälle pystytään rakentamaan matemaattinen ongelmanmuotoilu. Toisin sanoen loimme PostGIS:n avulla todellisesta tieverkosta topologisesti ehjän graafin. Graafi on verkosto, joka koostuu solmuista (kuvaavat tässä tapauksessa teiden risteyksiä) ja niitä yhdistävistä kaarista (vastaavat teitä). Graafit jaotellaan luokkiin niiden ominaisuuksien mukaan. Tärkeimmät graafeja määrittävät ominaisuudet liittyvät siihen, onko graafi suunnattu (jokaiseen kaareen liittyy suuntatieto → yksi lähtösolmu, yksi päätesolmu), kytketty (jokaiselle solmuparille (a,b) on olemassa yhtenäinen polku solmusta a solmuun b) tai painotettu (jokaiseen kaareen liittyy painokerroin, yksinkertaisimmillaan kaaren pituus).

Tavanomaisimmat graafiteorian mallit, kuten aiemmin mainittu kauppamatkustajaongelma, perustuvat ajatukselle, että tavoitteena on käydä jokaisessa graafin solmussa. Tämä tavoite ei kuitenkaan sovellu kunnossapidon tavoitteisiin, sillä solmuissa käymisen sijaan tavoitteena on kulkea jokainen kaari. Käsillä olevan ongelman mallintamiseen soveltui paremmin Chinese Postman Problem (CPP), jonka periaatteet voidaan tiivistää seuraavasti:

• Postimiehen tavoitteena on jakaa kaikki alueen postit kulkien mahdollisimman lyhyttä reittiä
• Kyetäkseen tekemään tämän, hänen tulee kulkea jokainen tienpätkä vähintään kertaalleen ja palata sen jälkeen lähtöpisteeseen
• Mikäli CPP saadaan ratkaistua, tuloksena saatua polkua voidaan pitää optimaalisena tapana kiertää tieverkosto (turhien ajokilometrien määrä minimoituu)

Yllä esitellyssä CPP-muotoilussa on kuitenkin yksi iso ongelma, joka asettaa koko mallin validiteetin kyseenalaiseksi: siinä kaikki tiet ymmärretään samanlaisiksi, kahta risteystä yhdistäväksi suuntaamattomaksi kaareksi. Toisin sanoen, perus-CPP:n avulla ei ole mahdollista ottaa huomioon ajosuuntaa ja sitä, että on olemassa sekä yksisuuntaisia että kaksisuuntaisia teitä. Siksipä hankkeessa kehitettiinkin muokattu versio CPP kokonaislukuoptimointiongelmasta, jonka periaatteet voidaan tiivistää seuraavasti:

1. Minimoidaan kuljettavaa matkaa
2. Jokaiseen tienpätkään liittyy yksi kokonaislukumuuttuja, joka kuvaa montako kertaa kyseinen tiepätkä optimaalisessa ratkaisussa kannattaisi ajaa
3. Jokainen kaksisuuntainen tie tulee kulkea kuhunkin suuntaan vähintään kertaalleen
4. Jokainen yksisuuntainen tie tulee kulkea sallittuun kulkusuuntaan vähintään kahdesti
5. Aura-auton tulee lähteä varikolta ja optimaalisen reitin tulee päättyä varikolle
6. Ratkaisuna saatavan optimaalisen polun tulee olla topologisesti ehjä (jokaisessa tieverkon risteyskohdassa tulee olla tasapainoehto voimassa)

Aurausongelman muodostus

Ongelman ratkaisuprosessi sisälsi seuraavat vaiheet:

1. Aineiston esikäsittely QGISillä

• Leikkaa Digiroad-aineistoa (DR_LINKKI_K) tutkittavan alueen määrittävällä aluerajauksella
• Muokkaa tarvittaessa aluerajauksen reunoja siten, ettei se katkaise yhtään tiesegmenttiä “keskeltä”
• Luo uusi tiesegmentti lähtöpisteestä lähimpään tiehen (jos sitä ei ole vielä olemassa)
• Tarkista, ettei leikkauksen tuloksena saatu verkosto sisällä multiedgejä (tilanne, jossa samaa pisteparia yhdistä kaksi eri tiesegmenttiä). Käytännössä tällainen tilanne voi muodostua “kaariteiden” yhteydessä
• Tarkista, ettei yksisuuntaisia teitä ole verkoston reunoilla (ulos alueelta / sisään alueelle), koska siellä ei tällöin voitaisi käydä kääntymässä → mahdotonta löytää topologisesti ehjää aurauspolkua

2. Graafin muodostaminen PostGISin pg_routing-laajennuksen avulla

• Luo PostGISiin tietokantaklusteri ja tietokanta (esim. pgAdminilla), jonne voit viedä tarkastelualueen tieverkoston

CREATE EXTENSION postgis;
CREATE EXTENSION pgrouting;
CREATE SCHEMA reititys;

• Vie esikäsitelty tieaineisto PostGISiin

ogr2ogr -update -append -a_srs EPSG:3067 -nlt LINESTRING -lco GEOMETRY_NAME=geom -lco FID=id -lco SCHEMA=reititys -f PostgreSQL "PG:host= port= user= dbname= password=" -nln reititys.tietPgis tietQgis.gpkg

3. Tiedon jalostaminen

ALTER TABLE reititys.tietPgis
ALTER COLUMN geom TYPE geometry(LineString,3067)
USING ST_Force2D(geom);
ALTER TABLE reititys.tietPgis
ADD COLUMN source integer;
ALTER TABLE reititys.tietPgis
ADD COLUMN target integer;
SELECT pgr_createTopology('reititys.tietPgis',0.0001,'geom','id');
ALTER TABLE reititys.tietPgis
ADD COLUMN pituus float;
UDATE reititys.tietPgis
SET pituus = ST_Length(geom);

• Luodaan uusi PostGIS-taulu, johon tallennetaan vain tarvittavat tiedot tienpätkistä

CREATE TABLE reititys.tiet(
id BIGSERIAL,
ajosuunta BIGINT,
source BIGINT,
target BIGINT,
pituus FLOAT,
geom text,
temp1 BIGINT,
temp2 BIGINT);

INSERT INTO reititys.tiet(
id, ajosuunta, source, target, pituus, geom, temp1,temp2)
select id, ajosuunta, source, target, pituus, ST_AsText(geom), source, target
from reititys.tietPgis;

• Lisätään tauluun sarake, joka sisältää tiedon siitä, mihin tiesegmenttiin kukin tienpätkä liittyy

ALTER TABLE reititys.tiet
ADD COLUMN tieid float;
UPDATE reititys.tiet
SET tieid = id;

• Lisätään jokaista kaksisuuntaista kaarta kohti myös digitointisuunnan suhteen vastainen rivi

INSERT INTO reititys.tiet(
id, ajosuunta, source, target, pituus, geom, temp1, temp2, tieid)
select id+kaarien_lkm, ajosuunta, source, target, pituus, ST_AsText(geom), source, target, id
from reititys.tietPgis
where ajosuunta=2;

• Muokataan näille lisätyille riveille source ja target toisinpäin

UPDATE reititys.tiet
SET source = temp2,
target = temp1
where id > kaarien_lkm;

• Muokataan digitointisuunnan vastaisesti tallennettujen kaarien osalta source ja target tiedot oikein päin

UPDATE reititys.tiet
SET source = temp2,
target = temp1
where ajosuunta = 3;

• Korvataan ajosuunnat 3 / 4 arvolla 1, joka kertoo, että kyseessä on yksisuuntainen tie

UPDATE reititys.tiet
SET ajosuunta = 1
where ajosuunta = 3 or ajosuunta = 4;

• Viedään luodut tiedot pois PostGISista csv-tiedostoina psql avulla

\copy (select * from reititys.tiet order by id) TO '/tiet2.csv' CSV HEADER
\copy (select id, ST_AsText(the_geom) from reititys.tiet_vertices_pgr order by id) TO '/solmut.csv' CSV HEADER

4. Optimointiongelman muodostaminen

Edellisessä vaiheessa luodut csv-tiedostot pitävät sisällään kaiken tiedon, jota tarvitset optimointiongelman muodostamiseen (tiedon jokaisen tienpätkän lähtösolmusta, päätesolmusta ja painokertoimena toimivasta pituudesta).

Leluesimerkki:

minimize pituus1 x1+pituus2 x2+pituus3 x3+...+pituusN xN
subject to

• Solmusta A lähteviin tienpätkiin liittyvät päätösmuuttujat – solmuun A päättyviin tienpätkiin liittyvät päätösmuuttujat = 0:

x2-x1-x4=0
x1-x3=0
...
bounds

• Yksisuuntaiseen tiehen liittyville päätösmuuttujille:

x1<=2

• Kaksisuuntaiseen tiehen liittyville päätösmuuttujille:

x2<=1
x3<=1
...
xN<=1
integer
x1
...
xN
end

• Huomaa, että tasapainoehtoja (subject to -osio) tulee yksi jokaista graafin solmua kohti ja rajarajoitteita (bounds-osio) yksi kutakin graafin kaarta kohti
• Huomaa myös, että tässä leluesimerkissä pituus1=pituus2, sillä päätösmuuttujat x1 ja x2 ovat saman tien kaksi vastakkaissuuntaista pätkää
• Optimointiongelman muodostaminen kannattaa automatisoida esimerkiksi luomalla lyhyt python skripti, joka hyödyntää csv-tiedostojen sisältöjä ja kirjoittaa niiden pohjalta optimointiongelman formuloinnin leluesimerkin mukaisessa muodossa tekstitiedostoon
  • LP-tiedoston luomiseen liittyy omat avainsanansa ja oma syntaksinsa [2]
• Lopuksi tulostiedostosta (optongelma.txt) tulee ottaa kopio ja tallentaa se .lp-muodossa

Optimointiongelman ratkaiseminen

CPLEX on lineaaristen ja rajoitteellisten kokonaislukuoptimointiongelmien ratkaisemiseen soveltuva ohjelmisto. CPLEX-ohjelmisto on IBM ILOG:n akateemisiin tarkoituksiin avoimesti ladattavissa oleva optimointiohjelmistopaketti, joka koostuu algoritmeista, työkaluista ja rajapinnoista. Koska kokonaislukuoptimointitehtävien ratkaisemiseen ei ole olemassa yhtä ylivertaisen tehokasta algoritmia, CPLEX-ohjelmistokin sisältää useita vaihtoehtoisia optimointitekniikoita. Ohjelmisto osaa itse valita kuhunkin tilanteeseen parhaiten soveltuvan ratkaisumenetelmän. Kokonaislukumuuttujia sisältäviin optimointiongelmiin soveltuvia eksakteja (takaavat ratkaisun optimaalisuuden) menetelmiä ovat CPLEX-ohjelmiston optimoijista muun muassa Branch and Cut -menetelmä ja dynaamisen etsimisen menetelmä. CPLEX pystyy lukemaan ratkaistavana olevan optimointiongelman suoraan komentorivin kautta lp-tiedoston muodossa tallennetusta tekstitiedostosta:

read 

Itse optimointitehtävän ratkaisu onnistuu yhdellä käskyllä:

optimize

Optimaaliset päätösmuuttujan arvot saa näkyviin syöttämällä CPLEX:n komentoriville:

display solution variables *

• CPLEX on todella tehokas tämän tyyppisten ongelmien ratkaisemisessa; yli 900 päätösmuuttujan ongelman ratkaisemiseen meni alle puoli sekuntia

Ratkaisusta käy ilmi, että optimaalinen reitti, joka kulkee jokaisen tutkitun alueen tien kautta optimointiongelman rajoitteet täyttäen, on 58.9 kilometriä pitkä. Kyseessä on ehdoton alaraja sille, kuinka monta kilometriä vähintään täytyy ajaa, jotta alueen tiet saadaan käytyä läpi. Tätä alarajatietoa voi hyödyntää esimerkiksi arvioitaessa alueen läpikäymiseen varattavan polttoaineen tai sepelin määrää.

Kuvassa 1 on visualisoitu optimaalisen ratkaisun ajokerrat. Ensinnäkin on hieman yllättävää, että suurin osa kaksisuuntaisista teistä pystyttäisiin periaatteessa ajamaan vain kertaalleen molempiin suuntiin. Se taas on täysin odotettua, että yksisuuntaisia teitä ei kannata ajaa kuin minimimäärä eli kahdesti kulkusuuntaan (havainnollistettu nuolella). Mielenkiintoisin osa ratkaisua lienee se, että kuvasta nähdään mitä teitä pitkin kannattaa reitin kokonaismatkan minimoinnin kannalta kulkea ne pakolliset kierrokset, jotka välttämättä joudutaan suorittamaan, jotta verkoston jokainen kaksisuuntainen tie voidaan kulkea vähintään kerran molempiin suuntiin ja jokainen yksisuuntainen tie voidaan kulkea topologisesti ehjää reittiä pitkin vähintään kahdesti rikkomatta liikennesääntöjä.

Kiertojärjestyksen määrääminen optimaalisen ratkaisun pohjalta

Huolimatta siitä, että kokonaislukuoptimointiongelmaan on jo saatu määritettyä “ratkaisu”, emme silti vielä pysty vastaamaan otsikossa esitettyyn mistä, minne ja miten -kysymykseen. Pystyäksemme vastaamaan tähän kysymykseen, meidän on vielä selvitettävä missä järjestyksessä aura-auton tulee tieverkkoa kuvaavan graafin solmuissa käydä, jotta aura-auto pystyy lähtemään varikolta ja palaamaan sinne siten, että aura-auto on kulkenut läpi koko tieverkkoa vastaavan graafin ajamalla kutakin tienpätkää täsmälleen niin monta kertaa kuin CPLEXillä löydetty optimaalinen ratkaisu ohjeistaa.

Ajojärjestyksen määräämiseen kehitettiin toinen python skripti. Tämä python ohjelma tarvitsee kuitenkin toimiakseen huomattavan määrän valmiita “aliratkaisuja”. Python ohjelman logiikka on seuraava:

1. Hyödynnetään CPP ongelman ratkaisemiseen kehitettyä kokeellista QGIS pluginia Chinese Postman Solver
2. Tarkastellaan pluginin palauttamaa ratkaisua karttapohjalla ja jaetaan tarkasteltava verkosto alialueisiin sen mukaan, että jokainen alialue sisältää yhden yhtenäisen, pluginin palauttamassa ratkaisussa vain kertaalleen toiseen suuntaan kuljettavan polun, josta poiketaan muille teille vain edestakaisilla pistoilla
3. Tallennetaan alialueet omiksi karttatasoikseen ja valitaan “porttisolmut”, joiden kautta siirrytään alialueelta toiselle (tämä solmu voi olla mikä tahansa kahta alialuetta yhdistävä edestakaisen “pistotien”solmu) 

• Samalla tulee miettiä järkevä järjestys edetä alialueelta toiselle (tärkeää, että polku “sisimpään” alialueeseen kulkee kaikkien muiden alialueiden kautta)

4. Ratkaistaan CPP ongelma uudelleen jokaiselle alialueelle em. QGIS pluginin avulla

• Tuloksena saadaan lista tieverkoston solmujen ID:itä, joka määrittää optimaalisen kiertojärjestyksen alialueelle

5. Luodaan python skripti, joka noudattaa näitä alialueiden optimaalisia ratkaisupolkuja siihen asti, että kyseinen ratkaisupolku kulkee jonkin toisen alueen porttisolmun kautta → edetään suorittamaan seuraavan alialueen ratkaisupolkua
6. Edetään eteenpäin verkostossa aina siihen asti, että päädytään sisimmän alialueen yhtenäisen polun päähän

• Tämän jälkeen lähdetään peruuttamaan yhtenäistä polkua takaisin päin aina siihen asti kunnes palataan sisimmän alialueen porttisolmulle
• Porttisolmulle palaamisen jälkeen jatketaan toiseksi sisimmän alialueen optimaalisen ratkaisupolun suorittamista, kunnes päädytään kyseisen alialueen ratkaisupolun päähän → aletaan jälleen peruuttaa kohti toiseksi ja kolmanneksi sisimmän alialueen välistä porttisolmua
• Tällä logiikalla palaamme lopulta takaisin varikolle siten, että jokaista verkoston tienpätkää on kuljettu kertaalleen molempiin kulkusuuntiin

Kuten tarkkasilmäisimmät saattoivat huomatakin, edellä mainittu logiikka perustuu ajatukselle, että jokaista tietä tulisi kulkea tasan kerran molempiin suuntiin. Jo pelkästään ongelmanmuotoilu (yksisuuntaisten teiden huomioonottaminen) määrittää, ettei tällaista oletusta voida tehdä. Lisäksi tiedämme CPLEXin tuottaman ratkaisun perusteella, että osaa kaksisuuntaisista teistä joudutaan ajamaan useamman kerran toiseen kulkusuuntaan. Syy, miksi voimme hyödyntää kiertojärjestyksen määräämisessä yllä kuvatun kaltaista logiikkaa on se, että eristimme tieverkostograafista ensin ne tienpätkät, joille ei päde se, että optimaalisessa ratkaisussa ko. tiesegmentti tulisi ajaa täsmälleen kerran molempiin kulkusuuntiin.

Tästä saatiin ensimmäinen alialue, jonka optimaalinen kiertojärjestys määrättiin manuaalisesti karttapohjaa katsomalla ja miettimällä minne seuraavaksi etenemällä pystyn kiertämään kaikki tiet täsmälleen niin monesti kuin optimaalinen ratkaisu ohjeistaa. Myös tälle “looppialueelle” määritettiin porttisolmu vastaavalla tavalla kuin muille alialueille, ja python skriptin näkökulmasta se oli samanlainen alialue kuin kaikki muutkin. Ainoa ero on se, että looppialueen ratkaisupolun tuottamiseen ei voitu hyödyntää QGIS pluginia, vaan se määritettiin loogisen päättelyn avulla.

Prosessiputken rakentamisen kannalta oli keskeistä oivaltaa, että looppialue kannattaa eristää ja että sille voidaan loogisesti päätellä järkevä kiertojärjestys. Ensinnäkin tämä mahdollisti kiertojärjestyksen ongelman redusoitumisen sen kokoiseksi, että ihmisaivot pystyivät looppialueen ratkaisujärjestyksen määrittämään. Toisekseen tällä tavalla saimme ensiarvoisen tärkeää tietoa siitä, miten moni asia vaikuttaa kiertojärjestyksen määräytymiseen. Kolmanneksi saimme muun tutkimusalueen muovattua sellaiseen muotoon, joka on hyvin lähellä perus-CPP:n ongelmanmuotoilua. Toki me tiesimme CPLEXin ratkaisun perusteella jo, että jokainen tie tulisi kulkea edestakaisin ja tätä ei perus-CPP:ssä vaadita. Kuitenkin, perus-CPP:ssä vaaditaan, että jokainen tie kuljetaan läpi ainakin kertaalleen. Todennäköisesti siis pystyisimme pluginilla tuottamaan sellaisen ratkaisun tälle verkoston loppuosalle, josta saisimme selville jotain hyödyllistä. Osa teistä varmasti tulisi pluginin ratkaisussa käytyä edestakaisesti, jolloin ratkaisu olisi näiden osalta jo valmis. Ja vaikka osa teistä käytäisiin vain kertaalleen läpi, eikö olisi mahdollista kulkea tällainen yhtenäinen polku (matkalle osuvissa “pussinperissä” poiketen) aluesta loppuun asti ja peruuttaa sitten takaisin, jolloin kaikki tiet tulisi ajettua täsmälleen kerran molempiin kulkusuuntiin?

Suoritettuani pluginin koko “ykkösverkostolle” (koko verkosto – looppialue), havaitsin, että saatu ratkaisu oli pitkälti toivomani kaltainen. Ainoana isona ongelmana näytti olevan se, ettei tällaista yhtä yhtenäistä yhden kulkusuunnan polkua näyttänyt muodostuvan, vaan niitä oli muodostunut useita ympäri ykkösverkostoa. Niinpä päätin rajata ykkösverkoston alialueisiin sen mukaan, että jokainen alialue sisältää täsmälleen yhden tällaisen yhtenäisen yhteen suuntaan pluginin ratkaisussa kuljettavan polun + kasan pussinperäksi luokiteltavia visiittejä sivuteille. Tarve uuden alialueen muodostamiselle syntyi siis aina, kun yhtenäinen polku katkesi tiellä, joka pluginin ratkaisussa haluttiin ajaa edestakaisin.

Python skriptiin ohjelmoitiin myös tarkistusproseduuri siltä varalta, ettei plugin ole kaikilta osin tehnyt samoja valintoja kuin CPLEXillä tuotettu optimaalinen ratkaisu edellyttäisi. Jos näin on, joitakin tienpätkiä jää kulkematta. Tällaiset tilanteet ratkottiin manuaalisesti katsomalla karttapohjasta, että tässä kohtaa ollaan toisen kerran käytetty samaa kaarta, mutta samat solmut voi yhdistää myös kiertämällä useampia solmuja pitkin (nämä ovat juuri niitä solmuja, jotka ovat jääneet kulkematta). Kaiken kaikkiaan voisi sanoa, että osittamalla ongelma järkevällä tavalla alialueisiin, päästiin niin lähelle, että perus-CPP:n ratkaisemiseen kykenevää QGIS pluginia hyödyntämällä pystyttiin päättelemään loput ja löytämään kiertojärjestys, joka noudattaa täsmälleen CPLEXillä määrätyn optimaalisen ratkaisun ajokertoja.

Lopputulos

On ilmeistä, että skaalautuvuus on kehitetyn prosessiputken haaste. Tieverkoston graafin rakentaminen ja optimointiongelman ratkaiseminen on nopeaa, kiertojärjestyksen määrääminen taas monilta osin manuaalista ja virhealtista. Hyvä puoli kehitetyssä menetelmässä on, että se mallintaa ongelman realistisesti, löydetyn ratkaisun optimaalisuus on taattu ja ratkaisu on otettavissa käyttöön sellaisenaan. Ratkaisu määrittää suoran toimintaohjeen, joka on validi niin pitkään, kun tieverkkoon ei tule muutoksia.

Alla olevista videoista näet, miten Tampereen Pispalan kadut kannattaisi aurata. Ratkaisusta käy ilmi, että toteuttamalla reittioptimointi edellä kuvatun prosessiputken kautta on mahdollista vastata kysymykseen, miten jonkin alueen tiet kannattaisi ajaa läpi, jos halutaan minimoida aura-auton ajamaan kokonaismatkaa. Tavoite ajoreitin kokonaispituuden minimoinnista on perusteltu, sillä tällöin ajoaika ja sitä kautta ilmakehään päätyvät päästötkin minimoituvat.

Valitettavasti projektin aikana tuotettua tulosta ei voitu suoraan ottaa käyttöön. Digiroad-aineiston sisältövirheiden vuoksi muutama portaikko oli digitoitu teiksi, joita pitkin optimaaliset aurauspolutkin sitten kulkivat. Huolimatta harmittavasta takaiskusta, projektissa onnistuttiin luomaan prosessiputki, jonka avulla todellisesta tieverkosta (virheineen) voidaan luoda graafi, jolle voidaan luoda muokattu reaalimaailman ongelmaa todenmukaisesti mallintava optimointiongelma, joka kyetään ratkaisemaan ja jonka ratkaisu kyetään muuntamaan niin suoraksi toimintaohjeeksi, että siitä voidaan muutamassa minuutissa nähdä, mitä ratkaisu käytännössä ehdottaa. Valitettavasti virheellisyydetkin ovat tällöin helpommin tunnistettavissa kuin kokonaislukuoptimointiongelmaa minimoivaan tulosvektoriin piilotettuina arvoina.

Lisäksi, taisin näyttää tässä projektissa todeksi eräässä toisessa blogissa näkemäni hieman maagisen määritelmän reittioptimoinnille. Jos optimoimalla voi saada aurat lentämään portaiden yli niin maybe there really is some magic in the air?

Lähteet

[1] P. Mäkinen: Ambulanssien optimaaliseen sijoittamiseen ohjaava monitavoitemalli. Pro gradu -tutkielma, Turun yliopisto, 2018.

[2] IBM Knowledge Center: Using the LP format. https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.6.1/ilog.odms.cplex.help/CPLEX/GettingStarted/topics/tutorials/InteractiveOptimizer/usingLPformat.html

[3] M. P.L. Haslbeck: Algorithms for the Mixed Chinese Postman Problem. Final Report for an Interdisciplinary Project, Technische Universität Munchen, 2015.

[4] Informaatiota Travelling Salesman Problem historiasta, sovelluksista ja ajankohtaisista aiheeseen liittyvistä tutkimuksista:

http://www.math.uwaterloo.ca/tsp/index.html

Gispo

Gispo on suomalainen avoimen lähdekoodin paikkatietotalo, jonka palveluihin kuuluu paikkatietokonsultointia, sovelluskehitystä, koulutusta sekä ylläpitoa ja tukea.