Ajoneuvojen reititysongelma

Abstract

Tässä tutkielmassa käsitellään yleistä ajoneuvojen reititysongelmaa, joka on yksi matemaattisen optimoinnin tutkituimmista ongelmista. Ajoneuvojen reititysongelmassa pitää palvella joukko asiakkaita jakeluautoilla, jotka lähtevät varastolta. Tämän lisäksi asiakkaat jaetaan jakeluautoille siten, että jokainen asiakas palvellaan tasan kerran. Tehtävässä minimoidaan jakeluautoille määrättyjen reittien yhteiskustannuksia. Tehtävänä ajoneuvojen reititysongelma on NP-vaikea eli sille tiedetään vain eksponentaalisen ajan vieviä algoritmeja. Lisäksi ongelmasta on olemassa monia erilaisia muunnoksia, kuten kapasiteetillinen, usean varaston sekä dynaaminenversio. Tässä työssä esitetään kaksi erilaista tapaa mallintaa yleinen ajoneuvojen reititysongelma. Lisäksi esitellään kaksi eri menetelmää ajoneuvojen reititysongelman ratkaisemiseksi. Ensimmäinen menetelmistä on säästävä algoritmi, jossa kaikki mahdolliset kahden asiakkaan asiakasparit listataan paremmuusjärjestykseen. Paremmuusjärjestys saadaan sen perusteella, minkä verran muodostuu säästöä kahden asiakkaan yhdistämisestä samalle reitille. Säästävästä algoritmista on olemassa kaksi eri versiota: rinnakkain ja peräkkäin tehty reitin muodostus. Rinnakkaisella tavalla voidaan muodostaa usempi reitti samanaikaisesti, kun taas peräkkäisellä versiolla reitit muodostetaan yksi kerrallaan. Työssä esitellään molemmat tavat. Peräkkäisellä tavalla saadaan usein parempi ratkaisu, minkä lisäksi se on yleensä tehokkaampi tapa muodostaa ratkaisu useammalle asiakkaalle. Toinen työssä esiteltävä algoritmi on pyyhkäisy algoritmi. Siinä kaikki asiakkaat listataan ensin napakoordinaattien mukaan listaan, jota hyödyntäen määrätään asiakkaat jakeluautoille. Jokaisen jakeluauton reittiä parannetaan lopuksi vielä 2-optimaalisella haulla.