动态接力模式下箱位分配与双场桥调度协同优化

舒帆; 董琳; 汤新宇; 石歆怡

doi:10.12404/j.issn.1671-1815.2505178

科学技术与工程 ›› 2026, Vol. 26 ›› Issue (14) :6189-6200 DOI: 10.12404/j.issn.1671-1815.2505178

交通运输

动态接力模式下箱位分配与双场桥调度协同优化

舒帆 ¹ ,
董琳 ² ,
汤新宇 ¹ ,
石歆怡 ¹

作者信息 +

Integrated Optimization of Storage Space Allocation and Dual-yard Crane Scheduling under Dynamic Relay Mode

SHU Fan ¹ ,
DONG Lin ² ,
TANG Xin-yu ¹ ,
SHI Xin-yi ¹

Author information +

文章历史 +

摘要

为应对集装箱吞吐量增长与船舶大型化给自动化集装箱码头运营带来的挑战,出口箱箱位分配与场桥调度的协同优化成为提高堆场作业效率的研究热点。以纵向布局自动化集装箱码头为研究对象,在双场桥动态接力模式下,以最小化翻箱量及最小化场桥最大完工时间为目标构建了多目标协同优化数学模型,设计了结合传统非支配排序遗传算法(non-dominated sorting genetic algorithm Ⅱ,NSGA-Ⅱ)与变邻域搜索算法(variable neighborhood search,VNS)的混合启发式算法对协同优化数学模型进行求解,利用NSGA-Ⅱ进行全局搜索,结合VNS的多邻域结构对子代进行局部优化,增强局部搜索能力。算例实验结果表明,混合算法求解的场桥作业完工时间较传统NSGA-Ⅱ算法优化了4.4%10.9%。基于混合NSGA-Ⅱ变邻域搜索算法求解出口箱箱位分配及场桥作业序列协同方案,达到减少翻箱量、缩短场桥作业完工时间的目的。

Abstract

In response to the challenges posed by increasing container throughput and the trend towards larger vessels in automated container terminal operations, the integrated optimization of export container storage space allocation and yard crane scheduling has emerged as a critical research focus for enhancing yard efficiency. A longitudinally configured automated container terminal operating under a dynamic dual-crane relay mode was investigated. A multi-objective collaborative optimization model was developed with the aims of minimizing both the number of rehandling operations and the maximum completion time of yard cranes. To solve this model, a hybrid heuristic algorithm was designed that integrates NSGA-Ⅱ (non-dominated sorting genetic algorithm Ⅱ) with VNS (variable neighborhood search). The NSGA-Ⅱ performed global search while VNS enhanced local optimization through multiple neighborhood structures, thereby strengthening local search capabilities. Results from numerical experiments demonstrated that the completion time achieved by the hybrid algorithm was reduced by 4.4% to 10.9% compared to that obtained using traditional NSGA-Ⅱ methods. Through this proposed approach, an effective coordinated solution for export container storage space allocation and yard crane operation sequencing was generated, successfully achieving objectives related to reducing rehandling operations and shortening yard crane completion times.

Graphical abstract

关键词

自动化集装箱码头 / 箱位分配 / 双场桥调度 / 动态接力模式 / 混合NSGA-Ⅱ变邻域搜索算法

Key words

automated container terminal / storage space allocation / dual-yard crane scheduling / dynamic relay mode / hybrid NSGA-Ⅱ-VNS algorithm

引用本文

引用格式 ▾

舒帆, 董琳, 汤新宇, 石歆怡. 动态接力模式下箱位分配与双场桥调度协同优化[J]. 科学技术与工程, 2026, 26(14): 6189-6200 DOI:10.12404/j.issn.1671-1815.2505178

SHU Fan, DONG Lin, TANG Xin-yu, SHI Xin-yi. Integrated Optimization of Storage Space Allocation and Dual-yard Crane Scheduling under Dynamic Relay Mode[J]. Science Technology and Engineering, 2026, 26(14): 6189-6200 DOI:10.12404/j.issn.1671-1815.2505178

登录浏览全文

4963

注册一个新账户忘记密码

随着全球贸易深化,海上运输因其运能大、成本低等优势,已成为国际物流的主要方式。集装箱码头作为海运网络的关键枢纽,承担水陆衔接与集装箱作业核心功能,对全球供应链至关重要。2024年全球十大集装箱港口中国占六席,体现中国在全球航运中的重要地位。

然而,贸易规模扩大在推动吞吐量增长的同时,也对港口运营效率、自动化及智能化水平提出更高要求。集装箱码头正由传统模式向数字化、智能化系统转型,逐步构建高效、协同、韧性的运营体系^[1]。如上海洋山四期码头采用“双小车岸桥+自动化导引车(automated guided vehicle,AGV)+双自动化轨道吊(automated rail-mounted gantry,ARMG)”(下文简称双场桥)的装卸工艺,在智能化程度、单体规模和运营效率方面全球领先。

随着集装箱吞吐量增长与船舶大型化的发展,如何提高堆场作业效率成为研究关键,现有研究主要集中在箱位分配和场桥调度两个方面。

箱位分配方面,部分研究优化箱区或贝位分配,其余则聚焦具体箱位的分配。余明珠等^[2]提出了“长途箱压短途箱”的箱位分配策略以优化装船效率并减少翻箱。李隋凯等^[3]考虑带中转贝位的堆场布局下的出口箱贝位分配问题,以最小化翻箱数为目标设计了多阶段动态规划算法进行求解。在箱位分配研究中,Yu等^[4]提出了基于贝叶斯共享的堆场空间分配策略,依次优选箱区与箱位。罗浩铭等^[5]考虑了集装箱进出场时间与堆场作业压力问题,以压箱数最小建立指派模型。Park等^[6]构建了基于双模块数据驱动的动态堆垛策略,根据重量分类实现箱位动态分配。尹延冬等^[7]针对集卡失约导致的堆场效率问题,提出一种邻域搜索启发式算法,通过动态调整落箱位,降低翻箱数与场桥移动距离。任刚等^[8]将最小化压箱数和场桥移动贝位数作为箱位分配目标,设计启发式算法求解优化模型。黄子钊等^[9]在场桥接力作业模式下考虑多箱区协同作业问题,提出了基于强化学习的超启发式方法处理出口箱选位问题,证明了其相较于传统智能算法的优越性。Ambrosino等^[10]将存储成本最小化、场桥操作效率最大化以及策略鲁棒性提升作为优化目标。此外,部分学者将研究视角投向特殊布局码头,曹梦洁等^[11]针对U型自动化码头提出两阶段箱位分配优化,设计融合免疫机制改进的遗传算法求解。

