TIME DEPENDING SHORTEST-PATH PROBLEMS WITH APPLICATIONS TO RAILWAY NETWORKS

In this paper the shortest path problem in a time depending transit network is discussed. A usual approach in public transport is to compute the shortest path for every possible starting time separately by the use of a modified Dijkstra procedure. Here a label correcting method is used to calculate the desired transit function for all starting times with one path search procedure. The methods discussed in the general theory of algebraic path problems are not efficient for the case that we only want to have the transit function between two specific vertices. We generalize AI search techniques to get a more efficient one-to-one method.