Abstract: When the scale of disrupted transportation networks is large, the optimal cost allocation problem for multiple pairs of shortest paths recovery game is often intractable. In this paper, we propose a cost allocation algorithm based on Lagrangian relaxation method, which decomposes the multiple pairs of shortest paths recovery game into two subgames approximatively. We then find some properties for these two subgames which can help to solve their optimal cost allocations efficiently. According to the optimal cost allocations of the subgames, we are able to develop a near-optimal stable cost allocation for the original game. In the end, we conduct some computational experiments by checking the performance of our cost allocation algorithm on both simulated networks and the disrupted transportation network of Yushu after earthquake. The results show that our algorithm is both efficient and effective in solve optimal cost allocation problem for multiple pairs of shortest paths recovery game.

Key words: cooperative game, transportation network, disruption recovery, cost allocation