Optimaalinen järjestys nähtävyyksien kiertämiseen eli travelling salesman -ongelma

Travelling salesman eli kauppamatkustajan ongelma on vanha pähkinä siitä, missä järjestyksessä annetuissa kohteissa kannattaa käydä, jotta kokonaismatkasta tulisi mahdollisimman lyhyt. Täydellinen optimi löytyy vain kokeilemalla kaikki eri vaihtoehdot, joiden määrä nousee kaavan (n-1)! mukaisesti erittäin nopeasti. Viidessä kohteessa voidaan käydä 4x3x2x1 = 24 eri järjestyksessä, minkä pystyy vielä arvioimaan omassa päässään. Mutta jos kohteita on esimerkiksi 10 ja ne ovat hajallaan eri puolilla karttaa, vaihtoehtoja on jo 362 880.

Järjestys on tärkeä vaikkapa jakeluyhtiöille tai Wolt-kuskeille, jotka haluavat minimoida matkan annettujen pisteiden välillä. Tietokoneille on kehitetty erilaisia optimointialgoritmeja, mutta varmuudella lyhin reitti löytyy vain kokeilemalla.

Kesän lomamatkoja suunnitellessa tuli mieleen, missä järjestyksessä kohteet kannattaisi kulkea. Yllättäen tähän ei löytynytkään valmista mobiili- tai nettisovellusta, kuten olin ajatellut. Löysin kuitenkin näppärän ratkaisun Franco Folinin blogista. Hän oli tehnyt pienen koodinpätkän, joka siirtää työn Google Mapsin tehtäväksi. 

Sivumennen sanoen on ällistyttävää, mitä kaikkea nykyään voi saada aikaan muutamalla koodirivillä valmiita ilmaispalveluita hyödyntämällä. 

Ja näin se toimii. 

Syötetään Google Docsiin joukko pääkaupunkiseudun museoiden osoitteita. Folinin koodia kutsutaan solussa A2 funktiona optimalRoute(), jolle annetaan kolme parametria: lista kohteista, lähtöpiste ja loppupiste. Lähtö- ja loppupisteet voivat olla soluja tai ne voidaan kirjoittaa lainausmerkeissä auki suoraan funktiokutsuun. 

Helsingin museoiden osoitteita.

Esimerkissä on kahdeksan osoitetta. Lähtö- ja loppupisteeksi on merkitty Tekniikantie 12, Espoo (solu B2), mutta sen tilalla voisi olla ensimmäisen vierailukohteen osoite.

Folinin mukaan Google Mapsin ilmaisversio hyväksyy enintään 25 kohdetta, maksamalla saisi vielä pidemmän listan.

Funktio palauttaa numerolistan, jonka mukaisesti osoitteissa kannattaa vierailla. Folinin koodissa liikkumistavaksi on valittu auto, mutta sen voi vaihtaa vaikka kävelyksi, jos vierailee kesällä vieraassa kaupungissa.

Numerolista kannattaa vielä lajitella, jolloin saadaan havainnollinen listaus:

Museoiden optimaalinen vierailujärjestys.

Espoosta lähdettäessä kannattaa siis ensiksi vierailla Suomen valokuvataiteen museossa, jatkaa sieltä Ateneumiin, sitten Mannerheim-museoon ja niin edelleen.

Jos kesälomalla täytyy kiertää sukuloimassa eri puolilla maata, kohteiksi riittävät pelkät kuntien nimet. Google Maps on mainio, sillä se valitsee automaattisesti kunnan keskipisteen, mikä riittää järjestyksen optimointiin.

Kaupunkien vierailujärjestys.

Espoosta lähdettäessä kannattaa siis ajaa reittiä Kotka - Kouvola - Savonlinna - Kuopio - Kokkola - Seinäjoki - Tampere - Turku ja takaisin Espooseen.

Vielä yksi esimerkki on Googlen kyky tunnistaa kohteet suoraan niminä, jolloin edes osoitteita ei tarvita. 

Nähtävyyksien vierailujärjestys, aloitus Finlandia-talolta.

Kun lähtöpiste on Finlandia-talolla, siitä tulee luonnollisesti myös ensimmäinen vierailukohde. Sieltä jatketaan sitten Hämeen linnaan, Tampereelle Särkänniemeen ja niin edelleen.

