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

Bulk storage assignment algorithm in bulk port based on game theory

针对散货港口因堆场面积有限,在货物进港作业时,如何在进出港货物动态变化的情况下兼顾作业效率并安排货物在堆场中合理堆放的问题,提出了一种基于博弈论的散货港口堆场堆位分配算法(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.