场桥调度方面,于蒙等^[12]分别建立了混堆箱区中单吊具场桥和双40 ft场桥的调度模型,使用遗传模拟退火算法求解,对比分析了两者的效率差异。Zheng等^[13]引入集装箱动态处理时间的概念并以作业任务延迟时间最短为目标建立双场桥调度优化模型。Eilken^[14]将双场桥调度问题划分为进出场、翻箱和接力作业的子调度问题,采用分支定界法进行求解。在冲突规避方面,Nossack等^[15]在场桥调度时加入作业冲突的修正操作,建立混合整数规划模型并采用分支定界法求解。Lu等^[16]在场桥协同调度中将最小化AGV等待时间作为优化目标,设计了基于图论模型的粒子群算法。Jin等^[17]考虑了集装箱随机到达与场桥间安全距离等因素,利用深度强化学习方法,减少场桥运行时间和干扰情况的发生。

实际生产作业中,箱位资源分配和场桥调度相互制约,需进行协同优化。范厚明等^[18]在送箱集卡失约背景下,在多箱区内选择合适堆存位置,并协同考虑场桥调度,设计混合遗传变邻域算法求解优化模型。Jiang等^[19]研究了集装箱贝位分配及箱区内场桥配置数量问题,以场桥移动成本和翻箱成本最小建立模型并设计分支定界法求解,结果表明在场桥数量不变的前提下可减少场桥移动、提高箱位使用率。

部分学者则特别针对接力模式下的调度展开研究,邱亚等^[20]在兼顾安全距离和作业冲突约束的基础上,基于对比实验分析得出动态接力模式下场桥作业效率优于固定接力模式。Kress等^[21]提出了将海侧集装箱完工延迟时间最短且保证陆侧集装箱按时完成作业作为优化目标,分析接力模式下的双场桥调度问题,利用动态规划算法求解混合整数规划模型。Dong等^[22]构建以场桥作业总时间最短为目标的出口箱箱位分配与双场桥调度协同优化模型,并设计融合模拟退火算子的改进遗传算法及深度强化学习算法求解,有效提升了堆场作业效率。Fan等^[23]考虑双场桥安全距离和缓冲区容量对场桥调度和箱位分配问题的影响,定义作业优先级规则及其作业顺序,利用混合变邻域遗传算法求解优化模型。

综上所述,现有研究多为单独优化箱位分配或场桥调度,对两者协同优化并面向纵向布局双场桥接力工艺的研究较少。即便在涉及该工艺的协同研究中,也存在将多目标问题简化为单目标处理的倾向。然而,由于箱位分配与场桥调度是相互耦合的复杂决策过程,最小化场桥作业时间和最小化翻箱量两大目标之间存在着难以回避的内在冲突,因此有必要展开多目标优化研究。

为此,现提出建立箱位分配问题与场桥调度双目标协同优化模型,依据出口箱属性设定作业优先级,并精确分配具体箱位;同时,引入双场桥动态接力模式,对接力区及接力点的位置进行动态调整,根据出口箱任务特性为双场桥设置作业优先级和避碰规则,加快双场桥堆存出口箱作业进程,优化堆场整体作业效率。研究基于混合NSGA-Ⅱ变邻域搜索算法求解出口箱箱位分配及场桥作业序列协同方案,可达到减少翻箱量、缩短场桥作业完工时间的目的;为集装箱码头出口箱的智能堆存决策提供理论依据与方法支撑,具有较高的实际应用价值。

1 出口箱箱位分配与场桥调度协同优化模型

1.1 问题描述

以垂岸式布局码头为研究对象,箱区两侧分别设有陆侧交换区和海侧交换区,箱区内配备两台相同的自动化轨道吊,海侧记为ARMG1,陆侧记为ARMG2。

出口集装箱在船舶靠泊前需要进行集港作业,根据出口箱的属性将其堆放到码头堆场的指定箱位。外集卡将出口集装箱运送至目标箱区的陆侧交换区后,ARMG2从前一任务的结束位置移动至陆侧交换区进行收箱作业,并将目标箱送至接力区的指定箱位中进行暂存,再由ARMG1从前一任务的结束位置到达接力区进行接力作业,提取目标箱后将该箱运送至海侧指定箱位进行堆存,如图1所示。

1.1.1 基于优先级的翻箱量计算

堆场箱位由箱区、贝位、栈位和层数构成。出口箱箱位分配需结合箱区现状与船舶配载图,考虑箱型、重量等级、到场次序和卸货港,遵循远压近、重压轻原则。为减少翻箱,主要根据卸货港和重量等级来设计优先级。优先规则为:同一船的集装箱,先按卸货港挂靠顺序(越远优先级越高),再按重量等级(越重优先级越高)。

以20 ft出口集装箱为例,其重量等级可分为5级:1级(010 t)、2级(1015 t)、3级(1520 t)、4级(2025 t)、5级(>25 t)。结合卸货港的综合信息,集装箱整体优先级定义为q_i=Wd_i+w_i,其中,d_i为出口集装箱i对应的卸货港挂靠顺序,w_i为集装箱i的重量级,W为w_i的最大值。

