We study the problem of computing all Pareto-optimal journeys in a public transit network regarding the two criteria of arrival time and number of transfers taken. We take a novel approach, focusing on trips and transfers between them, allowing fine-grained modeling. Our experiments on the metropolitan network of London show that the algorithm computes full 24-hour profiles in 70ms after a preprocessing phase of 30s, allowing fast queries in dynamic scenarios.
The time-dependent approach produces much smaller graphs in comparison. In the simple model, nodes correspond to stops. Edges no longer have constant weight, but are instead associated with (piecewise linear) travel time functions, which map departure times to travel times (or, equivalently, arrival times). The weight then depends on the time at which this function is evaluated. This model can be extended to allow for minimum change times by adding a node for each line at each stop @cite_14 . Some speedup techniques have been applied successfully to time-dependent graphs, such as ALT @cite_1 and Contraction @cite_8 , although not for multi-criteria problems. For these, several extensions to Dijkstra's algorithm exist, among them the @cite_4 , the @cite_13 , the @cite_0 , and the @cite_9 algorithms. However, as Dijkstra-variants, each of them has to perform rather costly priority queue operations.
@cite_14 @cite_4 @cite_8 @cite_9 @cite_1 @cite_0 @cite_13
1964915778 119169328 1908662580 2021134775 2110861948 2189110458
We consider two approaches that model timetable information in public transportation systems as shortest-path problems in weighted graphs. In the time-expanded approach, every event at a station, e.g., the departure of a train, is modeled as a node in the graph, while in the time-dependent approach the graph contains only one node per station. Both approaches have been recently considered for (a simplified version of) the earliest arrival problem, but little is known about their relative performance. Thus far, there are only theoretical arguments in favor of the time-dependent approach. In this paper, we provide the first extensive experimental comparison of the two approaches. Using several real-world data sets, we evaluate the performance of the basic models and of several new extensions towards realistic modeling. Furthermore, new insights on solving bicriteria optimization problems in both models are presented. The time-expanded approach turns out to be more robust for modeling more complex scenarios, whereas the time-dependent approach shows a clearly better performance. Bicriterion path problems in directed graphs are systematically studied. A series of ten problems are defined and their computational complexity examined. Algorithms are provided for some of them, including polynomial algorithms for the MAXMIN-MAXMIN problem and the MINSUM-MAXMIN problem, and a pseudo-polynomial exact algorithm as well as a fully polynomial approximation scheme for the MINSUM-MINSUM problem. We contribute a fast routing algorithm for timetable networks with realistic transfer times. In this setting, our algorithm is the first one that successfully applies precomputation based on node contraction: gradually removing nodes from the graph and adding shortcuts to preserve shortest paths. This reduces query times to 0.5 ms with preprocessing times below 4 minutes on all tested instances, even on continental networks with 30 000 stations. We achieve this by an improved contraction algorithm and by using a station graph model. Every node in our graph has a one-to-one correspondence to a station and every edge has an assigned collection of connections. Also, our graph model does not require parallel edges. Exploiting parallelism in route planning algorithms is a challenging algorithmic problem with obvious applications in mobile navigation and timetable information systems. In this work, we present a novel algorithm for the one-to-all profile-search problem in public transportation networks. It answers the question for all fastest connections between a given station S and any other station at any time of the day in a single query. This algorithm allows for a very natural parallelization, yielding excellent speed-ups on standard multicore servers. Our approach exploits the facts that, first, time-dependent travel-time functions in such networks can be represented as a special class of piecewise linear functions and, second, only few connections from S are useful to travel far away. Introducing the connection-setting property, we are able to extend Dijkstra's algorithm in a sound manner. Furthermore, we also accelerate station-to-station queries by preprocessing important connections within the public transportation network. As a result, we are able to compute all relevant connections between two random stations in a complete public transportation network of a big city (New York) on a standard multi-core server in real time. Abstract We consider efficient algorithms for exact time-table queries, i.e. algorithms that find optimal itineraries for travelers using a train system. We propose to use time-dependent networks as a model and show advantages of this approach over space-time networks as models. We consider the problem of computing shortest paths through a dynamic network – a network with time-varying characteristics, such as arc travel times and costs, which are known for all values of time. Many types of networks, most notably transportation networks, exhibit such predictable dynamic behavior over the course of time. Dynamic shortest path problems are currently solved in practice by algorithms which operate within a discrete-time framework. In this thesis, we introduce a new set of algorithms for computing shortest paths in continuous-time dynamic networks, and demonstrate for the first time in the literature the feasibility and the advantages of solving dynamic shortest path problems in continuous time. We assume that all time-dependent network data functions are given as piece-wise linear functions of time, a representation capable of easily modeling most common dynamic problems. Additionally, this form of representation and the solution algorithms developed in this thesis are well suited for many augmented static problems such as time-constrained minimum-cost shortest path problems and shortest path problems with time windows. We discuss the classification, formulation, and mathematical properties of all common variants of the continuous-time dynamic shortest path problem. Two classes of solution algorithms are introduced, both of which are shown to solve all variants of the problem. In problems where arc travel time functions exhibit First-In-First-Out (FIFO) behavior, we show that these algorithms have polynomial running time; although the general problem is NP-hard, we argue that the average-case running time for many common problems should be quite reasonable. Computational results are given which support the theoretical analysis of these algorithms, and which provide a comparison with existing discrete-time algorithms; in most cases, continuous-time approaches are shown to be much more efficient, both in running time and storage requirements, than their discretetime counterparts. Finally, in order to further reduce computation time, we introduce parallel algorithms, and hybrid continuous-discrete approximation algorithms which exploit favorable characteristics of algorithms from both domains. Thesis Supervisor: Ismail Chabini Title: Assistant Professor, Department of Civil and Environmental Engineering, Massachusetts Institute of Technology