Suunnistusongelma ja heurististen ratkaisujen empiirinen arviointi

Abstract

Kombinatorisessa optimoinnissa tavoitteena on löytää paras ratkaisu äärellisestä vaihtoehtojen joukosta: monet tunnetut laskennan rajoja koettelevat ongelmat kuuluvat tähän luokkaan. Useille näistä ongelmista ei ole esitetty tehokasta algoritmia, jonka laskenta-aika skaalautuisi kohtuullisesti (polynomisesti) syötteen koon kasvaessa. Tässä tutkimuksessa käsitellään kombinatoristen ongelmien heuristisia ratkaisumenetelmiä, jotka eivät takaa parhaan mahdollisen ratkaisun löytymistä. Teoreettisten takuiden puuttuessa empiiristen mittausten rooli korostuu, mutta samaan aikaan mittausten tekeminen vertailukelpoisella tavalla ja oikean kokoluokan ongelmissa on haastavaa. Syntyy tarve kehittää erilaisia tapoja mitata ratkaisimen suorituskykyä ja lisätä varmuutta heurististen ratkaisujen laadusta. Tässä työssä pyritään vastaamaan kyseiseen tarpeeseen soveltamalla heuristisia ratkaisumenetelmiä ja ratkaisimen suorituskyvyn mittaustapoja erityisesti suunnistusongelmaan, jota käsitellään ensin teorian tasolla ja myöhemmin vertaillaan toteutetun ratkaisimen tuloksia kirjallisuudessa esitettyihin ratkaisimiin. Lopputuloksena julkaistaan myös lähdekoodi suunnistusongelmageneraattoriin, joka tuottaa ennalta määritellyn optimin sisältäviä suunnistusongelmia mittaustarkoituksiin.