Optimizing Route Calculation

Ok -- I've searched the internet high and low, and even spoken with the makers of MileCharter.....

I have thousands of zipcodes in a database. I need to find out how far (driving distance) each of those zipcodes is to each of the other zipcodes.

I have written code to do this, and it works great, but it is incredibly slow. I am getting 1 - 3 routes per second. So for 1,000 zipcodes (500,000 routes) it takes between 46 and 138 hours to get the distances.

I have Application.Visible set to false, so it is not having to render the maps, but I need other advice on how to speed up the process....

I set my waypoints using:

objMap.ActiveRoute.Waypoints.Add(objMap.GetLocatio n(dblLat1, dblLon1))

Where dblLat1,dblLon1 are the lat and lon of the zipcode (because mappoint does not recognize all of the zips...)

Any ideas to help optimize this process would be great... If I can squeeze out even 6 routes per second that would cut the time in half.

Obviously I know the obvious answer of throwing more computers at the problem -- I am looking for code optimizations.

Thank you in advance for any ideas....

As I was suggesting on the phone, time isn't your only problem. Have you considered how you are going to store 800 million mileages? Is that going into a database? Which one? Access won't handle that many (it has a 2GB limit).

Richard

Richard,

I have reserved myself to the fact that getting the distance for all 40,000 that we discussed isn't likely an option, but I have narrowed the list down to 100 zips that I need to compare to the 40,000.... This is 4 Million Routes instead of 800 Million.... Drastically less.

But that's still 4 Million seconds (46 Days) worth of processing...

I'm just wondering if anyone is willing to offer help in optimizing the code... I didn't really want to ask you directly, because it's your livelyhood, and I didn't want to ask you to give up trade secrets...

Thanks!!!

It is Microsoft you need to be talking to...

Route finding is computationally difficult ("NP Complete"). All things considered, MapPoint's route finding doesn't perform too badly.


Richard

jper043
This may not help as I guess you may have already done things this obvious. I will list them because I did not when I did it first:
1. Make sure that you recognise mirror calculations (ie Loc2 to Loc1 picks up data for calculation already done for Loc1 to Loc2) rather than recalculating
2. Create all the location objects before you start the calculation run
3. Consider whether you can live with straightline distance which you then multiply by a fiddle factor (1.2 being the favorite, but you could do a sample of real routes and establish a better factor for your geography). This of course is MUCH faster.
4. Divide the database into multiple parts and run on multiple computers