Kauppamatkustajaongelman muunnoksia
531.31 KB
avoin
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
Lataukset92
Pysyvä osoite
Verkkojulkaisu
DOI
Tiivistelmä
Tämä tutkielma on kirjallisuuskatsaus, jossa esitellään kauppamatkustajaongelman erilaisia muunnoksia. Kaikille tarkastelluille ongelmille esitellään tarkka määritelmä ja mallinnus joko lineaarisena binäärioptimointitehtävänä tai lineaarisena sekalukuoptimointitehtävänä. Aluksi esitellään klassinen kauppamatkustajaongelma ja määritellään Hamiltonin sykli. Tämän jälkeen käydään läpi hyvin yksinkertaisia muunnoksia klassisen kauppamatkustajaongelman epäsymmetriselle versiolle. Seuraavaksi tarkastellaan kahta kauppamatkustajaongelmaa, joissa läpikäytävät kaupungit on jaettu ryhmiin. Kahdessa viimeisessä muunnoksessa on sen sijaan useampi kuin yksi kauppamatkustaja. Lopuksi esitellään lyhyesti joitakin ratkaisumenetelmiä esitellyille kauppamatkustajaongelmille.