[dba-SQLServer] Route Planning

MartyConnelly martyconnelly at shaw.ca
Sat Jan 20 19:34:18 CST 2007


Most of these programs will plot a route but not compute the optimum
route. For this you need the TSP (Traveling Salesman Problem) algorithm
The TSP is an NP-complete problem, it could be done on google maps.
but I have not seen any JavaScript code to solve this, it would  be hairy.

I have some quick VBA code that will display a route via Virtual Earth
with driving distances I can post,


Why is it difficult for optimising??

If you know the distances of the routes, or are happy to work with
straight line distances, then obtaining the solution for a small
number of points can be achieved by running a simple exhaustive search.
The problem with the travelling salesman is that an exhaustive search
algorithm needs to examine (n-1)!/2 possible routes. So for 6 markers
there's 60 possibilities to be checked, but for 12 markers there's just
short of 20 million, and for 18 markers there's nearly 15 trillion
possibilities. By the time you get to the classic problem of visiting
all the US state capitals the amount of processing involved in an
exhaustive search becomes somewhat impractical but has been
done and quicker algorithms have replaced the original solution
from the late 50's

You could try this

Concode TSP for Windows program
http://www.tsp.gatech.edu/concorde/gui/gui.htm


artful at rogers.com wrote:

>Does anyone know whether such software as MapQuest or MapPoint provides a way to plan a route (such as a Fedex truck delivery route) that would optimize for least distance? From what I can see, MapPoint expects you to plan the route. What I had in mind was piping in 20 addresses and having it do the planning.
>
>TIA,
>Arthur
>
>
>  
>

-- 
Marty Connelly
Victoria, B.C.
Canada




More information about the dba-SQLServer mailing list