Fast Shapley Value Approximation Through Machine Learning With Application in Routing Problems

Kurzfassung/Abstract

For many routing applications, it is not only necessary to minimize total costs but also to allocate them to individual customers. In this context, the allocation according to the Shapley value is a well-known method highly regarded for its fulfillment of major fairness criteria. However, its computational complexity restricts its applicability, especially for NP-hard underlying optimization problems like routing problems, since the exact computability of the Shapley values is no longer possible within a reasonable time. In this study, we propose a general Machine Learning-based Shapley Value Approximator (MLSVA) and apply it to routing problems based on the exploitation of routing-specific problem structures as features, enabling real-time approximations. Within an extensive numerical study, we show that our MLSVA outperforms current state-of-the-art approximation results for the Traveling Salesman Problem (TSP) and, at the same time, achieves very good results for the Capacitated Vehicle Routing Problem (CVRP), for which it is the first efficient method that quickly delivers high-quality approximations. On average, we approximate Shapley values with a mean absolute percentage error of 2.4% for the TSP and 3.5% for the CVRP. Further, the MLSVA achieves strong approximation results even when trained on biased labels. This shows the scalability of the MLSVA and allows high-quality approximations even for large routing problems. Finally, we demonstrate the generalizability of our approach by successfully approximating Shapley values for items in a variant of the bin packing problem.