基于策略搜索算法的出口集装箱翻箱作业优化

doi:10.19678/j.issn.1000-3428.0069376

摘要/Abstract

摘要：

随着港口物流在集装箱码头的高速发展, 在自动化集装箱码头中, 堆场出口集装箱贝位翻箱问题备受关注。考虑堆场出口集装箱贝位翻箱问题, 设计不同集装箱分布下的启发式翻箱规则, 并在处理空栈与特殊栈时进行细致的优化, 提出基于策略的快速求解算法。基于该算法引入规则得分, 构建基于规则排序的分支定界算法和定向搜索算法, 分支定界算法可求得该问题最优解, 而定向搜索算法可在较短时间内求得较优可行解。算例结果表明, 基于规则排序的分支定界算法与定向搜索算法在小规模算例上均能高效求解, 并且在大规模算例中, 通过与现有研究求解算法对比, 基于规则排序的分支定界算法与定向搜索算法求解效率提升近47.78%和56.59%。

关键词: 翻箱问题, 启发式算法, 分支定界算法, 定向搜索算法, 自动化集装箱码头

Abstract:

With the rapid development of port logistics and the increasing prevalence of automated container terminals, the issue of relocating export containers at specific locations in yard bays has garnered significant attention. This study addresses the container bay relocation problem by designing heuristic relocation rules under various container distributions and meticulously optimizes the handling of empty and special stacks. Moreover, it proposes a policy-based fast solution algorithm. Building on this algorithm, this study introduces a rule scoring system to develop a rule-based ordered branch and bound algorithm and a directed search algorithm. The branch and bound algorithm can obtain the optimal solution to a problem, whereas the directed search algorithm can achieve a superior feasible solution in a shorter time. Case study results demonstrate that both the rule-based ordered branch and bound algorithm and the directed search algorithm efficiently solve small-scale cases and achieve 47.78% and 56.59% improvements in solving efficiency for large-scale cases, respectively, compared with existing algorithms.

Key words: relocation problem, heuristic algorithm, branch and bound algorithm, directional search algorithm, automated container terminal

陈逸飞, 韩晓龙, 牛雅凡. 基于策略搜索算法的出口集装箱翻箱作业优化[J]. 计算机工程, 2025, 51(9): 362-372.

CHEN Yifei, HAN Xiaolong, NIU Yafan. Optimization of Export Container Relocation Operations Based on Policy Search Algorithm[J]. Computer Engineering, 2025, 51(9): 362-372.

https://www.ecice06.com/CN/Y2025/V51/I9/362

图/表 17

图1 集装箱堆场贝位示意图

Fig.1 Schematic diagram of container yard bay position layout

图2 提箱与翻箱操作示意图

Fig.2 Schematic diagram of lifting and relocation operation

图3 翻箱操作示意图

Fig.3 Schematic diagram of relocation operation

图4 规则示例图

Fig.4 Rule example diagram

图5 空栈处理示例图

Fig.5 Example diagram of empty stack handling

图6 特殊栈处理示例图

Fig.6 Example diagram of special stack handling

图7 分支示意图

Fig.7 Branch schematic diagram

图8 分支定界算法剪枝操作

Fig.8 Branch and bound algorithm pruning operation

图9 限束剪枝操作

Fig.9 Constrained pruning operation

图10 不同算法结果对比

Fig.10 Comparison of the results of different algorithms

图11 小规模算例结果对比

Fig.11 Comparison of results from small-scale case studies

图12 3种算法的大规模算例对比

Fig.12 Large-scale case comparison of three algorithms

图13 不同限束值下算法对比

Fig.13 Algorithm comparison under different constraint values

参考文献 25

1	包甜甜, 连峰, 杨忠振. 航运管理研究综述. 交通运输工程学报, 2020, 20 (4): 55- 69.
	BAO T T , LIAN F , YANG Z Z . Research review of shipping management. Journal of Traffic and Transportation Engineering, 2020, 20 (4): 55- 69.
