Santa’s Most Efficient Tour

I am sitting at the airport, waiting to go home for the holidays…   Of course, being reminded of the Traveling Salesman Problem* (TSP)… No theoretical abstractions but simple sentences are enough define it (see below if you are not familiar), yet it is far from being trivial, still waiting to be solved efficiently… Much progress has been made to solve it, see e.g., one of my favorite OR websites on TSP.

santas-tsp-tour

In the spirit of the holidays, above is an application of TSP for finding Santa’s most efficient tour. The above picture comes from an old article that appeared in Florida Sun-Sentinel.  The current challenge for Santa’s Tour is the World TSP -a 1,904,711 city TSP around the world, still waiting to be provably optimally solved.

You can also use TSP for your personal trip planning, see for instance Plan a Trip on Google Maps…

Ahh, boarding started… Back to my own world TSP…

[*: Imagine a salesman who has to visit a number of cities to sell a particular product. The problem is to find a tour for this salesman that visits each city exactly once, returning back to where he started, such that the total distance or time traveled is minimized.]

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: