基于动态决策和数据挖掘的集装箱翻倒问题研究

In order to reduce the container-reshuffling rate during loading process, this project investigates two types of reshuffling problems at container terminals: pre-marshalling problems and container relocation problems. The former occurs before loading and after stowage planning, while the latter occurs in the loading process, with the difference that no containers are retrieved in the former operation while containers are continuously retrieved in the latter. Due to the large number of containers to be transferred around the world, it is of important economic significance and research value even with a slight reduction in the percentage of reshuffling rate. This project mainly deals with the following topics: (1) a dynamic programming model is constructed based on the well-designed representation of container stacking states in a bay, so as to generate the optimal decision for each stacking state (regarding which containers need to be relocated and to which stacks), which can be used as a benchmark for evaluating other algorithms; (2) in order to overcome the curse of dimensionality suffered by the dynamic programming method, an approximate dynamic programming algorithm based on the accurate estimation of the cost-to-go function via adaptive sampling is proposed to improve the efficiency of the solution; (3) a tight lower bound is estimated for each stacking state based on an in-depth analysis so that an effective and efficient branch and bound algorithm can be developed; and (4) in addition to MIP-based algorithms, this project attempts to construct the decision tree based on the optimal solutions provided by the dynamic programming, and even seeks an alternative algorithm using reinforcement learning, providing a new perspective on solving the problem.

为降低集装箱装船翻倒率，本项目研究集装箱码头上的两类翻倒问题：预翻倒问题和装船翻倒问题。预翻倒发生在配载之后装船之前，装船翻倒发生在装船过程，两者的区别在于前者在翻倒过程中没有集装箱被提走而后者的集装箱逐步被提走。由于集装箱基数巨大，微小的翻倒率改善，都具有重要的经济意义和研究价值。本项目的主要工作有：（1）拟在识别集装箱堆垛状态的基础上，构建动态规划模型，从而获得每种堆垛状态下的最优决策（哪些集装箱需要翻倒以及翻倒到哪些垛），作为评价其它算法的标杆；（2）为克服状态规模急剧增长的弊端，拟采用自适应采样方法估测剩余成本，从而构建近似动态规划算法，提高求解效率；（3）对堆垛状态进行深入分析，估测该状态下翻倒次数的下界值，从而设计高效的分支定界算法；（4）除了基于整数规划的算法外，本项目拟从数据挖掘的角度，构建基于动态规划结果的决策树，以及直接设计增强学习算法，为求解该问题提供一种新思路。

本项目的主要研究内容是如何降低集装箱码头的翻倒率。集装箱翻倒一般发生在两种场景：一是装船从堆场取出箱子的时候，二是为了准备装船对堆场的箱子进行整理的时候。前一个场景对应着装船翻倒问题，后一个场景对应着预翻倒问题。此外，集港时候的箱子堆存质量对后续的提取具有显著的影响，因而，面向翻倒的收箱问题也是重要的研究内容。因此，本项目在问题方面以集装箱翻倒为核心，主要研究了“装船翻倒”、“装船预翻倒”、“考虑翻倒的收箱”等问题。在研究方法上构建了整数规划、动态规划等模型；设计了动态规划、分支定界等精确算法，以及基于数据驱动的高效启发式方法；基于文献中已有的公开数据或企业的实际数据，通过与文献中的相关算法进行对比分析，验证了模型和算法的有效性。此外，基于所研究的方法，把研究对象拓展到集装箱码头运作、集装箱运输、物流网络设计、生产调度等问题。在项目执行期间，共发表了12篇论文，其中9篇SCI论文和3篇EI国际会议论文，申请一项发明专利，并指导毕业了7名硕士生，圆满完成了计划书所规定的所有目标任务。该项目的研究成果对港口集装箱翻倒问题的模型拓展和创新、算法研究和产业应用都具有重要的理论价值和指导意义，培养的学生将能够承担优化相关的核心工作，为智能制造时代下高端人才的需求做好培养和储备工作。