90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Refine
Year of publication
Document Type
- ZIB-Report (175)
- Master's Thesis (5)
- Bachelor's Thesis (3)
- Doctoral Thesis (2)
- In Proceedings (1)
Has Fulltext
- yes (186) (remove)
Keywords
Institute
- Mathematical Optimization (143)
- Mathematical Optimization Methods (32)
- Network Optimization (20)
- Applied Algorithmic Intelligence Methods (13)
- AI in Society, Science, and Technology (8)
- Mathematics of Telecommunication (7)
- Mathematics of Transportation and Logistics (6)
- ZIB Allgemein (4)
- Mathematical Algorithmic Intelligence (3)
- Numerical Mathematics (3)
Cycle inequalities play an important role in the polyhedral study of the periodic
timetabling problem. We give the first pseudo-polynomial time separation algo-
rithm for cycle inequalities, and we give a rigorous proof for the pseudo-polynomial
time separability of the change-cycle inequalities. Moreover, we provide several
NP-completeness results, indicating that pseudo-polynomial time is best possible.
The efficiency of these cutting planes is demonstrated on real-world instances of the
periodic timetabling problem.
A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable
(2018)
We consider the following planning problem in public transportation: Given a
periodic timetable, how many vehicles are required to operate it?
In [9], for this sequential approach, it is proposed to first expand the periodic
timetable over time, and then answer the above question by solving a flow-based
aperiodic optimization problem.
In this contribution we propose to keep the compact periodic representation of
the timetable and simply solve a particular perfect matching problem. For practical
networks, it is very much likely that the matching problem decomposes into several
connected components. Our key observation is that there is no need to change any
turnaround decision for the vehicles of a line during the day, as long as the timetable
stays exactly the same.
The Cycle Embedding Problem
(2014)
Given two hypergraphs, representing a fine and a coarse "layer", and a cycle cover of the nodes of the coarse layer, the cycle embedding problem (CEP) asks for an embedding of the coarse cycles into the fine layer. The CEP is NP-hard for general hypergraphs, but it can be solved in polynomial time for graphs. We propose an integer rogramming formulation for the CEP that provides a complete escription of the CEP polytope for the graphical case. The CEP comes up in railway vehicle rotation scheduling. We present computational results for problem instances of DB Fernverkehr AG that justify a sequential coarse-first-fine-second planning approach.
Planning and operating railway transportation systems is an extremely
hard task due to the combinatorial complexity of the underlying discrete
optimization problems, the technical intricacies, and the immense size of
the problem instances. Because of that, however, mathematical models
and optimization techniques can result in large gains for both railway cus-
tomers and operators, e.g., in terms of cost reductions or service quality
improvements. In the last years a large and growing group of researchers
in the OR community have devoted their attention to this domain devel-
oping mathematical models and optimization approaches to tackle many
of the relevant problems in the railway planning process. However, there
is still a gap to bridge between theory and practice, with
a few notable exceptions. In this paper we address three success stories,
namely, long-term freight train routing (part I), mid-term rolling stock
rotation planning (part II), and real-time train dispatching (part III). In
each case, we describe real-life, successful implementations. We will dis-
cuss the individual problem setting, survey the optimization literature,
and focus on particular aspects addressed by the mathematical models.
We demonstrate on concrete applications how mathematical optimization
can support railway planning and operations. This gives proof that math-
ematical optimization can support the planning of rolling stock resources.
Thus, mathematical models and optimization can lead to a greater effi-
ciency of railway operations and will serve as a powerful and innovative
tool to meet recent challenges of the railway industry.
We introduce a concurrent solver for the periodic event scheduling problem (PESP). It combines mixed integer programming techniques, the modulo network simplex method, satisfiability approaches, and a new heuristic based on maximum cuts. Running these components in parallel speeds up the overall solution process. This enables us to significantly improve the current upper and lower bounds for all benchmark instances of the library PESPlib.
The Rolling Stock Rotation Problem is to schedule rail vehicles in order to cover timetabled trips by a cost optimal set of vehicle rotations. The problem integrates several facets of railway optimization, i.e., vehicle composition, maintenance constraints, and regularity aspects.
In industrial applications existing schedules often have to be re-optimized to integrate timetable changes or construction sites.
We present an integrated modeling and algorithmic approach for this task as well as computational results for industrial problem instances of DB Fernverkehr AG.
We propose a game theoretic model for the spatial distribution of inspectors on a
transportation network.
The problem is to spread out the controls so as to enforce the payment of a transit
toll. We formulate a linear program to find
the control distribution which maximizes the expected toll revenue,
and a mixed integer program for the problem of minimizing
the number of evaders. Furthermore, we show that the problem of finding an optimal
mixed strategy for a coalition of $N$ inspectors can be solved
efficiently by a column generation procedure. Finally, we give experimental results
from an application to the truck toll on German motorways.
We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design
efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor
details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems.
Duty rostering problems occur in different application contexts and come in different flavors. They give rise to very large scale integer programs which ypically have lots of solutions and extremely fractional LP relaxations. In such a situation, heuristics
can be a viable algorithmic choice. We propose an mprovement method of the Lin-Kernighan type for the solution of duty rostering problems. We illustrate its versatility and solution quality on three different applications in public transit, vehicle routing, and
airline rostering with a focus on the management of preferences, fairness, and fatigue, respectively.
We propose a model for the integrated optimization of vehicle
rotations and vehicle 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 computationally 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 cooperation partner DB
Fernverkehr can be solved.
We study an extension of the shortest path network interdiction problem and present a novel real-world application in this area. We consider the problem of determining optimal locations for toll control stations on the arcs of a transportation network. We handle the fact that drivers can avoid control stations on parallel secondary roads. The problem is formulated as a mixed integer program and solved using Benders decomposition. We present experimental results for the application of our models to German motorways.
The covering of a graph with (possibly disjoint) connected subgraphs is a fundamental problem in graph theory. In this paper, we study a version to cover a graph's vertices by connected subgraphs subject to lower and upper weight bounds, and propose a column generation approach to dynamically generate feasible and promising subgraphs. Our focus is on the solution of the pricing problem which turns out to be a variant of the NP-hard Maximum Weight Connected Subgraph Problem. We compare different formulations to handle connectivity, and find that a single-commodity flow formulation performs best. This is notable since the respective literature seems to have dismissed this formulation. We improve it to a new coarse-to-fine flow formulation that is theoretically and computationally superior, especially for large instances with many vertices of degree 2 like highway networks, where it provides a speed-up factor of 10 over the non-flow-based formulations. We also propose a preprocessing method that exploits a median property of weight constrained subgraphs, a primal heuristic, and a local search heuristic. In an extensive computational study we evaluate the presented connectivity formulations on different classes of instances, and demonstrate the effectiveness of the proposed enhancements. Their speed-ups essentially multiply to an overall factor of 20. Overall, our approach allows the reliabe solution of instances with several hundreds of nodes in a few minutes. These findings are further corroborated in a comparison to existing districting models on a set of test instances from the literature.
Balanced separators are node sets that split the graph into size bounded components. They find applications in different theoretical and practical problems. In this paper we discuss how to find a minimum set of balanced separators in node weighted graphs. Our contribution is a new and exact algorithm that solves Minimum Balanced Separators by a sequence of Hitting Set problems. The only other exact method appears to be a mixed-integer program (MIP) for the edge weighted case. We adapt this model to node weighted graphs and compare it to our approach on a set of instances, resembling transit networks. It shows that our algorithm is far superior on almost all test instances.
The Periodic Event Scheduling Problem (PESP) is a notoriously hard combinatorial optimization problem, essential for the design of periodic timetables in public transportation. The coefficients of the integer variables in the standard mixed integer linear programming formulations of PESP are the period time, e.g., 60 for a horizon of one hour with a resolution of one minute. In many application scenarios, lines with different frequencies have to be scheduled, leading to period times with many divisors. It then seems natural to consider derived instances, where the period time is a divisor of the original one, thereby smaller, and bounds are scaled and rounded accordingly. To this end, we identify two rounding schemes: wide and tight. We then discuss the approximation performance of both strategies, in theory and practice.
The Graduate-Level Research in Industrial Projects (G-RIPS) Program provides an
opportunity for high-achieving graduate-level students to work in teams on a
real-world research project proposed by a sponsor from industry or the public
sector. Each G-RIPS team consists of four international students (two from
the US and two from European universities), an academic mentor, and an industrial sponsor.
This is the report of the Rail-Lab project on the definition and integration of
robustness aspects into optimizing rolling stock schedules. In general, there is
a trade-off for complex systems between robustness and efficiency. The ambitious
goal was to explore this trade-off by implementing numerical simulations and
developing analytic models.
In rolling stock planning a very large set of industrial railway requirements,
such as vehicle composition, maintenance constraints, infrastructure capacity,
and regularity aspects, have to be considered in an integrated model. General
hypergraphs provide the modeling power to tackle those requirements.
Furthermore, integer programming approaches are able to produce high quality
solutions for the deterministic problem.
When stochastic time delays are considered, the mathematical programming problem
is much more complex and presents additional challenges. Thus, we started with a
basic variant of the deterministic case, i.e., we are only considering
hypergraphs representing vehicle composition and regularity.
We transfered solution approaches for robust optimization
from the airline industry to the setting of railways and attained a
reasonable measure of robustness. Finally, we present and discuss different
methods to optimize this robustness measure.
Current linear energy system models (ESM) acquiring to provide sufficient detail and reliability frequently bring along problems of both high intricacy and increasing scale. Unfortunately, the size and complexity of these problems often prove to be intractable even for commercial state-of-the-art linear programming solvers. This article describes an interdisciplinary approach to exploit the intrinsic structure of these large-scale linear problems to be able to solve them on massively parallel high-performance computers. A key aspect are extensions to the parallel interior-point solver PIPS-IPM originally developed for stochastic optimization problems. Furthermore, a newly developed GAMS interface to the solver as well as some GAMS language extensions to model block-structured problems will be described.
In this paper, we consider the Cyclic Crew Rostering Problem with Fairness Requirements (CCRP-FR). In this problem, attractive cyclic rosters have to be constructed for groups of employees, considering multiple, a priori determined, fairness levels. The attractiveness follows from the structure of the rosters (e.g., sufficient rest times and variation in work), whereas fairness is based on the work allocation among the different roster groups. We propose a three-phase heuristic for the CCRP-FR, which combines the strength of column generation techniques with a large-scale neighborhood search algorithm. The design of the heuristic assures that good solutions for all fairness levels are obtained quickly, and can still be further improved if additional running time is available. We evaluate the performance of the algorithm using real-world data from Netherlands Railways, and show that the heuristic finds close to optimal solutions for many of the considered instances. In particular, we show that the heuristic is able to quickly find major improvements upon the current sequential practice: For most instances, the heuristic is able to increase the attractiveness by at least 20% in just a few minutes.
The Scenario Technique is a strategic planning method that aims to describe and analyze potential developments of a considered system in the future. Its application consists of several steps, from an initial problem analysis over an influence analysis to projections of key factors and a definition of the scenarios to a final interpretation of the results. The technique itself combines qualitative and quantitative methods and is an enhancement of the standard Scenario Technique. We use the numerical values gathered during the influence analysis, and embed them in a System Dynamics framework. This yields a mathematically rigorous way to achieve predictions of the system‘s future behavior from an initial impulse and the feedback structure of the factors. The outcome of our new method is a further way of projecting the present into the future, which enables the user of the Scenario Technique to obtain a validation of the results achieved by the standard method.
This thesis represents a game-theoretic investigation of the allocation of inspectors in a transportation network, comparing Nash and Stackelberg equilibrium strategies to a strategy in which inspections are conducted proportionally to the traffic volume. It contains specifications for the integration of space and time dependencies and extensive experimental tests for the application on the transportation network of German motorways using real data. Main results are that - although the formulated spot-checking game is not zero-sum - we are able to compute a Nash equilibrium using linear programming and secondly, that experimental results yield that a Nash equilibrium strategy represents a good trade-off for the Stackelberg equilibrium strategy between efficiency of controls and computation time.