Sie möchten diese Information von HOLM mit anderen teilen?

Sie möchten diese Information über einen Social Network- oder einen Bookmark-Dienst teilen:

Facebook Twitter AddThis
×

Besuchen Sie uns:



Förderpartner des HOLM


×
Frankfurt am Main, den 26.09.2017

Quantencomputer für hochkomplexe Optimierungsprobleme

Frankfurt Consulting Engineers GmbH will für die Routenberechnung autonomer Bustaxen Quantenrechner nutzen


Noch ist es eine Vision für die Mobilität der Zukunft: Im 24-Std-Betrieb befördern elektrisch angetriebene, autonome Busse Fahrgäste im Ruftaxi-Betrieb. Der statische Fahrplan wird durch den nachfrage-abhängigen dynamischen Fahrplanergänzt, die starre durch eine flexible Route ersetzt, die so verläuft, dass Passagiere auch abseits von Haltestellen abgeholt und in einer vertretbaren Zeit bei möglichst wenig Umstiegen an ihr Ziel kommen.

Diese autonom und elektrisch fahrenden Bustaxen sind an keine festen Strecken und Fahrpläne mehr gebunden und zeichnen sich durch eine hohe Flexibilität aus. Der Service setzt ein hochkomplexes Optimierungsverfahren voraus, bei dem Routen und Fahrzeiten der Bustaxen berechnet und definiert werden müssen und bei dem der Verkehrsdienstleister permanent entscheidet, wann welcher Passagier wo abgeholt wird. Im Ergebnis könnte die Servicequalität für Fahrgäste deutlich erhöht werden, weil Wartezeiten und Wege zum Ziel reduziert und verkürzt werden können.

In zehn bis 15 Jahren könnten solche Services zunächst in Großstädten Realität sein. Um dieses Ziel zu erreichen, arbeitet die FCE Frankfurt Consulting Engineers GmbH an einer Lösung für das so genannte „Bustaxi-Problem“. Bis Jahresende will das Team um Wolfgang Mergenthaler im House of Logistics and Mobility (HOLM) einen Algorithmus entwickeln, mit dem die Zielfunktionen des autonom fahrenden Bustaxis´ wie Umsteigen, Fahrzeit und Fahrweg für einen begrenzten Raum berechnet werden können.

„Wir wollen herausfinden, um wie viel sich der Rechenaufwand erhöht, wenn sich das Netz für die Bustaxen in seiner Größe verdoppelt. Angesichts der hohen Komplexität der Aufgabe und der benötigten Rechnerkapazität geht es darum, ob wir einen Quantencomputer nutzen müssen“, sagte Mergenthaler im Gespräch mit dem HOLM. „Mein Gefühl sagt mir, wir brauchen den Quantencomputer auf alle Fälle.“

Zugegeben: Quantenmechanik und Quantencomputer entziehen sich dem Verständnis eines normal Gebildeten. Das war einer der Gründe, warum Chris Ferrie ein Buch über Quantenmechanik für Babies geschrieben hat. Viel Vergnügen bei der online-Lektüre: https://imgur.com/gallery/qq6Yd


Um diese komplexe Herausforderung bewältigen zu können, müssen Anwender eine Antwort auf das so genannte Travelling Salesman Problem geben. Dabei muss ein Handlungsreisender eine bestimmte Anzahl von Städten durchfahren. Die Aufgabe besteht darin, eine Reihenfolge für den Besuch mehrerer Orte so zu wählen, dass die gesamte Reisestrecke möglichst kurz und die erste Station gleich der letzten Station ist. Bei einer Menge von n Städten gibt es n! (n Fakultät) Möglichkeiten, die für die optimale Routenplanung geprüft werden müssen.

„Beim Travelling Salesman Problem und seiner industriellen Variante, die Produktionsplanung etwa in der Autobranche, geht es darum, welche Objekte und Merkmalskombination baue ich in welchen Zeiteinheiten und Reihenfolgen. Da hat man es sofort mit einem Problem zu tun, das der kombinatorischen Explosion unterliegt“, sagte Mergenthaler. Bei der kombinatorischen Explosion führt schon eine geringe Vergrößerung des Problemumfangs zu einem gewaltigen Anwachsen der Zeitspanne, die für die Berechnung der Lösung erforderlich ist.

