@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{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{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} }