T.: A study of proxies for Shapley allocation of transport costs

We propose and evaluate a number of solutions to the prob-lem of calculating the cost to serve each location in a single-vehicle transport setting. Such cost to serve analysis has ap-plication both strategically and operationally in transporta-tion. The problem is formally given by the traveling sales-person game (TSG), a cooperative total utility game in which agents correspond to locations in a travelling salesperson problem (TSP). The cost to serve a location is an allocated portion of the cost of an optimal tour. The Shapley value is one of the most important normative division schemes in co-operative games, giving a principled and fair allocation both for the TSG and more generally. We consider a number of di-rect and sampling-based procedures for calculating the Shap-ley value, and present the first proof that approximating the Shapley value of the TSG within a constant factor is NP-hard. Treating the Shapley value as an ideal baseline allocation, we then develop six proxies for that value which are relatively easy to compute. We perform an experimental evaluation us-ing Synthetic Euclidean games as well as games derived from real-world tours calculated for fast-moving consumer goods scenarios. Our experiments show that several computation-ally tractable allocation techniques correspond to good prox-ies for the Shapley value