artful at rogers.com
artful at rogers.com
Sat Jan 20 23:32:26 CST 2007
I am well acquainted with the TSP problem, and have written some Genetic Algorithms to solve it, but they all depend on a pre-existing databases of distances between cities, and thus are not appropriate. I thought that maybe MapQuest or MapPoint had these distances built-in. Actually, they both do. They simply (or complexly) have not applied the TSP algorithms to them. Maybe that's an extension that could be for sale. I was hoping that it already was, but if not, then since I am well acquainted with the problem, maybe that's my next project. A. ----- Original Message ---- From: Jim Lawrence <jlawrenc1 at shaw.ca> To: dba-sqlserver at databaseadvisors.com Sent: Saturday, January 20, 2007 10:08:22 PM Subject: Re: [dba-SQLServer] Route Planning Hi Marty: My Gawd where do you come up with this stuff... Quite impressive but scary. :-) Jim -----Original Message----- From: dba-sqlserver-bounces at databaseadvisors.com [mailto:dba-sqlserver-bounces at databaseadvisors.com] On Behalf Of MartyConnelly Sent: Saturday, January 20, 2007 5:34 PM To: dba-sqlserver at databaseadvisors.com Subject: Re: [dba-SQLServer] Route Planning 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 _______________________________________________ dba-SQLServer mailing list dba-SQLServer at databaseadvisors.com http://databaseadvisors.com/mailman/listinfo/dba-sqlserver http://www.databaseadvisors.com _______________________________________________ dba-SQLServer mailing list dba-SQLServer at databaseadvisors.com http://databaseadvisors.com/mailman/listinfo/dba-sqlserver http://www.databaseadvisors.com