Title (eng)
Ring star problem with user equilibrium constraints
Parallel title (deu)
Ring Star Problem mit Benutzergleichgewichts Nebenbedingungen
Author
Nadja Friesen
Advisor
Walter Gutjahr
Assessor
Walter Gutjahr
Abstract (deu)
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 (eng)
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.
Keywords (eng)
Ring Star ProblemUser EquilibriumMulti-objective optimizationNSGA-IIClarke&Wright Savings AlgorithmFrank Wolfe Algorithm
Keywords (deu)
Ring Star ProblemBenutzergleichgewichtMehrzieloptimierungNSGA-IIClarke&Wright Savings AlgorithmusFrank Wolfe Algorithmus
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1339344
rdau:P60550 (deu)
viii, 69 Seiten : Diagramme
Number of pages
78
Association (deu)
Title (eng)
Ring star problem with user equilibrium constraints
Parallel title (deu)
Ring Star Problem mit Benutzergleichgewichts Nebenbedingungen
Author
Nadja Friesen
Abstract (deu)
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 (eng)
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.
Keywords (eng)
Ring Star ProblemUser EquilibriumMulti-objective optimizationNSGA-IIClarke&Wright Savings AlgorithmFrank Wolfe Algorithm
Keywords (deu)
Ring Star ProblemBenutzergleichgewichtMehrzieloptimierungNSGA-IIClarke&Wright Savings AlgorithmusFrank Wolfe Algorithmus
Subject (deu)
Type (deu)
Persistent identifier
https://phaidra.univie.ac.at/o:1339345
Number of pages
78
Association (deu)
License
Citable links
Other links
Managed by
Details
Metadata
Export formats
Universitätsring 1, 1010 Wien | T
T +43-1-4277-0