Joeleonhart’s Weblog

To Learn and To Share

Traveling Salesman Problem (TSP)

The problem requires a tour beginning at specificlocation and visiting the remaining n-1 locations, each beingvisited only once, with a return to the beginning point so as tominimize the total distance traveled. Although the problem sound verysimple, its exact solution is not. In a small problem with fivelocations, there are (n-1)!/2 possible solutions. The division by2 reduces the problem since we assume that thedistance from i to j is the same as the distance from j to i.

Thus, afive-city problem has 12 possible solutions. However, a problem with10 cities has more 180,000 possible solutions.Although exact solutions to the problem exist, theyare not efficient. Many operations researchers consider this problemso difficult that it will never solved efficiently. (If you can solve it,You can becomefamous!)

Sajadin Sembiring

Data mining & Knowledge Management Research Group

Departement of Computer Science

Faculty of Computer System & Software Engineering

Universiti Malaysia Pahang
www.sajadinbiring. multiply. com

June 12, 2008 - Posted by | Info and Events, News - Articles

No comments yet.

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: