Abstract: Railway dispatchers reschedule trains in real-time in order to limit the propagation of disturbances and to regulate traffic in their respective dispatching areas by minimizing the deviation from the off-line timetable. However, the decisions taken in one area may influence the quality and even the feasibility of train schedules in the other areas. Regional control centers coordinate the dispatchers’ work for multiple areas in order to regulate traffic at the global level and to avoid situations of global infeasibility. Differently from the dispatcher problem, the coordination activity of regional control centers is still underinvestigated, even if this activity is a key factor for effective traffic management. This paper studies the problem of coordinating several dispatchers with the objective of driving their behavior towards globally optimal solutions. With our model, a coordinator may impose constraints at the border of each dispatching area. Each dispatcher must then schedule trains in its area by producing a locally feasible solution compliant with the border constraints imposed by the coordinator. The problem faced by the coordinator is therefore a bilevel programming problem in which the variables controlled by the coordinator are the border constraints. We demonstrate that the coordinator problem can be solved to optimality with a branch and bound procedure. The coordination algorithm has been tested on a large real railway network in the Netherlands with busy traffic conditions. Our experimental results show that a proven optimal solution is frequently found for various network divisions within computation times compatible with real-time operations.

Abstract: Inland waterways form a natural network that is an existing, congestion free infrastructure with capacity for more traffic. The European commission promotes the transportation of goods by ship as it is a reliable, efficient and environmental friendly way of transport. A bottleneck for transportation over water are the locks that manage the water level. The lockmaster's problem concerns the optimal strategy for operating such a lock. In the lockmaster's problem we are given a lock, a set of ships coming from downstream that want to go upstream, and another set of ships coming from upstream that want to go downstream. We are given the arrival times of the ships and a constant lockage time; the goal is to minimize total waiting time of the ships. In this paper a dynamic programming algorithm (DP) is proposed that solves the lockmaster's problem in polynomial time. We  extend this DP to different generalizations that consider weights, water usage, capacity, and (a fixed number of) multiple chambers. Finally, we prove that the problem becomes strongly NP-hard when the number of chambers is part of the input.

Abstract: In this paper, we consider rail-freight hump yards and the process of forming outbound freight trains from cars of inbound freight trains. Given the arrival times and the composition of the inbound trains, and the departure times and the composition of the outbound trains, we study the problem of allocating and reserving classification tracks for the outbound trains such that every outbound train is built on a single classification track. We focus on an extension where individual cars can temporarily be stored on a special subset of the tracks (the ``mixed tracks''). This practice allows the reservation times of classification tracks to be shorter, which in turn allows for more outbound trains to be assigned to a track. We observe that the core problem can be formulated as a special list coloring problem of interval graphs, which is known to be NP-complete. The problem we study induces several new variants of the list-coloring problem, in which the given intervals can be shortened by cutting-off a prefix of the interval. We show that such a problem can be solved in polynomial time, if the goal is to minimize the total cut-off.  Based on these results, we devise two heuristics to tackle the problem, which we empirically evaluate on real-world instances. We further design a mixed integer program for the problem and apply it in the experiments. As a case study, we consider a real-world problem instance from the Hallsberg Rangerbang\r{a}rd hump yard in Sweden. Planning over horizons of seven days, we obtain feasible solutions from the mixed integer program that allow all outbound trains to leave on time. The heuristics deliver schedules that require as much as 3.4 times the allowed capacity of the mixed tracks.

Abstract: We study the problem of computing batched shortest paths on road networks efficiently. Our focus is on computing paths from a single source to multiple targets (one-to-many queries). We perform a comprehensive experimental comparison of several approaches, including new ones. We conclude that an extension of PHAST (a recent one-to-all algorithm), called RPHAST, has the best performance in most cases, often by orders of magnitude. When used to compute distance tables (many-to-many queries), RPHAST often outperforms all previous approaches.

Abstract: Shortest paths on road networks can be efficiently calculated using Dijkstra's algorithm (D). In addition to roads, multi-modal transportation networks include public transportation, walking paths, bicycle lanes, etc. For paths on this type of network, further constraints, e.g., preferences in using certain modes of transportation, may arise. The regular language constraint shortest path problem deals with this kind of problem. It uses a regular language to model the   constraints. The problem can then be solved efficiently by using a generalization of Dijkstra's algorithm (DREGLC). In recent years, much focus has been given to accelerate D on large road graphs. DREGLC has received less attention and only a few methods have been described.  In this paper we propose an adaption of the speed-up technique uniALT, in order to accelerate DREGLC. We call our algorithm SDALT. We provide experimental results on a realistic multi-modal public transportation network including time-dependent as well as time-independent cost functions on arcs. It consists of five layers: private bike, rental bike, walking, car (including changing traffic conditions) and public transportation. The experiments show that our algorithm performs well, with speed-ups of 2 to 20, with respect to plain DREGLC without speed-up.

Abstract: In timetable information in public transport the goal is to search for a good  passenger's path between an origin and a destination. Usually, the travel time and the number of transfers shall be minimized. In this paper, we consider robust timetable information, i.e. we want to identify a path which will bring the passenger to the planned destination even in the case of delays.The classic notion of strict robustness leads to the problem of identifying those changing activities which will never break in any of the expected delay scenarios. We show that this is in general a strongly NP-hard problem. Therefore, we propose a conservative heuristic which identifies a large subset of these robust changing activities in polynomial time by dynamic programming and so allows us to find strictly robust paths efficiently. We also transfer the notion of light robustness, originally introduced for timetabling, to timetable information. In computational experiments we then study the price of strict and light robustness: How much longer is the travel time of a robust path than of a shortest one according to the published schedule?
Based on the schedule of high-speed trains within Germany of 2011, we quantitatively explore the trade-off between the level of guaranteed robustness and the increase in travel time. Strict robustness turns out to be too conservative, while light robustness is promising: a modest level of guarantees is achievable  at a reasonable price for the majority of passengers.

