OPTIMAL ROUTING IN A TRANSPORTATION NETWORK

This paper investigates a routing problem in a public transportation network, more precisely the problem of finding an optimal journey plan in a transportation network, given a timetable. The following issues are discussed: a graph model of a transportation network that takes into account changes of means of transport in a non-zero time; reduction of a large network to a network with a smaller number of nodes and arcs, and algorithms that find an optimal connection by different optimality criteria given. It is shown that the routing problem is closely related to the shortest-path problem in a weighted graph. However, well-known graph-theory algorithms cannot be directly applied as the time factor and the effect of changing means of transport require a specific approach. Moreover, miscellaneous constraints may be imposed on the set of acceptable routes. An implementation of the presented approach in a commercial routing program has been described.