计算箱区翻箱量时,先计算各堆栈的翻箱量,再进行累加求和。如图2所示,在某堆栈内,第3层堆放的箱A卸货港顺序为2,重量等级为3,依据公式其整体优先级q_A为13,第2层堆放的箱B卸货港顺序为3,重量等级为2,整体优先级q_B为17,q_B>q_A,即该栈内产生一次翻箱。

1.1.2 场桥接力及避碰处理

自动化码头堆场两台ARMG不可跨越且需保持安全距离,因此作业中会互相干扰。传统接力区模式一般为固定接力区模式,易导致场桥忙闲不均和箱区中部堆存浪费,因此提出动态接力模式,即接力贝位范围是动态确定的,双场桥拥有公共作业区域,可在一定范围内进入对方区域提放箱。

在双场桥动态作业模式下,首先需要基于箱位分配方案,以箱区中间贝位为分界线判断任务箱的初始位置和目标位置是否同侧;若同侧则由单场桥独立完成作业,若分处两侧则需进行接力作业。对于需要接力的出口箱任务,作业过程分解为主作业和接力作业:主作业由ARMG2负责将集装箱从初始位置运送至动态接力区暂存;随后,接力作业由ARMG1负责将该箱从接力区接力箱位运送至海侧目标位置堆存。其次需解决作业冲突问题。尽管该模式能规避大部分冲突,但因双场桥均可进入接力区,在接力点附近仍存在碰撞风险。鉴于仅处理出口箱堆存且ARMG1必须在ARMG2完成接力区放箱后方能提箱,因此假设在集港高度繁忙的工况下,当双场桥发生冲突时,赋予ARMG2更高的作业优先级,此时ARMG1需向海侧移动避让、留出安全距离等待,待ARMG2完工后才进入接力区执行提箱任务。

1.1.3 动态接力区及接力点选择

动态接力区由传统接力模式下的箱区中部若干个固定贝位变为根据作业任务特性调整其位置的多个连续贝位。堆场作业状态和任务箱状态实时变化会导致场桥作业路径随之改变,采用动态接力区更符合自动化码头实际。

对于最优接力点的确定,在待选动态贝位范围内,比较各待选位置的目标函数值,选择目标函数取值最小的箱位作为接力箱位,从而确定最佳接力点。整体接力区和接力点决策流程如图3所示。

协同优化模型旨在最小化翻箱量和场桥最大完工时间。仅优化场桥完工时间可能忽略提箱优先级等要求而增加后续的翻箱操作;仅减少翻箱操作则可能出现分散堆存,导致场桥作业时间延长。因此,研究在动态接力模式下,结合安全距离约束与出口箱优先级规则,协同优化海侧箱区及接力区的箱位分配与双场桥调度,以提升堆场整体作业效率。

1.2 模型构建

1.2.1 基本假设

(1)自动化集装箱码头中双场桥无法跨箱区作业,因此考虑单箱区内的双场桥调度问题。

(2)不考虑双场桥的启动加速时间以及设备故障,两场桥在作业过程中始终保持匀速行驶。

(3)仅考虑20 ft(1 ft=0.304 8 m)普通出口集装箱的堆存作业问题。

(4)初始时刻已有部分集装箱堆存在箱区内,初始堆存状态和场桥初始位置已知。

(5)出口集装箱的相关属性信息已知。

(6)双场桥为非穿越式,在作业时通常需要保持2 个贝位的安全距离。

1.2.2 目标函数

目标函数1表示最小化翻箱量,由各栈翻箱量求和所得。

(1)

$min{f}_{1}=\sum _{b=1}^{{N}_{B}}\sum _{r=1}^{{N}_{R}}\sum _{e=2}^{{N}_{E}}\sum _{\nu =1}^{e-1}{R}_{br(e-\nu )}^{i}$

式(1)中:

${R}_{br(e-v)}^{i}$

为0-1变量,表示若箱位b贝r栈e层上的集装箱整体优先级低于e-v层上的集装箱,造成翻箱则为1,否则为0;N_B为箱区包含的贝位总数,箱区所有贝位组成贝位集合B,用B={0,1,2,…,N_B,N_B+1}表示,其中第0贝表示海侧I/O点,第N_B+1号贝位表示陆侧I/O点;N_R为箱区包含的栈总数,所有栈组成栈的集合R,用R={1,2,…,N_R}表示;N_E为箱区的最高层数,所有层组成层的集合E,用E={1,2,…,N_E}表示。

目标函数2表示最小化出口箱堆存过程中场桥最大完工时间。

(2)

$min{f}_{2}=max{C}_{i}$

式(2)中:C_i为出口箱作业任务i的作业结束时刻。

1.2.3 约束条件

箱位分配约束为

(3)

${\sum }_{r\in R}^{}{\sum }_{e\in E}^{}{\sum }_{b\in {B}_{m}}^{}{x}_{bre}^{i}=1, \forall i\in I$

式(3)中:

${x}_{bre}^{i}$

为0-1变量,若出口箱任务i堆存于箱位(b,r,e)上则为1,否则为0;B_m为接力贝位,B_m={b_m+1,b_m+2,…,b_m+n},n为接力贝位的数量; I为出口集装箱任务的集合,I={1,2,…,N_I}。

(4)

${\sum }_{r\in R}^{}{\sum }_{e\in E}^{}{\sum }_{b\in {B}_{1}}^{}{x}_{bre}^{i}=1, \forall i\in I$

式(4)中:B₁为海侧箱区贝位,B₁={1,2, …,b_m}。B₂为陆侧箱区贝位B₂={b_m+n+1,b_m+n+2,…,N_B},因此B={0}∪B₁∪B_m∪B₂∪{N_B+1}。

(5)

${\sum }_{i\in I}^{}{x}_{bre}^{i}+{E}_{bre}^{0}\le 1, \forall b\in {B}_{1},\forall r\in R,\forall e\in E$

式(5)中:

${E}_{bre}^{0}$

