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

GTalk

Blog archive

Loading…

Tags

Galleries

Not signed in
Sign in

Powered by BlogBuilder
© MMXXII