Driveable routes: solving shortest path problems in practice

With the increasing use of geographical information systems (GIS) and route planning software, users have demanded faster, more realistic routes. Traditionally, operational researchers have focused on developing fast exact and heuristic procedures for the point-to-point shortest path problem. To complement these advancements, we extend the functionality of route planning by describing a number of user-driven route planning requirements and an approach for handling them. A linear time graph modifcation technique is used for modelling routing problems within a real-life traffic network. The work facilitates 'driveable' routes. We also provide a simple heuristic for speeding-up Dijkstra's algorithm which does not rely on preprocessing. Our experiments on the UK road network indicate that optimality can be maintained in practice by considering on average only 12% of the search spac