Kauppamatkustajan ongelman ratkaiseminen unkarilaisella algoritmilla

Abstract

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.