Neuer Algorithmus löst mehr begrenzte stochastische Wegprobleme

Ein neuer Ansatz namens CARL verspricht, die Lösung von begrenzten stochastischen Wegproblemen (CSSPs) deutlich zu beschleunigen. CSSPs modellieren Situationen, in denen ein Hauptkostenfaktor minimiert werden soll, während gleichzeitig Nebenbedingungen – etwa ein Budget – eingehalten werden müssen. Traditionelle Verfahren lösen dafür immer größere lineare Programme, bis die optimale Lösung gefunden ist.

CARL arbeitet anders: Es wandelt das Problem in eine Reihe von unbeschränkten stochastischen Wegproblemen (SSPs) um, die mit effizienten Heuristik-Suchalgorithmen gelöst werden können. Dabei werden die verschiedenen Kosten (Haupt- und Nebenkosten) mittels einer Skalarisation auf einen einzigen Kostenwert reduziert. Der Algorithmus sucht anschließend nach der optimalen Skalarisation, indem er einen Optimierungsmechanismus ähnlich dem Subgradientenverfahren einsetzt. Die daraus resultierenden SSP-Lösungen werden zu einer optimalen Richtlinie für das ursprüngliche CSSP zusammengeführt.

In Experimenten konnte CARL die Anzahl der gelösten Probleme im Vergleich zum aktuellen Stand der Technik um 50 % steigern. Damit eröffnet der Ansatz neue Möglichkeiten für die effiziente Planung in unsicheren, kostenbegrenzten Umgebungen.