Vuonna 2021 teimme Nicon kanssa matemaattisen optimoinnin maailmanennätyksen. SMPTSP-ongelman ratkaisemisessa. Optimoinnin kohteena olivat 277 erilaista ongelman testi-instanssia, joihin alan huippututkijat ovat yrittäneet löytää yhä parempia ratkaisuja. Ongelma on julkaistu vuonna 2001.
SMPTSP (Shift Minimization Personnel Task
Scheduling Problem) on käytännön
ongelma, jossa työntekijät käyvät asiakkaiden luona suorittamassa
aikaikkunaan sidottuja työtehtäviä, joissa tulee huomioida mm. työntekijöiden
osaamiset ja valmiudet. Tavoitteena on muodostaa samaan aikaan sekä
kustannustehokkaat että työntekijöiden ja asiakkaiden kannalta sopivat
työvuororakenteet.
Testi-instanssit ovat tämän käytännön ongelman
tieteellisiä erikoistapauksia,
joissa jopa tuhansia työtehtäviä pitää sijoittaa sadoille työntekijöille siten,
että käytettävien työntekijöiden määrä tulee minimoida. Esimerkkejä tällaisesta
työstä ovat kotihoitopalvelut, siivouspalvelut, vartiointipalvelut,
asennuspalvelut, sanomalehtien jakelu ja jätehuolto.
Uusi
maailmanennätys tehtiin Nicon väitöskirjassaan kehittämällä uudella
laskennallisen älykkyyden (*) GFA-algoritmilla.
Algoritmin kolme keskeistä osaa ovat elitistinen ratkaisupooli, tehokas
paikallishakuoperaattori ja vahvistusoppimiseen perustuva painotusmekaniikka.
GFA-algoritmi
kykeni löytämään parhaat ja optimaaliset ratkaisut kaikkiin 277
testi-instanssiin. Kolmeen instanssiin löydettiin uudet parhaat ratkaisut. Tutkimuksen tulokset julkaistaan Ateenassa lokakuussa konferenssissa International
Conference on Mathematics and Computers in Sciences and Industry.
GFA:n
suoritusaika on erittäin nopea. Lähes kaikkiin instansseihin löydettiin optimiratkaisu
alle kymmenessä sekunnissa. Vain neljän testi-instanssin kohdalla optimaalisen
arvon löytäminen kesti yli minuutin. Hyvistä tuloksista huolimatta mysteeriksi
jäi, miksi jotkin testi-instanssit ovat erittäin haastavia ratkaista. Tämän
tutkiminen onkin jo käynnissä yhdessä intialaisen matemaatikon kanssa.
Nico Kyngäs
väitteli tohtoriksi Turun yliopistossa keväällä 2023. Väitöskirjan otsikko
on An Algorithmic approach to shift
structure optimization. Kyngäs
työskentelee nykyään USA:ssa
toimivassa yrityksessä väitöskirjan sisältöä vastaavissa tehtävissä.
**********
(*) Laskennallinen
älykkyys on tekoälyn muoto, jossa käytetään luonnosta
inspiraationsa saaneita laskennallisia menetelmiä kuten evoluutioalgoritmeja, parvietsintää
ja oppivia heuristiikkoja. Tällaisella tekoälyllä pyritään ratkaisemaan
ihmisjärjen ulottumattomissa olevia erittäin monimutkaisia ongelmia, jotka
vaativat tietokoneeltakin massiivista laskentatehoa, esimerkkeinä lentoliikenteen
ja julkisen liikenteen optimointi, työvuorolistojen optimointi ja
ammattilaisliigojen sarjaohjelmien optimointi. Todettakoon, että neuroverkkoihin
perustuvat ja esimerkiksi ChatGPT-tyyppiset tekoälyt eivät sovellu näiden
ongelmien ratkaisemiseen.
