TIME DEPENDING SHORTEST-PATH PROBLEMS WITH APPLICATIONS TO RAILWAY NETWORKS

In this paper the shortest path problem in a time depending transit ne twork 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 i s used to calculate the desired transit function for all starting time s 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 vertic es. We generalize AI search techniques to get a more efficient one-to- one method.