Ovatko tulokset oikeita? Tein pistokokeita siirtämällä osoitteet kartalle ja katsomalla lenkin yhteispituutta, algoritmin ehdottama järjestys oli kaikissa tapauksissa kilometrimääriltään pienin. Matka-ajan optimointi voisi kuitenkin johtaa toisenlaiseen järjestykseen.

Google Street View menee Ateneumiin (ja Finlandia-taloon ja...)

Viime vuoden maaliskuussa kirjoitin, että Googlen karttapalvelu näyttää sisätilakarttoja vain muutamasta kohteesta. Hieman yllättäen Googlen palvelu ei näytä kehittyneen lainkaan puolessatoista vuodessa. Edes New Yorkin JFK-kenttää ei ole mukana, eurooppalaisista kohteista puhumattakaan.

Sen sijaan Googlen Street View -toimintoon on tullut uusia kohteita, ja tällä kertaa ne ovat talojen sisältä. Esimerkiksi Ateneumin sisällä pääsee nyt kulkemaan virtuaalisesti:

Virtuaalikäynti Ateneumissa.

Kuvat ovat huomattavasti parempilaatuisia kuin katunäkymien kuvat. Isolla näytöllä vaikutelma on todella tyylikäs.

Kokeilemalla löysin pari muutakin kohdetta: Kulttuuritalon ja Finlandia-talon.

Kävelyllä Finlandia-talossa.

Konserttisali.

Konserttisaliin pääsee, mutta vessaan ei : -)

Olisin odottanut, että myös Espoon Dipoli olisi päässyt arkkitehtuurinsa vuoksi mukaan, mutta sieltä ei ollut kuvia, ei liioin Tampere-talosta. Pikainen haku ei löytänyt kuvia myöskään Pariisin Louvresta tai Pietarin Eremitaasista.

Virtuaaliretki näihin kolmeen kohteeseen antaa esimakua tulevasta. Kenties jonain päivänä kohteet eivät ole pelkkiä kuvia, vaan niissä on mukana videota ja vuorovaikutteisia palveluita. Silloin voidaan puhua jo keinotodellisuudesta.

Lisäys 3.9.2014: Ja kertauksena vielä, miten tämä toimii: otetaan kiinni siitä oranssisesta pikku-ukosta ja viedään se hiirellä kartalle, jolloin Street Viewin kattamat alueet näkyvät sinisellä. Sisäkuvista kertovat rakennusten sisällä siniset viivasykkyrät.

Street View -näkymän aktivointi.

Lisäys 3.9.2014: Alvar Aalto -museo otti yhteyttä ja viittasi tiedotteeseen, jossa kerrotaan Google-yhteistyöstä. Yhdeksän Aallon piirtämää rakennusta on jo kuvattu. Yllä esiteltyjen lisäksi mukana ovat mm. Säynätsalon kunnantalo arkkitehdin kotikaupungista Jyväskylästä, Kolmen Ristin Kirkko Imatralta sekä Aallon oma ateljee Helsingin Munkkiniemestä.

Lisäys 4.9.2014: Gizmodo kertoo tänään ilmestyneessä tekstissä millaista tekniikkaa Google käyttää rakennusten sisäkuviin. Laitteisto on rakennettu selkäreppuun. Ehkä jo seuraava versio kartoittaa itsenäisesti koko tilan, aivan kuten Prometheus-elokuvassa.

Google Maps tuntee pyörätiet ja liikenneongelmat

Google Mapsiin tulee vaivihkaa uusia ominaisuuksia. Jokin aika sitten huomasin, että mukana ovat myös pyörätiet (ehkä tämä on ollut jo ennenkin?):

Pyynikin pyöräilytiet Google Mapsin mukaan.

Pikainen kokeilu näytti pyörätiet esimerkiksi lapsuuden maisemista Pyynikinharjulta sekä Tampereen Kirkkopuistosta. Hieno homma -- vielä kun nämä saisi mukaan navigaattoreihin, niin pyöräilijä voisi etsiä lyhintä reittiä ajon aikana ohi perinteisten liikenneväylien.

Liikenteen ruuhkanäyttö Google Mapsissa on ollut jo pitkään, mutta jossain vaiheessa siihen on lisätty liikennetiedotteet:

Tietyö Turunväylällä.

