Traveling Salesman Problem

Salesmen have existed for thousands of years. In the early years, they traveled from cave to cave selling sticks and stones and tried their hand at up selling their clientele on "fire." The plight of the traveling salesman has not changed that much in the past millennia though. They still travel door to door trying to sell us products and services (thought a lot of perennial d-t-d sales have moved to the Web). As they travel door-to-door, they must do so in a way that conserves their time (the more potential clients they can see, the more fruitful their labors), and increasingly, their gas.

Though the price of gas wasn't at issue hundreds of years ago, efficiency still was. From that quest came the Traveling Salesman Problem. According to Wikipedia, the problem can be summarized as: "Given a number of cities and the costs [mileage] of traveling from any city to any other city, what is the least-cost round-trip route that visits each city exactly once and then returns to the starting city?"

For a small collection of cities, it's relatively easy and can be done by hand. As the number of cities increase, the computational power increases to compensate for all of the new permutations. Hundreds of people much smarter than I have battled the problem for ages trying to come up with the optimal (read: least cost) path.

All that aside, there are two things I wanted to get out there in this article. First, a Google Maps implementation or the TSP available for your personal travels this holiday season. As the Nuclear Family has exploded and we have so many more holiday family gatherings to attend, this site could help you get it all done in one day -- efficiently!

For a little more (geeky) fun, try your hand at some simple TSP games for yourself.

Happy travels...