Integer programming method for the pre-marshalling problem in container yards based on transcoding technology

CHEN Yifei, HAN Xiaolong, NIU Yafan

doi:10.16411/j.cnki.issn1006-7736.2024.03.008

Journal of Dalian Maritime University >

2024 , Vol. 50 >Issue 3: 67 - 77

DOI: https://doi.org/10.16411/j.cnki.issn1006-7736.2024.03.008

Integer programming method for the pre-marshalling problem in container yards based on transcoding technology

Expand

（Institute of Logistics Science ＆ Engineering，Shanghai Maritime University，Shanghai 201306，China）

Online published: 2024-02-27

Fold

Abstract

In order to improve loading efficiency, focusing on the pre-marshalling problem and taking the priority of the slot-storage export containers as the main decision variable, a priority model for the pre-marshalling problem of export containers in storage yard was proposed. Considering containers flipping operations as the core objective of the decision process, a transcoding technique was introduced based on the properties of decimal and binary conversion. Combining with existing research models and the proposed integer programming model, a set of transcoding models were constructed. By testing on existing data sets, compared with existing models, the proposed priority model can reduce the average solution time by 75.66%,while the solution time of the transcoding model group is significantly lower than that of the original model group, in addition that the maximum solution efficiency is increased by 182.5%.

Key words： container terminal；yard operation optimization; pre-marshalling problem；transcoding technique；integer programming

Cite this article

CHEN Yifei, HAN Xiaolong, NIU Yafan . Integer programming method for the pre-marshalling problem in container yards based on transcoding technology[J]. Journal of Dalian Maritime University, 2024 , 50(3) : 67 -77 . DOI: 10.16411/j.cnki.issn1006-7736.2024.03.008

References

[1]FACILITATION T. United Nations Conference on Trade and Development. 50 years of review of maritime transport, 1968-2018: reflecting on the past, exploring the future[M]. Geneva, Switzerland: United Nations, 2018.

[2]HOFFMANN J, HOFFMANN J J U T, QUARTER T F N N-F. Bigger ships and fewer companies—Two sides of the same coin[J].UNCTAD Transport and Trade Facilitation Newsletter N, 2021, 89.

[3]CASERTA M, SCHWARZE S, VOß S. Container rehandling at maritime container terminals[M]//Böse J W. Handbook of Terminal Planning: Vol. 49. New York, NY: Springer New York, 2011: 247-269.

[4]丁一, 杨旭泽. 考虑动态加权A星算法的预翻箱作业优化[J]. 运筹与管理, 2023, 32(5): 36-41, 48.

DING Y, YANG X Z. A Dynamic Weighted A* Algorithm for the Pre-marshalling Problem[J]. Operations Research and Management Science, 2023, 32(5): 36-41.(in chinese)

[5]黄子钊, 庄子龙, 滕浩, 等. 自动化码头出口箱箱位分配优化超启发式算法[J]. 计算机集成制造系统, 2022, 28(8): 2619-2632.

HUANG Z Z, ZHUANG Z L, TENG H, QIN W, QIN T, ZOU Y. Optimization of outbound container space assignment in automated container terminals based on hyper-heuristic algorithm[J]. Computer Integrated Manufacturing System, 2022, 28(8): 2619-2632.(in chinese)

[6]刘庭玮, 段凯耀. 基于贪婪算法的物流堆场策略建模研究[J]. 中国储运, 2021(5): 101-104.

LIU W T，Duan Y K. Research on Logistics Yard Strategy Modeling Based on Greedy Algorithm[J]. China Storage and Transportation,2021，(05)：101-104.(in chinese)

[7]张艳伟, 姜旎旎, 计三有. 基于贪婪禁忌搜索算法的垂岸式堆场出口箱装船翻箱研究[J]. 运筹与管理, 2023, 32(1): 154-158.

ZHANG Y W, JIANG N N, JI S Y. Research on Export Container Relocation Problem on Greedy Tabu Search Algorithm in Perpendicular Container Yard[J]. Operations Research and Management Science, 2023, 32(1): 154-158.(in chinese)

