基于博弈论的散货港口堆场堆位分配算法

doi:10.11772/j.issn.1001-9081.2020060911

计算机应用 ›› 2021, Vol. 41 ›› Issue (3): 867-874.DOI: 10.11772/j.issn.1001-9081.2020060911

所属专题：前沿与综合应用

基于博弈论的散货港口堆场堆位分配算法

张舒瑶^1,2, 李勇华^1,2, 范家佳^1,2

1. 武汉理工大学计算机科学与技术学院, 武汉 430063;
2. 交通物联网技术湖北省重点实验室(武汉理工大学), 武汉 430070

收稿日期:2020-06-28 修回日期:2020-10-20 出版日期:2021-03-10 发布日期:2021-03-15
通讯作者: 李勇华
作者简介:张舒瑶(1997-),女,浙江平阳人,硕士研究生,主要研究方向:博弈论、港口调度算法;李勇华(1977-),男,湖北武汉人,副教授,博士,主要研究方向:博弈论、港口调度算法;范家佳(1994-),男,重庆人,硕士研究生,主要研究方向:调度优化、博弈论。
基金资助:
中央高校基本科研业务费专项资金资助项目（2019Ⅲ137CG）；内河航运技术湖北省重点实验室基金资助项目（NHHY2017003）；交通物联网技术湖北省重点实验室基金资助项目（2017III028-002）。

Bulk storage assignment algorithm in bulk port based on game theory

ZHANG Shuyao^1,2, LI Yonghua^1,2, FAN Jiajia^1,2

1. School of Computer Science and Technology, Wuhan University of Technology, Wuhan Hubei 430063, China;
2. Hubei Key Laboratory of Transportation Internet of Things(Wuhan University of Technology), Wuhan Hubei 430070, China

Received:2020-06-28 Revised:2020-10-20 Online:2021-03-10 Published:2021-03-15
Supported by:
This work is partially supported by the Fundamental Research Fund for the Central Universities (2019Ⅲ137CG), the Fund of Hubei Key Laboratory of Inland Shipping Technology (NHHY2017003), the Fund of Hubei Key Laboratory of Transportation Internet of Things (2017III028-002).

摘要/Abstract

摘要： 针对散货港口因堆场面积有限，在货物进港作业时，如何在进出港货物动态变化的情况下兼顾作业效率并安排货物在堆场中合理堆放的问题，提出了一种基于博弈论的散货港口堆场堆位分配算法（BSAABG）。首先，将堆位分配行为建模为动态博弈，并运用满足均衡分析该博弈。假设每票货物对分配所得效益都有一个预期，当所有货物都达到预期时博弈即达到满足均衡。然后，使用基于博弈论的散货堆场堆位分配算法BSAABG求解之前建立的该模型，从理论上证明算法的收敛性。实验结果表明，当货物票数为20时，基于博弈论的散货堆场堆位分配算法BSAABG的货物平均满足度比人工分配方法（用贪心算法（GA）模拟）和基于规则的堆位分配算法（SABR）分别提高了62.5%和18.2%，堆场分配效益是贪心算法（GA）的6.83倍，是SABR的3.22倍。可见所提算法能够有效地提高货物的平均满足度和堆场分配效益。

关键词: 散货港口, 满足均衡, 堆场堆位分配, 博弈论, 贪心算法

Abstract: The bulk port has a limited storage yard, during the entering port operation of cargos, there is the problem that how to give consideration to both the operating efficiency and arranging the reasonable storage of cargos in the storage yard with dynamic changes of cargos entering and leaving the port. In order to solve the problem, a Bulk Storage Assignment Algorithm in Bulk port based on Game theory (BSAABG) was proposed. Firstly, the storage assignment behavior was modelled as a dynamic game, and the satisfaction equilibrium was applied to analyze this game. Assuming that each batch of cargos has an expectation for assignment benefit, the game will reach satisfaction equilibrium when all cargos meet their expectations. Then, BSAABG was used to solve the model constructed above, and the convergence of the proposed algorithm was proved theoretically. Experimental results show that, when the number of cargo batches is 20, BSAABG can increase the average cargo satisfaction by 62.5% and 18.2% compared to the manual assignment method (simulated by Greedy Algorithm (GA)) and Storage Assignment algorithm Based on Rule (SABR) respectively, and has the storage assignment benefit 6.83 times and 3.22 times of those of GA and SABR respectively. It can be seen that the proposed algorithm can effectively improve the average cargo satisfaction and the storage assignment benefit.

