Detailansicht
Ring star problem for disaster relief
Göran Sjöström
Art der Arbeit
Diplomarbeit
Universität
Universität Wien
Fakultät
Fakultät für Wirtschaftswissenschaften
Betreuer*in
Richard Hartl
DOI
10.25365/thesis.17314
URN
urn:nbn:at:at-ubw:1-29136.32605.474455-2
Link zu u:search
(Print-Exemplar eventuell in Bibliothek verfügbar)
Abstracts
Abstract
(Deutsch)
In Zeiten von Katastrophen ist die schnelle Hilfe für die betroffene Bevölkerung von größter Wichtigkeit. Mit Hilfe des Ring Star Problem (RSP) als Modell für Katastrophenhilfe, können hierfür unterschiedlichste Situationen in Betracht gezogen werden, um eine effiziente Hilfeleistung zu garantieren.
Da die gesamte betroffene Bevölkerung nicht immer direkt mit Hilfslieferungen versorgt werden kann, wird mithilfe des RSP versucht diese Lieferungen an angrenzende Gebiete, zu welchen der Zugang möglich ist, die betroffene Bevölkerung zu erreichen. Diese Gebiete/Ortschaften werden dann mit Hilfe einer Routenplanung miteinander verbunden, um eine effiziente und schnelle Hilfslieferung in alle betroffenen Gebiete zu garantieren.
Zur Untersuchung dieses Problems wurden Datensätze in den Größen von 12 bis 100 Ortschaften untersucht.
Zur Lösung dieses Problems wurden unterschiedliche Ansätze untersucht. Zu einem wurde eine exakte Lösungsmethode mithilfe einer CPLEX Schnittstelle im Microsoft Visual C++ implementiert. Diese Methode wurde mit einer integrativen gewichteten Zielfunktion gelöst. Als Grundlage hierfür diente das p-Median, für die Zuweisung der nicht besuchten Gebiete zu den besuchten Ortschaften, sowie das Travelling Salesman Problem (TSP) für die effiziente Routenplanung. Die erzielten Werte dieser exakten Methode dienten in weiterer Folge als Vergleichswerte für weitere Lösungsansätze.
Infolge wurde das Problem in zwei Teilprobleme zerlegt (p-Median und TSP). Diese wurden zu einem Teil sukzessiv mithilfe der CPLEX Schnittstelle gelöst. Zum Anderen wurde nur der Zuweisungsteil, das p-Median, mit CPLEX gelöst und im Anschluss das Routing der besuchten Orte mithilfe von Heuristiken.
Weiters wurde das gesamte Problem mittels der Large Neighbourhood Search (LNS) Metaheuristik gelöst. Dies erfolgte durch sukzessives Zerstören und Reparieren von bestehenden Zuweisungen und Routen.
Die Auswertungen der gesamten Daten ergaben ein klares Bild bezüglich der Effizienz der erstellten, heuristischen Lösungsansätze. Die Zerlegung des RSP in zwei Teilprobleme und hierbei die Kombination von exakter und heuristischer Methoden stellte eine äußerst effektive Lösungsmethode dar. So erreichte diese Methode im Durchschnitt eine Lösungsgüte von 99,77%, und benötigte hierfür lediglich 0,01% (0,82 Sekunden) der Rechenzeit im Vergleich zur optimalen Lösung. Die Metaheuristik konnte eine noch bessere Lösung erzeugen, welche im Durchschnitt nur 0,01% von der optimalen Lösung entfernt war. Die Rechenzeit lag im Durchschnitt bei lediglich 2,19% der exakten Lösung, was einer durchschnittlichen Dauer von 257,87 Sekunden entspricht.
Abstract
(Englisch)
In disaster situations, quick relief for the affected population is the key. Ring Star Problem (RSP) can be used to model problems related to Disaster Relief. The idea of RSP lies in the assumption that in post-disaster not all of the affected population can be supplied directly with aid. Therefore they would need to travel to the closest location where help can been supplied. For solving the problem several approaches were implemented. An integrative exact weighted sum approach and as well two step methods. Additionally different Large Neighbourhood Search (LNS) approaches were created. The data was then evaluated by comparing the achieved results of costs and the needed computing time for achieving results. Instances up to 100 nodes could be solved to optimality with the integrative weighted sum approach. The LNS solved up to 100 nodes efficiently.
Schlagwörter
Schlagwörter
(Englisch)
P-Median Travelling Salesman Problem Large Neighbourhood Search Ring Star Problem
Schlagwörter
(Deutsch)
P-Median Travelling Salesman Problem Large Neighbourhood Search Ring Star Problem
Autor*innen
Göran Sjöström
Haupttitel (Englisch)
Ring star problem for disaster relief
Paralleltitel (Deutsch)
Ring Star Problem für Katastrophenhilfe
Publikationsjahr
2011
Umfangsangabe
VII, 43 S. : graph. Darst.
Sprache
Englisch
Beurteiler*in
Richard Hartl
AC Nummer
AC08884313
Utheses ID
15515
Studienkennzahl
UA | 157 | | |