Im Beitrag von Johannes Gückel und Pirmin Fontaine wurde untersucht, wie sich Kosten in Routingproblemen fair auf einzelne Kunden verteilen lassen, wobei der Shapley-Wert aus der kooperativen Spieltheorie als Referenzmaß dient. Aufgrund der hohen Rechenkomplexität entwickeln die Autoren einen Machine Learning-basierten Approximator (MLSVA), der routing-spezifische Merkmale nutzt, um die individuellen Kostenanteile effizient zu schätzen. In einer umfangreichen numerischen Studie zeigt sich, dass der Ansatz bestehende Methoden deutlich übertrifft: Für das Traveling Salesman Problem wird ein durchschnittlicher Fehler von 2,4 %, für das Capacitated Vehicle Routing Problem von 3,5 % erzielt. Der MLSVA liefert auch bei verzerrten Trainingsdaten robuste Ergebnisse und kann auf andere Allokationsprobleme, wie etwa Varianten des Bin Packing, übertragen werden.
Der Artikel ist hier verfügbar.