@inproceedings{Sagnol2012, author = {Sagnol, Guillaume}, title = {Network-related problems in optimal experimental design and second order cone programming}, volume = {51}, booktitle = {Proceedings of PROBASTAT'2011, Tatra Mountains Mathematical Publications}, doi = {10.2478/v10127-012-0016-x}, pages = {161 -- 171}, year = {2012}, abstract = {In the past few years several applications of optimal experimental designs have emerged to optimize the measurements in communication networks. The optimal design problems arising from this kind of applications share three interesting properties: (i) measurements are only available at a small number of locations of the network; (ii) each monitor can simultaneously measure several quantities, which can be modeled by ``multiresponse experiments"; (iii) the observation matrices depend on the topology of the network. In this paper, we give an overview of these experimental design problems and recall recent results for the computation of optimal designs by Second Order Cone Programming (SOCP). New results for the network-monitoring of a discrete time process are presented. In particular, we show that the optimal design problem for the monitoring of an AR1 process can be reduced to the standard form and we give experimental results.}, language = {en} } @inproceedings{HildenbrandtReineltHeismann2013, author = {Hildenbrandt, Achim and Reinelt, Gerhard and Heismann, Olga}, title = {Integer Programming Models for the Target Visitation Problem}, booktitle = {Proceedings of the 16th International Multiconference INFORMATION SOCIETY - IS 2013}, pages = {569 -- 572}, year = {2013}, abstract = {The target visitation problem (TVP) is concerned with finding a route to visit a set of targets starting from and returning to some base. In addition to the distance traveled a tour is evaluated by taking also preferences into account which address the sequence in which the targets are visited. The problem thus is a combination of two well-known combinato- rial optimization problems: the traveling salesman and the linear ordering problem. In this paper we present several possible IP-Models for this problem and compared them to their usability for branch-and-cut approaches.}, language = {en} } @inproceedings{HeismannBorndoerfer2012, author = {Heismann, Olga and Bornd{\"o}rfer, Ralf}, title = {Minimum Cost Hyperassignments with Applications to ICE/IC Rotation Planning}, booktitle = {Operations Research Proceedings 2011}, pages = {59 -- 64}, 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} } @inproceedings{Schlechte2012, author = {Schlechte, Thomas}, title = {Railway Track Allocation}, booktitle = {Operations Research Proceedings}, doi = {10.1007/978-3-319-00795-314}, pages = {15 -- 20}, year = {2012}, language = {en} } @inproceedings{ScheumannFuegenschuhSchenkeretal.2012, author = {Scheumann, Ren{\´e} and F{\"u}genschuh, Armin and Schenker, Sebastian and Vierhaus, Ingmar and Bornd{\"o}rfer, Ralf and Finkbeiner, Matthias}, title = {Global Manufacturing: How to Use Mathematical Optimisation Methods to Transform to Sustainable Value Creation}, booktitle = {Proceedings of the 10th Global Conference on Sustainable Manufacturing}, editor = {Seliger, G{\"u}nther}, isbn = {978-605-63463-1-6}, pages = {538 -- 545}, year = {2012}, language = {en} } @inproceedings{BorndoerferNeumann2011, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika}, title = {Linienoptimierung - reif f{\"u}r die Praxis?}, booktitle = {Heureka '11 : Optimierung in Verkehr und Transport}, year = {2011}, abstract = {Wir stellen in dieser Arbeit ein mathematisches Optimierungsmodell zur Bestimmung eines optimalen Linienplans vor, das sowohl die Fahrzeiten und die Anzahl der Umstiege ber{\"u}cksichtigt als auch die Kosten des Liniennetzes. Dieses Modell deckt wichtige praktische Anforderungen ab, die in einem gemeinsamen Projekt mit den Verkehrsbetrieben in Potsdam (ViP) formuliert wurden. In diesem Projekt wurde der Linienplan 2010 f{\"u}r Potsdam entwickelt. Unsere Berechnungen zeigen, dass die mathematische Optimierung in nichts einer "Handplanung" des Liniennetzes nachsteht. Im Gegenteil, mit Hilfe des Optimierungsprogramms ist es m{\"o}glich, durch Ver{\"a}nderung der Parameter mehrere verschiedene Szenarien zu berechnen, miteinander zu vergleichen und Aussagen {\"u}ber minimale Kosten und Fahrzeiten zu machen.}, language = {de} } @inproceedings{BorndoerferHoppmannKarbstein2013, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {A Configuration Model for the Line Planning Problem}, volume = {33}, booktitle = {ATMOS 2013 - 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems}, editor = {Frigioni, Daniele and Stiller, Sebastian}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik}, doi = {10.4230/OASIcs.ATMOS.2013.68}, pages = {68 -- 79}, year = {2013}, language = {en} } @inproceedings{Karbstein2016, author = {Karbstein, Marika}, title = {Integrated Line Planning and Passenger Routing: Connectivity and Transfers}, booktitle = {Operations Research Proceedings 2014}, doi = {10.1007/978-3-319-28697-6_37}, pages = {263 -- 269}, year = {2016}, abstract = {The integrated line planning and passenger routing problem is an important planning problem in service design of public transport. A major challenge is the treatment of transfers. A main property of a line system is its connectivity. In this paper we show that analysing the connecvitiy aspect of a line plan gives a new idea to handle the transfer aspect of the line planning problem.}, language = {en} } @inproceedings{BeckenbachBorndoerfer2016, author = {Beckenbach, Isabel and Bornd{\"o}rfer, Ralf}, title = {An Approximation Result for Matchings in Partitioned Hypergraphs}, booktitle = {Operations Research Proceedings 2014}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-28697-6_5}, pages = {31 -- 36}, year = {2016}, abstract = {We investigate the matching and perfect matching polytopes of hypergraphs having a special structure, which we call partitioned hypergraphs. We show that the integrality gap of the standard LP-relaxation is at most \$2\sqrt{d}\$ for partitioned hypergraphs with parts of size \$\leq d\$. Furthermore, we show that this bound cannot be improved to \$\mathcal{O}(d^{0.5-\epsilon})\$.}, language = {en} } @inproceedings{LiebchenSwarat2008, author = {Liebchen, Christian and Swarat, Elmar}, title = {The Second Chvatal Closure Can Yield Better Railway Timetables}, booktitle = {ATMOS 2008 - 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems}, editor = {Fischetti, Matteo and Widmayer, Peter}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany}, address = {Dagstuhl, Germany}, doi = {10.4230/OASIcs.ATMOS.2008.1580}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-15802}, year = {2008}, language = {en} } @inproceedings{SchlechteTanner2010, author = {Schlechte, Thomas and Tanner, Andreas}, title = {Railway capacity auctions with dual prices}, booktitle = {Selected Proceedings of the 12th World Conference on Transport Research}, year = {2010}, language = {en} } @inproceedings{BorndoerferSchlechte2007, author = {Bornd{\"o}rfer, Ralf and Schlechte, Thomas}, title = {Models for Railway Track Allocation}, volume = {07001}, booktitle = {ATMOS 2007 - 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems}, editor = {Liebchen, Christian and Ahuja, Ravindra and Mesa, Juan}, publisher = {Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany}, year = {2007}, language = {en} } @inproceedings{BorndoerferSchlechte2008, author = {Bornd{\"o}rfer, Ralf and Schlechte, Thomas}, title = {Balancing Efficiency and Robustness}, booktitle = {MCDM for Sustainable Energy and Transportation Systems}, editor = {Ehrgott, Matthias and Naujoks, Boris and Stewart, Theo and Wallenius, Jyrki}, publisher = {Lecture Notes in Economics and Mathematical Systems}, year = {2008}, language = {en} } @inproceedings{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}, booktitle = {Operations Research Proceedings 2016}, 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{DuarteSagnolOliveira2015, author = {Duarte, Belmiro P.M. and Sagnol, Guillaume and Oliveira, Nuno M.C.}, title = {A Robust Minimax Semidefinite Programming Formulation for Optimal Design of Experiments for Model Parametrization}, volume = {37}, booktitle = {12th International Symposium on Process Systems Engineering and 25th European Symposium on Computer Aided Process Engineering}, doi = {10.1016/B978-0-444-63578-5.50146-8}, pages = {905 -- 910}, year = {2015}, abstract = {Model-based optimal design of experiments (M-bODE) is a crucial step in model parametrization since it encloses a framework that maximizes the amount of information extracted from a battery of lab experiments. We address the design of M-bODE for dynamic models considering a continuous representation of the design. We use Semidefinite Programming (SDP) to derive robust minmax formulations for nonlinear models, and extend the formulations to other criteria. The approaches are demonstrated for a CSTR where a two-step reaction occurs.}, language = {en} } @inproceedings{GrimmBorndoerferReutheretal.2016, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Schade, Stanley}, title = {Regularity patterns for rolling stock rotation optimization}, volume = {8}, booktitle = {8th International Conference on Applied Operational Research, Proceedings}, pages = {28 -- 32}, year = {2016}, abstract = {The operation of railways gives rise to many fundamental optimization problems. One of these problems is to cover a given set of timetabled trips by a set of rolling stock rotations. This is well known as the Rolling Stock Rotation Problem (RSRP). Most approaches in the literature focus primarily on modeling and minimizing the operational costs. However, an essential aspect for the industrial application is mostly neglected. As the RSRP follows timetabling and line planning, where periodicity is a highly desired property, it is also desired to carry over periodic structures to rolling stock rotations and following operations. We call this complex requirement regularity. Regularity turns out to be of essential interest, especially in the industrial scenarios that we tackle in cooperation with DB Fernverkehr AG. Moreover, regularity in the context of the RSRP has not been investigated thoroughly in the literature so far. We introduce three regularity patterns to tackle this requirement, namely regular trips, regular turns, and regular handouts. We present a two-stage approach in order to optimize all three regularity patterns. At first, we integrate regularity patterns into an integer programming approach for the minimization of the operational cost of rolling stock rotations. Afterwards regular handouts are computed. These handouts present the rotations of the first stage in the most regular way. Our computational results (i.e., rolling stock rotations evaluated by planners of DB Fernverkehr AG) show that the three regularity patterns and our concept are a valuable and, moreover, an essential contribution to rolling stock rotation optimization.}, language = {en} } @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} } @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} } @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} } @inproceedings{BorndoerferMuraSchlechte2009, author = {Bornd{\"o}rfer, Ralf and Mura, Annette and Schlechte, Thomas}, title = {Vickrey Auctions for Railway Tracks}, booktitle = {Operations Research Proceedings 2008}, editor = {Fleischmann, Bernhard and Borgwardt, Karl and Klein, Robert and Tuma, Axel}, publisher = {Springer-Verlag}, pages = {551 -- 556}, year = {2009}, language = {en} } @inproceedings{BorndoerferNeumannPfetsch2009, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {The Line Connectivity Problem}, booktitle = {Operations Research Proceedings 2008}, editor = {Fleischmann, Bernhard and Borgwardt, Karl and Klein, Robert and Tuma, Axel}, publisher = {Springer-Verlag}, pages = {557 -- 562}, year = {2009}, language = {en} } @inproceedings{BorndoerferGroetschelKlostermeieretal.1999, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Klostermeier, Fridolin and K{\"u}ttner, Christian}, title = {Telebus Berlin: Vehicle Scheduling in a Dial-a-Ride System}, booktitle = {Proceedings of the 7th International Workshop on Computer-Aided Transit Scheduling}, editor = {Wilson, Nigel}, publisher = {Springer Verlag}, address = {Berlin}, doi = {10.1007/978-3-642-85970-0_19}, pages = {391 -- 422}, year = {1999}, language = {en} } @inproceedings{BorndoerferSchlechteWeider2010, author = {Bornd{\"o}rfer, Ralf and Schlechte, Thomas and Weider, Steffen}, title = {Railway Track Allocation by Rapid Branching}, volume = {14}, booktitle = {Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems}, editor = {Erlebach, Thomas and L{\"u}bbecke, Marco}, publisher = {Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, doi = {http://dx.doi.org/10.4230/OASIcs.ATMOS.2010.13}, pages = {13 -- 23}, year = {2010}, language = {en} } @inproceedings{BorndoerferNeumannPfetsch2008, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {Angebotsplanung im {\"o}ffentlichen Nahverkehr}, booktitle = {HEUREKA'08}, publisher = {FGSV Verlag}, year = {2008}, language = {en} } @inproceedings{GrimmBorndoerferReutheretal.2017, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Reuther, Markus and Schade, Stanley and Schlechte, Thomas}, title = {A Propagation Approach to Acyclic Rolling Stock Rotation Optimization}, booktitle = {Proceedings of the IAROR conference RailLille}, year = {2017}, abstract = {The rolling stock, i.e., railway vehicles, are one of the key ingredients of a running railway system. As it is well known, the offer of a railway company to their customers, i.e., the railway timetable, changes from time to time. Typical reasons for that are different timetables associated with different seasons, maintenance periods or holidays. Therefore, the regular lifetime of a timetable is split into (more or less) irregular periods where parts of the timetable are changed. In order to operate a railway timetable most railway companies set up sequences that define the operation of timetabled trips by a single physical railway vehicle called (rolling stock) rotations. Not surprisingly, the individual parts of a timetable also affect the rotations. More precisely, each of the parts brings up an acyclic rolling stock rotation problem with start and end conditions associated with the beginning and ending of the corresponding period. In this paper, we propose a propagation approach to deal with large planning horizons that are composed of many timetables with shorter individual lifetimes. The approach is based on an integer linear programming formulation that propagates rolling stock rotations through the irregular parts of the timetable while taking a large variety of operational requirements into account. This approach is implemented within the rolling stock rotation optimization framework ROTOR used by DB Fernverkehr AG, one of the leading railway operators in Europe. Computational results for real world scenarios are presented to evaluate the approach.}, language = {en} } @inproceedings{BorndoerferSagnolSwarat2012, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Swarat, Elmar}, title = {A Case Study on Optimizing Toll Enforcements on Motorways}, volume = {22}, booktitle = {3rd Student Conference on Operational Research}, doi = {10.4230/OASIcs.SCOR.2012.1}, pages = {1 -- 10}, year = {2012}, abstract = {In this paper we present the problem of computing optimal tours of toll inspectors on German motorways. This problem is a special type of vehicle routing problem and builds up an integrated model, consisting of a tour planning and a duty rostering part. The tours should guarantee a network-wide control whose intensity is proportional to given spatial and time dependent traffic distributions. We model this using a space-time network and formulate the associated optimization problem by an integer program (IP). Since sequential approaches fail, we integrated the assignment of crews to the tours in our model. In this process all duties of a crew member must fit in a feasible roster. It is modeled as a Multi-Commodity Flow Problem in a directed acyclic graph, where specific paths correspond to feasible rosters for one month. We present computational results in a case-study on a German subnetwork which documents the practicability of our approach.}, language = {en} } @inproceedings{BorndoerferSchenkerSkutellaetal.2016, author = {Bornd{\"o}rfer, Ralf and Schenker, Sebastian and Skutella, Martin and Strunk, Timo}, title = {PolySCIP}, volume = {9725}, booktitle = {Mathematical Software - ICMS 2016, 5th International Conference, Berlin, Germany, July 11-14, 2016, Proceedings}, editor = {Greuel, G.-M. and Koch, Thorsten and Paule, Peter and Sommese, Andrew}, edition = {Mathematical Software - ICMS 2016}, publisher = {Springer International Publishing}, isbn = {978-3-319-42431-6}, doi = {10.1007/978-3-319-42432-3_32}, pages = {259 -- 264}, year = {2016}, abstract = {PolySCIP is a new solver for multi-criteria integer and multi-criteria linear programs handling an arbitrary number of objectives. It is available as an official part of the non-commercial constraint integer programming framework SCIP. It utilizes a lifted weight space approach to compute the set of supported extreme non-dominated points and unbounded non-dominated rays, respectively. The algorithmic approach can be summarized as follows: At the beginning an arbitrary non-dominated point is computed (or it is determined that there is none) and a weight space polyhedron created. In every next iteration a vertex of the weight space polyhedron is selected whose entries give rise to a single-objective optimization problem via a combination of the original objectives. If the ptimization of this single-objective problem yields a new non-dominated point, the weight space polyhedron is updated. Otherwise another vertex of the weight space polyhedron is investigated. The algorithm finishes when all vertices of the weight space polyhedron have been investigated. The file format of PolySCIP is based on the widely used MPS format and allows a simple generation of multi-criteria models via an algebraic modelling language.}, language = {en} } @inproceedings{Hoppmann2016, author = {Hoppmann, Heide}, title = {An Extended Formulation for the Line Planning Problem}, booktitle = {Operations Research Proceedings 2015}, doi = {10.1007/978-3-319-42902-1_2}, pages = {11 -- 17}, year = {2016}, abstract = {In this paper we present a novel extended formulation for the line planning problem that is based on what we call "configurations" of lines and frequencies. Configurations account for all possible options to provide a required transportation capacity on an infrastructure edge. The proposed configuration model is strong in the sense that it implies several facet-defining inequalities for the standard model: set cover, symmetric band, MIR, and multicover inequalities. These theoretical findings can be confirmed in computational results. Further, we show how this concept can be generalized to define configurations for subsets of edges; the generalized model implies additional inequalities from the line planning literature.}, language = {en} } @inproceedings{BorndoerferHoppmannKarbstein2016, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Separation of Cycle Inequalities for the Periodic Timetabling Problem}, volume = {57}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, doi = {10.4230/LIPIcs.ESA.2016.21}, year = {2016}, abstract = {Cycle inequalities play an important role in the polyhedral study of the periodic timetabling problem. We give the first pseudo-polynomial time separation algorithm for cycle inequalities, and we give a rigorous proof for the pseudo-polynomial time separability of the change-cycle inequalities. The efficiency of these cutting planes is demonstrated on real-world instances of the periodic timetabling problem.}, language = {en} } @inproceedings{BorndoerferSagnolSwarat2012, author = {Bornd{\"o}rfer, Ralf and Sagnol, Guillaume and Swarat, Elmar}, title = {An IP Approach to Toll Enforcement Optimization on German Motorways}, booktitle = {Operations Research Proceedings 2011}, doi = {10.1007/978-3-642-29210-1_51}, pages = {317 -- 322}, year = {2012}, abstract = {This paper proposes the first model for toll enforcement optimization on German motorways. The enforcement is done by mobile control teams and our goal is to produce a schedule achieving network-wide control, proportional to spatial and time-dependent traffic distributions. Our model consists of two parts. The first plans control tours using a vehicle routing approach with profits and some side constraints. The second plans feasible rosters for the control teams. Both problems can be modeled as Multi-Commodity Flow Problems. Adding additional coupling constraints produces a large-scale integrated integer programming formulation. We show that this model can be solved to optimality for real world instances associated with a control area in East Germany.}, language = {en} } @inproceedings{BorndoerferBuwayaSagnoletal.2013, author = {Bornd{\"o}rfer, Ralf and Buwaya, Julia and Sagnol, Guillaume and Swarat, Elmar}, title = {Optimizing Toll Enforcement in Transportation Networks: a Game-Theoretic Approach}, volume = {41}, booktitle = {Proceedings of INOC'2013}, doi = {http://dx.doi.org//10.1016/j.endm.2013.05.100}, pages = {253 -- 260}, year = {2013}, abstract = {We present a game-theoretic approach to optimize the strategies of toll enforcement on a motorway network. In contrast to previous approaches, we consider a network with an arbitrary topology, and we handle the fact that users may choose their Origin-Destination path; in particular they may take a detour to avoid sections with a high control rate. We show that a Nash equilibrium can be computed with an LP (although the game is not zero-sum), and we give a MIP for the computation of a Stackelberg equilibrium. Experimental results based on an application to the enforcement of a truck toll on German motorways are presented.}, language = {en} } @inproceedings{BorndoerferOmontSagnoletal.2012, author = {Bornd{\"o}rfer, Ralf and Omont, Bertrand and Sagnol, Guillaume and Swarat, Elmar}, title = {A Stackelberg game to optimize the distribution of controls in transportation networks}, volume = {105}, booktitle = {Proceedings of the 3rd International Conference on Game Theory for Networks (GAMENETS 2012)}, doi = {http://dx.doi.org/10.1007/978-3-642-35582-0_17}, pages = {224 -- 235}, year = {2012}, abstract = {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.}, language = {en} } @inproceedings{KlugJunoszaSzaniawskiKwasiborskietal.2015, author = {Klug, Torsten and Junosza-Szaniawski, Konstanty and Kwasiborski, Slawomir and F{\"u}genschuh, Armin and Schlechte, Thomas}, title = {Fastest, Average and Quantile Schedule}, booktitle = {SOFSEM 2015: Theory and Practice of Computer Science}, publisher = {Springer Berlin Heidelberg}, doi = {10.1007/978-3-662-46078-8_17}, pages = {201 -- 216}, year = {2015}, abstract = {We consider problems concerning the scheduling of a set of trains on a single track. For every pair of trains there is a minimum headway, which every train must wait before it enters the track after another train. The speed of each train is also given. Hence for every schedule - a sequence of trains - we may compute the time that is at least needed for all trains to travel along the track in the given order. We give the solution to three problems: the fastest schedule, the average schedule, and the problem of quantile schedules. The last problem is a question about the smallest upper bound on the time of a given fraction of all possible schedules. We show how these problems are related to the travelling salesman problem. We prove NP-completeness of the fastest schedule problem, NP-hardness of quantile of schedules problem, and polynomiality of the average schedule problem. We also describe some algorithms for all three problems. In the solution of the quantile problem we give an algorithm, based on a reverse search method, generating with polynomial delay all Eulerian multigraphs with the given degree sequence and a bound on the number of such multigraphs. A better bound is left as an open question.}, language = {en} } @inproceedings{BlancoSchlechte2014, author = {Blanco, Marco and Schlechte, Thomas}, title = {Analysis of Micro-Macro Transformations of Railway Networks}, booktitle = {Operations Research Proceedings 2013}, doi = {10.1007/978-3-319-07001-8_6}, pages = {37 -- 42}, year = {2014}, abstract = {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.}, language = {en} } @inproceedings{HeismannBorndoerfer2014, author = {Heismann, Olga and Bornd{\"o}rfer, Ralf}, title = {A Generalization of Odd Set Inequalities for the Set Packing Problem}, booktitle = {Operations Research Proceedings 2013}, doi = {10.1007/978-3-319-07001-8_26}, pages = {193 -- 199}, year = {2014}, abstract = {The set packing problem, sometimes also called the stable set problem, is a well-known NP-hard problem in combinatorial optimization with a wide range of applications and an interesting polyhedral structure, that has been the subject of intensive study. We contribute to this field by showing how, employing cliques, odd set inequalities for the matching problem can be generalized to valid inequalities for the set packing polytope with a clear combinatorial meaning.}, language = {en} } @inproceedings{BorndoerferHoppmannKarbstein2017, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Umsteigen ohne Warten}, booktitle = {HEUREKA 2017}, year = {2017}, abstract = {Wir stellen einen mathematischen Optimierungsansatz zur Berechnung von periodischen Taktfahrpl{\"a}nen vor, bei dem die Umsteigezeiten unter Ber{\"u}cksichtigung des Passagierverhaltens minimiert werden. Wir untersuchen damit den Einfluss wichtiger Systemparameter und Verhaltensmuster auf die Bef{\"o}rderungsqualit{\"a}t.}, language = {de} } @inproceedings{BorndoerferHoppmannKarbstein2015, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika}, title = {Timetabling and Passenger Routing in Public Transport}, booktitle = {Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015)}, year = {2015}, abstract = {The task of timetabling is to schedule the trips in a public transport system by determining periodic arrival and departure times at every station. The goal is to provide a service that is both attractive for passengers and can be operated economically. To date, timetable optimization is generally done with respect to fixed passenger routes, i.e., it is assumed that passengers do not respond to changes in the timetable. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We propose several models that differ in the allowed passenger paths and the objectives. We compare these models theoretically and report on computations on real-world instances for the city of Wuppertal.}, language = {en} }