@inproceedings{BorndoerferSagnolSchwartz2016, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Schwartz, Stephan}, title = {An Extended Network Interdiction Problem for Optimal Toll Control}, volume = {52}, booktitle = {INOC 2015 - 7th International Network Optimization Conference}, doi = {10.1016/j.endm.2016.03.040}, pages = {301 -- 308}, year = {2016}, abstract = {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.}, language = {en} } @misc{SchadeSchlechteWitzig2017, author = {Schade, Stanley and Schlechte, Thomas and Witzig, Jakob}, title = {Structure-based Decomposition for Pattern-Detection for Railway Timetables}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-64525}, year = {2017}, abstract = {We consider the problem of pattern detection in large scale railway timetables. This problem arises in rolling stock optimization planning in order to identify invariant sections of the timetable for which a cyclic rotation plan is adequate. We propose a dual reduction technique which leads to an decomposition and enumeration method. Computational results for real world instances demonstrate that the method is able to produce optimal solutions as fast as standard MIP solvers.}, language = {en} } @misc{BorndoerferHoppmannKarbsteinetal.2016, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika and L{\"o}bel, Fabian}, title = {The Modulo Network Simplex with Integrated Passenger Routing}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-60319}, year = {2016}, abstract = {Periodic timetabling is an important strategic planning problem in public transport. The task is to determine periodic arrival and departure times of the lines in a given network, minimizing the travel time of the passengers. We extend the modulo network simplex method, a well-established heuristic for the periodic timetabling problem, by integrating a passenger (re)routing step into the pivot operations. Computations on real-world networks show that we can indeed find timetables with much shorter total travel time, when we take the passengers' travel paths into consideration.}, language = {en} } @inproceedings{SchadeStrehler2016, author = {Schade, Stanley and Strehler, Martin}, title = {The Maximum Flow Problem for Oriented Flows}, volume = {54}, booktitle = {16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016)}, editor = {Goerigk, Marc and Werneck, Renato}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, isbn = {978-3-95977-021-7}, issn = {2190-6807}, doi = {10.4230/OASIcs.ATMOS.2016.7}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-65318}, pages = {1 -- 13}, year = {2016}, abstract = {In several applications of network flows, additional constraints have to be considered. In this paper, we study flows, where the flow particles have an orientation. For example, cargo containers with doors only on one side and train coaches with 1st and 2nd class compartments have such an orientation. If the end position has a mandatory orientation, not every path from source to sink is feasible for routing or additional transposition maneuvers have to be made. As a result, a source-sink path may visit a certain vertex several times. We describe structural properties of optimal solutions, determine the computational complexity, and present an approach for approximating such flows.}, language = {en} } @misc{BorndoerferKlugLamorgeseetal.2015, author = {Bornd{\"o}rfer, Ralf and Klug, Torsten and Lamorgese, Leonardo and Mannino, Carlo and Reuther, Markus and Schlechte, Thomas}, title = {Recent Success Stories on Optimization of Railway Systems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-53726}, year = {2015}, abstract = {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.}, language = {en} } @misc{BorndoerferKarbstein2015, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika}, title = {Metric Inequalities for Routings on Direct Connections with Application in Line Planning}, issn = {1438-0064}, doi = {10.1016/j.disopt.2015.07.004}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-53507}, year = {2015}, abstract = {We consider multi-commodity flow problems in which capacities are installed on paths. In this setting, it is often important to distinguish between flows on direct connection routes, using single paths, and flows that include path switching. We derive a feasibility condition for path capacities supporting such direct connection flows similar to the feasibility condition for arc capacities in ordinary multi-commodity flows. The concept allows to solve large-scale real-world line planning problems in public transport including a novel passenger routing model that favors direct connections over connections with transfers.}, language = {en} } @misc{HarmanSagnol2015, author = {Harman, Radoslav and Sagnol, Guillaume}, title = {Computing D-optimal experimental designs for estimating treatment contrasts under the presence of a nuisance time trend}, issn = {1438-0064}, doi = {10.1007/978-3-319-13881-7_10}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-53640}, year = {2015}, abstract = {We prove a mathematical programming characterisation of approximate partial D-optimality under general linear constraints. We use this characterisation with a branch-and-bound method to compute a list of all exact D-optimal designs for estimating a pair of treatment contrasts in the presence of a nuisance time trend up to the size of 24 consecutive trials.}, language = {en} } @inproceedings{SagnolHarman2015, author = {Sagnol, Guillaume and Harman, Radoslav}, title = {Optimal Designs for Steady-state Kalman filters}, volume = {122}, booktitle = {Stochastic Models, Statistics and Their Applications}, editor = {Steland, Ansgar and Rafajłowicz, Ewaryst and Szajowski, Krzysztof}, publisher = {Springer}, doi = {10.1007/978-3-319-13881-7_17}, pages = {149 -- 157}, year = {2015}, abstract = {We consider a stationary discrete-time linear process that can be observed by a finite number of sensors. The experimental design for the observations consists of an allocation of available resources to these sensors. We formalize the problem of selecting a design that maximizes the information matrix of the steady-state of the Kalman filter, with respect to a standard optimality criterion, such as \$D-\$ or \$A-\$optimality. This problem generalizes the optimal experimental design problem for a linear regression model with a finite design space and uncorrelated errors. Finally, we show that under natural assumptions, a steady-state optimal design can be computed by semidefinite programming.}, language = {en} } @inproceedings{HarmanSagnol2015, author = {Harman, Radoslav and Sagnol, Guillaume}, title = {Computing D-optimal experimental designs for estimating treatment contrasts under the presence of a nuisance time trend}, volume = {122}, booktitle = {Stochastic Models, Statistics and Their Applications}, editor = {Steland, Ansgar and Rafajłowicz, Ewaryst and Szajowski, Krzysztof}, publisher = {Springer}, doi = {10.1007/978-3-319-13881-7_10}, pages = {83 -- 91}, year = {2015}, abstract = {We prove a mathematical programming characterisation of approximate partial D-optimality under general linear constraints. We use this characterisation with a branch-and-bound method to compute a list of all exact D-optimal designs for estimating a pair of treatment contrasts in the presence of a nuisance time trend up to the size of 24 consecutive trials.}, language = {en} } @misc{BorndoerferSchlechteSwarat2011, author = {Bornd{\"o}rfer, Ralf and Schlechte, Thomas and Swarat, Elmar}, title = {Railway Track Allocation - Simulation, Aggregation, and Optimization}, issn = {1438-0064}, doi = {10.1007/978-3-642-27963-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14031}, number = {11-35}, year = {2011}, abstract = {Today the railway timetabling process and the track allocation is one of the most challenging problems to solve by a railway company. Especially due to the deregulation of the transport market in the recent years several suppliers of railway traffic have entered the market in Europe. This leads to more potential conflicts between trains caused by an increasing demand of train paths. Planning and operating railway transportation systems is extremely hard due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense size of the problem instances. In order to make best use of the infrastructure and to ensure economic operation, efficient planning of the railway operation is indispensable. Mathematical optimization models and algorithms can help to automatize and tackle these challenges. Our contribution in this paper is to present a renewed planning process due to the liberalization in Europe and an associated concept for track allocation, that consists of three important parts, simulation, aggregation, and optimization. Furthermore, we present results of our general framework for real world data.}, language = {en} } @misc{BorndoerferFriedowKarbstein2012, author = {Bornd{\"o}rfer, Ralf and Friedow, Isabel and Karbstein, Marika}, title = {Optimierung des Linienplans 2010 in Potsdam}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14486}, number = {12-04}, year = {2012}, abstract = {Im Zuge der {\"U}bernahme von 6 Linien der Havelbus Verkehrsgesellschaft mbH durch die ViP Verkehr in Potsdam GmbH ergab sich 2009 die Notwendigkeit der Entwicklung eines neuen Linien- und Taktplans f{\"u}r das Jahr 2010. Das Konrad-Zuse-Zentrum f{\"u}r Informationstechnik Berlin (ZIB) entwickelt in einem Projekt des DFG-Forschungszentrums Matheon ein Verfahren zur mathematischen Linienoptimierung. Dieses Tool wurde bei der Optimierung des ViP Linienplans 2010 in einer projektbegleitenden Studie eingesetzt, um Alternativen bei verschiedenen Planungs- und Zielvorgaben auszuloten. In dem Artikel wird eine Auswertung der Ergebnisse mit dem Verkehrsanalysesystem Visum der PTV AG beschrieben. Die Auswertungen best{\"a}tigen, dass mit Hilfe von mathematischer Optimierung eine weitere Verk{\"u}rzung der Reisezeit um 1\%, eine als um 6\% verk{\"u}rzt empfundene Reisezeit, 10\% weniger Fahrzeit im Fahrzeug und eine gleichzeitige Kostenreduktion um 5\% m{\"o}glich sind.}, language = {de} } @misc{BorndoerferHeismann2012, author = {Bornd{\"o}rfer, Ralf and Heismann, Olga}, title = {Minimum Cost Hyperassignments with Applications to ICE/IC Rotation Planning}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14564}, number = {11-46}, year = {2012}, abstract = {Vehicle rotation planning is a fundamental problem in rail transport. It decides how the railcars, locomotives, and carriages are operated in order to implement the trips of the timetable. One important planning requirement is operational regularity, i.e., using the rolling stock in the same way on every day of operation. We propose to take regularity into account by modeling the vehicle rotation planning problem as a minimum cost hyperassignment problem (HAP). Hyperassignments are generalizations of assignments from directed graphs to directed hypergraphs. Finding a minimum cost hyperassignment is NP-hard. Most instances arising from regular vehicle rotation planning, however, can be solved well in practice. We show that, in particular, clique inequalities strengthen the canonical LP relaxation substantially.}, language = {en} }