Tour around national parks in Finland

English summary Seven national parks in Finland have their 60th anniversary in year 2016. But how much driving it would result to visit every park? Using Openstreetmap and open source tools it is quite easy to find the shortest route. It takes 4922 km drive to visit them all. Read below how I found this out!
Finnish summary: Seitsemän kansallispuistoa täyttää tänä vuonna 60 vuotta. Kuinka pitä reissu siitä tulisi jos kiertäisi kaikki, minkä ehtisi hyvin tehdä 6 viikon kesälomalla (jos sellainen olisi)? Hyödynetäen Openstreetmap:n tietokantaa ja vapaita ohjelmistoja on helppo laskea etäisyydet kansallispuistojen välillä ja tämän jälkeen ratkaista ns. kauppamatkustajan ongelma lyhyimmän reitin löytämiseksi. Lyhin löytämäni reitti on 4922 km, jossa pisin ajo oli Lemmenjoelta Pyhä-Luostolle 290 km. Lataa GPX-reittijälki ja lähde retkelle. Sattumalta lyhin reitti alkaa Pohjois-Karjalasta Patvinsuolta ja päättyy Kolille, mikä ei ole ollenkaan hullumpi paikka päättää kotimaan kierros. Toki reitin voi aloittaa muustakin kohdasta.

Background

In 2012 I was involved in a project where at one point there was a plan to visit about 200 locations around Finland to deliver some equipment. So to get an estimate how long it would take at minimum, I went into search how to resolve traveling salesman problem.
Found lots of different programs to resolve travelling salesman problem but in many cases preparing data or understanding how they worked do was a bit complicated. Quite typical for a research problem! At end wroted a quite simple python script - can't remember if I wrote it fully by myself or was it partly copied it from Internet (could not find source with Google).
Anyway, the method is quite simple:

1. Start with one node.
2. For each node that is closer than certain threshold, select as candidate for optimum brances (this limits search space so it is not order of factorial of N).
3. Repeat operation for each branch until all nodes are put into branches.
4. Working backwards on each branch, select the shortest one.

Result obviously depends on starting node and on order nodes are walked. As this is real-world case and not some patheologigal worst-case data, we may end with reasonably good results. Code runs quite fast, so we can run it using each node as starting point.
Luckily, I did not had to visit all 200 places but we got delivery organised by other people, so manual optimisation was just fine to deliver equipment into few central locations.

National parks

Our family enjoys visiting national parks and other recreational areas in Finland and also aboard. We often park our camper car on one designated areas (or even some other places where it is not explicitly prohibited, thanks to great Freedom to roam in Finland). Then we take hike, bikes or take our inflatable boat and canoe and enjoy quietness and nature.
We do not have to leave our home city, Espoo, to reach national park. And even if Nuuksio parking is full of cars (and it is also possible to reach with public transport or by bike), one has plenty of space to roam, especilally a bit further away from most popular fire places.

In this year (2016) 7 national park have their 60th anniversary. There are total 39 national parks and on next year Hossa hiking area will get promoted to national park as part of Finlands 100 years of independence celebration.
So, I was wondering how much driving you need to visit every national park on summer vacation. With 40 parks, one needs full 6-weeks vacation to spend a day in every park. Unfortunately, I do not have that time.

Finding shortest path

So, I checked all national parks, collected coordinates for a one parking place for each park. Tried to select either the main parking area, or one close to major roads. There may be some open data resource, but at end it was quite easy to check them out from retkikartta map service.
As five of national parks are actually sea and achipelago, there is no "parking space" where to reach them by walking. However, I made following decissions and waypoints are more or less approximate:

• Itäinen Suomenlahti: harbour in Hamina. There is regular taxi boat on summer time.
• Tammisaaren saaristo: Tammisaari harbour, I guess you can get a boat from there, either talk youself into private boat or check if there are some boat trips available.
• Saaristomeri: Information center Sinisimpukka at Kasnäs. There is frequent ferry / boat traffic to major islands.
• Selkämeri: Rauma harbour. Same as with Tammisaari.
• Perämeri: Kemi harbour. Same as with Tammisaari.

As I had list collected, then I downloaded Finland extract from openstreetmap data and feed it to routino routing software (as it was readly available for Debian unstable). Turned out that on default settings it does not use track type highways for motorcar routing. So it was not able to reach some of national parks. This was easy to modify and just put low speed and low precedence on tracks so it will avoid using them unless absolutely required.
Finland has about 350 000 km of tracks which it quite a lot compared to 78 000 km of higer class roads (50 000 km paved). About one thirds of tracks is towards permanent residencies, one third are forest roads and one third to summer cottages. These can be driven with normal car. So you need to travel along them to reach many destinations in Finland.
After this it was just calculating full matrix of road distances between all parks. As all routing takes place on my computer, I have not to worry about some rate limits or AUP if I would be using Google routing service or similar.
After ten minutes, I had 1560 possible routes. Now just to launch my simple router and in a second I had 40 possible routes with distances from 5598 km to 6898 km. Now just create path along the shortest one and we are good to hit the road.

More advanced methods or how to save more than 100 kg CO₂

