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

Bulk storage assignment algorithm in bulk port based on game theory

作　　者：张舒瑶 李勇华[1,2] 范家佳[1,2] ZHANG Shuyao;LI Yonghua;FAN Jiajia(School of Computer Science and Technology,Wuhan University of Technology,Wuhan Hubei 430063,China;Hubei Key Laboratory of Transportation Internet of Things(Wuhan University of Technology),Wuhan Hubei 430070,China)

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

出　　处：《计算机应用》2021年第3期867-874,共8页journal of Computer Applications

基　　金：中央高校基本科研业务费专项资金资助项目(2019Ⅲ137CG);内河航运技术湖北省重点实验室基金资助项目(NHHY2017003);交通物联网技术湖北省重点实验室基金资助项目(2017Ⅲ028-002)。

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

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

分 类 号：TP311.5[自动化与计算机技术—计算机软件与理论]