@misc{WessaelyWernerEckeletal., author = {Wess{\"a}ly, Roland and Werner, Axel and Eckel, Klaus and Seibel, Julia and Orlowski, Sebastian and Louchet, Hadrien and Patzak, Erwin and Bentz, Winfried}, title = {Sch{\"a}tze heben bei der Planung von FTTx-Netzen: optimierte Nutzung von existierenden Leerrohren - eine Praxisstudie}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14861}, abstract = {Das vom BMBF gef{\"o}rderte Projekt FTTX-PLAN entwickelt mathematische Modelle und Optimierungsverfahren, um automatisiert kostenoptimierte FTTx-Netze berechnen zu k{\"o}nnen. Wir zeigen anhand einer Praxisstudie in Zusammenarbeit mit der Regensburger R-KOM, wie ein Planer von diesen Verfahren profitieren kann, um die Auswirkungen bestimmter Entscheidungen auf die Netzstruktur und -kosten zu untersuchen. Wir illustrieren dies am Beispiel eines FTTB/FTTH-Vergleichs, der Variation von Kundenanbindungsraten und der gezielten Ausnutzung existierender Leerrohre, um Tiefbau zu vermeiden.}, language = {de} } @misc{Werner, author = {Werner, Axel}, title = {Kombinatorische Optimierung und die 40-Punkte-Regel}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14871}, abstract = {Wieviele Punkte braucht eine Mannschaft in der Fußball-Bundesliga mindestens, um sicher dem Abstieg zu entgehen? Wir benutzen kombinatorische Optimierung, um diese und {\"a}hnliche Fragen zu beantworten.}, language = {de} } @misc{Wyczik, 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}, 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} } @masterthesis{Akil, type = {Bachelor Thesis}, author = {Akil, Fatima}, title = {Lineare Gleichungssysteme modulo T}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-71560}, pages = {52}, 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} } @masterthesis{Vornberger, 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}, 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{Husemann, type = {Bachelor Thesis}, author = {Husemann, Christoph}, title = {Multimodales Routing mit Leihfahrradsystemen am Beispiel Berlins}, pages = {45}, 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} } @misc{Mett, type = {Master Thesis}, author = {Mett, Fabian}, title = {{\"U}ber die optimale Platzierung von Ladestationen f{\"u}r Elektrobusse}, pages = {76}, 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{Wirsching, type = {Bachelor Thesis}, author = {Wirsching, Marie}, title = {Der Einfluss von Langzahlarithmetik auf das Gewichtsraumpolyeder in mehrkriterieller Optimierung}, pages = {59}, abstract = {Die Arbeit befasst sich mit einem gewichtsraumbasierten Algorithmus, der ganzzahlige und lineare Optimierungsprobleme mit mehreren Zielfunktionen l{\"o}st und die Menge der unterst{\"u}tzt nicht dominierten Punkte ermittelt. Die dabei erzeugten Gewichtsraumpolyeder sind das entscheidende Mittel, um die gesuchte L{\"o}sungsmenge zu bestimmen. Aus softwaretechnischer Sicht sind numerische Ungenauigkeiten potentielle Fehlerquellen, die sich negativ auf das Endergebnis auswirken. Aus diesem Grund untersuchen wir anhand von Zuweisungs- und Rucksackinstanzen mit 3 Zielfunktionen, inwieweit der Gebrauch von Langzahlarithmetik die Gewichtsraumpolyeder und die damit verbundene Menge der unterst{\"u}tzt nicht dominierten Punkte beeinflusst.}, language = {de} } @misc{Jeschke, type = {Master Thesis}, author = {Jeschke, Bj{\"o}rn-Marcel}, title = {Alternativen zum Dijkstra Algorithmus in der (Nah-) Verkehrsoptimierung}, pages = {74}, 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{BorndoerferEgererKarbsteinetal., author = {Bornd{\"o}rfer, Ralf and Egerer, Ascan and Karbstein, Marika and Messerschmidt, Ralf and Perez, Marc and Pfisterer, Steven and Strauß, Petra}, title = {Kombil{\"o}sung: Optimierung des Liniennetzes in Karlsruhe}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-69677}, abstract = {Wir beschreiben die Optimierung des Nahverkehrsnetzes der Stadt Karlsruhe im Zusammmenhang mit den Baumaßnahmen der sogenannten Kombil{\"o}sung.}, language = {de} }