1486
deu
reportzib
0
2012-03-19
2012-03-19
--
Schätze heben bei der Planung von FTTx-Netzen: optimierte Nutzung von existierenden Leerrohren - eine Praxisstudie
Das vom BMBF geförderte Projekt FTTX-PLAN entwickelt mathematische Modelle und Optimierungsverfahren, um automatisiert kostenoptimierte FTTx-Netze berechnen zu kö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.
1438-0064
http://www.vde-verlag.de/buecher/453339/breitbandversorgung-in-deutschland-itg-fb-227.html
urn:nbn:de:0297-zib-14861
Ersch. in: ITG (Hrsg.) Breitbandversorgung in Deutschland (ITG-FB 227) Vorträge der 5. ITG-Fachkonferenz vom 29. bis 30. März 2011 in Berlin ITG-Fachbericht Band 227, 2011, ISBN 978-3-8007-3339-2
Axel Werner
Roland Wessäly
Axel Werner
Klaus Eckel
Julia Seibel
Sebastian Orlowski
Hadrien Louchet
Erwin Patzak
Winfried Bentz
ZIB-Report
11-47
deu
uncontrolled
Praxisstudie
deu
uncontrolled
Optische Zugangsnetze
deu
uncontrolled
Optimierung
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
https://opus4.kobv.de/opus4-zib/files/1486/ITG-2011.pdf
1487
deu
reportzib
0
2012-03-19
2012-03-19
--
Kombinatorische Optimierung und die 40-Punkte-Regel
Wieviele Punkte braucht eine Mannschaft in der Fußball-Bundesliga mindestens, um sicher dem Abstieg zu entgehen? Wir benutzen kombinatorische Optimierung, um diese und ähnliche Fragen zu beantworten.
1438-0064
urn:nbn:de:0297-zib-14871
Ersch. in: Mitteilungen der DMV, 19 (2011) 153-157
Axel Werner
Axel Werner
ZIB-Report
11-48
deu
uncontrolled
Kombinatorische Optimierung
deu
uncontrolled
Sport
deu
uncontrolled
Bundesliga
GENERAL
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
https://opus4.kobv.de/opus4-zib/files/1487/ZIB-Report-40-punkte.pdf
7155
2018
deu
44
masterthesis
0
--
--
--
Optimierung von Deployment- und Umgebungs-Integrität durch ein dezentrales Konfigurationsrepository auf Basis einer Blockchain
Viele Firmen nutzen fü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ür den Endnutzer. Hierbei ist es wichtig, dass die Konfiguration der Server regelmäßig überprüft wird. Eine solche Sicherstellung der Deployment- und Umgebungs-Integrität wird meistens durch eine Mitarbeiter der Firma oder durch einen externen Dienstleister erbracht. D.h. die Firma muss sich auf die Zuverlässigkeit eines Mitarbeiters oder einer externen Dienstleistung verlassen, bie zunehmender Komplexität ist sie sogar abhängig.
Das Ziel dieser Masterarbeit ist es, zu untersuchen, ob die Sicherstellung der Deployment- und Umgebungs-Integrität durch automatisierte kryptografische Beweise, anstelle externer Dienstleistungen oder anderer Mitarbeiter, gewährleistet werden kann. Als Anwendungsfall dient die Toll Collect GmbH. Im ersten Teil dieser Arbeit wird das Matheamtische Modell einer Blockchain erläutert. die Blockchain wurde erstmals in einem Dokument, welches unter dem Pseudonym Satoshi Nakamoto verö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ät durch eine heirführ entwickelte Blockchainlösung dezentralisiert werden. Es wird außerdem der Übergang vom Mathematischen Modell zur Implementierung gezeigt.
Thorsten Koch
Christopher Wyczik
Ralf Borndörfer
Ralf Borndörfer
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
MODAL-SynLab
MODAL-Gesamt
Technische Universität Berlin
7156
2018
deu
52
bachelorthesis
0
--
--
--
Lineare Gleichungssysteme modulo T
Mit dem Voranschreiten der Technologie erhalten die öffentlichen Verkehrsmittel eine größere Bedeutung. Die Beförderung mehrerer Personen eröffnet der Gesellschaft viele Möglichkeiten, unter Anderem den Vorteil der Zeitersparnis. Die Dauer des Verkehrswegs mit öffentlichen Verkehrsmitteln ist häufig geringer, als die mit individuellen Verkehrsmitteln. Jedes öffentliche Transportmittel ist mit einem Fahrplan versehen. Dieser bietet Passagieren, die öffentliche Verkehrsmittel öfter nutzen, eine Strukturierung und Planung ihrer Zeit. Dabei lassen sich Taktfahrpläne aufgrund ihres periodischen Verhaltens leicht einprägen. Dieses periodische Verhalten ist durch mathematische Modellierungen darstellbar. Das persönliche Nutzverhalten vieler Bürger im Personenverkehr ist auf die öffentlichen Verkehrsmittel beschrä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ährend ich dieses Problem betrachtet habe, wurde ich auf das Rechnen mit linearen Gleichungssystemen modulo T aufmerksam. Bei periodischen Taktfahrplänen wird ein einheitliches zeitliches Muster, welches sich nach T Minuten wiederholt, betrachtet. Das dabei zu betrachtende Lösungsproblem eröffnet ein Teilgebiet der Mathematik, welches bislang nicht im Vordergrund stand: Das Lösen linearer Gleichungen modulo T, wobei T für die Zeit in Minuten steht und somit 60 ist. Da 60 keine Primzahl ist, kann – wie im Laufe der Arbeit präsentiert – das lineare Gleichungssystem nicht mehr über einen Körper gelöst werden. Lineare Gleichungssysteme werden nun über Nicht-Körpern betrachtet. Die Literatur weist sowohl im deutschsprachigem als auch im englischsprachigen Raum wenig Umfang bezüglich linearer Gleichungssysteme über Nicht-Körper auf. Der Bestand an Fachliteratur bezü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 über Restklassenringe, die keinen Körper bilden, nicht fündig. Dabei recherchierte ich sowohl in den Universitätsbibliotheken als auch in webbasierenden Suchmaschinen.
Aufgrund dem geringen Bestand an Fachliteratur in diesem Kontext, war ich gezwungen, an vielen Stellen eigene logische Verknüpfungen zu konzipieren und zu beweisen. Dies brachte viele Schwierigkeiten mit sich, die mit bestmöglichem Verständnis bearbeitet wurden.
Abseits der Zugänglichkeit der Literatur, finde ich es sehr überraschend, dass sich viele Professoren der Mathematik mit diesem Themenbereich nicht beschä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ärliteratur dienen kann.
urn:nbn:de:0297-zib-71560
false
true
Ralf Borndörfer
Fatima Akil
Ralf Borndörfer
Niels Lindner
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
ECMath-MI3
Freie Universität Berlin
https://opus4.kobv.de/opus4-zib/files/7156/Akil2018.Lineare Gleichungssysteme modulo T (Bachelor's thesis).pdf
7157
2018
deu
49
bachelorthesis
0
--
--
--
Approximation von Windkomponenten in der Luftfahrt durch lineare Interpolation
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ämlich das statische WIP auf einer Planfläche (SWIPP). Dazu wird zuerst ein Algorithmus besprochen, der das SWIPP zwar lö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. Ä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öst. Hier wird deutlich seltener
auf die Interpolation zwischen vier Punkten zurückgegriffen - stattdessen wird fast immer linear zwischen zwei Punkten interpoliert. Die Algorithmen zum Lö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 übertrifft.
urn:nbn:de:0297-zib-71570
false
true
Ralf Borndörfer
Leo Vornberger
Ralf Borndörfer
Thorsten Koch
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
LHS-ATN
Freie Universität Berlin
https://opus4.kobv.de/opus4-zib/files/7157/Vornberger2018.Approximation von Windkomponenten in der Luftfahrt durch lineare Interpolation (Bachelor's thesis).pdf
7158
2018
deu
45
bachelorthesis
0
--
--
--
Multimodales Routing mit Leihfahrradsystemen am Beispiel Berlins
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.
Ralf Borndörfer
Christoph Husemann
Ralf Borndörfer
Günter Rote
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
MOIN
Freie Universität Berlin
7161
2018
deu
76
masterthesis
0
--
--
--
Über die optimale Platzierung von Ladestationen für Elektrobusse
In dieser Arbeit wird die Platzierung von Ladestationen für Elektrobusse untersucht. Dabei soll fü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ächst wird der Fall betrachtet, dass die Batterie an jeder Station komplett vollgeladen werden könnte. Dieses Problem stellt sich als NP-schwer heraus. Für einige einfachere Fä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ösung vereinfachter Problemstellungen gegeben und analysiert. Wird zudem angenommen, an jeder Station würde ein individueller Wert geladen, so ist das Problem schon für nur eine einzige Linie NP-schwer. Dennoch werden zwei exakte und ein approximierender Algorithmus entwickelt. Schließlich wird eine Batteriekapazität hinzugefügt und die zuvor entwickelten Algorithmen
werden entsprechend angepasst. Für die abschließende Problemdefinition werden verschiedene Batteriegröß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ößeren Teil der Kosten ausmachen als die Ladestationen. Zudem sollten kleinere Batterien statt größerer und mehr Ladestationen genutzt werden.
false
true
Ralf Borndörfer
Fabian Mett
Ralf Borndörfer
Natalia Kliewer
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
ECMath-MI3
Freie Universität Berlin
7151
2018
deu
59
bachelorthesis
0
--
--
--
Der Einfluss von Langzahlarithmetik auf das Gewichtsraumpolyeder in mehrkriterieller Optimierung
Die Arbeit befasst sich mit einem gewichtsraumbasierten Algorithmus, der ganzzahlige und lineare Optimierungsprobleme mit mehreren Zielfunktionen
löst und die Menge der unterstützt nicht dominierten Punkte ermittelt. Die dabei erzeugten Gewichtsraumpolyeder sind das entscheidende Mittel, um die gesuchte Lö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ützt nicht dominierten Punkte beeinflusst.
false
true
Martin Skutella
Marie Wirsching
Ralf Borndörfer
Ralf Borndörfer
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
CRC1026
Technische Universität Berlin
7153
2017
deu
74
masterthesis
0
--
--
--
Alternativen zum Dijkstra Algorithmus in der (Nah-) Verkehrsoptimierung
In dieser Arbeit betrachten wir das Problem, für den Fahrplan eines (Nah-) Verkehrsnetzes schnellste Wege zu berechnen. Da die Verkehrsmittel zu unterschiedlichen Zeiten von den einzelnen Haltestellen/Bahnhöfen abfahren, kann das Problem nicht ohne Weiteres mit einem „statischen“ Graphen modelliert werden. Es gibt zwei unterschiedliche Ansätze für dieses zeitabhängige Problem: Erstens können die verschiedenen An-/Abfahrtereignisse an einem Halt durch „Kopien“ dargestellt werden, das ist das zeit-expandierte Modell. Zweitens können die Gewichte der Kanten zeitabhängig sein, das ist
das zeitabhä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ä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 überlegen ist für genügend große Nahverkehrsnetze. Wir testen anhand der echten Verkehrsnetze von Berlin und Aachen. Unsere Berechnungen zeigen, dass die gewählte Heuristik besonders gut ist für Start- und Zielknoten, welche unabhängig von ihrer Distanz nur 1–2 verschiedene mögliche kürzeste Pfade für alle Zeitschritte haben. Dort ist der A* Algorithmus bis zu 20-mal schneller. Dies kommt aber nicht häufig in unseren Testinstanzen vor. Die einzelnen Laufzeitvergleich zeigen, dass
der A* Algorithmus durchschnittlich 7-mal so schnell ist wie der Dikstra-Algorithmus.
false
true
Ralf Borndörfer
Björn-Marcel Jeschke
Ralf Borndörfer
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
ECMath-MI3
Freie Universität Berlin
6967
deu
reportzib
0
--
2018-07-30
--
Kombilösung: Optimierung des Liniennetzes in Karlsruhe
Wir beschreiben die Optimierung des Nahverkehrsnetzes der Stadt Karlsruhe im Zusammmenhang mit den Baumaßnahmen der sogenannten Kombilösung.
1438-0064
urn:nbn:de:0297-zib-69677
Der Nahverkehr 1-2, p. 33-38, 2019
07.11.2018
Ralf Borndörfer
Ralf Borndörfer
Ascan Egerer
Marika Karbstein
Ralf Messerschmidt
Marc Perez
Steven Pfisterer
Petra Strauß
ZIB-Report
18-45
deu
uncontrolled
ÖPNV
deu
uncontrolled
Linienplanung
Mathematics of Computing
GENERAL
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Borndörfer, Ralf
ECMath-MI3
MATHEON-B15
MODAL-RailLab
MODAL-Gesamt
https://opus4.kobv.de/opus4-zib/files/6967/ZR-18-45.pdf