Nach 70 Jahren gefunden: Mathematiker haben einen schnellen und einfachen Lösungsalgorithmus für ein oft gebrauchtes Problem der Netzwerk- und Routenplanung gefunden. Bei dieser für Logistik und Navigation wichtigen Frage geht es darum, von einem Punkt aus die kürzesten Wege zu allen anderen Punkten im Netzwerk zu finden. Seit den 1950er Jahren fehlt hierfür eine schnelle Lösung, wenn auch negativ gewichtete Strecken darunter sind, beispielsweise energie- und zeitaufwendige Bergauffahrten.
Ob bei der Routenplanung mit dem Navi, der Planung von Transportwegen für Güter oder der optimalen Struktur für ein Leitungsnetz: In Logistik und Technologie geht es oft darum, kurze und effiziente Wege durch ein Netzwerk zu finden oder Netzwerke möglichst effizient zu strukturieren. Dies passiert meist mithilfe spezieller Algorithmen, die die computergestützte Planung ermöglichen.
SSSP: Suche nach den kürzesten Verbindungen
Eines der typischen Netzwerk-Probleme ist das das sogenannte „Single Source Shortest Path“-Problem (SSSP): Es müssen die kürzesten Routen zwischen einem Punkt und allen anderen Knoten im Netzwerk gefunden werden. In Teilen war dies bereits gelöst, es fehlte jedoch ein schneller Algorithmus für eine für viele Anwendungen wichtige Variante dieses Problems: das SSSP mit negativen Gewichtungen. Bei dieser wird auch berücksichtigt, dass einige Wege im Netzwerk mehr Energie und Zeit kosten und daher mathematisch abgewertet werden.
„Ein praktisches Beispiel dafür sind Steigungen in einem Straßennetz: Wenn man ein Elektroauto fährt, ist das Wissen um Steigungen und Bergabstrecken wichtig, weil dies die Reichweite beeinflusst“, erklärt Seniorautor Christian Wulff-Nilsen von der Universität Kopenhagen. Während Steigungen die Batterien leersaugen, kann das Elektroauto Abfahrten zum Wiederaufladen der Batterien nutzen.
Algorithmus für Netzwerke mit negative Gewichtungen
Für das SSSP-Problem ohne negative Gewichtungen gilt der Dijkstra-Algorithmus als schnelle und vergleichsweise einfache Lösung. Doch für SSSP-Probleme mit negativen Gewichtungen stand ein ähnlich schneller Algorithmus noch aus. „Schnellere Algorithmen für SSSP mit negativen Kantengewichtungen zu entwickeln, ist eines der grundlegenden und am längsten existierenden Probleme unter den Graph-Algorithmen“, erklären die Forscher. „Seit den 1950er Jahren hat es dabei alle paar Jahrzehnte Schübe der Verbesserungen gegeben.“
Doch erst jetzt ist es Wulff-Nilsen und seinen Kollegen gelungen, einen Algorithmus zu entwickeln, der breit anwendbar ist und dieses Problem ähnlich schnell knacken kann wie der Dijkstra-Algorithmus die nicht negativen SSSPs. „Wir haben einen Algorithmus gefunden, der das Problem in nahezu linearer Zeit löst, auf die schnellste mögliche Weise“, erklärt Wulff-Nilsen. Die Lösung basiert dabei auf einem von den Forschern im letzten Jahr entwickelten Algorithmus, der das SSSP-Problem für sich mit der Zeit verändernde Netzwerke löst.
Anwendbar in Technik, Logistik und Finanzwesen
„Im Gegensatz zu jüngst entwickelten Ansätzen, die auf anspruchsvoller kontinuierlicher Optimierungszerlegung und dynamischen Algorithmen beruhen, ist unser Algorithmus einfach: Er erfordert nur eine einfache Graphenzerlegung und grundlegende kombinatorische Werkzeuge“, erklären die Wissenschaftler. Ihrer Ansicht nach ebnet er damit den Weg für eine besonders schnelle und einfache Lösung solcher Probleme, sei es im Straßenverkehr, der Logistik oder auch im Finanzwesen:
„Im Prinzip könnte der Algorithmus auch eingesetzt werden, um beispielsweise Zentralbanken vor einer Währungsspekulation zu warnen – etwas das heute vorwiegend mittels Computer erfolgt“, erklärt Wulff-Nilsen. „Aber unser Algorithmus ist so schnell, dass er Schlupflöcher finden kann, bevor sie für solche Spekulationen ausgenutzt werden.“ Der Lösungsalgorithmus des Teams wurde jüngst auf der renommierten „Foundation of Computer Science“-Konferenz der theoretischen Computerwissenschaften als bester Fachartikel ausgezeichnet. (Preprint, 2022; arXiv: 2203.03456)
Quelle: University of Copenhagen