Quantencomputer sind aufgrund ihrer Arbeitsweise für die Lösung solcher Probleme besser geeignet als herkömmliche digitale Computer. Bei bestimmten Aufgaben liegt der Beschleunigungsfaktor eines Quantencomputers für die Lösung des Problems laut Mergenthaler bei einer Million.

Ein kombinatorisches Optimierungsproblem liegt auch vor, wenn entschieden werden muss, wie  optimale Routen für eine große Anzahl von Bussen aussehen, die verschiedene Haltestellen bedienen. „Eine solche Route ist eine Kombination von aufeinanderfolgenden Haltestellen. Für beispielsweise 1000 Busse die Kombination zu finden, die dafür sorgt, dass jeder Passagier mitgenommen werden kann, dass jeder Passagier minimal häufig umsteigen muss und jeder Passagier in endlicher Zeit  an sein Ziel kommt, das ist schon eine sehr komplexe kombinatorische Möglichkeit. Es explodiert alles mit der Zahl der Haltestellen in dieser Stadt“, erläutert Mergenthaler die Herausforderung.

Bei 1000 Linien mit vielleicht 5000 Haltestellen wächst die Herausforderung enorm. „Dafür braucht man sehr schnelle Rechner, weil man sich leicht vorstellen kann, wie schwierig es ist, jedem Bus die optimale Route zuzuweisen.“  

Die nächste, noch schwierigere Herausforderung liegt nach Einschätzung von Mergenthaler darin, aus einem Bus ein Bustaxi zu machen. „Das ist der Punkt, wo man die Hand am Pulsschlag der Forschung hat, wenn man´s beherrscht. Dieses Fahrzeug fährt vermutlich schon autonom die Linien ab, muss aber permanent Ausnahmen machen, weil irgendein Passagier ruft, der nicht unbedingt unmittelbar an der Strecke steht. Jetzt muss man wissen, darf ich diesen Umweg in Kauf nehmen? Wenn der Bus wenig oder kaum besetzt ist, kann er die Passagiere einsammeln. Sitzen im Bus aber schon Fahrgäste, denen es nicht passt, wenn alle fünf Minuten ein Umweg gefahren werden soll, wird es schwierig.“

Wann holt das Bustaxi einen Passagier ab und bringt ihn ans Ziel, wenn es nicht direkt an der Linie liegt? Das sei die Herausforderung des so genannten Bustaxi-Problems, das nur mittels hochkomplexer Optimierungsverfahren gelöst werden kann. „Das ist dann aber kein Planungsproblem mehr, sondern ein Steuerungsproblem. Im Fünf-Minuten-Abstand oder kürzer muss die jeweils richtige Entscheidung getroffen werden, wer abgeholt wird und wer nicht. Da wird permanent gerechnet.“

Auf Grundlage des Travelling Salesman Problems und dem Einsatz von Hochleistungsrechnern lassen sich laut Mergenthaler auch Lösungen finden, wie Transportwege minimiert werden können, indem nicht nur die  Routen optimiert werden, sondern auch Lkw und Containerfrachter besser bepackt werden.

Das gilt auch für die zeit- und wegeminimale Umfliegung von Schlechtwetterzonen in der Luftfahrt.  „Da sprechen wir zurzeit mit einem großen US-amerikanischen Flugzeugbauer.“

Zum Jahresende wollen Wolfgang Mergenthaler und sein Team der FCE Frankfurt Consulting Engineers GmbH die ersten Ergebnisse erarbeitet haben.

Pressekontakt:


Jürgen Schultheis

House of Logistics & Mobility (HOLM) GmbH
Geschäftsbereich Netzwerk & Kollaboration
Bessie-Coleman Straße 7
Gateway Gardens
60549 Frankfurt am Main

Tel.: + 49 69 / 240070-556

E-Mail: juergen.schultheis@frankfurt-holm.de

Web: www.frankfurt-holm.de