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.
XUAN Hongwei, LI Zhendong, SHENG Zhoushan, LIU Lindong
. Cost allocation for multiple pairs of shortest paths recovery game on disrupted networks[J]. Operations Research Transactions, 2021
, 25(3)
: 183
-199
.
DOI: 10.15960/j.cnki.issn.1007-6093.2021.03.012
[1] 谢政. 对策论导论[M]. 北京:科学出版社, 2010.
[2] 于晓辉, 杜志平, 张强, 等. 基于T-联盟Shapley值的分配策略[J]. 运筹学学报}, 2020, (4):113-127.
[3] 于晓辉, 杜志平, 张强, 等. 一种资源投入不确定情形下的合作博弈形式及收益分配策略[J]. 运筹学学报, 2019, (4):71-85.
[4] Maschler M, Peleg B, Shapley L S. Geometric properties of the kernel, nucleolus, and related solution concepts[J]. Mathematics of Operations Research, 1979, 4(4):303-338.
[5] Kern W, Paulusma D. Matching games:The least core and the nucleolus[J]. Mathematics of Operations Research, 2003, 28(2):294-308.
[6] Schulz A S, Uhan N A. Sharing supermodular costs[J]. Operations Research, 2004, 58(4):1051-1056.
[7] Schulz A S, Uhan N A. Approximating the least core value and least core of cooperative games with supermodular costs[J]. Discrete Optimization, 2013, 10(2):163-180.
[8] Jain K, Mahdian M. Cost sharing[M]//Algorithmic Game Theory. New York:Cambridge University Press, 2007:385-410.
[9] Faigle U, Fekete S P, Hochstattler W, et al. On approximately fair cost allocation in Euclidean TSP games[J]. Operations Research-Spektrum, 1998, 20(1):29-37.
[10] Blaser M, Ram L S. Approximately fair cost allocation in metric traveling salesman games[J]. Theory of Computing Systems, 2008, 43(1):19-37.
[11] Caprara A, Letchford A N. New techniques for cost sharing in combinatorial optimization games[J]. Mathematical Programming, 2010, 124(1):93-118.
[12] Liu L, Qi X. Network disruption recovery for multiple pairs of shortest paths[C]//201411th International Conference on Service Systems and Service Management (ICSSSM). Beijing:IEEE, 2014:1-6.
[13] Andonov R, Poirriez V, Rajopadhye S. Unbounded knapsack problem:Dynamic programming revisited[J]. European Journal of Operational Research, 2000, 123(2):394-407.
[14] Held M, Karp R M. The traveling-salesman problem and minimum spanning trees[J]. Operations Research, 1970, 18(6):1138-1162.
[15] Zhang C, Gao Y, Yang L, et al. Joint optimization of train scheduling and maintenance planning in a railway network:A heuristic algorithm using Lagrangian relaxation[J]. Transportation Research Part B:Methodological, 2020, 134:64-92.
[16] Liu L, Qi X, Xu Z. Computing near-optimal stable cost allocations for cooperative games by Lagrangian relaxation[J]. INFORMS Journal on Computing, 2016, 28(4):687-702.
[17] 张惠珍, 魏欣, 马良. 求解无容量设施选址问题的半拉格朗日松弛新方法[J]. 运筹学学报, 2015, (4):37-47.
[18] 赵宇哲, 周晶淼, 匡海波, 等. 航运资产整合下海运网络的航线、路径和船舶的集成优化[J]. 系统工程理论与实践, 2018, (8):2110-2122.
[19] Held M, Wolfe P, Crowder H P. Validation of subgradient optimization[J]. Mathematical Programming, 1974, 6(1):62-88.