2	LERSTEAU C , SHEN W M . A survey of optimization methods for block relocation and PreMarshalling problems. Computers & Industrial Engineering, 2022, 172, 108529.
3	朱明华, 程奂翀, 范秀敏. 基于定向搜索算法的集装箱堆场翻箱问题. 计算机集成制造系统, 2012, 18 (3): 639- 644.
	ZHU M H , CHENG H C , FAN X M . Blocks relocation problem with filter based beam search algorithm. Computer Integrated Manufacturing Systems, 2012, 18 (3): 639- 644.
4	NIU M F , HU Y Y , SUN S L , et al. A novel hybrid decomposition-ensemble model based on VMD and HGWO for container throughput forecasting. Applied Mathematical Modelling, 2018, 57, 163- 178.
5	CASERTA M , SCHWARZE S , VOS S . A mathematical formulation and complexity considerations for the blocks relocation problem. European Journal of Operational Research, 2012, 219 (1): 96- 104.
6	CARLO H J , VIS I F A , ROODBERGEN K J . Storage yard operations in container terminals: literature overview, trends, and research directions. European Journal of Operational Research, 2014, 235 (2): 412- 430.
7	PETERING M E H , HUSSEIN M I . A new mixed integer program and extended look-ahead heuristic algorithm for the block relocation problem. European Journal of Operational Research, 2013, 231 (1): 120- 130.
8	DE MELO DA SILVA M , TOULOUSE S , WOLFLER CALVO R . A new effective unified model for solving the pre-marshalling and block relocation problems. European Journal of Operational Research, 2018, 271 (1): 40- 56.
9	KIM K H , HONG G P . A heuristic rule for relocating blocks. Computers & Operations Research, 2006, 33 (4): 940- 954.
10	TANAKA S , VOS S . An exact approach to the restricted block relocation problem based on a new integer programming formulation. European Journal of Operational Research, 2022, 296 (2): 485- 503.
11	DAVIES A , VELIČKOVIĆ P , BUESING L , et al. Advancing mathematics by guiding human intuition with AI. Nature, 2021, 600 (7887): 70- 74.
12	HOTTUNG A , TANAKA S , TIERNEY K . Deep learning assisted heuristic tree search for the container pre-marshalling problem. Computers & Operations Research, 2020, 113, 104781.
13	TRICOIRE F , SCAGNETTI J , BEHAM A . New insights on the block relocation problem. Computers & Operations Research, 2018, 89, 127- 139.
14	杨小明, 周云鹏, 耿志康, 等. 基于规则集定向搜索算法的装船翻箱问题. 计算机集成制造系统, 2023, 29 (3): 1040- 1054.
	YANG X M , ZHOU Y P , GENG Z K , et al. The loading and unloading container problem based on the rule set directional search algorithm. Computer Integrated Manufacturing Systems, 2023, 29 (3): 1040- 1054.
15	FORSTER F , BORTFELDT A . A tree search procedure for the container relocation problem. Computers & Operations Research, 2012, 39 (2): 299- 309.
16	FEILLET D , PARRAGH S N , TRICOIRE F . A local-search based heuristic for the unrestricted block relocation problem. Computers & Operations Research, 2019, 108, 44- 56.
17	MARKO D , MATEJA D . Automated design of heuristics for the container relocation problem using genetic programming. Applied Soft Computing, 2022, 130, 109696.
18	ZHANG C R , GUAN H , YUAN Y F , et al. Machine learning-driven algorithms for the container relocation problem. Transportation Research Part B: Methodological, 2020, 139, 102- 131.
19	张艳伟, 蔡梦蝶. 基于逆向强化学习的装船时堆场翻箱智能决策. 同济大学学报(自然科学版), 2021, 49 (10): 1417- 1425.
	ZHANG Y W , CAI M D . An inverse reinforcement learning method for container relocation in container terminal yard during loading. Journal of Tongji University (Natural Science), 2021, 49 (10): 1417- 1425.