Of course, in four years there has been lots of open source development and example scripts to resolve travelling salesman probles exists for R and python among others.
For example Randal S. Olson has published a notebook with code explaining how to resolve problem using genetic algorihtm. We do not need to ask Google anything, so we can ignore first sections and just make few modifications to match my data file format and output format.
Turns out, genetic algortihm provided route that was only 4922 km, 676 km shorter. With our camper car, it is more than 100 kg CO₂.

Scripts and source data

Scripts and datafiles can be found from github. About only depency is python3-pandas. All scripts have been run under Debian Unstable (mainly because of more recent version of routino), but for example Ubuntu 16.04 (Xenial) has version 3.0 of routino so it should be ok.

Create routing database

First download Openstreetmap Planet extract. As we are only travelling within Finland, we do not need full planet but can download Finland only from Geofabrik. Genereate routing database using our custom routing rules (including tracks into all forms of motor transport with slow speed and low preference).

wget http://download.geofabrik.de/europe/finland-latest.osm.pbf
planetsplitter --prune-none --tmpdir=/tmp --tagging=./tagging-drive.xml finland-latest.osm.pbf

This needs to be done only once.

Finding routes

At first we transform list of waypoints into tab separated format. With this, we create full matrix of sources and destinations. If we like to make some shortcuts, we could assume distance is the same in both directions - on these routes difference is just minor because of some one-way links to motorways and similar. But CPU cycles are cheap, so we can work bot directions.
We use specific routing profile optimised for our camping car: as it has legal limit of 100 km/hour, that is also the maximum speed it travels motorway (routino default for a motorcar at motorway is 112 km/h).

./recs2csv.pl kansallispuistot.txt > kansallispuistot.csv
./full-matrix.pl kansallispuistot.csv

Resolving travelling natureman problem

Armed with the matrix, we then need to be hit the hardest problem, finding optimal route. I ran first my old, simplistic method but turns out genetic algortihm works much better. Based on experiments, running more random start positions provides better results compared for many generations. Typically there is no much change after 500 or 1000 generations with this dataset. So I run genetic algorihm for 100 times for 3000 generations each.
In my run, I end with four identical-length routes. Two of those are identical, so I guess there is no significantly shorther route. Then I select one of those, build both individual route segments and then overall track.
At final, sort out trip segments based on length to find out that the shortest distance is from Liesjärvi to Torronsuo (23.1 km) and the longest is from Lemmenjoki to Pyhä-Luosto (290 km). Note that as this is random process, you may get different results.

mkdir gen
for i in $(seq 0 99); do python3 genetic-travel.py matrix-kansallispuistot.csv > $(printf "gen/%02d.txt" $i); done
shortest=$(fgrep 2999 gen/* | sort -rn -k 2 | tail -1 | cut -f 1 -d :)
./part-tracks.pl kansallispuistot.csv <(fgrep 2999 $shortest)
./full-track.pl kansallispuistot.csv <(fgrep 2999 $shortest)
fgrep 'Waypt#2' parts-2999/*_shortest.txt | sort -n -k 8 | awk '{s+=$8;print}END{print s}'

And finally we also want waypoints with labels to plot on map and combine it with track:

gpsbabel -i xcsv,style=style.gps -f kansallispuistot.csv -i gpx -f 2999.gpx -o gpx -F kansallispuistot.gpx

Now we can open kansallispuistot.gpx in our favorite map browser, like viking, or import to you GPS and start a tour around Finnish national parks.

Other layouts

Above generates track having trackpoints in about very Openstreetmap way node, i.e. quite much. If you want just routing information, you can generate it with script or download:

gpsbabel -i gpx $(for f in parts-2999/*-route.gpx; do echo -f $f; done) -o gpx -F kansallispuistot-route.gpx

Route listing

And here is the route above in list format. This one starts and ends at Northen Carelia. The last point, Koli, was a very important location for many artists in romantic nationalism period late 19th and early 20th century. These include Jean Sibelius, Eero Järnefelt, Pekka Halonen, and Juhani Aho. If you do not have time to visit all, Koli is a good candidate to include your list.

1. Patvinsuo
2. Petkeljärvi
3. Kolovesi
4. Linnansaari
5. Repovesi
6. Itäinen Suomenlahti
7. Valkmusa
8. Sipoonkorpi
9. Nuuksio
10. Liesjärvi
11. Torronsuo
12. Teijo
13. Tammisaaren saaristo
14. Saaristomeri
15. Kurjenrahka
16. Selkämeri
17. Puurijärvi ja Isosuo
18. Lauhanvuori
19. Kauhaneva-Pohjankangas
20. Seitseminen
21. Helvetinjärvi
22. Isojärvi
23. Päijänne
24. Leivonmäki
25. Etelä-Konnevesi
26. Pyhä-Häkki
27. Salamajärvi
28. Rokua
29. Perämeri
30. Pallas-Yllästunturi
31. Urho Kekkonen
32. Lemmenjoki
33. Pyhä-Luosto
34. Oulanka
35. Riisitunturi
36. Syöte
37. Hossa
38. Hiidenportti
39. Tillikkajärvi
40. Koli

Happy travelling!