Posted by: thebylog | April 16, 2010

Traveling Yard Saler’s Problem

The Traveling Salesman Problem (TSP) is a very famous and hard optimization problem. Given a list of destinations and the pairwise distances between them, the solution is the shortest route beginning and ending at the originating destination while visiting every other destination exactly once.

This evening my wife made a list of nine yard sales she wants to visit tomorrow. Here they are, numbered in the order she gave them to me:

Eyeballing it, I guessed a shortest route solution of 1 7 3 6 2 10 8 9 5 4 1 (i.e. beginning at our house, 1, and continuing to 7, then 3, …, until returning to 1. According to Google Maps, this route covers 28.6 miles and takes 1 hour and 10 minutes.

Using a very nice TSP solver, the route actually producing the minimum driving time is:

This second map reorders the numbers, so my eyeballed guess at a solution in terms of these new numbers is 1 2 4 3 5 9 10 8 7 6 1 versus the optimal solution of 1 2 3 4 5 6 7 8 9 10 1. The biggest difference between the optimized route and my guess is that, instead of going from 5 to 9 like I figured it would do, it takes her from 5 all the way out to 6 before coming back and eventually returning to 1. I think this is because there is no good, direct route from 6 back to home. The optimized route covers 27.3 miles and should take about 1 hour and 3 minutes.

So I saved her roughly 7 minutes! Alas, it took me well over 7 minutes to produce the optimized route. I got a kick out of it though.

On the other hand, if she would have visited the yard sales in the order she happened to write them down (i.e. 1 2 3 4 5 6 7 8 9 10 1, using the first map’s numbers again), the distance would have been 37.4 miles with an estimated time of 1 hour and 26 minutes.

Advertisements

Responses

  1. I enjoyed this post =)

    I don’t go to yard sales frequently, but I can appreciate a good optimization problem. Questions like this get interesting when distance and time compete. Since I live relatively close to 322, when I am driving south/east it is often faster for me to use the bypass than Atherton Street, though from a distance perspective the trip is longer.


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

Categories

%d bloggers like this: