Joulupukin aattoillan ajoreitti

Joonas Ollila 22.12.2021

Koko valtakunta alkaa olla lumen peitossa, mikä auttaa huomattavasti Korvatunturilla asuvaa joulupukkia lahjojen toimittamisessa perille lyhintä mahdollista reittiä. Joulupukin reitin valinta lahjojen toimittamiseksi perille on tyypillinen kauppamatkustajan ongelma (traveling salesman problem, TSP), eli miten käydä useassa pisteessä vähintään kerran siten, että ajoreitti on mahdollisimman lyhyt.

 

TSP on todennäköisesti kaikista tutkituin optimointiongelma ja myös joulupukin reittilaskennasta löytyy kaikenlaista tietoa eri puolilta internetiä. Jos kuitenkin oletetaan, että joulupukilla jos kenellä on parhaat laskentamallit mitä rahalla saa, niin paljonko kilometrejä on taivallettavana aattoiltana? Tarkkaa vastausta on hankala antaa – joku viettää joulua isovanhemmilla, toinen lomailee, kolmas on mökillä – mutta ainakin jokaisessa asutuskeskuksessa on käytävä vähintään kerran.

 

Asutuskeskusten lukumäärä onkin sitten hankalampi juttu. Joka maassa tilastoidaan vähän fiilispohjalta ja rajan vetäminen sille, mihin yksi kaupunki loppuu ja toinen alkaa ei ole lainkaan yksiselitteistä (esim. onko Espoo oikeasti erillinen kaupunki vai Helsingin esikaupunki?). Kaikeksi onneksi joku muu on jo ratkaissut ongelman ja määritellyt, että maailmassa on vajaat kaksi miljoonaa asutuskeskusta, tarkalleen ottaen 1 904 711 kpl.

 

Lyhimmän reitin löytäminen vajaan kahden miljoonan pisteen välille on haastava optimointiongelma.


Yleisesti ottaen, kun tarkastellaan n:ssä pisteessä käyviä reittejä, on eri reittivaihtoehtoja yhteensä (n-1)! kappaletta. Eli kun käyntipisteitä on n=2, 3, 4, 5, 6… löytyy vastaavasti reittivaihtoehtoja (n-1)! = 1, 2, 6, 24, 120…..

 

Näin ollen joulupukin reittivaihtoehtojen lukumäärä räjähtää nopeasti käsiin ja lukuarvoa 1904710! on turha kysyä taskulaskimelta tai googlelta, sillä kumpikaan ei suostu laskemaan näin isoja lukuja. Stirlingin kaavan avulla saadaan selville, että:

kaava1

 

Normaalisti isot luvut näytetään kymmenen potensseina, joten muunnetaan tämä siihen muotoon:

 
kaava2
 

Voimme siis todeta, että pukilla on mahdollisia reittivaihtoehtoja reilusti yli 10¹⁰ ⁰⁰⁰ ⁰⁰⁰ kappaletta.

 

Kun havaittavassa maailmankaikkeudessa on noin 10⁸⁰ alkeishiukkasta, on hyvin ilmeistä, ettei ns. brute force -ratkaisulla päästä kovin pitkälle.

 

Onneksi lyhimmän polun laskentaan on muitakin algoritmeja. On aika pysäyttävää, että paras tähän mennessä löydetty ratkaisu ongelmaan on vain 0.0471% optimiratkaisua huonompi!

 

Reitti Korvatunturilta kaikkiin maailman asutuskeskuksiin ja takaisin on 7 515 756km pitkä, kun oletetaan, että pukki liikkuu Amerikan tyyliin lentävällä reellä.

 

Reilu 7.5 miljoonaa kilometriä ei oikein vertaudu mihinkään arkielämän etäisyyteen. Se vastaa noin 188:a kierrosta maapallon ympäri tai lähes kymmentä matkaa kuuhun ja takaisin.

 

Unohdetaan hetkeksi globaali perspektiivi ja tarkastellaan tilannetta keskimääräisen valtion näkökulmasta. Suomi on kohtalaisen keskiverto tässä olennaisten mittarien eli pinta-alan (sijalla 65/190) ja väestön (sijalla 115/190) osalta, joten katsotaan miten kotimaan lahjat saataisiin perille.

 

Samainen Kanadassa sijaitseva Waterloon yliopisto, jonka sivuilta löytyy maailman kaikissa kaupungeissa käyvä reitti, on koonnut listaa yksittäisten valtioiden kaikissa kaupungeissa käyvistä reiteistä. Sivuston mukaan Suomessa on 10 639 asutuskeskusta ja niiden välisen lyhimmän reitin pituus on 54 020km. Tämä on optimaalinen reitti, eli lyhin mahdollinen kaikista tarjolla olevista vaihtoehdoista.

 

route-finland

 

