Verleihung der Diplom- und Masterarbeitspreise 1999

von ERWIN PESCH, BONN

Auch in diesem Jahr hatte die GOR zu einem studentischen Wettbewerb aufgerufen, bei dem in 1998 abgeschlossene Diplomarbeiten (auf dem Gebiet des Operations Research) ausgezeichnet werden sollten.

Insgesamt wurden nur 4 Arbeiten eingereicht, und ich möchte an dieser Stelle allen vier Studierenden ganz herzlich für ihre Teilnahme danken. Die Arbeiten deckten ein breites Spektrum an Modellen, Methoden und Anwendungen des Operations Research ab. Alle Arbeiten waren von den Betreuern als hervorragend eingestuft worden. Die Jury hatte damit die schwierige Aufgabe herauszufinden, welche dieser Diplomarbeiten als preiswürdig einzuschätzen seien.

Als Mitglieder der Jury fungierten: Prof. Dr. Heiner Kuhn, Katholische Universität Eichstätt, Dr. Carsten Jordan, KPMG-Consulting und Prof. Dr. Erwin Pesch (Vorsitz), Universität Bonn.

Nach gründlicher Lektüre der eingereichten Arbeiten kam die Jury zu dem Ergebnis, daß nicht nur eine, sondern zwei Arbeiten (gleichermaßen) preiswürdig seien. Es handelt sich dabei um die Arbeiten von Herrn Olaf Jahn und von Frau Anja Houdek.

Bei der Verleihung der diesjährigen Diplomarbeitspreise der GOR
(v.l.n.r.: die Preisträger Frau Anja Houdek, Herr Olaf Jahn, Prof. Dr. Erwin Pesch)

Olaf Jahn, TU Berlin (Betreuer: Prof. Dr. R. Möhring)
„Multicommodity Flow-Modelle und Algorithmen zur dynamischen Lenkung von Verkehrsströmen“

Navigationssysteme (oder Route Guidance Systeme) in Fahrzeugen lotsen den Fahrer üblicherweise durch Berechnung eines kürzesten Weges basierend auf einer digitalen Straßenkarte, der ermittelten Position und aktueller Verkehrsinformationen, die per Funk übertragen werden, ohne Wissen welche Routen die anderen Fahrzeuge nehmen. Solche Navigationssysteme minimieren die Gesamtfahrzeit in einem Straßennetz (d.h. die Summe aller Einzelfahrzeiten, was als Maß der Straßenbelastung angesehen werden kann). Dadurch ließe sich auf einem vorhandenen Straßennetz »mehr« Verkehr realisieren. Dieser positive Effekt geht jedoch verloren, sobald der Anteil der mit einem Navigationssystem ausgestatteten Fahrzeuge einen gewissen Prozentsatz übersteigt. Die einfachen Algorithmen sind nämlich nicht in der Lage die Auswirkungen ihrer eigenen Empfehlungen zu berücksichtigen. Als Folge könnte ein Navigationssystem Staus gerade erst verursachen, indem es viele Fahrzeuge auf die gleiche Straße schickt.

Herr Jahn minimiert die Straßengesamtbelastung (Summe der Fahrzeiten auf allen benutzten Wegen) „unter Vermeidung, daß wenige Fahrer auf große Umwege gelotst werden, damit die Mehrheit der Fahrer die schnelleren Wege benutzen können“, um die Akzeptanz eines solchen Systems zu gewährleisten. Dazu wird garantiert, daß die Länge jedes zu generierenden Weges nicht wesentlich von der Länge des kürzesten Weges abweicht. Das Problem wird NP-schwer. Die Modellierung erfolgt als Multicommodity Minimum Cost Flow Problem in dem der Verkehr als Fluß in einem gerichteten Graphen aufgefaßt wird. Jede Kante hat eine Kapazität, eine Länge und eine Fahrzeit in nichtlinearer Abhängigkeit vom Fluß.
Mittels einer Feasible Direction Methode wird das eigentliche nichtlineare Problem gelöst. In jeder Iteration tritt das Problem mit konstanten Kantenfahrzeiten auf und wird mittels Column Generation gelöst. Wegen der Längenbeschränkungen werden für die auftretenden Constrained Shortest Path Probleme ein Branch and Bound und einem Labelling Verfahren eingesetzt.

Anja Houdek, Universität Ulm (Betreuer: Prof. Dr. U. Rieder)
„Kanalvergabe in Mobilfunknetzen“

In Mobilfunktnetzen wird das zu versorgende Gebiet in viele kleine Einheiten, sog. Zellen, aufgeteilt. Jede Zelle enthält eine Basisstation, mit der die mobilen Teilnehmer über Funk kommunizieren; die mobilen Teilnehmer kommunizieren nicht direkt miteinander. Für die Datenübertragung zwischen Basisstation und einer Mobilstation muß ein Funkkanal bereitgestellt werden. Um Interferenzstörungen zu vermeiden, müssen bestimmte Abstände zwischen Kanälen, die im selben Gebiet benutzt werden, eingehalten werden, d.h. auch, es dürfen nur hinreichend weit entfernte Zellen dieselben Kanäle benutzen. Wie sollen die Kanäle den Stationen zugeteilt werden (Fixed-Channel-Assignment), um möglichst viele Verbindungen aufzubauen, wobei Mindestabstände zur Vermeidung von Störungen der zu übertragenden Information infolge von Interferenz eingehalten werden müssen.

Können bei laufenden Datenübertragungen die hierzu verwendeten Kanäle gewechselt werden, so wird jede Anforderung bearbeitet, solange ein beliebiger freier Kanal existiert (Maximum-Packing-Strategie). Für wenig genutzte Mobilfunksysteme ist die Maximum-Packing-Strategie die beste Lösung, bei hoher Auslastung ist Fixed-Channel-Assignment optimal. Das Problem wird als zeitdiskretes stochastisches dynamisches Programm modelliert unter der Zielsetzung der Durchschnittskostenminimierung. Die Modellierung erlaubt die Integration des Fixed-Channel-Assignment, des Maximum-Packing sowie die Beschreibung jeder Zwischenform. Es werden Optimalitätskriterien hergeleitet und gezeigt, unter welchen Voraussetzungen eine Fixed-Channel-Assignment Politik dynamischen Kanalvergabeverfahren überlegen ist.

Beide Arbeiten demonstrieren in beeindruckender Weise die Kombination und Integration theoretischer Ergebnisse des Operations Research und deren Möglichkeiten zur effektiven Lösung vielfältiger Probleme in der Praxis.