@misc{Masing, type = {Master Thesis}, author = {Masing, Berenike}, title = {Optimal Line Planning in the Parametric City}, abstract = {One of the fundamental steps in the optimization of public transport is line planning. It involves determining lines and assigning frequencies of service such that costs are minimized while also maximizing passenger comfort and satisfying travel demands. We formulate the problem as a mixed integer linear program that considers all circuit-like lines in a graph and allows free passenger routing. Traveler and operator costs are included in a linear scalarization in the objective. We apply said programming problem to the Parametric City, which is a graph model introduced by Fielbaum, Jara-D{\´i}az and Gschwender that exibly represents different cities. In his dissertation, Fielbaum solved the line planning problem for various parameter choices in the Parametric City. In a first step, we therefore review his results and make comparative computations. Unlike Fielbaum we arrive at the conclusion that the optimal line plan for this model indeed depends on the demand. Consequently, we analyze the line planning problem in-depth: We find equivalent, but easier to compute formulations and provide a lower bound by LP-relaxation, which we show to be equivalent to a multi-commodity flow problem. Further, we examine what impact symmetry has on the solutions. Supported both by computational results as well as by theoretical analysis, we reach the conclusion that symmetric line plans are optimal or near-optimal in the Parametric City. Restricting the model to symmetric line plans allows for a \kappa-factor approximation algorithm for the line planning problem in the Parametric City.}, language = {en} } @masterthesis{Lange, type = {Bachelor Thesis}, author = {Lange, Johanna}, title = {A Decomposition and Dualization Approach to the Periodic Event Scheduling Problem}, abstract = {Scheduling ist ein wichtiger Forschungsgegenstand im Bereich der diskreten Optimierung. Es geht darum, einen Schedule, d.h. einen Ablaufplan, f{\"u}r gegebene Ereignisse zu finden. Dieser soll optimal hinsichtlich einer Zielfunktion wie zum Beispiel minimaler Dauer oder Kosten sein. Dabei gibt es in der Regel Nebenbedingungen wie Vorrangbeziehungen zwischen den Ereignissen oder zeitliche Einschr{\"a}nkungen, die zu erf{\"u}llen sind. Falls die Ereignisse periodisch wiederkehren, spricht man von periodischem Scheduling. Beispiele sind das Erstellen von Zugfahrpl{\"a}nen, die Schaltungvon Ampelsignalen oder die Planung von Produktionsabl{\"a}ufen. Mathematisch k{\"o}nnen diese Probleme mit dem Periodic Event Scheduling Problem (PESP) modelliert werden, das als gemischt-ganzzahliges Programm formuliert werden kann. In dieser Bachelorarbeit wird ein Ansatz zur L{\"o}sung des PESP mittels Zerlegung und Dualisierung entwickelt. In den Kapiteln 2 und 3 werden zun{\"a}chst die notwendigen graphentheoretischen Grundlagen und das PESP eingef{\"u}hrt. In Kapitel 4 wird das PESP durch Fixierung der ganzzahligen Variablen in lineare Programme zerlegt. Dieses Unterproblem wird dualisiert und wieder in das PESP eingesetzt. Daf{\"u}r ist eine weitere Nebenbedingung n{\"o}tig. Im f{\"u}nften Kapitel behandeln wir die L{\"o}sung des teildualisierten PESP. Eine M{\"o}glichkeit ist es, sich auf eine Teilmenge der Nebenbedingungen zu beschr{\"a}nken. Eine weitere M{\"o}glichkeit ist ein Algorithmus, der{\"a}hnlich wie BendersZerlegung die Nebenbedingungen dynamisch erzeugt. Dieser Algorithmus wird in Kapitel 6 implementiert und an vier Beispielen getestet.}, language = {en} } @misc{Kuehner, type = {Master Thesis}, author = {K{\"u}hner, Arno}, title = {Shortest Paths with Boolean Constraints}, abstract = {For this thesis we study the Constrained Horizontal Flightplanning Problem (CHFPP) for which one has to find the path of minimum cost between airports s and t in a directed graph that respects a set of boolean constraints. To this end we give a survey of three different multilabel algorithms that all use a domination subroutine. We summarize an approach by Knudsen, Chiarandini and Larsen to define this domination and afterwards present our own method which builds on that approach. We suggest different implementation techniques to speed up the computation time, most notably a Reoptimization for an iterative method to solve the problem. Furthermore we implemented the different versions of the algorithm and present statistics on their computation as well as an overview of statistics on the set of real-world constraints that we were given. Finally we present two alternative approaches that tackle the problem, a heuristic with similarities to a Lagrangian relaxation and an approach that makes use of an algorithm which finds the k shortest path of a graph such as the ones of Epstein or Yen.}, language = {en} } @misc{Bortoletto, type = {Master Thesis}, author = {Bortoletto, Enrico}, title = {The tropical tiling of periodic timetable space and a dual modulo network simplex algorithm}, abstract = {We propose a tropical interpretation of the solution space of the Periodic Event Scheduling Problem as a collection of polytropes, making use of the characterization of tropical cones as weighted digraph polyhedra. General and geometric properties of the polytropal collection are inspected and understood in connection with the combinatorial properties of the underlying periodic event scheduling instance. Novel algorithmic ideas are presented and tested, making use of the aforementioned theoretical results to solve and optimize the problem.}, language = {en} } @masterthesis{Kraus, type = {Bachelor Thesis}, author = {Kraus, Luitgard}, title = {A Label Setting Multiobjective Shortest Path FPTAS}, abstract = {Algorithms that solve the shortest path problem can largely be split into the two categories of label setting and label correcting. The Multiobjective Shortest Path (MOSP) problem is a generalization of the classical shortest path problem in terms of the dimension of the cost function. We explore the differences of two similar MOSP label setting algorithms. Furthermore, we present and prove a general method of how to derive Fully Polynomial Time Approximation Schemes (FPTAS) for MOSP label setting algorithms. Finally, we explore two pruning techniques for the one to one variants of exact label setting MOSP algorithms and adapt them to their FPTAS variants.}, language = {en} } @misc{Rahmati, type = {Master Thesis}, author = {Rahmati, Niloofar}, title = {Resource Constrained APSP-Algorithm with Possible Reloading Stops}, language = {en} } @misc{BorndoerferSchwartzSurau, author = {Bornd{\"o}rfer, Ralf and Schwartz, Stephan and Surau, William}, title = {Rooted Maximum Weight Connected Subgraphs with Balancing and Capacity Constraints}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-84427}, language = {en} } @misc{Buwaya, type = {Master Thesis}, author = {Buwaya, Julia}, title = {Optimizing control in a transportation network when users may choose their OD-path}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42330}, school = {Zuse Institute Berlin (ZIB)}, pages = {81}, abstract = {This thesis represents a game-theoretic investigation of the allocation of inspectors in a transportation network, comparing Nash and Stackelberg equilibrium strategies to a strategy in which inspections are conducted proportionally to the traffic volume. It contains specifications for the integration of space and time dependencies and extensive experimental tests for the application on the transportation network of German motorways using real data. Main results are that - although the formulated spot-checking game is not zero-sum - we are able to compute a Nash equilibrium using linear programming and secondly, that experimental results yield that a Nash equilibrium strategy represents a good trade-off for the Stackelberg equilibrium strategy between efficiency of controls and computation time.}, language = {en} } @misc{HarrodSchlechte, author = {Harrod, Steven and Schlechte, Thomas}, title = {A Direct Comparison of Physical Block Occupancy Versus Timed Block Occupancy in Train Timetabling Formulations}, issn = {1438-0064}, doi = {10.1016/j.tre.2013.04.003}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17946}, abstract = {Two fundamental mathematical formulations for railway timetabling are compared on a common set of sample problems, representing both multiple track high density services in Europe and single track bidirectional operations in North America. One formulation, ACP, enforces against conflicts by constraining time intervals between trains, while the other formulation, HGF, monitors physical occupation of controlled track segments. The results demonstrate that both ACP and HGF return comparable solutions in the aggregate, with some significant differences in select instances, and a pattern of significant differences in performance and constraint enforcement overall.}, language = {en} } @misc{FuegenschuhGroesserVierhaus, author = {F{\"u}genschuh, Armin and Gr{\"o}sser, Stefan N. and Vierhaus, Ingmar}, title = {A Global Approach to the Control of an Industry Structure System Dynamics Model}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42932}, abstract = {We consider a system dynamics model that describes the effect of human activity on natural resources. The central stocks are the accumulated profit, the industry structures, and the water resources. The model can be controlled through two time-dependent parameters. The goal in this paper is to find a parameter setting that leads to a maximization of a performance index, which reflects both environmental and economic aspects. Thus, the goal is to identify the most sustainable stock of industry structures within the model's constraints and assumptions. In order to find a proven global optimal parameter set, we formulate the System Dynamics Optimization model as a mixed-integer nonlinear problem that is accessible for numerical solvers. Due to the dynamic structure of the model, certain steps of the solution process must be handled with greater care, compared to standard non-dynamic problems. We describe our approach of solving the industry structure model and present computational results. In addition, we discuss the limitations of the approach and next steps.}, language = {en} }