The curse of the sat-nav system

In the UK, and I guess in most other countries, satellite navigation systems (sat-navs) are a blessing and a curse. Surprisingly little has been published about the design of the algorithms used in them, though essentially they use modified forms of Dijkstra's method, which is also the dynamic programming approach. A fellow blogger has commented on some of the stories from the UK, Belgium and the Netherlands.

Over a meal on Friday evening, friends were talking about stories which don't reach the national papers. They mentioned the large number of small sites for caravans (there is a club which has private use of fields in many farms) which have the warning "Do not use sat nav" in their guide-book. Another friend mentioned that a passenger ferry across a river, at the end of a lane, is marked as accessible to vehicles.

There are several problems with sat-navs that these stories highlight. Most obvious is that data can be incorrect, and once published, is hard to retract. Next is that data may change; roads can be closed for repair, and even online updates may not help, even if the user chooses to subscribe to such a facility. But from an O.R. point of view, there is the question of the wrong algorithm. Many of the problems could be dealt with if the algorithm took into account the kind of vehicle, which would mean solving a constrained shortest path problem ... and for nearly all cases, that would mean using the normal algorithm on a modified dataset. But that would increase the price of the system.

So we end up with people cursing the system, damage to property thanks to incorrectly routed vehicles, a cost to society with special road signs trying to stop vehicles routed with sat-nav ....