Ajoneuvoreititysongelman analysointi ja ratkaiseminen geneettisellä algoritmilla

Abstract

Tässä diplomityössä analysoidaan ja ratkaistaan ajoneuvoreititysongelma, joka on operaatiotutkimuksessa sekä logistiikka-alalla hyvin tunnettu kombinatorinen optimointiongelma. Ajoneuvoja lähetetään varastosta palvelemaan asiakkaita, ja kun tämä on tehty, ne palaavat varastoon. Tavoitteena on minimoida ajoneuvojen tuottamat matkakustannukset. Ajoneuvoreititysongelma muuttuu kauppamatkustajan ongelmaksi, jos ajoneuvoja on vain yksi.

Ajoneuvoreititysongelmasta on esitetty erilaisia laajennuksia, jotka soveltuvat käytännöllisiin tilanteisiin paremmin. Laajennuksista valitaan tutkittavaksi ne, jotka käsittelevät kapasiteetteja, reittien avoimuutta, tuottoja, useampia varastoja ja aikaikkunoita.

Ajoneuvoreititysongelman ja sen valittujen laajennusten käsittelyä varten sovelletaan geneettistä algoritmia, joka kehittää ratkaisuja sisältävää populaatiota luonnonvalinnan sääntöjä noudattaen. Sitä muokataan siten, että se soveltuu ajoneuvoreititysongelmalle sekä valituille laajennuksille. Lisäksi erilaisia algoritmeja tutkitaan ja valitaan hybridisoitavaksi geneettisen algoritmin eri vaiheisiin, joita ovat populaation alustus, yksilöiden valinta, risteytys ja mutaatio. Hybridisaatioiden avulla pyritään parantamaan geneettisen algoritmin suorituskykyä.

Kun geneettinen algoritmi on suunniteltu, sen toimivuutta ja tehokkuutta testataan erilaisin aineistoin. Ensimmäisenä sitä testataan yksinkertaisella esimerkkitapauksella puhtaasti toimivuuden kannalta. Seuraavaksi tutkitaan sen tehokkuutta ratkaisemalla muissa tutkimuksissa käytettyjä suorituskykytestejä, joissa suurimmalla osalla tunnetut ratkaisut ovat saatavilla. Lopuksi geneettisellä algoritmilla yritetään ratkaista kuljetusyhtiön tarjoama anonymisoitu testitapaus.

Tulokset käytetyistä aineistoista osoittavat, että esitetty algoritmi on toimivuuden kannalta kunnossa. Laajuudeltaan pienien ongelmien tapauksessa se löytää ratkaisuja, jotka ovat hyvin lähellä tunnettuja ratkaisuja. Suurissa ongelmissa hyvän ratkaisun löytäminen osoittautuu aikaavieväksi. Lisäksi havaitaan, että toinen metaheuristinen algoritmi suoriutuu paremmin kuin esitetty algoritmi, minkä vuoksi todetaan, että ongelma on esitetyn algoritmin ja sen toteutuksen huonossa suunnittelussa. Tästä seuraaviksi toimenpiteiksi ehdotetaan ajoneuvoreititysongelman yhteen laajennukseen erikoistumista, risteytys- ja mutaatio-operaattoreiden parantamista sekä muuttuvan ajoneuvolukumäärän käyttöä vakiolukumäärän sijaan.