@article{GamrathBertholdHeinzetal.2019, author = {Gamrath, Gerald and Berthold, Timo and Heinz, Stefan and Winkler, Michael}, title = {Structure-driven fix-and-propagate heuristics for mixed integer programming}, volume = {11}, journal = {Mathematical Programming Computation}, number = {4}, publisher = {Springer}, address = {Berlin Heidelberg}, doi = {10.1007/s12532-019-00159-1}, pages = {675 -- 702}, year = {2019}, abstract = {Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They often provide good feasible solutions early and help to reduce the time needed to prove optimality. In this paper, we present a scheme for start heuristics that can be executed without previous knowledge of an LP solution or a previously found integer feasible solution. It uses global structures available within MIP solvers to iteratively fix integer variables and propagate these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. If sufficiently many variables can be fixed that way, the resulting problem is solved first as an LP, and then as an auxiliary MIP if the rounded LP solution does not provide a feasible solution already. We present three primal heuristics that use this scheme based on different global structures. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about 60 \% of the instances and by this, help to improve several performance measures for MIP solvers, including the primal integral and the average solving time.}, language = {en} } @misc{Elijazyfer2018, type = {Master Thesis}, author = {Elijazyfer, Ziena}, title = {L{\"a}ngenbeschr{\"a}nkte Teilgraphenbildung zur Maut-Kontrollstreckenoptimierung}, year = {2018}, language = {de} } @misc{Schreck2018, type = {Master Thesis}, author = {Schreck, Vanessa}, title = {Algorithmic Analysis of the Graph Segmentation Problem}, year = {2018}, language = {en} } @masterthesis{Vornberger2018, type = {Bachelor Thesis}, author = {Vornberger, Leo}, title = {Approximation von Windkomponenten in der Luftfahrt durch lineare Interpolation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71570}, pages = {49}, year = {2018}, abstract = {Das Wind-Interpolation-Problem (WIP) ist ein bisher selten diskutiertes Problem der Flugplanungsoptimierung, bei dem es darum geht, Wind-Komponenten auf einer Luftstraße zu approximieren. Anhand von Winddaten, die vektoriell an den Gitterpunkten eines den Globus umspannenden Gitters vorliegen, soll bestimmt werden, wie viel Wind entlang der Luftstraße und quer zu ihr weht. Thema dieser Arbeit ist ein Spezialfall des WIP, n{\"a}mlich das statische WIP auf einer Planfl{\"a}che (SWIPP). Dazu wird zuerst ein Algorithmus besprochen, der das SWIPP zwar l{\"o}st, aber einem Ansatz zugrunde liegt, der bei genauerem Hinsehen nicht sinnvoll erscheint: hier wird Wind zwischen vier Punkten interpoliert, wozu es keine triviale Methode gibt. {\"A}hnlich zu diesem Algorithmus, der heute als State-of-the-Art gilt, wird als Ergebnis dieser Arbeit ein neuer Algorithmus vorgestellt, der das SWIPP akkurater und schneller l{\"o}st. Hier wird deutlich seltener auf die Interpolation zwischen vier Punkten zur{\"u}ckgegriffen - stattdessen wird fast immer linear zwischen zwei Punkten interpoliert. Die Algorithmen zum L{\"o}sen des SWIPP werden auf ihre Genauigkeit, asymptotische Laufzeit und Geschwindigkeit untersucht und verglichen. Als Testareal dienen zum einen echte Wetterdaten sowie das Luftstraßennetz, das die Erde umspannt, und zum anderen ein eigens generiertes Windfeld und fiktive Luftstraßen. Es wird gezeigt, dass der hier vorgestellte Algorithmus die State-of-the-Art-Variante in allen genannten Aspekten {\"u}bertrifft.}, language = {de} } @masterthesis{Akil2018, type = {Bachelor Thesis}, author = {Akil, Fatima}, title = {Lineare Gleichungssysteme modulo T}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71560}, pages = {52}, year = {2018}, abstract = {Mit dem Voranschreiten der Technologie erhalten die {\"o}ffentlichen Verkehrsmittel eine gr{\"o}ßere Bedeutung. Die Bef{\"o}rderung mehrerer Personen er{\"o}ffnet der Gesellschaft viele M{\"o}glichkeiten, unter Anderem den Vorteil der Zeitersparnis. Die Dauer des Verkehrswegs mit {\"o}ffentlichen Verkehrsmitteln ist h{\"a}ufig geringer, als die mit individuellen Verkehrsmitteln. Jedes {\"o}ffentliche Transportmittel ist mit einem Fahrplan versehen. Dieser bietet Passagieren, die {\"o}ffentliche Verkehrsmittel {\"o}fter nutzen, eine Strukturierung und Planung ihrer Zeit. Dabei lassen sich Taktfahrpl{\"a}ne aufgrund ihres periodischen Verhaltens leicht einpr{\"a}gen. Dieses periodische Verhalten ist durch mathematische Modellierungen darstellbar. Das pers{\"o}nliche Nutzverhalten vieler B{\"u}rger im Personenverkehr ist auf die {\"o}ffentlichen Verkehrsmittel beschr{\"a}nkt. Diese beinhalten im Gegensatz zum individuellen Verkehrsmittel eine Wartezeit. Dabei stellt sich die Frage, ob man anhand mathematischer Modelle diese Wartezeit minimieren kann. Eine bekannte mathematische Modellierung dieses Problems ist das Periodic Event Scheduling Problem (PESP). Die optimale Planung eines periodischen Taktfahrplanes steht im Vordergrund. W{\"a}hrend ich dieses Problem betrachtet habe, wurde ich auf das Rechnen mit linearen Gleichungssystemen modulo T aufmerksam. Bei periodischen Taktfahrpl{\"a}nen wird ein einheitliches zeitliches Muster, welches sich nach T Minuten wiederholt, betrachtet. Das dabei zu betrachtende L{\"o}sungsproblem er{\"o}ffnet ein Teilgebiet der Mathematik, welches bislang nicht im Vordergrund stand: Das L{\"o}sen linearer Gleichungen modulo T, wobei T f{\"u}r die Zeit in Minuten steht und somit 60 ist. Da 60 keine Primzahl ist, kann - wie im Laufe der Arbeit pr{\"a}sentiert - das lineare Gleichungssystem nicht mehr {\"u}ber einen K{\"o}rper gel{\"o}st werden. Lineare Gleichungssysteme werden nun {\"u}ber Nicht-K{\"o}rpern betrachtet. Die Literatur weist sowohl im deutschsprachigem als auch im englischsprachigen Raum wenig Umfang bez{\"u}glich linearer Gleichungssysteme {\"u}ber Nicht-K{\"o}rper auf. Der Bestand an Fachliteratur bez{\"u}glich den Themen lineare diophantische Gleichungssysteme, Hermite- Normalform und Smith-Normalform ist zurzeit gering, dennoch erreichbar, beispielsweise in [1], welches in dieser Bachelorarbeit genutzt wurde. Insbesondere wurde ich bei der Suche nach geeigneter Literatur zu linearen Gleichungssystemen {\"u}ber Restklassenringe, die keinen K{\"o}rper bilden, nicht f{\"u}ndig. Dabei recherchierte ich sowohl in den Universit{\"a}tsbibliotheken als auch in webbasierenden Suchmaschinen. Aufgrund dem geringen Bestand an Fachliteratur in diesem Kontext, war ich gezwungen, an vielen Stellen eigene logische Verkn{\"u}pfungen zu konzipieren und zu beweisen. Dies brachte viele Schwierigkeiten mit sich, die mit bestm{\"o}glichem Verst{\"a}ndnis bearbeitet wurden. Abseits der Zug{\"a}nglichkeit der Literatur, finde ich es sehr {\"u}berraschend, dass sich viele Professoren der Mathematik mit diesem Themenbereich nicht besch{\"a}ftigten. Insbesondere gingen von den Dozenten, die ich um Literaturempfehlung bat, kein Werk aus. Damit wurde das Thema "Lineare Gleichungssysteme Modulo T" einerseits eine große Herausforderung, andererseits eine große Motivation, da ich mit dieser Bachelorarbeit vielen Interessenten der Mathematik als Sekund{\"a}rliteratur dienen kann.}, language = {de} } @misc{BorndoerferKarbsteinLiebchenetal.2018, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika and Liebchen, Christian and Lindner, Niels}, title = {A Simple Way to Compute the Number of Vehicles That Are Required to Operate a Periodic Timetable}, issn = {1438-0064}, doi = {10.4230/OASIcs.ATMOS.2018.16}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69688}, year = {2018}, abstract = {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.}, language = {en} } @misc{BorndoerferReutherSchlechteetal.2011, author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Weider, Steffen}, title = {A Hypergraph Model for Railway Vehicle Rotation Planning}, issn = {1438-0064}, doi = {/10.4230/OASIcs.ATMOS.2011.146}, url = {http://nbn-resolving.de/urn:nbn:de:0030-drops-32746}, number = {11-36}, year = {2011}, abstract = {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.}, language = {en} } @misc{Oleynikova2018, type = {Master Thesis}, author = {Oleynikova, Ekaterina}, title = {Mathematical optimization of joint order batching and picker routing problems}, pages = {60}, year = {2018}, abstract = {In this thesis we study order picking optimization problems for a two-blocks rectangle warehouse layout. We present combinatorial formulations and linear programming models based on the Steiner graph representation for order batching, picker routing, and joint order batching and picker routing problems. A special case of the latter is considered. This case assumes that each order contains exactly one item and each item can be picked from different possible locations in a warehouse. The underlying optimization problem is called joint multi-location order batching and picker routing problem (JMLOBPRP). Since having only one-item orders turns the JMLOBPRP into a special case of a capacitated vehicle routing problem, we suggest to implement algorithmic approaches for those to solve the JMLOBPRP. In particular, we define the JMLOBPRP as a generalization of the resource constrained assignment problem, for which a regional search method exists. The intention of the thesis is to investigate how a relaxation of the JMLOBPRP, a so-called group assignment problem (GrAP), can be solved following the ideas of regional search. We present a mathematical model of the GrAP and prove that it is NP-hard. Furthermore, we propose a novel heuristic algorithm for the GrAP. We call this method a network search algorithm, as it is based on a Lagrangian relaxation of the GrAP, which is solved by the network simplex method. On each its iteration network search examines a solution region suggested by the network simplex algorithm and improves the incumbent solution. Numerical experiments are conducted to assess a performance of the network search method. We create more realistic problem instances. The proposed algorithm is compared to the integer optimal solution of the GrAP and optimal fractional solution of its linear relaxation. Both computed using the commercial linear solver Gurobi. Our experiments show that the developed network search algorithm leads to the hight-quality solution within a short computing time. The results obtained testing large problem instances which cannot be solved by Gurobi within a reasonable computing time, show that the network search method provides a solution approach which can be used in practice.}, language = {en} } @misc{Wyczik2018, type = {Master Thesis}, author = {Wyczik, Christopher}, title = {Optimierung von Deployment- und Umgebungs-Integrit{\"a}t durch ein dezentrales Konfigurationsrepository auf Basis einer Blockchain}, pages = {44}, year = {2018}, abstract = {Viele Firmen nutzen f{\"u}r ihre eigenen Softwareentwicklungen verschiedene Server mit unterschiedlichen Konfigurationen. Manche Server werden dazu eingestzt das Verhalten einer Software in einer bestimmten Umgebung zu testen und andere dienen zur Bereitstellung der Software f{\"u}r den Endnutzer. Hierbei ist es wichtig, dass die Konfiguration der Server regelm{\"a}ßig {\"u}berpr{\"u}ft wird. Eine solche Sicherstellung der Deployment- und Umgebungs-Integrit{\"a}t wird meistens durch eine Mitarbeiter der Firma oder durch einen externen Dienstleister erbracht. D.h. die Firma muss sich auf die Zuverl{\"a}ssigkeit eines Mitarbeiters oder einer externen Dienstleistung verlassen, bie zunehmender Komplexit{\"a}t ist sie sogar abh{\"a}ngig. Das Ziel dieser Masterarbeit ist es, zu untersuchen, ob die Sicherstellung der Deployment- und Umgebungs-Integrit{\"a}t durch automatisierte kryptografische Beweise, anstelle externer Dienstleistungen oder anderer Mitarbeiter, gew{\"a}hrleistet werden kann. Als Anwendungsfall dient die Toll Collect GmbH. Im ersten Teil dieser Arbeit wird das Matheamtische Modell einer Blockchain erl{\"a}utert. die Blockchain wurde erstmals in einem Dokument, welches unter dem Pseudonym Satoshi Nakamoto ver{\"o}ffentlicht wurde, beschrieben. Die erste große Anwendungen der Blockchain ist das dezentrale Zahlungssystem Bitcoin. Im zweiten Teil dieser Arbeit wird die Softwareimplementierung vorgestellt, welche im Rahmen dieser Arbeit entstanden ist. Mithilfe dieses Programms kann die Deployment- und Umgebungs-Integrit{\"a}t durch eine heirf{\"u}hr entwickelte Blockchainl{\"o}sung dezentralisiert werden. Es wird außerdem der {\"U}bergang vom Mathematischen Modell zur Implementierung gezeigt.}, language = {de} } @misc{Mett2018, type = {Master Thesis}, author = {Mett, Fabian}, title = {{\"U}ber die optimale Platzierung von Ladestationen f{\"u}r Elektrobusse}, pages = {76}, year = {2018}, abstract = {In dieser Arbeit wird die Platzierung von Ladestationen f{\"u}r Elektrobusse untersucht. Dabei soll f{\"u}r eine Menge an gegebenen Linien eine Menge an Ladestationen gefunden werden, sodass jede Linie mit Nutzung der Ladestationen befahren werden kann und gleichzeitig die Kosten minimal sind. Zun{\"a}chst wird der Fall betrachtet, dass die Batterie an jeder Station komplett vollgeladen werden k{\"o}nnte. Dieses Problem stellt sich als NP-schwer heraus. F{\"u}r einige einfachere F{\"a}llewerden zudem Algorithmen entwickelt und untersucht. Anschließend wird der Fall einer unbegrenzt großen Batterie betrachtet, wobei an jeder Station derselbe Wert geladen werden kann. Auch dieses Problem ist NP-schwer. Erneut werden Algorithmen zur L{\"o}sung vereinfachter Problemstellungen gegeben und analysiert. Wird zudem angenommen, an jeder Station w{\"u}rde ein individueller Wert geladen, so ist das Problem schon f{\"u}r nur eine einzige Linie NP-schwer. Dennoch werden zwei exakte und ein approximierender Algorithmus entwickelt. Schließlich wird eine Batteriekapazit{\"a}t hinzugef{\"u}gt und die zuvor entwickelten Algorithmen werden entsprechend angepasst. F{\"u}r die abschließende Problemdefinition werden verschiedene Batteriegr{\"o}ßen betrachtet und es werden zwei gemischt-ganzzahlige Programme aufgestellt. Anhand von existierenden Buslinien aus Berlin werden diese untersucht. Dabei stellt sich heraus, dass die Batteriekosten einen deutlich gr{\"o}ßeren Teil der Kosten ausmachen als die Ladestationen. Zudem sollten kleinere Batterien statt gr{\"o}ßerer und mehr Ladestationen genutzt werden.}, language = {de} } @masterthesis{Husemann2018, type = {Bachelor Thesis}, author = {Husemann, Christoph}, title = {Multimodales Routing mit Leihfahrradsystemen am Beispiel Berlins}, pages = {45}, year = {2018}, abstract = {The aim of multimodal routing is to extract the best integrated journey of multiple transportation networks. The integration of bike rental networks is challenging particularly with respect to recognizing a valid path dependent on real-time availability of bike boarding and alighting places. In this work a common model for station-based bike rental networks extended with boarding possibilities for free floating bikes is presented. Moreover a new model for alighting inside a free floating area is introduced. In addition, a prototype of multimodal routing with a bike rental network in Berlin is developed by extending the OpenTripPlanner software. Due to recent public dispute about bike rental networks in Berlin, an examination about speed-up potential of an integrated bike rental network in the public transit of Berlin is provided.}, language = {de} } @masterthesis{Krug2018, type = {Bachelor Thesis}, author = {Krug, Matthias}, title = {Analysis of the Shortest Path Problem with Piecewise Constant Crossing Costs}, pages = {37}, year = {2018}, language = {en} } @misc{BertholdStuckeyWitzig2018, author = {Berthold, Timo and Stuckey, Peter and Witzig, Jakob}, title = {Local Rapid Learning for Integer Programs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71190}, year = {2018}, abstract = {Conflict learning algorithms are an important component of modern MIP and CP solvers. But strong conflict information is typically gained by depth-first search. While this is the natural mode for CP solving, it is not for MIP solving. Rapid Learning is a hybrid CP/MIP approach where CP search is applied at the root to learn information to support the remaining MIP solve. This has been demonstrated to be beneficial for binary programs. In this paper, we extend the idea of Rapid Learning to integer programs, where not all variables are restricted to the domain {0, 1}, and rather than just running a rapid CP search at the root, we will apply it repeatedly at local search nodes within the MIP search tree. To do so efficiently, we present six heuristic criteria to predict the chance for local Rapid Learning to be successful. Our computational experiments indicate that our extended Rapid Learning algorithm significantly speeds up MIP search and is particularly beneficial on highly dual degenerate problems.}, language = {en} } @misc{Hendel2018, author = {Hendel, Gregor}, title = {Adaptive Large Neighborhood Search for Mixed Integer Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71167}, year = {2018}, abstract = {Large Neighborhood Search (LNS) heuristics are among the most powerful but also most expensive heuristics for mixed integer programs (MIP). Ideally, a solver learns adaptively which LNS heuristics work best for the MIP problem at hand in order to concentrate its limited computational budget. To this end, this work introduces Adaptive Large Neighborhood Search (ALNS) for MIP, a primal heuristic that acts a framework for eight popular LNS heuristics such as Local Branching and Relaxation Induced Neighborhood Search (RINS). We distinguish the available LNS heuristics by their individual search domains, which we call neighborhoods. The decision which neighborhood should be executed is guided by selection strategies for the multi armed bandit problem, a related optimization problem during which suitable actions have to be chosen to maximize a reward function. In this paper, we propose an LNS-specific reward function to learn to distinguish between the available neighborhoods based on successful calls and failures. A second, algorithmic enhancement is a generic variable fixing priorization, which ALNS employs to adjust the subproblem complexity as needed. This is particularly useful for some neighborhoods which do not fix variables by themselves. The proposed primal heuristic has been implemented within the MIP solver SCIP. An extensive computational study is conducted to compare different LNS strategies within our ALNS framework on a large set of publicly available MIP instances from the MIPLIB and Coral benchmark sets. The results of this simulation are used to calibrate the parameters of the bandit selection strategies. A second computational experiment shows the computational benefits of the proposed ALNS framework within the MIP solver SCIP.}, language = {en} } @misc{WitzigBertholdHeinz2018, author = {Witzig, Jakob and Berthold, Timo and Heinz, Stefan}, title = {A Status Report on Conflict Analysis in Mixed Integer Nonlinear Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71170}, year = {2018}, abstract = {Mixed integer nonlinear programs (MINLPs) are arguably among the hardest optimization problems, with a wide range of applications. MINLP solvers that are based on linear relaxations and spatial branching work similar as mixed integer programming (MIP) solvers in the sense that they are based on a branch-and-cut algorithm, enhanced by various heuristics, domain propagation, and presolving techniques. However, the analysis of infeasible subproblems, which is an important component of most major MIP solvers, has been hardly studied in the context of MINLPs. There are two main approaches for infeasibility analysis in MIP solvers: conflict graph analysis, which originates from artificial intelligence and constraint programming, and dual ray analysis. The main contribution of this short paper is twofold. Firstly, we present the first computational study regarding the impact of dual ray analysis on convex and nonconvex MINLPs. In that context, we introduce a modified generation of infeasibility proofs that incorporates linearization cuts that are only locally valid. Secondly, we describe an extension of conflict analysis that works directly with the nonlinear relaxation of convex MINLPs instead of considering a linear relaxation. This is work-in-progress, and this short paper is meant to present first theoretical considerations without a computational study for that part.}, language = {en} } @misc{GrimmBorndoerferSchulzetal.2019, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Schulz, Christof and Weider, Steffen}, title = {The Rolling Stock Rotation Planning Problem under Revenue Considerations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71339}, year = {2019}, abstract = {In many railway undertakings a railway timetable is offered that is valid for a longer period of time. At DB Fernverkehr AG, one of our industrial partners, this results in a summer and a winter timetable. For both of these timetables rotation plans, i.e., a detailed plan of railway vehicle movements is constructed as a template for this period. Sometimes there are be periods where you know for sure that vehicle capacities are not sufficient to cover all trips of the timetable or to transport all passenger of the trips. Reasons for that could be a heavy increase of passenger flow, a heavy decrease of vehicle availability, impacts from nature, or even strikes of some employees. In such events the rolling stock rotations have to be adapted. Optimization methods are particularly valuable in such situations in order to maintain a best possible level of service or to maximize the expected revenue using the resources that are still available. In most cases found in the literature, a rescheduling based on a timetable update is done, followed by the construction of new rotations that reward the recovery of parts of the obsolete rotations. We consider a different, novel, and more integrated approach. The idea is to guide the cancellation of the trips or reconfiguration of the vehicle composition used to operate a trip of the timetable by the rotation planning process, which is based on the mixed integer programming approach presented in Reuther (2017). The goal is to minimize the operating costs while cancelling or operating a trip with an insufficient vehicle configuration in sense of passenger capacities inflicts opportunity costs and loss of revenue, which are based on an estimation of the expected number of passengers. The performance of the algorithms presented in two case studies, including real world scenarios from DB Fernverkehr AG and a railway operator in North America.}, language = {en} } @inproceedings{GrimmBorndoerferSchulzetal.2018, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Schulz, Christof and Weider, Steffen}, title = {The Rolling Stock Rotation Planning Problem under Revenue Considerations}, booktitle = {Proceedings of the Rail Transport Demand Management Conference}, year = {2018}, abstract = {In many railway undertakings a railway timetable is offered that is valid for a longer period of time. At DB Fernverkehr AG, one of our industrial partners, this results in a summer and a winter timetable. For both of these timetables rotation plans, i.e., a detailed plan of railway vehicle movements is constructed as a template for this period. Sometimes there are be periods where you know for sure that vehicle capacities are not sufficient to cover all trips of the timetable or to transport all passenger of the trips. Reasons for that could be a heavy increase of passenger flow, a heavy decrease of vehicle availability, impacts from nature, or even strikes of some employees. In such events the rolling stock rotations have to be adapted. Optimization methods are particularly valuable in such situations in order to maintain a best possible level of service or to maximize the expected revenue using the resources that are still available. In most cases found in the literature, a rescheduling based on a timetable update is done, followed by the construction of new rotations that reward the recovery of parts of the obsolete rotations. We consider a different, novel, and more integrated approach. The idea is to guide the cancellation of the trips or reconfiguration of the vehicle composition used to operate a trip of the timetable by the rotation planning process, which is based on the mixed integer programming approach presented in Reuther (2017). The goal is to minimize the operating costs while cancelling or operating a trip with an insufficient vehicle configuration in sense of passenger capacities inflicts opportunity costs and loss of revenue, which are based on an estimation of the expected number of passengers. The performance of the algorithms presented in two case studies, including real world scenarios from DB Fernverkehr AG and a railway operator in North America.}, language = {en} } @inproceedings{SagnolSchmidtgenanntWaldschmidtTesch2018, author = {Sagnol, Guillaume and Schmidt genannt Waldschmidt, Daniel and Tesch, Alexander}, title = {The Price of Fixed Assignments in Stochastic Extensible Bin Packing}, volume = {11312}, booktitle = {WAOA 2018: Approximation and Online Algorithms}, doi = {10.1007/978-3-030-04693-4_20}, pages = {327 -- 347}, year = {2018}, abstract = {We consider the stochastic extensible bin packing problem (SEBP) in which n items of stochastic size are packed into m bins of unit capacity. In contrast to the classical bin packing problem, the number of bins is fixed and they can be extended at extra cost. This problem plays an important role in stochastic environments such as in surgery scheduling: Patients must be assigned to operating rooms beforehand, such that the regular capacity is fully utilized while the amount of overtime is as small as possible. This paper focuses on essential ratios between different classes of policies: First, we consider the price of non-splittability, in which we compare the optimal non-anticipatory policy against the optimal fractional assignment policy. We show that this ratio has a tight upper bound of 2. Moreover, we develop an analysis of a fixed assignment variant of the LEPT rule yielding a tight approximation ratio of (1+e-1)≈1.368 under a reasonable assumption on the distributions of job durations. Furthermore, we prove that the price of fixed assignments, related to the benefit of adaptivity, which describes the loss when restricting to fixed assignment policies, is within the same factor. This shows that in some sense, LEPT is the best fixed assignment policy we can hope for.}, language = {en} } @misc{Jeschke2017, type = {Master Thesis}, author = {Jeschke, Bj{\"o}rn-Marcel}, title = {Alternativen zum Dijkstra Algorithmus in der (Nah-) Verkehrsoptimierung}, pages = {74}, year = {2017}, abstract = {In dieser Arbeit betrachten wir das Problem, f{\"u}r den Fahrplan eines (Nah-) Verkehrsnetzes schnellste Wege zu berechnen. Da die Verkehrsmittel zu unterschiedlichen Zeiten von den einzelnen Haltestellen/Bahnh{\"o}fen abfahren, kann das Problem nicht ohne Weiteres mit einem „statischen" Graphen modelliert werden. Es gibt zwei unterschiedliche Ans{\"a}tze f{\"u}r dieses zeitabh{\"a}ngige Problem: Erstens k{\"o}nnen die verschiedenen An-/Abfahrtereignisse an einem Halt durch „Kopien" dargestellt werden, das ist das zeit-expandierte Modell. Zweitens k{\"o}nnen die Gewichte der Kanten zeitabh{\"a}ngig sein, das ist das zeitabh{\"a}ngige Modell. Wir untersuchen in dieser Arbeit, wie der „klassische" Dijkstra-Algorithmus und der A* Algorithmus mit einer geeigneten Heuristik im Vergleich abschneiden. Die gew{\"a}hlte Heuristik ist der Abstand zum Zielknoten, wenn die Abfahrtszeiten ignoriert werden. Nach unseren Untersuchungen zeigt sich, dass der A* Algorithmus dem Dijkstra-Algorithmus weit {\"u}berlegen ist f{\"u}r gen{\"u}gend große Nahverkehrsnetze. Wir testen anhand der echten Verkehrsnetze von Berlin und Aachen. Unsere Berechnungen zeigen, dass die gew{\"a}hlte Heuristik besonders gut ist f{\"u}r Start- und Zielknoten, welche unabh{\"a}ngig von ihrer Distanz nur 1-2 verschiedene m{\"o}gliche k{\"u}rzeste Pfade f{\"u}r alle Zeitschritte haben. Dort ist der A* Algorithmus bis zu 20-mal schneller. Dies kommt aber nicht h{\"a}ufig in unseren Testinstanzen vor. Die einzelnen Laufzeitvergleich zeigen, dass der A* Algorithmus durchschnittlich 7-mal so schnell ist wie der Dikstra-Algorithmus.}, language = {de} } @misc{Euler2018, type = {Master Thesis}, author = {Euler, Ricardo}, title = {The Bienstock Zuckerberg Algorithm for the Rolling Stock Rotation Problem}, pages = {73}, year = {2018}, abstract = {The design of rolling stock rotations is an important task in large-scale railway planning. This so-called rolling stock rotation problem (RSRP) is usually tackled using an integer programming approach. Markus Reuther did so in his dissertation [15] for the ICE railway network of DB ("Deutsche Bahn"). Due to the size of the network and the complexity of further technical requirements, the resulting integer problems tend to become very large and computationally involved. In this thesis, we tackle the linear programming relaxation of the RSRP integer program. We will do so by applying a modified version of an algorithm recently proposed by Dan Bienstock and Mark Zuckerberg [2] for the precedence constrained production scheduling problem that arises in open pit mine scheduling. This problem contains a large number of "easy" constraints and a relatively small number of "hard" constraints. We will see that a similar problem structure can also be found in the RSRP. The Bienstock-Zuckerberg algorithm relies on applying Lagrangian relaxation to the hard constraints as well as on partitioning the variable set. We propose three different partition schemes which try to exploit the specific problem structure of the RSRP. Furthermore, we will discuss the influence of primal degeneracy on the algorithm's performance, as well as possible merits of perturbating the right-hand side of the constraint matrix. We provide computational results to assess the performance of those approaches.}, language = {en} }