Neues Verfahren mit Graph Neural Networks verbessert Team-Formation und Routing

Das Problem der Team-Formation und des Routings gilt als besonders anspruchsvoll und findet Anwendungen in Bereichen wie Flughäfen, Gesundheitswesen und Wartungsbetrieben. Traditionell werden dafür exakte Lösungsansätze auf Basis der Spaltengenerierung eingesetzt.

In der vorliegenden Arbeit wird eine innovative Partial-Column-Generation-Strategie vorgestellt, die für Szenarien mit mehreren Preisproblemen entwickelt wurde. Dabei wird vorhergesagt, welche Preisprobleme voraussichtlich Spalten mit negativem reduzierten Kostenwert erzeugen. Für diese Vorhersagen nutzt das Team ein speziell angepasstes Machine‑Learning-Modell, das Graph Neural Networks einsetzt.

Computational Experimente zeigen, dass die neue Strategie die klassische Partial-Column-Generation deutlich verbessert. Besonders bei schwierigen Instanzen und unter strengen Zeitbeschränkungen übertrifft sie die bisherigen Ansätze aus der Literatur.