Geographic routing & speed optimisation

Up until now we've been using MapPoint to get routes & distances between places, the data from which we use to create prices based on tariffs which can be fairly complex. Unfortunately making calls to MapPoint can be incredibly slow, and we only have MapPoint 2007 which means it won't contain any roads built in the past 18 months or so. I'm not sure there is a MapPoint 2008, but even if there is, we don't want it any more. In terms of licensing, it's not viable for us to go out to a web service as we will be making hundreds of thousands of routing queries each day and companies who supply such services charge by the hit, or charge huge sums based on the type of business. Ours, unfortunately, seems to come into the category of Asset Tracking which demands truly extortionate sums for a business like ours. We're also currently paying quite a lot for the Postcode Area File from the Post Office, which would need to be licensed on a per-site basis.

So we've got hold of the UK data from TeleAtlas which has a royalty-free license and we're now working on presenting the map data and creating routes. Address finding will come later, but it should be fairly simple.

Finding the shortest path is a very well documented problem. There are also plenty of very well documented algorithms and we may actually be looking at the Canadial Traveller Problem, where we know the position we want to get to, but we don't know how to get there and we don't know if all the roads on the route are open at that time.

However, these algorithms and problems are all approached on a per-instance basis. In general you're expected to want to find the length of the shortest path at the time that you want the information.

We've decided to take a different approach to the problem which involves mapping (in a grid) the time and distance from each node in our graph to every other node. The UK has a huge number of nodes, however, so the graph we map will be based on the bounding box around a local area with some further allowance for roads leading into, out of and around the area.

This does at first sound like a very time-intensive task, but we're planning to analyse the graph from multiple machines at once. We have SQL Server 2008, so having multiple concurrent connections won't be a problem.

I'll post more details on our method at a later date. Right now I have code to write :)