The Traveling Salesman Problem (sic)

i studied two of engineering’s newest fields.  They are called Operations Research and Industrial Engineering.   While broad the IE part is a bit easier to understand:

Examples of where industrial engineering might be used include: shortening lines (or queueing theory) at a theme park, streamlining an operating room, distributing products worldwide (also referred to as supply chain management), and manufacturing cheaper and more reliable automobiles

Operation Research is about mathematical optimization.  Solving all manner of problem using complex algorithms and usually computers.  One of the applications  of operations research was the invasion of Normandy.  One of the classic theoretical Operation Research problems is the “Traveling Salesman Problem” (sic).  Which is (from wikipedia):

Given a list of cities and their pairwise distances, the task is to find the shortest possible route that visits each city exactly once and returns to the origin city.

Don’t worry if you dont get this comic, it si super geeky

This is actually what i am doing this week, though the specific optimization is less about distances and more about buyers schedules. .  Visiting a collection of hammocks wholesalers on the East Coast, because we did so well at the trade show last year, that we cant really afford to go back (it costs roughly $30K) and then have new customers we cant satisfy because of our production limitations and at the same time we dont want to loose our existing customers.

in another life i did this all the time

And our customers mostly love us.  The product is quality made, they get few returns, it lasts for a long time, it is made in the US and it distinguishes them from the big box stores.  Should you wish to buy a hammock go to our online store.

===

Interestingly to me (and perhaps other geeky readers) the traveling salesperson problem is consider a difficult problem.  Specifically, NP-Hard where it is the hardest of its class of problems.  There are of course brute force approaches, where you measure from every city to every other city til you cover all the routes, but this gets big very fast.

Tags: , ,

About paxus

a funologist, memeticist and revolutionary. Can be found in the vanity bin of Wikipedia and in locations of imminent calamity. buckle up, there is going to be some rough sledding.

6 responses to “The Traveling Salesman Problem (sic)”

  1. Scott Busby says :

    If the joy is in the journey and not the destinations, we must invert the traveling salesman problem. I suspect that the mathematical solution is still classified as “n-hard.” Lately I have been exploring the idea of “travel hacking” and “couch surfing” ways of wandering the earth as free and unencumbered as possible!

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: