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