[dba-SQLServer] Route Planning

I worked in GIS systems throughout the 70's and had to build
or find my own math and stats algorithms, that meant haunting university 
libraries
there was no Internet *sob* , so most of the basic ones, I can still 
remember the
algorithm names. Some have been known for nearly 2 centuries.
I even published some code in a Canadian Cartographic journal in the 
early 70's.
Youngsters will laugh at my feeble attempts but they worked
in old Fortran II. Not efficient or very fast. A lot were based
on simple geometry. But back then they were golly gee whizz.


Jim Lawrence wrote:

>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