Key words: bulk port, satisfaction equilibrium, bulk storage assignment, game theory, greedy algorithm

中图分类号:

TP311.5

张舒瑶, 李勇华, 范家佳. 基于博弈论的散货港口堆场堆位分配算法[J]. 计算机应用, 2021, 41(3): 867-874.

ZHANG Shuyao, LI Yonghua, FAN Jiajia. Bulk storage assignment algorithm in bulk port based on game theory[J]. Journal of Computer Applications, 2021, 41(3): 867-874.

参考文献

[1] 王斌义. 港口物流[M]. 北京:机械工业出版社,2018:38-39. (WANG B Y. Port Logistics[M]. Beijing:China Machine Press, 2018:38-39.)
[2] RAJABI A,KHODADAD SARYAZDI A,BELFKIH A,et al. Towards smart port:an application of AIS data[C]//Proceedings of the IEEE 20th International Conference on High Performance Computing and Communications/IEEE 16th International Conference on Smart City/IEEE 4th International Conference on Data Science and Systems. Piscataway:IEEE,2018:1414-1421.
[3] YANG Y,ZHONG M,YAO H,et al. Internet of things for smart ports:Technologies and challenges[J]. IEEE Instrumentation and Measurement Magazine,2018,21(1):34-43.
[4] 陈致远. 黄骅港智能堆场研究[J]. 起重运输机械,2019(2):46-51.(CHEN Z Y. Smart stockyard system of Huanghua port[J]. Hoisting and Conveying Machinery,2019(2):46-51.)
[5] 陈磊, 赵宪花. 散货码头智能化发展制约因素研究[J]. 中国水运,2016,16(1):62-63.(CHEN L,ZHAO X H. Research on the restrictive factors of the intelligent development of bulk cargo terminals[J]. China Water Transport,2016,16(1):62-63.)
[6] WANG Y,MI W,CHANG D. Yard allocation for coal terminal based on rules[J]. Advanced Materials Research,2012,472/473/474/475:3223-3227.
[7] BRUGLIERI M,GERZELJ E,GUENZANI A,et al. Solving the 3-D yard allocation problem for break bulk cargo via variable neighborhood searching[J]. Electronic Notes in Discrete Mathematics,2015,47:237-244.
[8] 孙勇. 散货码头堆场系统仿真研究[D]. 大连:大连海事大学, 2015:16-20.(SUN Y. Simulation for yard system of bulk cargo[D]. Dalian:Dalian Maritime University,2015:16-20.)
[9] SAVELSBERGH M,SMITH O. Cargo assembly planning[J]. EURO Journal on Transportation and Logistics,2015,4(3):321-354.
[10] 徐克辉. 基于信息技术的港口堆场散货管理与作业流程优化研究——以秦皇岛港口为例[D]. 北京:北京交通大学,2018:34-46. (XU K H. Study on bulk management and operation process optimization of port yard based on information technology-taking Qinhuangdao harbor as an example[D]. Beijing:Beijing Jiaotong University,2018:34-46.)
[11] 宋昕. 基于本体和进化算法的散杂货港口堆场智能调度系统研究[D]. 北京:北京交通大学,2012:73-113.(SONG X. Research on bulk port stack-scheduling system based on ontology and evolutionary algorithm[D]. Beijing:Beijing Jiaotong University,2012:73-113.)
[12] ZHANG H,DU J,CHENG J,et al. Incomplete CSI based resource optimization in SWIPT enabled heterogeneous networks:a non-cooperative game theoretic approach[J]. IEEE Transactions on Wireless Communications,2018,17(3):1882-1892.
[13] XIAO Z,SHEN X,ZENG F,et al. Spectrum resource sharing in heterogeneous vehicular networks:a noncooperative gametheoretic approach with correlated equilibrium[J]. IEEE Transactions on Vehicular Technology,2018,67(10):9449-9458.
[14] 徐飞, 王少昌, 杨卫霞. 基于博弈论的云资源调度算法[J]. 计算机科学,2019,46(6A):295-299.(XU F,WANG S C,YANG W X. Cloud resource scheduling algorithm based on game theory[J]. Computer Science,2019,46(6A):295-299.)
[15] DONG G,HUANG R,NG P. Tacit collusion between two terminals of a port[J]. Transportation Research Part E:Logistics and Transportation Review,2016,93:199-211.
[16] ISHⅡ M,LEE P T W,TEZUKA K,et al. A game theoretical analysis of port competition[J]. Transportation Research Part E:Logistics and Transportation Review,2013,49(1):92-106.
[17] 徐蕾, 杨成, 姜春晓, 等. 协同过滤推荐系统中的用户博弈[J]. 计算机学报,2016,39(6):1176-1189.(XU L,YANG C, JIANG C X, et al. Game analysis of user participation in collaborative filtering systems[J]. Chinese Journal of Computers, 2016,39(6):1176-1189.)

