[dba-SQLServer] Route Planning

Have a look at MapInfo's Routing Server
They have an office in Toronto.
They don't list prices.

artful at rogers.com wrote:

>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