Posts Tagged ‘Traveling Salesman’

TSP Problem

editprogrammingcommentsNo Comments »
July 22nd 2010

I have just run into what appears to be a very classic problem that has been studied a lot:

The Problem:

A list of addresses in a neighborhood that someone must visit and complete in a timely manner.

This is very much related to a problem called The traveling salesman problem (TSP) where an optimal walking order needs to be computed which result in the shortest distance traveled and/or shortest time taken.

After taking a look at different approach to this problem and taking look at a current javascript implementation at
http://www.gebweb.net/optimap/

It gave me hope that this problem can be solved with web implementations, however there were two problems with the above solution.

1. It restricted to 24 addresses (Which is fine because TSP originally is for larger area route planning, even between cities)
2. Only given 15 or less address did it return the optimal route

The solution:

Due to computational resources and restrictions in scripting languages, I have decided that the best and easiest way to solve this problem would be using the “Nearest Neighbor” approach.

This approach takes the closest location as the next location and repeat this process for route planning. Although this is not the most optimal way of solving the problem but it provides a couple of advantages:

1. Can always calculate straight line distance to the next address and then use google map API to calculate the direction
2. The step can be repeated and increment the current location to the next address which is just calculated.

The biggest problem with the approach so far is that in order to calculate the route (On the server side), we must specify a starting point. Some ideas include use one of the boundary corners as a starting point, or use the middle most point and walk in a circular fashion.

Will keep updated with some implementation soon.