[dba-SQLServer] Route Planning

Jim Lawrence jlawrenc1 at shaw.ca
Sat Jan 20 21:08:22 CST 2007


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




More information about the dba-SQLServer mailing list