Hyppää sisältöön
    • Suomeksi
    • In English
  • Suomeksi
  • In English
  • Kirjaudu
Näytä aineisto 
  •   Etusivu
  • 1. Kirjat ja opinnäytteet
  • Kandidaatin tutkielmat (kokotekstit)
  • Näytä aineisto
  •   Etusivu
  • 1. Kirjat ja opinnäytteet
  • Kandidaatin tutkielmat (kokotekstit)
  • Näytä aineisto
JavaScript is disabled for your browser. Some features of this site may not work without it.

Ajoneuvojen reititysongelma

Harmanen, Rasmus (2024-02-19)

Ajoneuvojen reititysongelma

Harmanen, Rasmus
(19.02.2024)
Katso/Avaa
Harmanen_Rasmus_opinnayte.pdf (627.3Kb)
Lataukset: 

Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
avoin
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe202402268824
Tiivistelmä
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.
Kokoelmat
  • Kandidaatin tutkielmat (kokotekstit) [1298]

Turun yliopiston kirjasto | Turun yliopisto
julkaisut@utu.fi | Tietosuoja | Saavutettavuusseloste
 

 

Tämä kokoelma

JulkaisuajatTekijätNimekkeetAsiasanatTiedekuntaLaitosOppiaineYhteisöt ja kokoelmat

Omat tiedot

Kirjaudu sisäänRekisteröidy

Turun yliopiston kirjasto | Turun yliopisto
julkaisut@utu.fi | Tietosuoja | Saavutettavuusseloste