Ski all the Sun Peaks nordic trails in a day

It would be fun to ski the whole nordic trail network in a single day.  Too lazy to plot a good route by hand, I wrote a computer program to do it.  I used the program to find several routes that traverse the entire trail network in under 43km — see below (click the image for a larger version).

map_markupSome Background

Sun Peaks has about 35km of groomed nordic trails but it’s impossible to ski the whole network without repeating some trails.  In graph-theoretic terms, the network has no Eulerian path since it has a bunch of odd-degree vertices: where an odd number of trails meet, one of them has to be skied twice.  The problem is to choose which trails to ski twice, so that the total distance/elevation gain are as small as possible. There are zillions of possible routes; finding the optimal one is an instance of the “route inspection problem ” or “Chinese postman problem”.

That’s about all the graph theory I know, so rather than using a graph-theoretic algorithm I just wrote some code that uses simulated annealing.  It searches for a route that uses all the trails at least once, while trying to minimize a weighted sum of the total distance and total elevation gain, and avoiding having to ski certain trails in an “undesirable” direction (e.g. I don’t really want to skate up En Garde in the middle of a 43km ski).  The search is random so every time the code runs it finds a different the route.  The routes shown above are just a few that offer some variety, though inevitably there are similarities.

In all there are 29 intersections and 48 trail segments (not including the two isolated trails to the village and outpost cabin).  Stripping away the geography, the network graph looks like this (drawn using the igraph package in R):

networkMy numbering of the intersections is a little haphazard — the result of making many corrections.  Too much trouble to change it now.

Leave a Reply

Your email address will not be published. Required fields are marked *