Meldungen aus der Forschung

Operations Research. Antrittsvorlesung von Prof. Dr. Lin Xie

06.02.2017 Am 25. Januar 2017 hielt Prof. Dr. Lin Xie ihre Antrittsvorlesung zu „Entwicklung und Nutzung von Qualitativen Modellen und Methoden zur Entscheidungsunterstützung“. Darin legte die Wirtschaftsinformatikerin die Relevanz von Modellierung für komplexe Entscheidungen dar und stellte Anwendungsmöglichkeiten vor, unter anderem aus dem Bereich des öffentlichen Personennahverkehrs.

Bei praxisorientierter Forschung denke man oft nur an die großen Herausforderungen wie den Klimawandel, sagte Präsident Sascha Spoun in seiner Laudatio, dabei beträfen uns die kleinen Herausforderungen im Alltag ebenso - zum Beispiel das Umsteigen in einen anderen Bus. Mit der leichten Zugänglichkeit zu großen Datenmengen ändere sich auch die Frage nach Entscheidungen, fuhr er fort. Auch in der digitalen Welt ginge es darum, sich nicht nur auf Zahlen allein zu verlassen, sondern interpretationsfähig zu bleiben.

Dekan Peter Niemeyer ergänzte, dass Xies Methoden in vielen Bereichen anschlussfähig sind und freute sich, dass sie sich für die Wirtschaftsinformatik an der Leuphana entschieden hat. Dies gälte doppelt, da sie als Frau eine Professur für Wirtschaftinformatik inne hat, was in diesem Feld weiterhin selten sei.

Optimierung, Simulation und das Traveling Salesman Problem

In ihrer Forschung untersucht Lin Xie Operations Reaserch. Operations Research ist im Kern mathematische Planung von Unternehmensprozessen und verbindet Methoden aus den Wirtschaftswissenschaften, der Informatik und der angewandten Mathematik. Behandelt werden Fragen der Optimierung und Simulation, oft unter Zuhilfenahme von Modellen. Xie stellte verschiedene Arten von Methoden in Operations Research vor und hielt fest, dass sich Produktionsplanungsprobleme oft als Optimierungsprobleme formulieren lassen.  

Eines der bekanntesten Optimierungsprobleme ist das sogenannte Problem des Handelsreisenden („Traveling Salesman Problem“). Es ist beliebt, denn es veranschaulicht, wie einfache Planungsprobleme komplizierte Lösungen haben können. Ziel der Aufgabe des Handelsreisenden ist es, eine Rundreise durch mehrere Städte so zu planen, dass die Gesamtlänge der Reise minimiert wird sowie der Start- und Endpunkt identisch ist. Das scheint zunächst nicht schwer zu sein: Wenn man drei Städte hat, die der Handelsreisende besuchen soll, zum Beispiel Lüneburg (L), Hamburg (H), Berlin (B), gibt es sechs verschiedene Routen (LHBL, LBHL, HBLH, HLBH, BLHB, BHLB). Man könnte einfach messen wie lang jede Route ist und nimmt dann die kürzeste (im vorliegenden Fall sind jeweils zwei gleichlang, man muss also nur drei vergleichen). Leider gibt es allerdings schon bei 15 Städten 43 Milliarden mögliche Routen und bei 18 Städten bereits 177 Billionen. Da es dermaßen schnell so viele Möglichkeiten werden, verlängert sich mit jeder dazukommenden Stadt die Rechenzeit, die benötigt wird, um eine Lösung zu finden. Xie zeigt, dass es bei bis zu drei Städten noch nicht einmal eine Millisekunde Rechenzeit dauert, um eine Lösung zu finden, bei 16 Städten allerdings schon 20 Jahre.

Modellierung

Deswegen kann man Planungsprobleme ab einer bestimmten Komplexitätsstufe nicht mehr nur mit blanker Rechenkraft lösen und benutzt stattdessen Modellierung, also die Nutzung eines vereinfachten Abbilds des untersuchten Phänomens. Lin Xie stellte ein Beispiel vor: Eine Fahrradfabrik stellt zwei Arten von Fahrrädern her - ein normales Fahrrad und ein Deluxe-Fahrrad. Das normale kann man schnell produzieren, verdient aber auch nicht viel daran. Das Deluxe-Fahrrad ist aufwendiger zu produzieren, man macht damit aber auch mehr Gewinn. Die Fabrik kann nicht durchgängig produzieren (Zeit spielt also eine Rolle) und es gibt eine maximale Produktionsmenge. Was wäre die optimale Produktionsmenge um das erzielte Gewinn zu maximieren? Bei zwei Variablen kann man das anschaulich lösen, indem man eine je Kurve für die begrenzte Arbeitszeit und die maximale Produktionsmenge zeichnet, mit der Produktionsmenge der Deluxe-Fahrräder auf der x-Achse und der Produktionsmenge der normalen Fahrräder auf der y-Achse. Die ideale Produktionsmenge ist dann der Punkt, an dem sich beide Kurven schneiden. Soll noch ein dritter Fahrradtyp, zum Beispiel Premium-Fahrrad, lässt es weiterhin grafisch lösen, nur dass diesenfalls die Lösung kein Punkt wäre, sondern eine Fläche.

