OU blog

Personal Blogs

The Travelling Mailman Problem

Visible to anyone in the world
Edited by Richard Walker, Monday, 20 Jul 2020, 23:45

A couple of days ago an associate and friend who likes intriguing puzzles sent me this different take on the notorious Travelling Salesman Problem.

The original question is: given a collection of cities and all the travel distances between each pair, how can a travelling saleman plan a circular tour that is as short as possible? This is a hard problem, in the sense that when there are any substantial number of cities finding the best solution will bring any computer to its knees.

Although my friend is not a mathematician but a developmental psychologist, he had a mathematician's idea, one that follows one of George Pólya's heuristics: can you solve a simpler version of the problem?

So my friend asked himself, what if the cities are all in a line?

Imagine the cities are not cities, but houses on a street, assumed to be equally spaced out, and a mailman wants to minimise their walking distance. The solution is just to walk along the numbers in sequence 1, 2, 3... up to the last house number. Pretty obvious, huh?

And then he asked another good mathematical question, what if we varied the problem? So he asked for the longest path the mailman could take. Imagine they have a yen for exercise and want to walk as far as possible.

If we have 10 houses each 1 unit apart, what is longest route they could take to visit each house exactly once, and return to the end of the street where they started?

And what if there are n houses; can you find a formula?


Permalink Add your comment
Share post

Travelling Salesman Problem

Visible to anyone in the world
Edited by Richard Walker, Sunday, 7 Jun 2020, 01:58

I was reminded of this today by a friend and colleague. The TSP problem asks how to calculate the shortest round trip between a set of cities, given the respective distances between them.

Simply comparing all the possible routes one after another will obviously work, but with even a few cities, and the fastest computer in existence, it could take thousands or millions or more years. So is there a way to solve it in a feasible length of time?

The TSP attracts a lot of attention, because it’s easily stated and most people have a gut feeling there should be a lightbulb intuition that will show the way. However decades of professional and amateur endeavour have not succeeded. We have good ways to calculate it well enough for delivery services say, but no way of finding the absolute optimum until the customer is long dead. Amazon and Google and others use algorithms which are good enough, and they are good enough; shaving 100 metres off a delivery trip will avail nought if there is a parked car en route. 

So it’s a theoretical question, but to my mind they are the ones that we learn most from.

Let XKCD have the last word. This is the approach that will probably work best in this year of crisis, and perhaps at all times.


https://xkcd.com/399/


Permalink Add your comment
Share post

This blog might contain posts that are only visible to logged-in users, or where only logged-in users can comment. If you have an account on the system, please log in for full access.

Total visits to this blog: 1277095