Kotitalouksien sijainneista on hankala löytää laadukasta aineistoa. Waterloon yliopisto on käyttänyt omissa laskennoissaan datalähteenä Yhdysvaltain puolustusministeriön alaista kuvatiedusteluaineistoa käsittelevää virastoa NGA:ta. NGA:lta saattaisi vaikka löytyäkin tarvittava aineisto, mutta siinä rikottaisiin jo niin monta GDPR-pykälää, että lienee turvallisempaa käyttää summittaista arviota.

Oletetaan, että jokainen asutuskeskus on yhden neliökilometrin kokoinen ja kotitaloudet ovat satunnaisesti jakautuneet alueelle. Yhden asutuskeskuksen kaikissa n:ssä kotitaloudessa käyvän lyhimmän polun pituus on Ln. Yllättävää kyllä, vielä ei tunneta mikä lyhimmän polun pituuden odotusarvo E(Ln) on! Mutta sille on kuitenkin olemassa ylä- ja alarajat. Wikipedian mukaan voimme olla lähes varmoja siitä, että odotusarvolle pätee

kaava3

 

Näin ollen sadan kotitalouden kylän tapauksessa toimituksista ovelle asti aiheutuisi lisämatkaa noin 7.62-15.89km.

Omaan korvaan haarukka vaikuttaa turhan laajalta ja etenkin yläraja ihmetyttää. Lyhyt kirjallisuuskatsaus paljastaa, että yläraja on kohtalaisen korkealla kun vertaa laskennallisiin tutkimuksiin. Lisäksi Steinerbergerin (2014) mukaan teoreettiset rajat ovat myös selkeästi kapeammat

kaava4

 

Suomessa on noin 100 000 asutettua neliökilometriä (100 338 kpl). Keskimääräinen kotitalouden koko on 2.02 henkeä, joten voimme jakaa jokaisen asutetun neliön väestön 2.02:lla ja saada tulokseksi kotitalouksien lukumäärän. Suuri osa maasta on hyvin harvaan asuttua ja teoreettiset rajat lyhimmän polun odotetulle pituudelle pätevät vain kun n . Käytetään siis laskennallisia tuloksia kun kotitalouksia on neliökilometrillä niukasti ja teoreettisia rajoja kun liikutaan tiheämmin asutulla alueella.

 

Vedän rajan mielivaltaisesti 100 kotitalouteen neliökilometrillä. 96 125:llä asutuista neliökilometreistä on tätä harvempaa asutusta ja 4213:lla tiheämpää. Pikaisen excel-laskutoimituksen tuloksena saadaan selville, että pakettien toimittamisesta ovelle asti tulee pukille lisämatkaa noin 210 000 – 232 000km.

routeKuva: Alkuperäisen reitin ja ovelle asti toimitusten yhdistäminen.

 

Vielä yksi pieni pulma olisi ratkottava ennen kuin voidaan raportoida lopullinen lukema, sillä 100 338 asutettua neliökilometriä ja 10 639 käyntipistettä reitillä eivät ihan täsmää. Tarvitaan siis aimo annos käsien heiluttelua sovellettua matematiikkaa.

 

Ongelman voi ratkaista esim. siten, että jaetaan koko valtakunnan väestö 10 639 tiheimmin asuttuun neliökilometriin samassa suhteessa kuin näissä on väestöä. Tällöin kotitoimituksista aiheutuva lisämatka aliarvioidaan, koska tiheämmin asutetuilla alueilla toimitusreittien tehokkuus (käyntipisteitä per km) on parempi.

 

Toinen vaihtoehto on summata alkuperäinen reilun puolen miljoonan kilometrin reitti ja aiempi arvio kotitoimitusten aiheuttamasta lisämatkasta (210 000 – 232 000km). Tällöin koko reitin pituus aliarvioidaan, koska alkuperäinen reitti ei käy kaikissa asutuissa neliöissä. Toisaalta väestö ei ole neliöiden sisällä täysin satunnaisesti jakautunut – yleensä väestö on keskittynyt asuinalueille ja niiden sisällä joskus kerrostaloihin, jolloin kotitoimitusten reitin pituus on aavistuksen yliarvioitu. Summa summarum, virhearviot nollaavat osin toisensa ja lasken luvut yhteen lopullista arviota varten.

 

 

Yhteensä joulupukilla on siis noin 275 000km matka edessä, jotta kaikki suomalaiset saavat pakettinsa kotiovelle.

 

Perheissä on erilaisia perinteitä, mutta useimmat lahjat jaetaan klo 15-19. Tästä saamme joulupukin keskinopeudeksi 68 750km/h 19km/s. Ei ihan posketon lukema – jotkin avaruusluotaimet matkustavat jopa nopeammin.

 

Ei siis kannata ihmetellä, jos pukki vaikuttaa hieman hätäiseltä aattoiltana. Rommitotin tarjoaminen lämmikkeeksi kannattaa muuten varmuuden vuoksi jättää väliin. Jos joka kymmenennessä paikassa tarjotaan 2cl rommia, on pukki jo reilusti ennen reitin puoliväliä lähes 1000 promillen maistissa.

 
avatar

Joonas Ollila

joonas.ollila@twoday.com
044 230 3847

Sinua voisi kiinnostaa myös