Kapasiteettirajoitettujen ajoneuvojen reititysongelma

Abstract

Tutkielmassa esitellään yleisesti kapasiteettirajoitettujen ajoneuvojen reititysongelma (CVRP). Tämä on kauppamatkustajan ongelman laajennus ja yksi tutkituimmista matemaattisen optimoinnin ongelmista. Ongelma muodostuu kapasiteettirajoitetuista ajoneuvoista, joiden reitit asiakkaille optimoidaan esimerkiksi niiden matkan tai kustannusten minimoimiseksi. Kapasiteettirajoitukset tarkoittavat mitä vain kuormallista rajoitetta. Näitä voivat olla esimerkiksi tilataksin matkustajamäärä, toimitettavien pakettien määrä tai kokonaistilavuus. Kapasiteettirajoitus voi koskea toimitusten enimmäiskuorman lisäksi myös sitä, kuinka paljon tavaraa voidaan noutaa asiakkailta. Oikean maailman ongelmiin liittyy usein kapasiteettirajoitusten lisäksi muita tehtäväkohtaisia rajoituksia, kuten ajoneuvojen määrä tai ajomatkan enimmäispituus. Ongelmalle on monta eri matemaattista mallinnustapaa. Tutkielmassa esitellään lineaarinen kokonaislukuohjelmointimalli, kolmen indeksin ajoneuvovirtausmalli ja ositusmalli. CVRPt ovat NP-vaikeita ongelmia, eli niiden täsmällisten ratkaisujen laskeminen on vaikeaa varsinkin suurilla asiakasmäärillä. Ongelman monimutkaisuuden takia suuri osa tutkimuksista on keskittynyt erilaisten tehokkaiden epätäsmällisten menetelmien kehittämiseen. Menetelmien tehokkuus on usein tapauskohtaista, ja niitä voidaan arvioida esimerkiksi vertailemalla tarvittavaa laskennallista tehoa tai ratkaisujen optimaalisuutta. Tutkielmassa tarkastellaan yleisesti eri menetelmätyyppejä ja tarkemmin yhtä heuristista asiakkaiden ryhmittelyyn perustuvaa menetelmää: Ryhmittele ensin, reititä sitten (CFRS). Menetelmä perustuu nimensä mukaisesti siihen, että ensin ryhmitellään joukko asiakkaita eri ryppäisiin, minkä jälkeen optimoidaan ryppäiden asiakkaille ajoneuvojen toimitusreitit. Ryhmittelyn tarkoituksena on vähentää tarvittavien muuttujien määrää CVRP:n ratkaisemiseksi. Menetelmä on osoittautunut erityisen tehokkaaksi laskenallisten kustannusten ja ratkaisujen optimaalisuuserojen testeissä pienissä 32–82 asiakaspisteen tapauksissa.