Weighting the path continuation in route planning

Abstract

Shortest path algorithms optimize the costs of a journey in a graph. The cost function may differ; in geometric contexts for instance the travel distance, the travel time, or travel expenses are considered. Not considered so far are costs that are related to the combination of incident edges for a path. For example, if one is interested in continuing a route from a given edge with the turn of least angle, each continuation by an incident edge has to be weighted by the angle enclosed. Such cost functions produce a combinatorial complex number of weights that cannot be stored with the edges or nodes in the graph. Instead they lead to an optimization problem in a linear dual graph, for which th..