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.