Der Öffentliche Nahverkehr als Anwendung für Optimierung

Xie wendet ihre Forschung unter anderem auf den Öffentlichen Personennahverkehr (ÖPNV) an. Dort stellt sich die Situation allerdings erheblich komplexer dar. Auch wenn der behandelte ÖPNV ein, vergleichsweise, kleiner Betrieb mit zum Beispiel 200 Fahrer_innen ist, gibt es mehr als 800.000 Variablen und 4,5 Million Restriktionen, die beachtet werden müssen. Zu den Variablen und Restriktionen zählen neben der Personalkosten und Kraftstoffverbrauch auch die Arbeitszeiten der einzelnen Fahrer_innen oder Pausen und die Arbeitswünsche der Fahrer_innen. Dies ist so komplex, dass man mit Visualisierungen nicht weiter kommt und es erst recht nicht von Hand ausrechnen kann. Daher kommen hier Solver-Programme zum Einsatz, also Software, die solche Probleme numerisch löst. Aber auch diese versagen bei sehr großen Einheiten, zum Beispiel bei Nahverkehrssystemen mit mehr als 400 Fahrerinnen und Fahrern. Daher, erklärt Xie, greift man in solchen Fällen auf Heuristiken und Metaheuristiken zurück. Heuristiken sind Verfahren, mit denen man aus begrenzten Informationen wahrscheinliche Aussagen ableiten kann.

Ein Beispiel für eine Metaheuristik ist der Ameisen-Algorithmus: Wenn Ameisen eine Futterquelle finden, zum Beispiel eine Banane, hinterlassen sie auf dem Weg zurück zum Ameisenhügel eine Pheremon-Spur. Verschiedene Ameisen nehmen verschiedene Wege von der Futterquelle zum Nest, aber diejenigen, die den kürzesten Weg gefunden haben, können die Strecke am häufigsten gehen. Deren Pheremon-Spur ist also am deutlichsten und so etabliert sich nach einer gewissen Zeit der kürzeste Weg. Es macht also nichts aus, dass die einzelne Ameise vielleicht nicht den optimalen Weg findet - als Ganzes schaffen sie es. Nach diesem Prinzip, sozusagen einem kontrollierten Schätzen, funktionieren Metaheuristiken.

Neues Projekt zu Lagerrobotern als Anwendung für Simulation

Zum Schluss erzählte Xie das Simulationsmodell häufig sehr komplexe Optimierungsmodelle, für die keine analytischen Lösungsverfahren existieren und stellte sie ihr neues Projekt als Beispiel vor: Das Robotic Mobile Fullfilment System, das in Lagerhallen Anwendung findet. Momentan ist es so, dass Arbeiter_innen in Lagern enorm viel laufen müssen, um Waren aus den Regalen zu holen – etwa 16 Kilometer am Tag.

Xie entwickelte ein Robotersteuerungsystem, bei dem Roboter, die dies übernehmen; Menschen müssen nur an einer festen Station stehen und die Waren in Empfang nehmen. Zur Veranschaulichung und um zu zeigen, dass die Roboter auch bei verwickelten Wegen nicht kollidieren, hat sie Staubsaugerroboter so umprogrammiert, dass sie agieren wie die Lagerroboter. 


Lin Xie ist Juniorprofessorin für Wirtschaftsinformatik an der Leuphana Universität Lüneburg. Nach dem Bachelor und Master in Wirtschaftsinformatik an der Universität Paderborn promovierte sie dort 2014 am Fachbereich Wirtschaftsinformatik mit Auszeichnung. Seit Mai 2015 ist sie Juniorprofessorin für Wirtschaftsinformatik, insbesondere Operations Research, am Institut für elektronische Geschäftsprozesse. 

Prof. Dr. Lin Xie
Universitätsallee 1, C4.314
21335 Lüneburg
Fon +49 4131 677-2305
Fax +49 4131 677-1749
lin.xie@leuphana.de


Autor: Martin Gierczak, Universitätskommunikation. Neuigkeiten aus der Universität und rund um Forschung, Lehre und Studium können an news@leuphana.de geschickt werden.