Kapasiteettirajoitettujen ajoneuvojen reititysongelma

Tietueen suppeat tiedot
dc.contributor.authorKauppi, Henrik
dc.contributor.departmentfi=Matematiikan ja tilastotieteen laitos|en=Department of Mathematics and Statistics|
dc.contributor.facultyfi=Matemaattis-luonnontieteellinen tiedekunta|en=Faculty of Science|
dc.contributor.studysubjectfi=Sovellettu matematiikka|en=Applied Mathematics|
dc.date.accessioned2025-06-16T21:30:58Z
dc.date.available2025-06-16T21:30:58Z
dc.date.issued2025-06-12
dc.description.abstractTutkielmassa 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.
dc.format.extent25
dc.identifier.olddbid199256
dc.identifier.oldhandle10024/182293
dc.identifier.urihttps://www.utupub.fi/handle/11111/2933
dc.identifier.urnURN:NBN:fi-fe2025061669549
dc.language.isofin
dc.rightsfi=Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.|en=This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.|
dc.rights.accessrightsavoin
dc.source.identifierhttps://www.utupub.fi/handle/10024/182293
dc.subjectkapasiteettirajoitettujen ajoneuvojen reititysongelma (CVRP), ryhmittele ensin, reititä sitten -menetelmä (CFRS)
dc.titleKapasiteettirajoitettujen ajoneuvojen reititysongelma
dc.type.ontasotfi=Kandidaatintutkielma|en=Bachelor's thesis|

Tiedostot

Näytetään 1 - 1 / 1
Name:
Kauppi_Henrik_opinnayte.pdf
Size:
606.35 KB
Format:
Adobe Portable Document Format
Lataa

Kokoelmat

Kandidaatin tutkielmat (kokotekstit)