Refine
Year of publication
Document Type
- ZIB-Report (52)
- In Proceedings (38)
- Article (22)
- Book chapter (3)
- Book (1)
- Doctoral Thesis (1)
- Master's Thesis (1)
- Other (1)
Language
- English (119)
Keywords
- column generation (4)
- integer programming (4)
- network aggregation (4)
- rapid branching (4)
- Railway Track Allocation (3)
- railway track allocation (3)
- Column Generation (2)
- Fahrplanung (2)
- Netzwerkaggregation (2)
- Optimization (2)
Institute
This book promotes the use of mathematical optimization and operations research methods in rail transportation. The editors assembled thirteen contributions from leading scholars to present a unified voice, standardize terminology, and assess the state-of-the-art.
There are three main clusters of articles, corresponding to the classical stages of the planning process: strategic, tactical, and operational. These three clusters are further subdivided into five parts which correspond to the main phases of the railway network planning process: network assessment, capacity planning, timetabling, resource planning, and operational planning. Individual chapters cover:
Simulation
Capacity Assessment
Network Design
Train Routing
Robust Timetabling
Event Scheduling
Track Allocation
Blocking
Shunting
Rolling Stock
Crew Scheduling
Dispatching
Delay Propagation
Since railway companies have to apply for long-term public contracts to operate railway lines in public tenders, the question how they can estimate the operating cost for long-term periods adequately arises naturally. We consider a rolling stock rotation problem for a time period of ten years, which is based on a real world instance provided by an industry partner. We use a two stage approach for the cost estimation of the required rolling stock. In the first stage, we determine a weekly rotation plan. In the second stage, we roll out this weekly rotation plan for a longer time period and incorporate scheduled maintenance treatments. We present a heuristic approach and a mixed integer programming model to implement the process of the second stage. Finally, we discuss computational results for a real world tendering scenario.
Given a directed, acyclic graph, a source and a sink node, and a set of forbidden pairs of arcs, the path avoiding forbidden pairs (PAFP) problem is to find a path that connects the source and sink nodes and contains at most one arc from each forbidden pair. The general version of the problem is NP-hard, but it becomes polynomially solvable for certain topological configurations of the pairs. We present the first polyhedral study of the PAFP problem. We introduce a new family of valid inequalities for the PAFP polytope and show that they are sufficient to provide a complete linear description in the special case where the forbidden pairs satisfy a disjointness property. Furthermore, we show that the number of facets of the PAFP polytope is exponential in the size of the graph, even for the case of a single forbidden pair.
Real world routing problems, e.g., in the airline industry or in public and rail transit, can feature complex non-linear cost functions. An important case are costs for crossing regions, such as countries or fare zones. We introduce the shortest path problem with crossing costs (SPPCC) to address such situations; it generalizes the classical shortest path problem and variants such as the resource constrained shortest path problem and the minimum label path problem. Motivated by an application in flight trajectory optimization with overflight costs, we focus on the case in which the crossing costs of a region depend only on the nodes used to enter or exit it. We propose an exact Two-Layer-Dijkstra Algorithm as well as a novel cost-projection linearization technique that approximates crossing costs by shadow costs on individual arcs, thus reducing the SPPCC to a standard shortest path problem. We evaluate all algorithms’ performance on real-world flight trajectory optimization instances, obtaining very good à posteriori error bounds.
Real world routing problems, e.g., in the airline industry or in public and rail transit, can feature complex non-linear cost functions. An important case are costs for crossing regions, such as countries or fare zones. We introduce the shortest path problem with crossing costs (SPPCC) to address such situations; it generalizes the classical shortest path problem and variants such as the resource constrained shortest path problem and the minimum label path problem. Motivated by an application in flight trajectory optimization with overflight costs, we focus on the case in which the crossing costs of a region depend only on the nodes used to enter or exit it. We propose an exact Two-Layer-Dijkstra Algorithm as well as a novel cost-projection linearization technique that approximates crossing costs by shadow costs on individual arcs, thus reducing the SPPCC to a standard shortest path problem. We evaluate all algorithms’ performance on real-world flight trajectory optimization instances, obtaining very good à posteriori error bounds.
We study the Flight Planning Problem for a single aircraft, which deals with finding a path of minimal travel time in an airway network. Flight time along arcs is affected by wind speed and direction, which are functions of time. We consider three variants of the problem, which can be modeled as, respectively, a classical shortest path problem in a metric space, a time-dependent shortest path problem with piecewise linear travel time functions, and a time-dependent shortest path problem with piecewise differentiable travel time functions. The shortest path problem and its time-dependent variant have been extensively studied, in particular, for road networks. Airway networks, however, have different characteristics: the average node degree is higher and shortest paths usually have only few arcs. We propose A* algorithms for each of the problem variants. In particular, for the third problem, we introduce an application-specific "super-optimal wind" potential function that overestimates optimal wind conditions on each arc, and establish a linear error bound. We compare the performance of our methods with the standard Dijkstra algorithm and the Contraction Hierarchies (CHs) algorithm. Our computational results on real world instances show that CHs do not perform as well as on road networks. On the other hand, A* guided by our potentials yields very good results. In particular, for the case of piecewise linear travel time functions, we achieve query times about 15 times shorter than CHs.
We introduce the shortest path problem with crossing costs (SPPCC), a shortest path problem in a directed graph, in which the objective function is the sum of arc weights and crossing costs. The former are independently paid for each arc used by the path, the latter need to be paid every time the path intersects certain sets of arcs, which we call regions.
The SPPCC generalizes not only the classical shortest path problem but also variants such as the resource constrained shortest path problem and the minimum label path problem. We use the SPPCC to model the flight trajectory optimization problem with overflight costs.
In this paper, we provide a comprehensive analysis of the problem. In particular,
we identify efficient exact and approximation algorithms for the cases that are most relevant in practice.
A common technique in the solution of large or complex optimization problems is the use of micro-macro transformations. In this paper, we carry out a theoretical analysis of such transformations for the track allocation problem in railway networks. We prove that the cumulative rounding technique of Schlechte et al. satisfies two of three natural optimality criteria and that this performance cannot be improved. We also show that under extreme circumstances, this technique can perform inconvieniently by underestimating the global optimal value.
A common technique in the solution of large or complex optimization problems is the use of micro–macro transformations. In this paper, we carry out a theoretical analysis of such transformations for the track allocation problem in railway networks. We prove that the cumulative rounding technique of Schlechte et al. satisfies two of three natural optimality criteria and that this performance cannot be improved. We also show that under extreme circumstances, this technique can perform inconveniently by underestimating the global optimal value.
Bus rapid transit systems in developing and newly industrialized countries often consist of a trunk with a path topology. On this trunk, several overlapping lines are operated
which provide direct connections. The demand varies heavily over the day, with morning and afternoon peaks typically in reverse directions. We propose an integer programming model for this problem, derive a structural property of line plans in the static (or single period) ``unimodal demand'' case, and consider approaches to the solution of the multi-period version that rely on clustering the demand into peak and off-peak service periods. An application to the Metrobüs system of Istanbul is discussed.