[8]杨小明, 周云鹏, 耿志康, 等. 基于规则集定向搜索算法的装船翻箱问题[J]. 计算机集成制造系统, 2023, 29(3): 1040-1054.

YANG X M, ZHOU Y P, GENG Z K, XU Z Q. Loading relocation problem based on rule set based beam search algorithm[J]. Computer Integrated Manufacturing System, 2023, 29(3): 1040-1054.(in chinese)

[9]乐美龙, 姜丹. 堆场集装箱预翻箱问题[J]. 辽宁工程技术大学学报（自然科学版）, 2014, 33(3): 405-408.

LE M L, JIANG D. Pre-Marshalling Problem of Yard Containers[J]. Journal of Liaoning Technical University (Science)，2014，33(03)：405-408.(in chinese)

[10]范厚明, 孔靓, 岳丽君. 考虑出口箱进出场及预翻箱的箱位分配与场桥调度协同优化[J]. 运筹与管理, 2021, 30(6): 26-34.

FAN H M, KONG L,YUE L J. Yard Crane Scheduling and Storage Space Allocation Considering Container Storage, Retrieval, and Pre-marshalling[J]. Operations Research and Management Science, 2021, 30(6): 26-34.(in chinese)

[11] LEE Y S, HSU N Y. An optimization model for the container pre-marshalling problem[J]. Computers & Operations Research, 2007, 34(11): 3295-3313.

[12] DE MELO DA SILVA M, Toulouse S, Wolfler Calvo R. A new effective unified model for solving the Pre-marshalling and Block Relocation Problems[J]. European Journal of Operational Research, 2018, 271(1): 40-56.

[13] PARREÑO-TORRES C, ALVAREZ-VALDES R, RUIZ R. Integer programming models for the pre-marshalling problem[J]. European Journal of Operational Research, 2019, 274(1): 142-154.

[14] PARREÑO-TORRES C, ALVAREZ-VALDES R, RUIZ R, et al. Minimizing crane times in pre-marshalling problems[J]. Transportation Research Part E: Logistics and Transportation Review, 2020, 137: 101917.

[15] LERSTEAU C, SHEN W M. A survey of optimization methods for Block Relocation and PreMarshalling Problems[J]. Computers & Industrial Engineering, 2022, 172: 108529.

[16] CASERTA M, VOß S. A corridor method-based algorithm for the pre-marshalling problem[M]//Giacobini M, Brabazon A, Cagnoni S, et al. Applications of Evolutionary Computing: Vol. 5484. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009: 788-797.

[17] FORSTER F, BORTFELDT A. A tree search procedure for the container relocation problem[J]. Computers & Operations Research, 2012, 39(2): 299-309.

[18] HUANG S H, LIN T H. Heuristic algorithms for container pre-marshalling problems[J]. Computers & Industrial Engineering, 2012, 62(1): 13-20.

[19] HOTTUNG A, TIERNEY K. A biased random-key genetic algorithm for the container pre-marshalling problem[J]. Computers & Operations Research, 2016, 75: 83-102.

[20] DAVIES A, VELIČKOVIĆ P, BUESING L. Advancing mathematics by guiding human intuition with AI[J]. Nature, 2021, 600(7887): 70-74.

[21] HOTTUNG A, TANAKA S J, TIERNEY K. Deep learning assisted heuristic tree search for the container pre-marshalling problem[J]. Computers & Operations Research, 2020, 113: 104781.

[22] ZHANG C R, GUAN H, YUAN Y F, et al. Machine learning-driven algorithms for the container relocation problem[J]. Transportation Research Part B: Methodological, 2020, 139: 102-131.

[23] LI H L, LU H C. Global optimization for generalized geometric programs with mixed free-sign variables[J]. Operations Research, 2009, 57(3): 701-713.

Options

Outlines

模态框（Modal）标题

Abstract

Cite this article

References