Shapley Value for Shortest Path Routing in Dynamic Networks
Aykhan Masimli · Preprints.org · 2023
Transportation is a crucial component of supply chain management, responsible for delivering goods and services to customers. This paper explores the application of game theory concepts, precisely the Shapley value, to cost allocation in transportation operations involving drones and trucks. Our focus is on shortest-path games in which agents own nodes in a network and seek to transport items between nodes at the lowest possible cost. We provide a comprehensive literature review of the Shapley value and its use in shortest-path games, with particular emphasis on transportation networks. Our proposed model includes sets of customers, drones, and trucks and uses binary decision variables to indicate whether a drone or truck serves a given customer. The objective is to minimize the total cost of serving all customers while adhering to capacity and synchronization constraints. We use the Shapley value to determine the contribution and cost-sharing of each drone and truck in serving the customers. Through a combination of denitions, theorems, and examples, we explore the formal meaning of the Shapley value and its relationship to shortest-path games in transportation networks. We highlight exceptional cases and considerations that must be taken into account when applying the Shapley value in such scenarios.