基于博弈论的散货港口堆场堆位分配算法

Bulk storage assignment algorithm in bulk port based on game theory

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	王艺洁, 凡佳飞, 王陈宇. 云边环境下基于博弈论的两阶段任务迁移策略[J]. 计算机应用, 2021, 41(5): 1392-1398.
[2]	毛莺池, 徐雪松, 刘鹏飞. 基于稳定匹配的多用户任务卸载策略[J]. 计算机应用, 2021, 41(3): 786-793.
[3]	郑延斌, 樊文鑫, 韩梦云, 陶雪丽. 基于博弈论及Q学习的多Agent协作追捕算法[J]. 计算机应用, 2020, 40(6): 1613-1620.
[4]	蔡豪, 袁正道. 云数据中心基于贪心模式的虚拟机选择算法[J]. 计算机应用, 2020, 40(6): 1707-1713.
[5]	杨艳, 刘生建, 周永权. 贪心二进制狮群优化算法求解多维背包问题[J]. 计算机应用, 2020, 40(5): 1291-1294.
[6]	范家佳, 刘洪星, 李勇华, 杨丽金. 基于博弈论的内河港口作业车辆协同选路方法[J]. 计算机应用, 2020, 40(1): 50-55.
[7]	张宪立, 唐建新, 曹来成. 基于反向PageRank的影响力最大化算法[J]. 计算机应用, 2020, 40(1): 96-102.
[8]	袁培燕, 蔡云云. 移动边缘计算中一种贪心策略的内容卸载方案[J]. 计算机应用, 2019, 39(9): 2664-2668.
[9]	王甜甜, 于双元, 徐保民. 基于策略梯度算法的工作量证明中挖矿困境研究[J]. 计算机应用, 2019, 39(5): 1336-1342.
[10]	刘枭, 王晓国. 基于密集子图的银行电信诈骗检测方法[J]. 计算机应用, 2019, 39(4): 1214-1219.
[11]	郑延斌, 王林林, 席鹏雪, 樊文鑫, 韩梦云. 基于蚁群算法及博弈论的多Agent路径规划算法[J]. 计算机应用, 2019, 39(3): 681-687.
[12]	刘开南. 云数据中心基于贪心算法的虚拟机迁移策略[J]. 计算机应用, 2019, 39(11): 3333-3338.
[13]	刘亚州, 王静, 潘晓中, 付伟. 社交网络中考虑节点度的演化博弈[J]. 计算机应用, 2018, 38(4): 1029-1035.
[14]	樊自甫, 周凯恒, 姚杰. 基于博弈论的SDN主控制器重选机制[J]. 计算机应用, 2018, 38(3): 776-779.
[15]	唐海波, 林煜明, 李优, 蔡国永. 基于模拟退火与贪心策略的平衡聚类算法[J]. 计算机应用, 2018, 38(11): 3132-3138.