OU blog

Personal Blogs

Richard Walker

The Travelling Mailman Problem

Visible to anyone in the world
Edited by Richard Walker, Monday, 20 July 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

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: 2135751