Abstract: The question of delay management is whether trains should wait for delayed feeder trains or should depart on time. Solutions to this problem strongly depend on the capacity constraints of the tracks making sure that no two trains can use the same piece of track at the same time. While these capacity constraints have been included in integer programming formulations for the delay management problem, the capacity constraints of the stations (only offering a limited number of platforms) have been neglected so far. This can lead to highly infeasible solutions. To overcome this problem we suggest two new formulations of the delay management problem both including the stations' capacities. We present numerical results showing that the assignment-based formulation is clearly superior to the packing formulation. We furthermore propose an iterative algorithm in which we improve the platform assignment with respect to the current delays of the trains at each station in each step. We will show that this subproblem asks for coloring the nodes of a graph with a given number of colors while minimizing the weight of the conflicts. We show that the graph to be colored is an interval graph and that the problem can be solved in polynomial time by presenting a totally unimodular IP formulation.

Abstract: In daily operation, railway traffic always deviates from the planned schedule to a certain extent. Primary initial delays of trains may cause a whole cascade of secondary delays of other trains over the entire network. In this paper, we propose a  stochastic model for delay propagation and forecasts of arrival and departure events which is applicable to all kind of public transport (not only to railway traffic). Our model is fully realistic, it includes general waiting policies (how long do trains wait for delayed feeder trains), it uses driving time profiles (discrete distributions) on travel arcs which depend on the departure time, and it incorporates the catch-up potential of buffer times on driving sections and train stops. The model is suited for an online scenario where a massive stream of update messages on the current status of trains arrives which has to be propagated through the whole network. Efficient stochastic propagation of delays has important applications in online timetable information, in delay management and train disposition, and in stability analysis of timetables.
The proposed approach has been implemented and evaluated on the German timetable of 2011 with waiting policies of Deutsche Bahn AG. A complete stochastic delay propagation for the whole German train network and a whole day can be performed in less than 14 seconds on a PC. We tested our propagation algorithm with artificial discrete travel time distributions which can be parameterized by the size of their fluctuations. Our forecasts are compared with real data. It turns out that stochastic propagation of delays is efficient enough to be applicable in practice, but the forecast quality requires further adjustments of our artificial travel time distributions to estimates from real data.

Abstract: The pooling problem is an important global optimization problem which is encountered in many industrial settings. It is traditionally modeled as a bilinear, nonconvex optimization problem, and solved by branch-and-bound  algorithms where the subproblems are convex. In some industrial applications, for instance in pipeline transportation of natural gas, a different modeling approach is often made. Rather than defining it as a bilinear problem, the range of qualities is discretized, and the complicating constraints are replaced by linear ones involving integer variables. Consequently, the pooling problem is approximated by a mixed-integer programming problem. With a coarse discretization, this approach represents a saving in computational effort, but may also lead to less accurate modeling. Justified guidelines for choosing between a bilinear and a discrete model seem to be scarce in the pooling problem literature. In the present work, we study discretized versions of models that have been proved to work well when formulated as bilinear programs. Through extensive numerical experiments, we compare the discrete models to their continuous ancestors. In particular, we study how the level of discretization must be chosen if a discrete model is going to be competitive in both running time and accuracy.

Abstract: We study the effect of perturbations on the Price of Anarchy for the Traffic Assignment Problem. Adopting the smoothed analysis approach, we randomly perturb the latency functions of the given network and estimate the expected Price of Anarchy on the perturbed instances. We provide both theoretical and experimental results that show that the Smoothed Price of Anarchy is of the same order of magnitude as the original one.

Abstract: The primary objective of this paper is to introduce Fuzzy Rule-Based Systems (FRBSs) as a relatively new technology into airport transportation research, with a special emphasis on ground movement operations. Hence, a Mamdani FRBS with the capability to learn from data has been adopted for taxi time estimations at Zurich Airport (ZRH). Linear regression is currently the dominating technique for such an estimation task due to its established nature, proven mathematical characteristics and straightforward explanatory ability. In this study, we demonstrate that FRBSs, although having a more complex structure, can offer more accurate estimations due to their proven properties as nonlinear universal approximators. Furthermore, such improvements in accuracy do not come at the cost of the model’s interpretability. FRBSs can offer more explanations of the underlying behavior in different regions. Preliminary results on data for ZRH confirmed and suggest that FRBSs are a valuable alternative to already established linear regression methods. FRBSs have great potential to be further seamlessly integrated into the taxiway routing and scheduling process due to the fact that more information is now available in the explanatory variable space.

Abstract: We propose a model for the integrated optimization of vehicle rotations and train compositions in long distance railway passenger transport. The main contribution of the paper is a hypergraph model that is able to handle the challenging technical requirements as well as very general stipulations with respect to the ``regularity'' of a schedule. The hypergraph model directly generalizes network flow models, replacing arcs with hyperarcs. Although NP-hard in general, the model is compuationally well-behaved in practice.  High quality solutions can be produced in reasonable time using high performance Integer Programming techniques, in particular, column generation and rapid branching.  We show that, in this way, large-scale real world instances of our cooperations partner DB Fernverkehr can be solved.