Kauppamatkustajaongelman muunnoksia

Abstract

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.