Hyppää sisältöön
    • Suomeksi
    • In English
Trepo
  • Suomeksi
  • In English
  • Kirjaudu
Näytä viite 
  •   Etusivu
  • Trepo
  • Kandidaatintutkielmat
  • Näytä viite
  •   Etusivu
  • Trepo
  • Kandidaatintutkielmat
  • Näytä viite
JavaScript is disabled for your browser. Some features of this site may not work without it.

Kauppamatkustajan ongelman ratkaiseminen unkarilaisella algoritmilla

Perasto, Teemu (2018)

 
Avaa tiedosto
perasto.pdf (1.785Mt)
Lataukset: 



Perasto, Teemu
2018

Teknis-luonnontieteellinen
Teknis-luonnontieteellinen tiedekunta - Faculty of Natural Sciences
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2018-08-15
Näytä kaikki kuvailutiedot
Julkaisun pysyvä osoite on
https://urn.fi/URN:NBN:fi:tty-201806011896
Tiivistelmä
Tässä kandidaatintyössä tutkitaan, miten kauppamatkustajan ongelma voidaan ratkaista soveltamalla unkarilaista algoritmia. Kokeilujen myötä huomataan, että unkarilaista algoritmia voidaan soveltaa ensin laskemalla kauppamatkustajan ongelmaa vastaava kohdistusongelma, jonka jälkeen saadaan optimikohdistus, joka joko kelpaa kauppamatkustajan ongelman ratkaisuksi tai ei. Todetaan, että on hyvin harvinaista, että ratkaisemalla kohdistusongelma saadaan ratkaisu suoraan kauppamatkustajan ongelmalle.

Kun unkarilaisen algoritmin soveltaminen kerran ei riitä, erilaisia toimenpiteitä tarvitaan ongelman ratkaisemista varten. Tässä kandidaatintyössä tutkitaan kolmea eri vaihtoehtoa, joilla yritetään saavuttaa jokin ratkaisu ongelmalle: alkioiden manuaalinen kohdistaminen, unkarilaisen algoritmin jatkuva iterointi ja unkarilaisen algoritmin hybridisaatio metaheuristisen algoritmin, Branch & Bound -algoritmin, kanssa.

Yllä mainittujen menetelmien käytön myötä voidaan todeta, että kauppamatkustajan ongelma voidaan ratkaista unkarilaisella algoritmilla. Lopuksi pohditaan, miten käytettyjä menetelmiä voidaan automatisoida kirjoittamalla tietokoneohjelma.
Kokoelmat
  • Kandidaatintutkielmat [5929]
Kalevantie 5
PL 617
33014 Tampereen yliopisto
oa[@]tuni.fi | Tietosuoja | Saavutettavuusseloste
 

 

Selaa kokoelmaa

TekijätNimekkeetTiedekunta (2019 -)Tiedekunta (- 2018)Tutkinto-ohjelmat ja opintosuunnatAvainsanatJulkaisuajatKokoelmat

Omat tiedot

Kirjaudu sisäänRekisteröidy
Kalevantie 5
PL 617
33014 Tampereen yliopisto
oa[@]tuni.fi | Tietosuoja | Saavutettavuusseloste