为0-1变量,初始状态下箱位(b,r,e)已被占用则为1,否则为0。

(6)

${x}_{bre}^{i}+{E}_{bre}^{0}\le 1, \forall b\in {B}_{m},\forall r\in R,\forall e\in E$

(7)

${\sum }_{i\in I}^{}{\sum }_{r\in R}^{}{\sum }_{e\in E}^{}{x}_{bre}^{i}+{\sum }_{r\in R}^{}{\sum }_{e\in E}^{}{E}_{bre}^{0}\le {F}_{b}, \forall b\in {B}_{1}$

式(7)中:F_b为贝位b的最大可容纳箱量。

(8)

${x}_{bre}^{i}\le {A}_{bre}, \forall b\in {B}_{m},\forall r\in R,\forall e\in E$

式(8)中:A_bre为0-1变量,若接力区箱位(b,r,e)可用于堆存任务i则为1,否则为0。

(9)

$\begin{array}{l}{\sum }_{i\in I}^{}{x}_{bre}^{i}\le {\sum }_{i\in I}^{}{x}_{br(e-1)}^{i}, \forall b\in {B}_{1},\\ \forall r,\forall e=\mathrm{2,3},\dots,E\end{array}$

(10)

$\begin{array}{l}{Y}_{br}=max\left\{{q}_{j}{x}_{brv}^{j}\right\}, \forall j\in I,\forall b\in {B}_{1},\\ \forall v=\mathrm{1,2},\dots,e-1\end{array}$

式(10)中:Y_br为堆存于b贝r栈中所有集装箱的最高优先级;q_i、q_j为出口箱作业任务i、j的整体优先级;

${x}_{brv}^{j}$

为0-1变量,表示出口箱任务j堆存于箱位(b,r,v)上则为1,否则为0。

(11)

$\begin{array}{l}{q}_{i}{R}_{br(e-v)}^{i}\ge {Y}_{br}-M(1-{R}_{br(e-v)}^{i})-\\ M(1-{x}_{bre}^{i}),\forall i\in I,\forall b\in {B}_{1},\\ \forall v=\mathrm{1,2},\dots,e-1,\forall e\in E\end{array}$

式(11)中:M为足够大的正数。

场桥调度约束为

(12)

${\sum }_{u\in I}^{}{z}_{ki}^{u}=1, \forall k\in K,\forall i\in I$

式(12)中:

${z}_{ki}^{u}$

为0-1变量,若场桥k第u个作业出口箱任务i则为1,否则为0;K为场桥的集合,K={1,2},k=1表示海侧场桥,k=2表示陆侧场桥。

(13)

${\sum }_{i\in I}^{}{z}_{ki}^{u}=1, \forall k\in K,\forall u\in I$

(14)

$\begin{array}{l}{x}_{bre}^{i}\le 1-{x}_{brv}^{j}+(1-{z}_{ki}^{u})+(1-{z}_{kj}^{g}),\\ \forall i,j,u,g\in I,\forall b\in {B}_{1},\forall r\in R,\\ \forall e,v\in E,e＞v,u＜g,k=1\end{array}$

式(14)中:

${z}_{kj}^{g}$

为0-1变量,若场桥k第g个作业出口箱任务j则为1,否则为0。

(15)

${S}_{i}\ge {T}_{i}, \forall i\in I$

式(15)中:S_i为出口箱作业任务i的主作业任务开始时刻;T_i为出口箱作业任务i到达堆场的时刻。

(16)

${U}_{i}\ge {P}_{i}, \forall i\in I$

式(16)中:U_i为出口箱作业任务i的接力任务开始时刻;P_i为出口箱作业任务i的主作业完成时刻。

(17)

$\begin{array}{l}{S}_{i}\ge {P}_{j}+{t}_{b}\left|b\right.-({N}_{B}+1)|-M(1-{x}_{bre}^{j})-\\ M(1-{z}_{ki}^{u+1})-M(1-{z}_{kj}^{u}), \forall i,j,u\in I,\\ \forall b\in {B}_{m},\forall r\in R,\forall e\in E,k=2\end{array}$

式(17)中:t_b为场桥移动一个贝位所需的时间。

(18)