20	YE R Y , YE R G , ZHENG S S . Machine learning guides the solution of blocks relocation problem in container terminals. Transportation Research Record, 2023, 2677 (3): 721- 737.
21	PARREÑO-TORRES C , ALVAREZ-VALDES R , RUIZ R , et al. Minimizing crane times in pre-marshalling problems. Transportation Research Part E: Logistics and Transportation Review, 2020, 137, 101917.
22	FILOM S , AMIRI A M , RAZAVI S . Applications of machine learning methods in port operations: a systematic literature review. Transportation Research Part E: Logistics and Transportation Review, 2022, 161, 102722.
23	TUS A, RENDL A, RAIDL G R. Metaheuristics for the two-dimensional container pre-marshalling problem[C]//Proceeding of the 9th International Conference on Learning and Intelligent Optimization. Berlin, Germang: Springer, 2015: 186-201.
24	AS'G WIEBODA J, ZAJAC M. Analysis of reshuffling cost at a container terminal[C]//Proceedings of the 11th International Conference on Dependability Engineering and Complex Systems. Berlin, Germang: Springer, 2016: 491-503.
25	ZHU W B , QIN H , LIM A , et al. Iterative deepening A* algorithms for the container relocation problem. IEEE Transactions on Automation Science and Engineering, 2012, 9 (4): 710- 722.

[1]	周春雷, 宋继勐, 沈子奇, 余晗, 雷杰, 林兵. 数联网标识解析系统中的标识数据布局策略[J]. 计算机工程, 2024, 50(6): 311-320.
[2]	林丹, 郑梓烨, 付齐双, 吴嘉婧, 郑子彬. 基于DeFi消息传递机制的跨链交易关联方法[J]. 计算机工程, 2024, 50(10): 61-68.
[3]	刘博宇, 梁承姬, 王钰. 特大型城市地下物流多层级网络优化研究[J]. 计算机工程, 2023, 49(12): 311-320.
[4]	黄金瑶, 刘同来, 吴嘉鑫, 武继刚. 多周期家庭护理的路径规划与调度算法[J]. 计算机工程, 2022, 48(7): 292-299.
[5]	耿海军, 张伟, 尹霞. 基于混合软件定义网络的路由保护算法[J]. 计算机工程, 2020, 46(6): 209-215.
[6]	李隋凯,励益韬,孙未未,秦涛,黄秀松. 一种自动化集装箱码头出口箱进箱选位算法[J]. 计算机工程, 2019, 45(5): 272-278,284.
[7]	龙恳, 钱美伶, 余翔, 陈侃. 一种基于网络切片的带宽资源编排算法[J]. 计算机工程, 2019, 45(10): 78-83.
[8]	许磊,顾进广,何亨. 基于SDN架构的网络能耗与性能动态调节机制[J]. 计算机工程, 2018, 44(4): 108-114.
[9]	郭羽含,杨晓翠. 绿色供应链网络构建的双阶段综合优化方法[J]. 计算机工程, 2016, 42(10): 192-200.
[10]	刘文锋. 一种基于最小能耗的手机传感调度算法[J]. 计算机工程, 2015, 41(6): 83-89.
[11]	徐超,曾学文,郭志川. 基于资源预测的智能终端资源缓存算法[J]. 计算机工程, 2015, 41(3): 59-63.
[12]	凌权,李枚毅. 无线Mesh网络中骨干节点部署算法研究[J]. 计算机工程, 2015, 41(11): 147-152.
[13]	高圣巍,彭超. 一种改进的邻接关系可查询压缩算法[J]. 计算机工程, 2015, 41(1): 61-64.
[14]	李静梅,王雪,韩启龙. 一种异构多核处理器启发式综合任务调度算法[J]. 计算机工程, 2014, 40(8): 242-245,252.
[15]	秦天保，彭嘉瑶，沙梅. 基于约束规划的岸桥与集卡集成调度[J]. 计算机工程, 2014, 40(5): 196-202.

选择文件类型/文献管理软件名称

选择包含的内容