Cooperative game theory in location-routing

Abstract

Horizontal collaboration in transportation is attracting increased interest from academics and practitioners. This approach can bring significant savings to the companies and help reduce their carbon footprints. Game theory acts as a useful tool to study horizontal collaboration. The thesis focuses on studying cooperative game theory in location-routing, which to our knowledge has never been done before. Locationrouting consists of locating facilities while taking into account routing aspects. The interdependence of location and routing has been acknowledged in the literature. The integrated approach of location-routing can lead to more efficient logistic planning. Location-routing has varied applications ranging from package delivery to spare parts distribution. In the thesis, we first define this new cooperative game. We study its properties analytically using tools from the operations research literature, and principles and methods from cooperative game theory. We find that this game, while being monotone and subadditive, can have an empty core and be non-convex. We also study this game numerically. 6,000 instances of the game are generated and played. The cost is reduced by 43% on average and emissions by 31%. Emptiness of the core is observed in 44% of the instances. In collaboration, allocating the costs of the coalition is a major issue. For each instance of the numerical experiment we compute the values obtained by several allocation methods, like the Shapley value and the Equal Profit Method. We then analyze how the cost sharing techniques fare in this new game. Their performance is examined through several criteria like stability, fairness and transparency of the method. There is no method which is best on all the criteria and their performance can vary depending on the properties of the instance. However, we find all cost sharing techniques perform well regarding stability for the location-routing game.