Spatio-temporal networks are spatial networks whose topology and parameters change with time. These networks are important due to many critical applications such as emergency traffic planning and route finding services and there is an immediate need for models that support the design of efficient algorithms for computing the frequent queries on such networks. This problem is challenging due to potentially conflicting requirements of model simplicity and support for efficient algorithms. Time expanded networks which have been used to model dynamic networks employ replication of the network across time instants, resulting in high storage overhead and algorithms that are computationally expensive. In contrast, the proposed time-aggregated graph (TAG) does not replicate nodes and edges across time; rather it allows the properties of edges and nodes to be modeled as a time series. Since the model does not replicate the entire graph for every instant of time, it uses less memory and the algorithms for common operations (e.g. connectivity, shortest path) are computationally more efficient than those for time expanded networks.

One important query on spatio-temporal networks is the computation of shortest paths. Shortest path computation in a time variant network raises many challenges. First new concepts need to be investigated to represent and classify potentially new alternative semantics for common graph operations such as shortest-path and connectivity. For example, a shortest path between a given pair of nodes may have at least two interpretations, one for a given start time-point and the other for the shortest travel-time for any start time in a given time interval. A second challenge is the design of efficient and correct query processing strategies and algorithms since some of the commonly assumed graph-properties may not hold for spatio-temporal graphs. For example, consider the optimal prefix property (required in greedy algorithm such as Dijkstra's algorithm) for shortest paths in a graph. While each prefix path (path from a source node to an intermediate node in an optimal path) is optimal in a static graph, it may not be optimal in a spatio-temporal graph due to a potential wait at an intermediate node.

This thesis proposes algorithms to compute shortest paths in a spatio-temporal network represented as a time aggregated graph. The design strategies that can be adopted is affected by the characteristics of the network such as the nature of the variation of travel time. We propose shortest path algorithms in the contexts of FIFO and non-FIFO networks. We propose a transformation which results in a network where optimal prefix property is satisfied, thus leading to the formulation of a greedy algorithm. Due to the dynamic nature of the graph, the start time choice has an effect on the problem characterization. Shortest path algorithms for a given start time and best start time (least cost paths over the entire time horizon) that exploit the proposed transformation are discussed.

Analytical and experimental evaluations of the model and the algorithms are provided for the sake of comparison with existing models/methods. Experimental results from an evaluation based on road network data show that the proposed approach performs better by an order of magnitude as compared to time expanded graph based methods.