An Improved Dung Beetle Optimizer for the Twin Stacker Cranes’ Scheduling Problem

Abstract

In recent years, twin stacker crane units have been increasingly integrated into large automated storage and retrieval systems (AS/RSs) in shipyards to enhance operational efficiency. These common rail units often encounter conflicts, and the additional time costs incurred during collision avoidance significantly diminish AS/RS efficiency. Therefore, addressing the twin stacker cranes’ scheduling problem (TSSP) with a collision-free constraint is essential. This paper presents a novel approach to identifying and avoiding collisions by approximating the stacker crane’s trip trajectory as a triangular envelope. Utilizing the collision identification equation derived from this method, we express the collision-free constraint within the TSSP and formulate a mixed-integer programming model. Recognizing the multimodal characteristics of the TSSP objective function, we introduce the dung beetle optimizer (DBO), which excels in multimodal test functions, as the foundational framework for a heuristic optimizer aimed at large-scale TSSPs that are challenging for exact algorithms. To adapt the optimizer for bi-level programming problems like TSSPs, we propose a double-layer code mechanism and innovatively design a binary DBO for the binary layer. Additionally, we incorporate several components, including a hybrid initialization strategy, a Cauchy–Gaussian mixture distribution neighborhood search strategy, and a velocity revision strategy based on continuous space discretization, into the improved dung beetle optimizer (IDBO) to further enhance its performance. To validate the efficacy of the IDBO, we established a numerical experimental environment and generated a series of instances based on actual environmental parameters and operational conditions from an advanced AS/RS in southeastern China. Extensive comparative experiments on various scales and distributions demonstrate that the components of the IDBO significantly improve algorithm performance, yielding stable advantages over classical algorithms in solving TSSPs, with improvements exceeding 10%.

Keywords

• shipbuilding material management
• automated storage and retrieval system
• improved dung beetle optimizer
• twin stacker cranes’ scheduling
• combinatorial optimization