[Back]

S. Winter:
"Route Specifications with a Linear Dual Graph";
in: "Advances in Spatial Data Handling", Springer, 2002, 329 - 338.

Web-based route planners find an optimal route in the network of a given mode of transport searching for the cheapest route corresponding to any cost function. For trips not all desired route properties can be satisfied by this way. I will propose a solution for planning hiking trips. The method can easily be transferred to tourist guides in urban areas, to advices for taking a drive, or to similar contexts. These applications will become more and more relevant in our mobile leisure society.
Planning a hiking route is based primarily on the intended length of the trip, and then on the decision whether start and destination need to coincide or. That means planning trips represents neither exactly a shortest path nor a traveling salesman problem. I propose an approach based on k shortest path algorithms.
The problem with this approach lies in the fact that hikers accept (and need) trip proposals which would never be provided by a shortest path algorithm: round tours, routes including cycles, or routes where a route segment has to be passed in both directions. A surprising simple solution for these requirements promises a linear dual graph: applying a k shortest path algorithm on the linear dual graph will produce realistic route tips.

http://aleph.ub.tuwien.ac.at/F?base=tuw01&func=find-c&ccl_term=AC04404201

ftp://ftp.geoinfo.tuwien.ac.at/winter/winter02route.pdf