Puutavaran metsäkuljetuksen optimointi
Juntunen, Teijo (2018)
2018
Automaatiotekniikka
Teknisten tieteiden tiedekunta - Faculty of Engineering Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2018-11-07
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tty-201810032388
https://urn.fi/URN:NBN:fi:tty-201810032388
Tiivistelmä
Kun hakkuukone on käynyt kaatamassa leimikolta puita pinoiksi, on seuraavaksi kuormatraktorin tehtävänä kerätä kyseiset pinot mahdollisimman tehokkaasti purkutien varteen purkulavoille jatkokuljetusta varten. Keruu tapahtuu harvesterin työskennellessä syntynyttä ajouraverkostoa pitkin. Tieto pinojen sijainnista ja ajourista tallennetaan GPS-paikannuksen avulla harvesterin työskentelydatasta. Tällä hetkellä metsätraktorin kuljettaja tekee keräyssuunnitelman kokemukseensa, koulutukseensa ja lahjakkuuteensa perustuen. Tämä aiheuttaa huomattavaa kuskien välistä vaihtelua keräyksen tehokkuudessa.
Tämän työn tarkoituksena oli luoda optimointialgoritmi, joka muodostaisi hyvän keräyssuunnitelman kuormatraktorinkuljettajan puolesta. Yhdessä metsäkonevalmistaja Ponsse oyj:n asiantuntijoiden kanssa luotiin vaatimusmäärittely, jonka mukaisesti algoritmin tulisi toimia. Tämän mukaan haluttiin, että osa algoritmille syötettävistä ajouraverkoston ajourista tulisi pystyä merkitsemään yksisuuntaisiksi. Myös ajourasegmenttien maksimiajokerrat täytyisi voida syöttää algoritmille ennen laskentaa. Laskenta-ajan haluttiin olevan alle 60 minuuttia.
Koska tehtävä on NP-vaikea kompleksisuusluokkaan kuuluvana mahdoton ratkaista täysin optimaalisesti, päätettiin optimoinnissa käyttää toistuvien sovitusten metaheuristiikkaa. Ensin muodostettiin GPS-datan perusteella suunnattu ja kustannuksilla painotettukarttagraafi, joka toimi herätteenä suunnitellulle optimointialgoritmille. Alustavaa ratkaisua lähdettiin parantamaan iteratiivisesti yhdistämällä edellisen ratkaisun reittejä toisiinsa. Yhdistäminen tapahtui joko liittämällä kahden reitin pinot toisiinsa satunnaisessa järjestyksessä tai vaihtamalla 1 -3 pinoa kahden edellisen ratkaisun reitin välillä. Jos kumpikaan näistä parituksista ei ollut kustannuksellisesti tehokkaampi kuin aikaisemman ratkaisun reittien yhteiskustannus, merkittiin aikaisemman iteraation yhteiskustannus parituskustannukseksi. Näin syntyneestä sovituskustannusgraafista muodostetaan kaikki mahdolliset täydelliset sovitukset, joista etsitään halvin sovitus. Ratkaisun päätyessä lopulta johonkin ääriarvoon, puretaan satunnaisesti yksi tai useampia reittejä yksittäisiä pinoja sisältäviksi reiteiksi ja jatketaan optimointia.
Suunniteltua toistuvien sovitusten menetelmään perustuvaa algoritmia käytettiin ratkaisemaan Ponsse Forwarder Game:n pelikartan reititysongelmaa. Kyseistä karttaa oli käytetty ”Taitaja 2014” -kilpailussa metsäkoneenkuljettajaopiskelijoiden reittisuunnittelukyvyn arvioimiseen. Algoritmin suoritusta verrattiin yhdeksän Taitaja-kilpailun finalistin suorituksiin. Algoritmi suoriutui tuotoksella mitattuna keskitasoisesti, vaikka ajourarajoitettujen reittiosuuksien yhdistämisessä tehtävään oli tulosten perusteella havaittavissa puutteita.
Tämän työn tarkoituksena oli luoda optimointialgoritmi, joka muodostaisi hyvän keräyssuunnitelman kuormatraktorinkuljettajan puolesta. Yhdessä metsäkonevalmistaja Ponsse oyj:n asiantuntijoiden kanssa luotiin vaatimusmäärittely, jonka mukaisesti algoritmin tulisi toimia. Tämän mukaan haluttiin, että osa algoritmille syötettävistä ajouraverkoston ajourista tulisi pystyä merkitsemään yksisuuntaisiksi. Myös ajourasegmenttien maksimiajokerrat täytyisi voida syöttää algoritmille ennen laskentaa. Laskenta-ajan haluttiin olevan alle 60 minuuttia.
Koska tehtävä on NP-vaikea kompleksisuusluokkaan kuuluvana mahdoton ratkaista täysin optimaalisesti, päätettiin optimoinnissa käyttää toistuvien sovitusten metaheuristiikkaa. Ensin muodostettiin GPS-datan perusteella suunnattu ja kustannuksilla painotettukarttagraafi, joka toimi herätteenä suunnitellulle optimointialgoritmille. Alustavaa ratkaisua lähdettiin parantamaan iteratiivisesti yhdistämällä edellisen ratkaisun reittejä toisiinsa. Yhdistäminen tapahtui joko liittämällä kahden reitin pinot toisiinsa satunnaisessa järjestyksessä tai vaihtamalla 1 -3 pinoa kahden edellisen ratkaisun reitin välillä. Jos kumpikaan näistä parituksista ei ollut kustannuksellisesti tehokkaampi kuin aikaisemman ratkaisun reittien yhteiskustannus, merkittiin aikaisemman iteraation yhteiskustannus parituskustannukseksi. Näin syntyneestä sovituskustannusgraafista muodostetaan kaikki mahdolliset täydelliset sovitukset, joista etsitään halvin sovitus. Ratkaisun päätyessä lopulta johonkin ääriarvoon, puretaan satunnaisesti yksi tai useampia reittejä yksittäisiä pinoja sisältäviksi reiteiksi ja jatketaan optimointia.
Suunniteltua toistuvien sovitusten menetelmään perustuvaa algoritmia käytettiin ratkaisemaan Ponsse Forwarder Game:n pelikartan reititysongelmaa. Kyseistä karttaa oli käytetty ”Taitaja 2014” -kilpailussa metsäkoneenkuljettajaopiskelijoiden reittisuunnittelukyvyn arvioimiseen. Algoritmin suoritusta verrattiin yhdeksän Taitaja-kilpailun finalistin suorituksiin. Algoritmi suoriutui tuotoksella mitattuna keskitasoisesti, vaikka ajourarajoitettujen reittiosuuksien yhdistämisessä tehtävään oli tulosten perusteella havaittavissa puutteita.