Unser Ziel bei GIRO ist es, unseren Kunden zur Einsparung von Zeit und Geld zu verhelfen. Mit unserer Optimierungssoftware maximieren international führende Verkehrsanbieter und Post-/Paketdienstleister die Effizienz ihres Angebots bei gleichzeitiger Minimierung der Kosten, weil sie komplizierte Probleme lösen und erhebliche Einsparungen erreichen können. Seit mehr als vierzig Jahren in der Branche widmen wir uns der Entwicklung extrem leistungsfähiger Algorithmen, die unsere Kunden bei der Zielerreichung unterstützen.
Wenn schon, dann richtig – aber trotzdem schnell, bitte
Häufig sind die Optimierungsprobleme unserer Kunden mathematisch extrem schwierig zu lösen und fallen in die Komplexitätsklasse NP (nichtdeterministisch, polynomielle Zeit). In der Praxis bedeutet dies, dass Algorithmen im Allgemeinen keine nachweislich optimalen Lösungen liefern können, zumindest nicht, ohne sehr lange Zeit zu laufen.
Zwei Leitsätze kommen einem in diesem Zusammenhang in den Sinn: „Zeit ist Geld“ und „wenn schon, dann richtig“. Beide passen nicht immer gut zusammen, wenn nämlich „richtig“ zu viel Zeit kostet.
Hochwertige Lösungen, die zu erheblichen Effizienzsteigerungen und Kosteneinsparungen führen, lassen sich für NP-schwere Probleme in vielen Fällen mittels heuristischer Methoden erzielen, die Regeln weniger streng anwenden als Algorithmen. Wenn diese Methoden entsprechend ausgereift sind, führen sie innerhalb weniger Minuten zu hochwertigen Lösungen. Der Zusatznutzen, wenn man mit der vollen algorithmischen Analyse auch noch das letzte Quäntchen an Einsparpotenzial herauskitzelt, rechtfertigt nicht in jedem Fall den Aufwand. Trotzdem gibt es Situationen, in denen eine optimale Lösung einer hochwertigen Lösung so weit überlegen ist, dass wir die Zeit für die Lösung NP-schwerer Probleme mithilfe von Algorithmen investieren müssen. Um hierbei den Nutzen zu maximieren, wollen wir die Algorithmen so schnell wie möglich ausführen. Die Parallelverarbeitung (Parallel Processing) ist eine Möglichkeit, den Prozess zu beschleunigen.
Um hierbei den Nutzen zu maximieren, wollen wir die Algorithmen so schnell wie möglich ausführen. Die Parallelverarbeitung (Parallel Processing) ist eine Möglichkeit, den Prozess zu beschleunigen.
Viele Hände, schnelles Ende – bei entsprechenden Aufgaben
Nehmen wir an, Sie möchten ein Zimmer mit vier gleich großen Wänden streichen. Wenn Sie sich drei Freunde dazu holen und jeder eine Wand streicht, sind Sie in einem Viertel der Zeit fertig, die Sie allein zum Streichen gebraucht hätten. Mathematisch ausgedrückt ist die Zeitersparnis linear, weil der Geschwindigkeitszuwachs der Anzahl der eingesetzten Ressourcen entspricht: Vier Maler sind viermal so schnell. Das gleiche Prinzip gilt für Software, die Aufgaben parallel bearbeiten kann, wenn mehrere Prozessoren zur Verfügung stehen.
Bei der Parallelverarbeitung wird eine Rechenaufgabe in Teilaufgaben zerlegt, die gleichzeitig von verschiedenen Prozessoren ausgeführt werden können, sodass die Gesamtaufgabe schneller erledigt ist. Allerdings eignen sich nicht alle Aufgaben für eine parallele Verarbeitung. Die Gesamtbeschleunigung des Rechentempos hängt davon ab, welcher Anteil der Programmaufgaben für die parallele Verarbeitung zerlegt werden kann, und ob mit der Unterteilung indirekter Aufwand verbunden ist.
Kommen wir auf unser Beispiel zurück: Die Malerarbeit eignet sich für eine Parallelverarbeitung, indem die Aufgabe auf mehrere Personen aufgeteilt wird. Ungeeignet ist die parallele Verarbeitung hingegen für das große Blech Pizza, mit dem Sie sich bei Ihren Freunden vielleicht für die tatkräftige Unterstützung bedanken möchten: Wenn Sie den belegten Pizzateig in Viertel schneiden, die Sie jeweils in einem eigenen Ofen backen, ist die Pizza vielleicht minimal früher fertig, aber keinesfalls in einem Viertel der Zeit. Wenn man die Kosten für die zusätzlichen Backöfen und die verbrauchte Energie berücksichtigt, sieht man sehr schnell, dass sich die Investition in die Parallelverarbeitung, um die Pizza vielleicht ein oder zwei Minuten früher auf den Tisch zu bringen, nicht lohnt.
Allerdings eignen sich nicht alle Aufgaben für eine parallele Verarbeitung. Die Gesamtbeschleunigung des Rechentempos hängt davon ab, welcher Anteil der Programmaufgaben für die parallele Verarbeitung zerlegt werden kann...
Processing oder Threading?
Für die Parallelverarbeitung gibt es zwei Ansätze: Multiprocessing und Multithreading. Beim Multiprocessing werden mehrere Prozesse gleichzeitig auf verschiedenen Prozessoren ausgeführt. Beim Multithreading wird ein einzelner Prozess in Threads (Ausführungsstränge) unterteilt, die so programmiert sind, dass sie im „Kontext“ dieses Prozesses gleichzeitig abgearbeitet werden. Jede Methode hat ihre Vor- und Nachteile. Multiprocessing verbraucht mehr Ressourcen, hat aber den Vorteil, dass es kaum Änderungen am bestehenden Code erfordert und einfacher zu implementieren ist. Multithreading ist in der Regel schwieriger zu implementieren und erhöht das Potenzial für Probleme durch so genannte Race Conditions (Wettlaufsituationen), wenn der Zugriff auf eine gemeinsame Ressource nicht adäquat gesteuert wird. Da sich die verschiedenen Threads jedoch dieselben Ressourcen wie den Arbeitsspeicher teilen, hat Multithreading einen kleineren technologischen Fußabdruck.
Mit beiden Methoden haben wir bei GIRO sehr viel Erfahrung. Einige unserer HASTUS-Softwaremodule nutzen seit mehr als 25 Jahren Multiprocessing, und vor etwa zehn Jahren haben wir auch mit Multithreading begonnen.
Ein Modul, das schon seit langem auf Multiprocessing setzt, ist unser CrewOpt-Modul zur Optimierung von Dienstplänen. Der Task Scheduler von CrewOpt ist eine Engine für die Parallelisierung, die alle Optimierungsaufgaben für die Teilprobleme eines großen Scheduling-Problems auf verschiedenen Prozessoren startet und gleichzeitig löst. Der Task Scheduler kann auch für die Verarbeitung mehrerer Strategien verwendet werden. Hierbei wird das Problem „geklont“ und mit jeweils verschiedenen Parametern gleichzeitig abgearbeitet. Die Parameter, die die beste Lösung ergeben, werden dann gespeichert. Hierbei erreicht der Task Scheduler von CrewOpt einen fast linearen Zuwachs an Verarbeitungsgeschwindigkeit gegenüber dem Testen der einzelnen Strategien nacheinander.
Immer mehr unserer Produkte können die Algorithmen dank Multithreading schneller ausführen, wobei oftmals eine Multithreading-Version von CPLEX, einem extrem leistungsfähigen Solver für die numerische Lösung mathematischer Probleme, zum Einsatz kommt. Bei den Algorithmen unseres Customer Impact Simulator und der ReachMap hat Multithreading unserem Kunden LA Metro bei seinem NextGen-Projekt enorm geholfen: Durch sie konnten eine Vielzahl von Simulationen zur Neukonzeption des Busnetzes schnell und präzise durchgeführt und dabei viel Zeit eingespart werden.
Mit der Cloud noch ein Level weiter
Immer mehr unserer Kunden entscheiden sich dafür, ihre HASTUS-Installation in der Cloud zu hosten, anstatt sie auf ihrer eigenen Infrastruktur zu pflegen. Dies erschließt auch neue Möglichkeiten für die Parallelverarbeitung und für die Ausführung von Algorithmen auf virtuellen Maschinen (VMs) unterschiedlicher Größe, je nach den Ressourcenbedarf der einzelnen Algorithmen. Nicht immer ist es kosteneffizient, wenn Sie Ihr lokales System erweitern, nur um gelegentlichen zusätzlichen Verarbeitungsbedarf abdecken zu können. In der Cloud zahlen Sie für zusätzliche Rechenleistung nur dann, wenn Sie diese auch brauchen, z. B. für Multiprocessing. Wir erwarten für die Zukunft eine weitere Zunahme der Parallelverarbeitung, weil die Mehrzahl unserer Kunden in die Cloud migrieren wird.
Immer mehr unserer Kunden entscheiden sich dafür, ihre HASTUS-Installation in der Cloud zu hosten, anstatt sie auf ihrer eigenen Infrastruktur zu pflegen. Dies erschließt auch neue Möglichkeiten für die Parallelverarbeitung...
Über die Autoren
Charles Fleurent, Senior Director, Optimization Algorithms
In seiner 25-jährigen Karriere bei GIRO war Charles Fleurent federführend bei der Entwicklung der Algorithmen für GIROs Softwarelösungen zur Optimierung der Planung, Disposition und Betriebslenkung im ÖV. Er leitet die Forschungsanstrengungen des Unternehmens, sowohl intern als auch in Zusammenarbeit mit verschiedenen wissenschaftlichen Instituten. 2021 wurde er in Anerkennung seiner Beiträge zu Fortschritten in der Optimierung des ÖV, insbesondere seiner Beteiligung an der Forschung über den Einsatz künstlicher Intelligenz zur Optimierung der Dienstplanerstellung mit dem Leadership Award for Excellence der Canadian Urban Transit Association ausgezeichnet. Außerdem ist er Senior Editor der wissenschaftlichen Fachzeitschrift Public Transport: Planning and Operations, die bei Springer erscheint.
Loïc Bodart, Assistant Director, Planning-Routing Algorithms
Loïc Bodart leitet die Abteilung, die die Algorithmen für GIROs Softwarelösungen zur Optimierung der Planung und der Routenführung für den ÖV und für Paket-/Postdienste entwickelt. Er begann seine Karriere mit der Entwicklung von Software zur Optimierung des Crew-Managements bei Fluggesellschaften. In seinen fast 15 Jahren bei GIRO hat er diverse Funktionen in der Softwareentwicklung ausgefüllt und sein Fachwissen perfektioniert. Er hat einen Masterabschluss in Operations Research der Polytechnique Montréal.
Véronique Bouffard, Assistant Director, HASTUS Algorithms
Véronique Bouffard leitet die Abteilung, die die Algorithmen für GIROs Softwarelösungen zur Optimierung der Disposition und der Betriebslenkung aller öffentlichen Verkehrsmittel auf Straße und Schiene entwickelt. In ihrer fast 20-jährigen Unternehmenszugehörigkeit bei GIRO hat sie ihr umfassendes Fachwissen mit einem ausgeprägten Schwerpunkt auf die Entwicklung von Algorithmen aufgebaut. Sie hat einen Masterabschluss in Computerwissenschaft der Université de Sherbrooke.