Another TSP solution
I opened the newspaper and looked at the map, with its accompanying story and picture, and thought: "There's a TSP solution in the map" (TSP = Travelling Salesperson Problem). But it was an intriguing problem.
Let's start with a bit of background, though much of it is in the newspaper article pictured - with the map - below. The Lake District in north-west England is famed for its lakes (obviously, but very few of them are called "lake") and its mountains. By international standards, the mountains are not especially high, but ascending some of them can be challenging. In the mid-twentieth century, a local man, Alfred Wainwright, wrote a series of seven guidebooks to the mountains and hills. His books are still in print, reproducing his original hand-written notes, his hand-drawn maps and his detailed pen-and-ink sketches of the peaks. They have achieved a cult following, together with his books on the Pennine Way and other walks. The pictures below shows the style of his books.
Creating lists of geographical objects leads to challenges, and so there is the challenge to climb every one of the "tops" listed by Wainwright. There are 214 of them. And there is a long list, online, of those who have visited every one of them. But the ultimate challenge is to visit all 214 in as short a time as possible, on foot, in a continuous tour. And the news story described a new record being set.
As the 214 locations are located in two-dimensional space, the optimal tour must not be self-intersecting. However, as is evident, the route followed by Paul Tierney did pass through some points more than once, and occasionally used a link between points more than once. This too can be shown to be acceptable in an optimum strategy. There will be points which are not Wainwright peaks where access routes to the mountains converge. There are several peaks where the best way to visit them is to climb one peak, move to a second, a neighbour, and return to the first. There are several in the south-east corner, below.
So it is not a "pure" TSP where returns to previously visited spots are forbidden. What makes it especially interesting is that the time to travel between spots is (a) asymmetric and (b) depends on how long the competitor has been running for (tiredness creeping in!)
Well dome to Paul for setting a new record for completion time, and for providing an illustration of a well-known operational research problem in the press.
Let's start with a bit of background, though much of it is in the newspaper article pictured - with the map - below. The Lake District in north-west England is famed for its lakes (obviously, but very few of them are called "lake") and its mountains. By international standards, the mountains are not especially high, but ascending some of them can be challenging. In the mid-twentieth century, a local man, Alfred Wainwright, wrote a series of seven guidebooks to the mountains and hills. His books are still in print, reproducing his original hand-written notes, his hand-drawn maps and his detailed pen-and-ink sketches of the peaks. They have achieved a cult following, together with his books on the Pennine Way and other walks. The pictures below shows the style of his books.
Creating lists of geographical objects leads to challenges, and so there is the challenge to climb every one of the "tops" listed by Wainwright. There are 214 of them. And there is a long list, online, of those who have visited every one of them. But the ultimate challenge is to visit all 214 in as short a time as possible, on foot, in a continuous tour. And the news story described a new record being set.
As the 214 locations are located in two-dimensional space, the optimal tour must not be self-intersecting. However, as is evident, the route followed by Paul Tierney did pass through some points more than once, and occasionally used a link between points more than once. This too can be shown to be acceptable in an optimum strategy. There will be points which are not Wainwright peaks where access routes to the mountains converge. There are several peaks where the best way to visit them is to climb one peak, move to a second, a neighbour, and return to the first. There are several in the south-east corner, below.
So it is not a "pure" TSP where returns to previously visited spots are forbidden. What makes it especially interesting is that the time to travel between spots is (a) asymmetric and (b) depends on how long the competitor has been running for (tiredness creeping in!)
Well dome to Paul for setting a new record for completion time, and for providing an illustration of a well-known operational research problem in the press.
Comments
Post a Comment