March 25, 2008

Finding the shortest route…

As I was driving down the M6 yesterday evening there was an accident that caused a bit of a hold-up. Not knowing how long this was going to take, I hit the “detour” button on the SatNav to see if there was a convenient way around the blockage. Oddly, after finding an alternative route, the SatNav’s ETA was earlier than previously, even though I have it set to plot the quickest route. If the detour was quicker, why wasn’t it sending me that way in the first place?

It turns out this is a variation of the Travelling Salesman Problem, which is hard to solve both accurately and quickly. I guess the SatNav is using an algorithm that gets close to, but not always exactly, the shortest route. To be fair, the difference was only a couple of minutes. I was just surprised, until I thought about it a bit more…

- One comment Not publicly viewable

  1. Travelling Salesman

    Travelling salesman problem

    26 Mar 2008, 21:52

Add a comment

You are not allowed to comment on this entry as it has restricted commenting permissions.

Search this blog


Blog archive




Not signed in
Sign in

Powered by BlogBuilder