Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (3): 867-874.DOI: 10.11772/j.issn.1001-9081.2020060911

Special Issue: 前沿与综合应用

• Frontier and comprehensive applications • Previous Articles     Next Articles

Bulk storage assignment algorithm in bulk port based on game theory

ZHANG Shuyao1,2, LI Yonghua1,2, FAN Jiajia1,2   

  1. 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).

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

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

  1. 1. 武汉理工大学 计算机科学与技术学院, 武汉 430063;
    2. 交通物联网技术湖北省重点实验室(武汉理工大学), 武汉 430070
  • 通讯作者: 李勇华
  • 作者简介:张舒瑶(1997-),女,浙江平阳人,硕士研究生,主要研究方向:博弈论、港口调度算法;李勇华(1977-),男,湖北武汉人,副教授,博士,主要研究方向:博弈论、港口调度算法;范家佳(1994-),男,重庆人,硕士研究生,主要研究方向:调度优化、博弈论。
  • 基金资助:
    中央高校基本科研业务费专项资金资助项目(2019Ⅲ137CG);内河航运技术湖北省重点实验室基金资助项目(NHHY2017003);交通物联网技术湖北省重点实验室基金资助项目(2017III028-002)。

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

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

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

CLC Number: