Kuinka paljon turhaa ajoa syntyy siitä, että reittejä ei suunnitella mahdollisimman tehokkaasti? Kysymys kuulostaa arkiselta, mutta sen taustalta löytyy yksi tunnetuimmista optimointiongelmista: kauppamatkustajan ongelma. Kauppamatkustajan ongelman tutkijana minua kiinnostaa erityisesti se, missä määrin pienet reittivalinnat vaikuttavat käytännön toiminnan tehokkuuteen.
Mikä kauppamatkustajan ongelma oikein on?
Kauppamatkustajan ongelmassa tavoitteena on löytää lyhin mahdollinen reitti, joka käy läpi kaikki annetut pisteet täsmälleen kerran ja palaa lopuksi lähtöpisteeseen. Idea on yksinkertainen. Jos kauppamatkustajan pitää käydä esimerkiksi useassa kaupungissa, missä järjestyksessä kaupungit kannattaa kiertää, jotta kokonaismatka olisi mahdollisimman lyhyt?
Ongelman nimi on lähtöisin kiertelevistä kauppamatkustajista, mutta sen perusajatus näkyy monissa käytännön sovelluksissa, kuten kuljetuksissa, huollossa ja kotihoidossa.
Kauppamatkustajan ongelma on mielenkiintoinen, sillä ihmiselle suhteellisen yksinkertaisesti muotoiltava ongelma on tietokoneelle hankala ratkaistava.
Yksinkertainen ratkaisutapa käy nopeasti mahdottomaksi. Jos annetaan esimerkiksi 10 pistettä ja ongelma ratkaistaan käymällä läpi kaikki mahdolliset reitit, niitä kertyy (10–1)! (kertoma) / 2 eli 181 440 kappaletta. Kaava syntyy siitä, että reitin lähtöpiste kiinnitetään johonkin kymmenestä vaihtoehdosta, jolloin seuraavalle pisteelle on 9 vaihtoehtoa, seuraavalle 8 ja niin edelleen. Tulos jaetaan kahdella, koska jokainen reitti voidaan kulkea myös päinvastaiseen suuntaan ilman, että sen pituus muuttuu. Jo 20 pisteellä mahdollisia reittejä olisi yli 60 biljardia!
Yllä olevasta esimerkistä huomaa, että kyseinen ratkaisutapa ei ole mahdollinen vähääkään isommilla datajoukoilla, sillä erilaisten mahdollisuuksien määrä kasvaa räjähdysmäisesti.
Tämä on toki vain yksinkertaisin ratkaisutapa ja erilaisten ratkaisumallien, eli heuristiikkojen, avulla voidaan muodostaa käypiä reittejä jopa tuhannen pisteen ongelmiin sekunneissa ja miljoonien pisteiden ongelmiin kymmenissä minuuteissa. Ratkaisujen laatu vaihtelee, mutta noin tuhannen pisteen ongelmissa voidaan usein löytää lyhin mahdollinen reitti, ja miljoonien pisteiden tapauksissakin päästään hyvinkin alle yhden prosentin päähän lyhyimmästä reitistä. Käytetty optimisointiaika toki vaikuttaa. Hienoja visualisointeja yksinkertaisista ja monimutkaisemmista ratkaisumenetelmistä löytyy esimerkiksi Stem Loungen animaatioista.
Kauppamatkustajasta käytännön reititysongelmiin
Käytännön reititysongelmat ovat usein monimutkaisempia kuin perinteinen kauppamatkustajan ongelma. Yrityksellä voi olla useita ajoneuvoja, kuljettajilla työaikarajoitteita, asiakkailla aikaikkunoita ja ajoneuvoilla kapasiteettirajoitteita. Tällöin puhutaan ajoneuvoreititysongelmasta (Vehicle Routing Problem, VRP), jolla on kuitenkin läheinen yhteys kauppamatkustajan ongelmaan. Ajoneuvoreititysongelman vihreissä versioissa (Green VRP) voidaan huomioida esimerkiksi polttoaineenkulutus, sähköajoneuvojen lataustarve, päästöt tai ajoneuvotyypit.
Taannoin vastaan tuli esimerkiksi tilanne, jossa erään yrityksen piti optimoida jäteautojen reittejä. Rakensin itsekin toimivan prototyypin kyseiseen ongelmaan. Tapaus jäi mieleen hyvänä esimerkkinä siitä, miten nopeasti teoreettinen optimointiongelma voi muuttua käytännön kehitystarpeeksi.
Miten kauppamatkustajan ongelma liittyy vihreään ICT:hen?
Vihreästä ICT:stä puhuttaessa voidaan erottaa kaksi erilaista näkökulmaa. Toisaalta voidaan kehittää itse ICT-toiminnan ympäristövastuullisuutta (Green for ICT). Toisaalta ICT:tä voidaan hyödyntää muun toiminnan vastuullisuuden tukena (Green by ICT). Kauppamatkustajan ongelmassa ja vastaavissa optimointiongelmissa näkyy hyvin tämä jälkimmäinen ajattelutapa: laskennan ja datan avulla voidaan tunnistaa tilanteita, joissa kilometrejä, aikaa, energiaa tai muita resursseja kuluu turhaan.
Tähän liittyy myös hiilikädenjäljen käsite. Siinä missä hiilijalanjälki kuvaa toiminnasta aiheutuvia kasvihuonekaasupäästöjä, hiilikädenjälki kuvaa potentiaalia vähentää päästöjä, kun olemassa oleva ratkaisu korvataan vähäpäästöisemmällä ratkaisulla. Reittioptimoinnissa tämmöinen kädenjälki voi syntyä esimerkiksi silloin, kun parempi reitti vähentää ajettuja kilometrejä ja sitä kautta energiankulutusta ja päästöjä. Vihreän ICT:n terminologiaan, periaatteisiin ja niiden käytännön soveltamiseen yrityksissä voi tutustua tarkemmin esimerkiksi VICTIS-hankkeessa laatimassamme oppaassa Johdatus vihreään ICT:hen yrityksille – nollapisteestä sankaritekoihin.
Samaa kädenjälkiajattelua voidaan hyödyntää myös tilanteissa, joissa kyse ei ole reitinsuunnittelusta. Jäntin ym. (2025) tapaustutkimuksessa tarkasteltiin metsäkoneyrityksen nestevarastojen etäseurantaa. Etäseurannan avulla varastosäiliöiden tilannetta ei tarvitsisi käydä tarkistamassa paikan päällä, vaan tilannetta voitaisiin seurata digitaalisesti. Tutkimuksen esimerkkilaskelmassa etäseurannan käyttöönotto kaikilla yrityksen etävarastoalueilla voisi vähentää tarkastusajoista syntyvää hiilijalanjälkeä noin 192 kg CO₂. Laskelma perustui 692 kilometrin ajoon useiden etävarastoalueiden välillä dieselkäyttöisellä pakettiautolla. Lisäksi etäseuranta voisi säästää ainakin yhden työpäivän kuukaudessa.
Tämä on hyvä esimerkki siitä, että vastuullisuushyödyt eivät synny pelkästään suurista teknologisista harppauksista. Joskus hyöty voi syntyä siitä, että tunnistetaan arjessa toistuva turha liike: ajettu tarkastuskierros, ylimääräinen huoltokäynti tai epäoptimaalisesti suunniteltu reitti. Juuri tällaisissa tilanteissa optimointiajattelu muuttuu käytännön hyödyksi.
Missä muualla vastaavaa optimointiajattelua voisi hyödyntää? Kauppamatkustajan ongelman tutkijana kuulisin mielelläni esimerkkejä tilanteista, joissa reittejä, käyntejä tai muuta liikkumista voisi suunnitella nykyistä tehokkaammin.
Kirjoittaja:
Jimi Tuononen
Jimi Tuononen toimii projektitutkijana Itä-Suomen yliopiston tietojenkäsittelytieteen laitoksella VICTIS-hankkeessa. Hänen tutkimuksensa keskittyy algoritmeihin ja erityisesti kauppamatkustajan ongelmaan. VICTIS-hankkeessa hän työskentelee vihreän ICT:n ja kestävän digitalisaation teemojen parissa.
Lähteitä ja lisälukemista:
Stem Lounge. Animated Algorithms for the Traveling Salesman Problem. https://stemlounge.com/animated-algorithms-for-the-traveling-salesman-problem/
Jäntti, M., Koponen, J. & Aho, M. 2025. How Digital Experiments Support Sustainability in a Forest Machine Operator Company: A Case Study. ICSEA 2025: The Twentieth International Conference on Software Engineering Advances.
Jäntti, M. & Tuononen, J. 2026. Johdatus vihreään ICT:hen yrityksille – nollapisteestä sankaritekoihin. Itä-Suomen yliopisto, VICTIS-hanke.
Pajula, T., Vatanen, S., Behm, K., Grönman, K., Lakanen, L., Kasurinen, H. & Soukka, R. 2021. Carbon Handprint Guide. V. 2.0 Applicable for Environmental Handprint. VTT Technical Research Centre of Finland Ltd.