In the article authored by Johannes Gückel and Pirmin Fontaine, we address the challenge of fair cost allocation in routing problems using the Shapley value from cooperative game theory. Due to the high computational complexity of exact calculations, the authors develop a machine learning-based Shapley Value Approximator (MLSVA) that leverages routing-specific features to efficiently estimate individual cost shares. In an extensive numerical study, the MLSVA outperforms existing methods, achieving an average error of 2.4% for the Traveling Salesman Problem and 3.5% for the Capacitated Vehicle Routing Problem. The approach proves robust even when trained on biased data and can be extended to other allocation problems, such as variants of the bin packing problem.
The article is now available online here