基于DQN的动态深度多分支搜索自动配载算法

DQN-based Automatic Stowage Planning Algorithm Using Dynamic Depth Multi-branch Search

自动配载是自动化码头运营的重要环节之一,往往需要考虑多种因素,限制条件复杂,是一个NP完全性问题。传统的配载算法更关注配载结果而忽视箱区调度对作业效率的影响,为提高堆场设备的利用率和配载结果的合理性,根据桥机计划安排的配载任务,提出一种深度优先且动态深度多分支搜索的配载算法。在线下学习阶段中通过历史数据学习得到箱区状态值函数,线上配载选箱时综合值函数与各项约束条件通过动态深度分支搜索的方式得到最佳决策。在上海洋山港四期自动化集装箱码头进行真实船舶数据仿真测试,结果表明,与传统的贪心策略相比,该算法可使翻箱率和双小车拼车率均降低2%~5%,堆场设备利用率稳定在90%~96%。

Automatic stowage planning is an import part of automatic terminal operation.As an NP-complete problem,it requires consideration of multiple factors and complex restrictions.Traditional stowage planning algorithms focus more on planning results and ignore the impact of container area scheduling on task efficiency.To improve the utilization rate of yard equipment and the rationality of stowage planning results,this paper proposes a stowage planning strategy using dynamic depth-first multi-branch search based on the stowage planning tasks arranged by the Crane Work Plan(CWP).In the offline learning phase,the state value function of the container area is obtained through learning of historical data.In the online planning phase,considering the value function and various constraints,the optimal decision for container selection is obtained by using dynamic deep multi-branch search.A simulation experiment is carried out using data of real ship in the fourth phase of the automatic container terminal project of Shanghai Ocean Port.Experimental results show that compared with the traditional greedy strategy,the proposed algorithm can reduce the turnover rate of containers and the sharing rate of double trolley by 2%to 5%,the utilization rate of yard equipment stabilized at 90%~96%.