Tie suljettu Nihtisillan lähellä.

Ruutukuvat ovat iPhonesta, mutta samat tiedot näkyvät myös web-versiossa. Voi vaikka ennen työmatkaa tarkistaa, ettei luvassa ole yllätyksiä.

Tiedotteissa on kuitenkin oleellinen rajoitus: kartalla ovat vain pysyvät tiedotteet. Kolareista, liukkaasta kelistä ym. kertovat tiedotteet näkyvät ilmeisesti vain navigaattoreissa, joiden valmistajat ovat maksaneet tiedotepalvelun lisenssin.

Vielä yksi havainto ruuhkatilanteesta. Anturiverkoston täytyy olla erittäin tiheä, koska se pystyy erottelemaan yksittäisen liikenneympyrän ja pienen pätkän sen jälkeen kulkevaa tietä:

Ruuhkaa Kehä II:n liikenneympyrässä.

Ruuhkamaksuja tai ei -- autot ovat jo nykyisin tarkassa seurannassa.

Lumia 920 ja sisätilojen kartat

Navigointi toimii hienosti ulkona, mutta suunnistusapu olisi tarpeen myös lentokentillä, sairaaloissa ja ostoskeskuksissa. GPS ei sisätiloissa toimi, mutta kartat auttavat asiaa.

Lumia-puhelinten karttasovellus tuntee monia ostoskeskuksia ja näyttää niiden sisältämät liikkeet, hissit ja vessat:

Ostoskeskus Sellon kaupat. 

Huomaa näytön reunassa oleva kerrosvalitsin, näppärää! Pieni kuva ei tee oikeutta kartalle, jonka saa zoomaamalla hyvinkin tarkaksi. Kauppojen kohdalla on myös linkkejä lisätietoihin.

Sisätilat ilmestyvät näkyviin, kun zoomaa karttaa tarpeeksi ja jaksaa odottaa hetken (paitsi että eilen kokeillessani mitään ei tapahtunut, illalla kartat taas toimivat).

Pikaisella kokeilulla puhelimesta löytyivät mm. Tampereen Koskikeskuksen, Ideaparkin sekä Helsingin Kampin ostoskeskukset. Myös Helsinki-Vantaan terminaali on mukana, mutta hyödyllinen tieto lähtöporttien numeroista puuttuu.

Sisäkarttoja voi katsella myös tietokoneen näytöllä, sillä Bing Maps sisältää lähes samat tiedot (ruutukuva isolta 24" näytöltä):

Sellon sisäkartassa on mukana kauppojen hakemistokin.

Puhelimen karttadata on laajempi, sillä nettiversiosta puuttuu ainakin lentokentän terminaalin sisäkartta. Toisaalta kauppojen hakemisto tekee halutun myymälän etsimisestä helppoa.

Myös Googlen kartoissa on rakennusten sisätiloja, mutta ei ainakaan vielä Suomesta. Myöskään Heathrow'n terminaaleja ei ole mallinnettu, mutta ainakin Miamin lentokentän terminaalista nähdään näin hieno versio:

Miamin terminaali näyttää myös lähtöportit.

Vanhalla iPhonellani en saanut näkymään mitään sisätilakarttoja.

Vielä ihan toinen juttu kartoista: niin loistava kuin Googlen karttapalvelu onkin, joskus kannattaa kokeilla myös kilpailevaa Microsoftin Bingiä.

Lomaillessani Arabiemiraateissa huomasin, että joidenkin arabimaiden karttadata aina maan nimeä myöten oli kirjoitettu arabiaksi, eikä siitä saanut mitään tolkkua:

Mikähän valtio tässä rajan pohjoispuolella on?

(Mistä ihmeen kartasta on tullut Emiratos Arabes Unidos??).

Bingin kartassa nimistöt olivat eurooppalaisilla kirjaimilla ja siten ymmärrettävässä muodossa:

Bing Maps on epätarkempi, mutta tekstit ymmärrettäviä.

Googlen kartat ovat selvästi tarkempia, mutta vasta Bingistä selvisi naapurimaan nimi (Oman) sekä tie, joka vei vanhaan Khabasin linnoituskaupunkiin. Ilman Bingin apua se olisi jäänyt näkemättä. Joku on kuvannut ajomatkan hienot maisemat myös Youtubeen.