Detailansicht
Ring star problem with user equilibrium constraints
Nadja Friesen
Art der Arbeit
Masterarbeit
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Studiumsbezeichnung bzw. Universitätlehrgang (ULG)
Masterstudium Quantitative Economics, Management and Finance
Betreuer*in
Walter Gutjahr
DOI
10.25365/thesis.49542
URN
urn:nbn:at:at-ubw:1-28679.64262.494893-5
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
In dieser Masterarbeit wird das Ring Star Problem (RSP) als ein bikriterielles Problem
gelöst. Im Unterschied zu der allgemeinen Formulierung des RSP, wird hier die
Zuweisung der Knoten zu dem Ring mit Hilfe des Benutzergleichgewichts bestimmt. Folglich
ist diese Zuweisung nicht nur basierend auf der Entfernung eines Knotens zu Ring,
sondern auch auf der "Service Qualität" dort. Diese wird an jedem Knotenpunkt an dem
Ring ermittelt und hängt von den insgesamt zugewiesenen Bedarf ab. Als Lösungsmethode
wurde der NSGA-II implementiert. Die einzelnen Zielfunktionen wurden jeweils mit
dem Clarke&Wright Algorithmus und dem Frank Wolfe Algorithmus gelöst. Wobei der
Savings-Algorithmus ein Traveling Salesman Problem (TSP) für den Ring gelöst hat und
der Frank Wolfe Algorithmus die Zuweisung der Knoten zu dem Ring. Um diesen anwenden
zu können wurde die zweite Zielfunktion in ein Netzwerk-Problem umformuliert.
Da keine Benchmark Lösungen für dieses Mehrziel-Problem vorliegen wurden kleine Test
Instanzen generiert und enumeriert. Anhand dieser wurde die Lösungsqualität der implementierten
Metaheuristik evaluiert.
Abstract
(Englisch)
In this Master’s Thesis the bi-objective Ring Star Problem is solved. Different to the
general formulation of the RSP, the assignment problem was extended by User Equilibrium
constraints. In that way the assignment to ring is not just based on the distance
to it, but also on the "service quality", respectively the incoming flow to a node on the
ring. As a solution approach the NSGA-II was implemented, with nested Clarke&Wright
savings algorithm and Frank Wolfe algorithm. The savings algorithm was used for solving
a TSP for each solution. For the approximation of the User Equilibrium the Frank
Wolfe algorithm was applied, after the assignment problem was transferred into a network
flow problem. Since no benchmark solution for such a formulation of a RSP exists,
test instances were generated and enumerated. These were used for the evaluation of the
quality of the implemented solution method.
Schlagwörter
Schlagwörter
(Englisch)
Ring Star Problem User Equilibrium Multi-objective optimization NSGA-II Clarke&Wright Savings Algorithm Frank Wolfe Algorithm
Schlagwörter
(Deutsch)
Ring Star Problem Benutzergleichgewicht Mehrzieloptimierung NSGA-II Clarke&Wright Savings Algorithmus Frank Wolfe Algorithmus
Autor*innen
Nadja Friesen
Haupttitel (Englisch)
Ring star problem with user equilibrium constraints
Paralleltitel (Deutsch)
Ring Star Problem mit Benutzergleichgewichts Nebenbedingungen
Publikationsjahr
2017
Umfangsangabe
viii, 69 Seiten : Diagramme
Sprache
Englisch
Beurteiler*in
Walter Gutjahr
Klassifikation
85 Betriebswirtschaft > 85.99 Betriebswirtschaft: Sonstiges
AC Nummer
AC14487187
Utheses ID
43792
Studienkennzahl
UA | 066 | 920 | |