$\begin{array}{l}{U}_{i}\ge {C}_{j}+{t}_{b}\left|b\right.-b\text{'}|-M(1-{x}_{b\text{'}r\text{'}e\text{'}}^{i})-\\ M(1-{x}_{bre}^{j})-M(1-{z}_{ki}^{u+1})-M(1-{z}_{kj}^{u}),\\ \forall i,j,u\in I,\forall b\text{'}\in {B}_{m},\forall b\in {B}_{1},\\ \forall r,r\text{'}\in R,\forall e,e\text{'}\in E,k=1\end{array}$

(19)

$\begin{array}{l}{P}_{i}\ge {S}_{i}+{t}_{p}+{t}_{b}\left|\right({N}_{B}+1)-\left.b\right|+{t}_{p}-\\ M(1-{x}_{bre}^{i}),\forall i\in I,\forall b\in {B}_{m},\\ \forall r\in R,\forall e\in E\end{array}$

式(19)中:t_p为场桥完成一次提箱或放箱作业所需的时间。

(20)

$\begin{array}{l}{P}_{i}\le {S}_{i}+{t}_{p}+{t}_{b}|{N}_{B}+1-\left.b\right|+{t}_{p}+M(1-{x}_{bre}^{i}),\\ \forall i\in I,\forall b\in {B}_{m},\forall r\in R,\forall e\in E\end{array}$

(21)

$\begin{array}{l}{C}_{i}\ge {U}_{i}+{t}_{p}+{t}_{b}|b\text{'}-\left.b\right|+{t}_{p}-\\ M(1-{x}_{b\text{'}r\text{'}e\text{'}}^{i})-M(1-{x}_{bre}^{i}), \forall i\in I,\\ \forall b\text{'}\in {B}_{m},\forall b\in {B}_{1},\forall r,r\text{'}\in R,\forall e,e\text{'}\in E\end{array}$

(22)

$\begin{array}{l}{P}_{i}-{t}_{p}\le {U}_{j}+{t}_{p}+{t}_{b}\left|b\right.-(b\text{'}-d)|+\\ M(1-{z}_{ki}^{u+1})+M(1-{z}_{kj}^{u})+M(1-{x}_{bre}^{i})+\\ M(1-{x}_{b\text{'}r\text{'}e\text{'}}^{j}), \forall i,j,u\in I,\forall b,b\text{'}\in {B}_{m},\\ \forall r,r\text{'}\in R,\forall e,e\text{'}\in E\end{array}$

式(22)中:d为场桥保持安全距离的最小贝位数。

(23)

$\begin{array}{l}{x}_{bre}^{i},{E}_{bre}^{0},{A}_{bre},{R}_{br(e-v)}\in \left\{\mathrm{0,1}\right\}, \forall b\in B,\\ \forall r\in R,\forall e\in E,\forall v=\mathrm{1,2},\dots,e-1\end{array}$

(24)

${z}_{ki}^{u}\in \left\{\mathrm{0,1}\right\},\forall k\in K, \forall i,u\in I$

式(3)表示需要且仅能为出口箱任务i在接力区分配一个临时堆存箱位;式(4)表示需要且仅能为出口箱任务i在海侧箱区分配一个目标箱位;式(5)表示同一时刻海侧箱区内每个箱位最多堆存一个集装箱;式(6)表示暂存于接力箱位中的出口箱作业任务i提走后,该箱位可继续用于堆存集装箱;式(7)表示海侧箱区任意贝位的堆箱量都不可超过该贝位的最大可堆存量;式(8)表示仅能在接力区的空箱位中为出口箱任务i选择暂存箱位;式(9)表示出口箱任务i在海侧箱区堆存时不得出现悬空的情况;式(10)和式(11)表示翻箱量计算的相关约束,由于优先级越大的集装箱越早进行装船作业,因此在海侧箱区内计算翻箱量时,找到本栈堆存的集装箱优先级最大值所在层数,据此判断是否需要翻箱;式(11)表示优先级最大箱上方的压箱量进行计算;式(12)表示每台场桥一次只能作业一个出口箱作业任务i;式(13)表示每个出口箱任务i都需要由每台场桥分别作业一次;式(14)表示确保出口箱任务i在海侧箱区堆放顺序早于其上方的集装箱;式(15)表示出口箱任务i送达堆场后场桥才能对其进行作业;式(16)表示出口箱任务i接力作业开始时刻不得早于主作业任务完成时刻;式(17)和式(18)表示两台场桥各自作业一对紧前后任务的起止时间关系,紧后任务开始时刻需要晚于紧前任务结束时刻加上任务间空驶时间之和;式(19)式(21)表示场桥作业同一个出口箱任务i时的作业开始时间与结束时间关系,式(19)和式(20)表示主作业任务开始与结束时间关系,式(21)表示接力作业任务开始与结束时间关系;式(22)表示接力区内两场桥安全距离限制;式(23)和式(24)保证了0-1决策变量。

通过使用CPLEX求解器对算法模型进行小规模算例求解,证明了模型的可行性与有效性。

2 混合NSGA-II变邻域搜索算法设计

箱位分配与场桥调度协同优化属于多目标NP-hard问题,目标间存在矛盾且受堆场空间、作业时间及安全距离等复杂约束,求解空间庞大、变量耦合性强,传统精确算法难以高效求解大规模问题。因此,利用NSGA-Ⅱ进行全局搜索,结合VNS的多邻域结构对子代进行局部优化,增强局部搜索能力、提升收敛速度并避免陷入局部最优;同时,VNS的扰动策略可防止早熟收敛、维持种群多样性。该混合算法平衡了全局多样性与局部精确性,算法流程如图4所示。

2.1 染色体编码与解码

在染色体设计方面采用实数编码,一条染色体由两条子染色体组成,染色体结构如图5所示。

以5 个待堆存作业的集装箱为例,子染色体1表示出口箱堆存的具体箱位,由贝位号、栈号和层号组成。子染色体2表示双场桥作业集装箱任务的顺序。

海侧和陆侧场桥分别编码为ARMG1和ARMG2,均从箱区两端交换区,即第0贝位和第N_B+1贝位出发,贝位号由海侧向陆侧递增。外集卡运送的任务箱在陆侧交换区等待,由双场桥接力堆存至海侧箱区,两台场桥保持一致的作业顺序执行任务的主作业和接力作业。对于两条子染色体通过解码以获取集装箱目标位置和场桥作业顺序信息,需模拟出口箱集港过程。首先获取箱区初始状态及集装箱重量级、目的港属性,用于后续按“远压近”“重压轻”规则计算翻箱量;其次检验随机生成的出口箱目标箱位合法性,避免箱位悬空或占用无效位置;随后为每个集装箱任务确定最优动态接力区位置并验证其暂存箱位合法性;接着双场桥按作业顺序依次处理任务,全程保持安全距离;最终记录场桥完工时间和翻箱次数,完成解码。

2.2 种群初始化

算法迭代前,通过随机策略生成规模为popsize的初始种群,提供初始调度方案。其中,目标箱位在海侧箱区内随机确定:先选一个满足翻箱容量限制且有空间的贝位,再在该贝位内选一个不超过最高堆存层数的栈,最后取其最底层箱位,保证箱位不悬空。场桥作业顺序也随机生成,确保完成所有任务。

2.3 交叉与变异

2.3.1 交叉操作

染色体由出口箱堆存箱位和场桥作业顺序两部分组成。对于携带场桥作业集装箱顺序信息的子染色体,由于顺序不能重复,采用部分匹配交叉(partially mapped crossover,PMX)。通过互换两个染色体中的基因片段,产生新个体,拓展调度方案。具体的交换流程如下。

步骤1 在两个父代染色体对应位置中随机选择两个交叉点,将父代1交叉区间内的基因值复制到子代2中,父代2交叉区间内的基因值复制到子代1中。

步骤2 在两个父代交叉区间建立映射关系,根据映射关系,分别对子代非交叉区域上重复基因值进行替换,直到子代非交叉区间中不存在重复的基因值。

步骤3 将剩余的没有被选择的部分从父代2复制到子代中。不断重复交换流程,直到生产满足数量要求的子代个体。

以图6所示的两条父代染色体为例,介绍基于PMX的场桥作业顺序的交叉过程。当子代1的非交叉区域基因值3与交叉区间内的基因值3重复时,由于作业顺序唯一性的限制,需要在父代1中找到交叉区间内基因值3对应的映射值,即基因4,将该映射值替换子代1非交叉区域的重复基因值3。采用相同的映射规则对子代2进行处理,直到子代染色中表示场桥作业顺序的基因值不再重复。

对于携带目标箱位信息的子染色体,不进行交叉操作,重新随机生成一个可行解,替换染色体中原本携带的目标箱位信息的基因。一方面,箱位在生成时需要满足合法性约束,交叉操作可能导致生成违反该约束的无效解。另一方面,箱位的解空间规模较大,交叉操作可能生成大量无效或重复的解,因此,综合考虑两方面后,对箱位采用重新生成新的可行解的处理方式。

2.3.2 变异操作

变异操作是通过一定的扰动对基因进行变化,以提高种群的多样性,增强算法的搜索能力,避免早熟收敛。与交叉作业相似,仅对场桥作业序列采用交换策略进行变异,在箱位的处理上选择重新生成一个可行解的方式。具体的场桥作业顺序变异操作如图7所示。在表示场桥作业顺序的子染色体中随机选择两个点,交换变异点处的基因值。

2.4 变邻域搜索策略

尽管通过交叉、变异的操作扩大了种群的多样性,但由于解空间的随机探索,算法可能会陷入局部最优的情况。因此,为了增强NSGA-Ⅱ算法的局部搜索能力,在NSGA-Ⅱ算法的基础上,引入VNS算法,在常用的扰动规则中选择3 种,设计不同的邻域搜索结构,对当前染色体中的基因位的值进行改变,在扩大局部搜索范围的同时,避免算法陷入局部最优。

2.4.1 交换邻域(Swap)算子

在染色体中随机选择两个基因点并互换基因值,形成新的基因序列。Swap操作过程如图8所示。

2.4.2 插入(Insert)算子

在染色体中随机选择两个不同的基因位置,规定位置b位于位置a后,移除位置a处的基因值,并将其插入在位置b之前形成新的基因序列。Insert算子操作过程如图9所示。

2.4.3 逆序(Reverse)算子

在染色体中随机选择两个不同的基因位置,反转这两个基因位值点之间的基因片段,形成新的基因序列。Reverse算子操作过程如图10所示。混合NSGA-Ⅱ变邻域搜索算法伪代码如表1所示。

3 算例分析

针对垂岸式布局的自动化集装箱码头堆场单箱区,规模为42贝×10栈×6层,考虑同贝翻箱需预留空位,单贝最大容量为55 TEU。配备两台同型号无悬臂场桥ARMG1和ARMG2的初始贝位分别为第0贝和第41贝,安全间距2贝位。场桥移动1贝位耗时1.7 s,提/放箱作业耗时10 s。实验处理50 个出口箱(表2),初始箱区占用率50%,接力区占用率80%。混合NSGA-Ⅱ变邻域算法参数设置为:交叉概率P_c=0.9,变异概率P_m=0.1,种群规模100,最大迭代200 次;为减少随机误差,各实验重复10 次并取均值。

3.1 小规模算例分析

为了验证模型正确性,使用CPLEX求解器与混合NSGA-Ⅱ变邻域算法对小规模算例进行求解。CPLEX允许的求解时间上限为7 200 s。初始将接力区设置在箱区中部的第1921贝,对比结果如表3所示。考虑到箱区规模较大,而小规模算例中处理的出口集装箱数量较少,集装箱在箱区中可分散堆存,在混合算法与CPLEX中能将翻箱数量优化至0,因此只讨论场桥完工时间目标的对比。

由表3可知,处理5 个出口箱任务时,CPLEX与混合算法在目标函数上的差值GAP₁为0.85%,混合算法在目标值上与精确解误差较小且求解时间稍快,表明混合算法具有有效性。当集港箱任务规模扩大至20 个时,混合算法在求解效率方面更具优势,且求得的场桥完工时间与精确解的误差为2.90%,处于可接受的误差范围内,能获得近似最优解。处理25 个出口集装箱任务时,CPLEX求解时间超出设定上限,无法求得精确解,混合算法的优势不断凸显。综上所述,随箱区规模扩大及出口箱作业任务的增加,虽然混合算法求得的场桥完工时间相较于精确解的误差有所增大,但求得了近似最优解。因此,混合NSGA-Ⅱ变邻域算法更适用于求解大规模算例下的出口箱箱位分配与场桥调度协同优化问题。

3.2 最佳动态接力区域分析

采用Python语言进行编程,为验证不同接力区域位置对场桥完工时间和翻箱量的影响,在40贝位箱区中:固定模式接力点设于中间20贝;动态模式则将接力点扩展为柔性连续贝位区间。分别测试3个区间:海侧(1719贝)、中部(1921贝)和陆侧(2123贝)在50 个出口箱的作业场景下表现,对比结果如表4所示。

从表4可知,基于接力作业与场桥避让策略下,陆侧箱区的2123贝作为接力贝时,在100、150和200 三种箱量规模下均实现了场桥作业完工时间最短和翻箱量最少的结果。因此,选择2123贝作为协同调度模型下的场桥作业接力贝位。

运行算法得到详细出口箱箱位分配方案与相应场桥调度优化结果,如表5所示。

根据求解的箱位分配和场桥调度方案,可得到双场桥在调度方案下的行走路径图如图11所示。由图可看出双场桥路径不相交,说明求解满足了场桥安全距离的约束,对作业任务的干扰进行了良好的处理,在避免了场桥之间的碰撞与干扰的同时有效减少了意外事故的发生。

该调度方案下的Pareto前沿如图12所示。帕累托前沿呈非线性递减趋势,证明场桥作业时间与翻箱量存在冲突:作业时间增加,翻箱量减少,但需权衡时间成本。在4 3604 370 s区间,前沿斜率大,适合大批量集港。在4 3704 380 s区间,翻箱量降至约3次,优化趋缓,适合效率与翻箱兼顾。超过4 380 s,翻箱量达1或2 次,继续优化成本过高,仅适合精细化作业。鉴于各方案时间接近,而每增加一次翻箱需付出更高成本,因此选择将翻箱量优化至1次。

3.3 动态接力模式有效性验证

设计5 组不同箱量规模的实验用以证明动态接力模式的有效性。出口集装箱数量分别为15、30、50、80和100,对固定接力模式与动态接力模式进行求解分析。固定接力模式选定箱区中间贝位即20贝为接力贝位,动态接力模式选定2123贝作为接力区域。对比结果见图13,动态接力模式在完工时间和翻箱量指标上均优于固定接力模式,且集装箱任务量越大优势越显著,有效减少后续装船翻箱数,节约作业资源、提高箱位利用率和堆场整体效率。

3.4 改进前后算法性能验证

通过5 组不同出口箱数量规模的实验,对比改进前后的NSGA-Ⅱ算法性能,实验过程中对比算法的参数设置保持一致,对比结果如图14所示。结果表明,随着处理集装箱任务数的增加,设计的NSGA-Ⅱ变邻域算法求解得场桥完工时间较传统NSGA-Ⅱ算法优化了4.4%10.9%。翻箱量指标上也优于传统NSGA-Ⅱ算法。因此,VNS的扰动策略优化了NSGA-Ⅱ的性能表现,得到更优解。

3.5 混合NSGA-Ⅱ变邻域算法参数验证

为评估交叉概率P_c和变异概率P_m对混合NSGA-Ⅱ变邻域算法性能的影响,设计50 个出口箱任务的参数实验,设定交叉率在0.60.9范围内,变异率在0.10.4范围内,求解结果如表6所示。由表可知,优先考虑场桥完工时间指标最短时,P_c=0.8、P_m=0.1的参数组合最优;优先考虑翻箱量最少时,P_c=0.9、P_m=0.1的参数组合最优。相较而言,在这两组参数组合下的混合算法具备更好的性能表现。在P_c=0.8、P_m=0.1的参数组合下,每次实验做10组,重复20次实验,离散系数均值为0.361%,实验结果的稳定性较高。

4 结论

针对出口箱箱位分配与双场桥调度协同优化问题,以垂岸式布局的自动化集装箱码头为研究对象,在双场桥动态接力作业模式下,以最小化场桥最大完工时间与最小化翻箱量为目标构建多目标优化数学模型,设计了混合NSGA-Ⅱ变邻域算法进行模型求解,得出如下结论。

(1)协同优化数学模型构建:基于双场桥动态接力模式,考虑相关约束条件,将最小化翻箱量和最小化场桥最大完工时间作为优化目标,建立了协同优化问题的多目标数学模型。

(2)混合NSGA-Ⅱ与VNS的智能算法设计:在NSGA-Ⅱ算法基本框架上引入VNS对其进行改进,使得混合算法既保留了良好的全局搜索能力,又增强了局部搜索能力,提高算法性能表现。突破了双场桥接力模式下较多转为单目标求解的局限。

(3)算例实验与结果分析:通过CPLEX求解证明了模型有效性的同时,也证明了混合算法更适用于求解大规模算例。以场桥作业完工时间为例,混合算法较传统NSGA-Ⅱ算法优化了4.4%10.9%,验证了改进算法的有效性。

综上所述,研究基于混合NSGA-Ⅱ变邻域搜索算法对出口箱箱位分配及场桥作业序列进行协同优化。研究成果的工程效益显著,可集成于上海港洋山四期、青岛港前湾四期等典型纵向布局自动化集装箱码头的生产运营系统中,形成箱位分配智能模块,在统筹未来翻箱需求与场桥作业效率的基础上,实现对出口箱的智能箱位分配,有效提升堆场整体作业效率。未来可进一步考虑外集卡送箱时间不确定性、多箱区以及进出口箱混堆的情况对箱位分配与场桥调度协同优化的影响。

参考文献

原文顺序 | 出版日期 | 本文引用

[1]	计明军, 郭旭, 郝柏懿, 等. 集装箱码头起重机数字化转型综述:自动化升级与智能化改造[J]. 科学技术与工程, 2025, 25(23): 9672-9685.

[2]	Ji Mingjun, Guo Xu, Hao Baiyi, et al. Review of digital transformation of container terminal cranes: automation upgrade and intelligence transformation[J]. Science Technology and Engineering, 2025, 25(23): 9672-9685.

[3]	余明珠, 梁卓斌, 金波. 基于仿真优化的自动化集装箱码头出口箱箱位分配[J]. 运筹与管理, 2023, 32(5): 181-189.

[4]	Yu Mingzhu, Liang Zhuobin, Jin Bo. Storage space allocation for outbound containers in automated container terminals using simulation-based optimization[J]. Operations Research and Management Science, 2023, 32(5): 181-189.

[5]	李隋凯, 励益韬, 孙未未, 等. 一种自动化集装箱码头出口箱进箱选位算法[J]. 计算机工程, 2019, 45(5): 272-278, 284.

[6]	Li Suikai, Li Yitao, Sun Weiwei, et al. A storage space allocation algorithm for export containers in automated container terminals[J]. Computer Engineering, 2019, 45(5): 272-278, 284.

[7]	Yu H, Huang M, Zhang L, et al. Yard template generation for automated container terminal based on bay sharing strategy[J]. Annals of Operations Research, 2024, 343(3): 1157-1175.

[8]	罗浩铭, 冷松乐, 张先燏. 基于混合遗传算法的自动化港口箱位指派研究[J]. 港口航道与近海工程, 2025, 62(1): 6-11.

[9]	Luo Haoming, Leng Songle, Zhang Xianyu. Study on container slot allocation in an automated terminal based on hybrid genetic algorithm[J]. Port Engineering Technology, 2025, 62(1): 6-11.

[10]	Park H J, Cho S W, Nanda A, et al. Data-driven dynamic stacking strategy for export containers in container terminals[J]. Flexible Services and Manufacturing Journal, 2023, 35(1): 170-195.

[11]	尹延冬, 靳志宏. 集装箱码头失约集卡出口箱落箱位选择优化[J]. 科学技术与工程, 2021, 21(25): 10956-10966.

[12]	Yin Yandong, Jin Zhihong. Optimization of slot selection of export containers under truck no-showing situation in a container terminal[J]. Science Technology and Engineering, 2021, 21(25): 10956-10966.

[13]	任刚, 靳志宏, 庞毛毛, 等. 基于班列抵港模式的海铁联运堆场箱位分配优化[J]. 大连海事大学学报, 2022, 48(1): 1-10.

[14]	Ren Gang, Jin Zhihong, Pang Maomao, et al. Container space allocation optimization in sea-rail intermodal transportation based on train arrival mode[J]. Journal of Dalian Maritime University, 2022, 48(1): 1-10.

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

[16]	Huang Zizhao, Zhuang Zilong, Teng Hao, et al. Optimization of outbound container space assignment in automated container terminals based on hyper-heuristic algorithm[J]. Computer Integrated Manufacturing Systems, 2022, 28(8): 2619-2632.

[17]	Ambrosino D, Xie H. Optimization approaches for defining storage strategies in maritime container terminals[J]. Soft Computing, 2023, 27(7): 4125-4137.

[18]	曹梦洁, 苌道方, 温富荣, 等. 考虑装船效率的U型自动化码头出口箱箱位分配[J]. 科学技术与工程, 2025, 25(17): 7380-7389.

[19]	Cao Mengjie, Chang Daofang, Wen Furong, et al. Considering the loading efficiency of the storage space allocation of export container in U-shaped automated terminal[J]. Science Technology and Engineering, 2025, 25(17): 7380-7389.

[20]	于蒙, 许珍丽, 谭天姣. 基于SAGA算法的双40英尺场桥作业调度优化及比较分析[J]. 系统仿真学报, 2022, 34(8): 1885-1898.

[21]	Yu Meng, Xu Zhenli, Tan Tianjiao. Scheduling optimization and comparative analysis of twin 40 feet yard crane based on SAGA[J]. Journal of System Simulation, 2022, 34(8): 1885-1898.

[22]	Zheng F, Man X, Chu F, et al. Two yard crane scheduling with dynamic processing time and interference[J]. IEEE Transactions on Intelligent Transportation Systems, 2018, 19(12): 3775-3784.

[23]	Eilken A. A decomposition-based approach to the scheduling of identical automated yard cranes at container terminals[J]. Journal of Scheduling, 2019, 22(5): 517-541.

[24]	Nossack J, Briskorn D, Pesch E. Container dispatching and conflict-free yard crane routing in an automated container terminal[J]. Transportation Science, 2018, 52(5): 1059-1076.

[25]	Lu H, Wang S. A study on multi-ASC scheduling method of automated container terminals based on graph theory[J]. Computers & Industrial Engineering, 2019, 129: 404-416.

[26]	Jin X, Mi N, Song W, et al. Deep reinforcement learning for dynamic twin automated stacking cranes scheduling problem[J]. Electronics, 2023, 12(15): 3288-3309.

[27]	范厚明, 马晓斌, 彭文豪, 等. 送箱集卡失约下多箱区箱位分配及场桥调度优化[J]. 上海交通大学学报, 2023, 57(10): 1261-1272.

[28]	Fan Houming, Ma Xiaobin, Peng Wenhao, et al. Container allocation in multi-blocks and optimization of yard crane dispatching in non-engagement of container delivery truck[J]. Journal of Shanghai Jiao Tong University, 2023, 57(10): 1261-1272.

[29]	Jiang X J, Jin J G. A branch-and-price method for integrated yard crane deployment and container allocation in transshipment yards[J]. Transportation Research Part B: Methodological, 2017, 98:62-75.

[30]	邱亚, 梁承姬, 张悦. 动态接力点模式下双自动化轨道吊协调调度[J]. 上海海事大学学报, 2020, 41(3): 53-59.

[31]	Qiu Ya, Liang Chengji, Zhang Yue. Coordination scheduling of twin automated stacking cranes under dynamic relay point mode[J]. Journal of Shanghai Maritime University, 2020, 41(3): 53-59.

[32]	Kress D, Dornseifer J, Jaehn F. An exact solution approach for scheduling cooperative gantry cranes[J]. European Journal of Operational Research, 2019, 273(1): 82-101.

[33]	Dong L, Wang W, Dong F. Optimization of container allocation and dual-crane scheduling in terminal yard based on improved genetic algorithm[C]//11th International Symposium on Project Management (ISPM2023). New York: ISPM, 2023: 1179-1189.

[34]	Fan H, Peng W, Ma M, et al. Storage space allocation and twin automated stacking cranes scheduling in automated container terminals[J]. IEEE Transactions on Intelligent Transportation Systems, 2021, 23(9): 14336-14348.

PDF (7289KB)

访问

被引

详细

导航

Received	Published	Revised
2025-07-10	2026-05-18	2025-12-18
Online Date
2026-08-06

摘要