灾后运输网络中的最短路修复合作博弈

在最短路修复合作博弈中，当灾后运输网络规模较大时，最优成本分摊问题难以直接求解。基于拉格朗日松弛理论，提出了一种最短路修复合作博弈成本分摊算法。该算法将最短路修复合作博弈分解为两个具有特殊结构的子博弈，进而利用两个子博弈的结构特性，可以{高效地}求解出二者的最优成本分摊，将这两个成本分摊相加，可以获得原博弈的一个近乎最优的稳定成本分摊。结果部分既包含运输网络的随机仿真，也包含玉树地震灾区的现实模拟，无论数据来源于仿真还是现实，该算法都能在短时间内为最短路修复合作博弈提供稳定的成本分摊方案。

Cost allocation for multiple pairs of shortest paths recovery game on disrupted networks

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.