The Traveling Salesman Problem

Hello to everyone! The topic I want to share with you is about The traveling salesman problem, I find it very interesting because we can apply it in everyday life actually, in my case I like traveling a lot, so these methods can be useful for me to be able to visit as so many cities posible, find the shortest and best route to fallow, so I can save money and have time for traveling in other places later.

The traveling salesmane problem is basically find the shortest path from the begining to end, going to through all the cities only once and returns to the start point. I think is a very good way to optimize time, distance and costs, and a very organized way of working too. The traveling salesman problem asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

Image

But, it is not as easy as it sounds, there are so many applications to solve this problem, it requieres an specific procedure to follow, depending of  wich methods we are going yo use, to achieve the best outcome. I will mention some of them:

As a Graph Problem

TSP can be modelled as an undirected weighted graph, such that cities are the graph’s vertices, paths are the graph’s edges, and a path’s distance is the edge’s length. It is a minimization problem starting and finishing at a specified vertex after having visited each other vertex exactly once. Often, the model is a complete graph (i.e. each pair of vertices is connected by an edge). If no path exists between two cities, adding an arbitrarily long edge will complete the graph without affecting the optimal tour.

Asymmetric and Symetric

In the symmetric TSP, the distance between two cities is the same in each opposite direction, forming an undirected graph, This symmetry halves the number of possible solutions. In the assymetric TSP, paths may not exist in both directions or the distances might be different, forming a directed graph. Traffic collisions, one-way streets and airfares for cities with different departure and arrival fees are examples of how this symmetry could break down.

Symmetric TSP with four cities

Even, due the complexity of TSP, it can be calculated by making formulas or by a computing solutions, with a spcecyfic programs or softwares able to solve the problematic.
So when I have many choices of cities to visit and I dont know what to do, definitetly I will take a time to analyse the paths, and  choose the shortest and best route for me.
Here’s a video that may help you to understand the traveling salesman problem concept with an easy explanation  .

Source: “Travelling salesman problem” http://en.wikipedia.org/wiki/Travelling_salesman_problem
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