作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2020, Vol. 46 ›› Issue (8): 313-320. doi: 10.19678/j.issn.1000-3428.0055667

• 开发研究与工程应用 • 上一篇    

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

杨奔, 王炜晔, 赵婉婷, 谢瑾奎   

  1. 华东师范大学 计算机科学与技术学院, 上海 200062
  • 收稿日期:2019-08-05 修回日期:2019-09-18 发布日期:2019-09-27
  • 作者简介:杨奔(1994-),男,硕士研究生,主研方向为计算智能控制;王炜晔、赵婉婷,硕士研究生;谢瑾奎(通信作者),副教授、博士。
  • 基金资助:
    国家自然科学基金(11871222)。

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

YANG Ben, WANG Weiye, ZHAO Wanting, XIE Jinkui   

  1. School of Computer Science and Technology, East China Normal University, Shanghai 200062, China
  • Received:2019-08-05 Revised:2019-09-18 Published:2019-09-27

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

关键词: 自动化码头, 自动配载, 翻箱率, 强化学习, 贪心算法

Abstract: 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%.

Key words: automated terminal, automatic stowage planning, turn-over rate, reinforcement learning, greedy algorithm

中图分类号: