The Efficiency of an online transit trip planning system depends on the underlying network data model and path-finding algorithms. This paper presents a spatiotemporal data model to represent highly dynamic transit network, and two schedule-based shortest path-finding algorithms. The data model was experimented in the traditional entity-relational (ER) approach and the object-oriented (OO) approach. It has been found that the OO model implementation is more efficient and flexible in handling data search, query, update and maintenances, as well as network analysis than the ER model. In the OO data model, the entire transit network and its components are modeled as space-time objects that have starting times, ending times and spans of lifetime. This model enables the construction of network topology on demand by using only active components of the system (i.e., with services available). Two network search algorithms have been developed: the forward search algorithm finds the most efficient path from an origin to a destination with a planned departure time, while the backward search algorithm finds the quickest path for an expected arrival time at the destination. The OO data model and the path-finding algorithms have demonstrated a great performance in path finding on a dynamic transit network as being implemented in an Internet trip planning system in the City of Waukesha, Wisconsin.
Abstract