Summary:
Though the problem of finding the best (quickest) path in an urban transit
system is related to some degree to the problem of finding the best route in a
road network, the first problem is not addressed adequately from the classic
graph solving algorithms that are used to solve the second problem. An
important difference between these two problems is the temporal dimension
introduced by the first problem.
A road network can be represented by a directed graph and the optimal route
between two points can be found using a classical algorithm (Dijkstra, A *). An
urban transit system is served by a set of lines each of which consists of a
set of services that can be changed depending on the day and time according to
the transit system schedule. The transit system is described by the set of
stops, routes, trips and the timetable of each trip. Finding the optimal path
depends not only on the topology of the network formed by the stops of the
system, but also on the temporal relevance of the means of transport crossing
them.
This essay proposes an algorithm for finding the best route (and any
alternative paths with similar costs) in a transit system. In contrast to the
classical graph-solving algorithms which examine subsequent nodes of the graph,
the search for the optimal path is performed estimating the cost of the paths
formed by successive (spatially and temporally) subsets services as reflected
in the schedule of the trips of the transit system.
As part of this work, the proposed algorithm has been implemented and can be
run from a web interface finding the best transit schedule between two
locations for a given time of departure for the cities of San Francisco and
Athens.
Keywords:
Transit System, Trip Planning, GIS, Route, Algorithm
