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

doi:10.15960/j.cnki.issn.1007-6093.2021.03.012

运筹学学报 ›› 2021, Vol. 25 ›› Issue (3): 183-199.doi: 10.15960/j.cnki.issn.1007-6093.2021.03.012

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

宣洪伟¹, 李振东¹, 盛舟山², 刘林冬^1,*

1. 中国科学技术大学管理学院国际金融研究院, 安徽合肥 230026;
2. 常熟理工学院计算机科学与工程学院, 江苏苏州 215500

收稿日期:2021-03-15 发布日期:2021-09-26
通讯作者: 刘林冬 E-mail:ldliu@ustc.edu.cn
基金资助:
国家自然科学基金优秀青年科学基金（No.72022018），中国科学院青年创新促进会（No.2021454），国家自然科学基金青年科学基金（No.71701192）

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

XUAN Hongwei¹, LI Zhendong¹, SHENG Zhoushan², LIU Lindong^1,*

1. International Institute of Finance, School of Management, University of Science and Technology of China, Hefei 230026, Anhui, China;
2. School of Computer Science and Engineering, Changshu Institute of Technology, Suzhou 215500, Jiangsu, China

Received:2021-03-15 Published:2021-09-26

摘要/Abstract

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

关键词: 合作博弈, 运输网络, 灾后修复, 成本分摊

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

中图分类号:

O221.4
O225

宣洪伟, 李振东, 盛舟山, 刘林冬. 灾后运输网络中的最短路修复合作博弈[J]. 运筹学学报, 2021, 25(3): 183-199.

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.

参考文献

[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.

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

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

编辑推荐

Metrics

本文评价

[1]	于晓辉, 杜志平, 张强, 逄金辉. 基于T-联盟Shapley值的分配策略[J]. 运筹学学报, 2020, 24(4): 113-127.
[2]	肖燕, 李登峰. 带策略约束的区间数双矩阵博弈的双线性规划求解方法[J]. 运筹学学报, 2019, 23(4): 59-70.
[3]	于晓辉, 杜志平, 张强, 周珍, 逄金辉. 一种资源投入不确定情形下的合作博弈形式及收益分配策略[J]. 运筹学学报, 2019, 23(4): 71-85.
[4]	侯丽娜, 孙海琳. 交通网络下的多厂商两阶段随机非合作博弈问题——基于随机变分不等式[J]. 运筹学学报, 2019, 23(3): 91-108.
[5]	王斯琪, 谢政, 戴丽. 一种求解合作博弈最公平核心的非精确平行分裂算法[J]. 运筹学学报, 2016, 20(2): 105-112.
[6]	邓喜才，向淑文，左羽. 不确定性下强Berge均衡的存在性[J]. 运筹学学报, 2013, 17(3): 101-107.