基于贪婪禁忌搜索算法的垂岸式堆场出口箱装船翻箱研究

张艳伟, 姜旎旎, 计三有

(1.武汉理工大学 交通与物流工程学院,湖北 武汉 430063; 2.港口物流技术与装备教育部工程研究中心,湖北 武汉 430063)

0 引言

堆场作业效率是码头作业效率的重要保障，堆场翻箱是当前相关研究的重要热点。通常出口集装箱在船舶到港前一个时段内提前集港，由于出口箱堆存计划受船舶配载信息不确定性影响、出口箱陆续到达堆场的时间点和先后顺序具有不确定性等，很难保证出口箱集港堆存状态完全满足后续装船顺序要求，装船时出口箱堆场翻箱无法避免，是制约堆场作业效率的重要瓶颈。

早期研究学者主要考虑顺岸式码头堆场单贝位限制翻箱问题，不涉及场桥大车移动，以翻箱次数衡量装船时场桥作业效率，利用分支界定、波束搜索、动态规划等算法进行求解。随着单贝位翻箱问题研究日渐成熟，目前非限制翻箱问题成为研究重心。Caserta[1]等证明了集装箱翻箱问题属于NP难问题，提出了非限制和限制翻箱两种数学模型。Expósito等[2]针对限制和非限制集装箱翻箱问题提出了best-first A*算法求解小算例，设计了一种基于领域特定知识的启发式算法近似求解提高计算效率。Zehendner等[3]改进了前人提出的集装箱翻箱模型[1]，提出每个周期中翻箱数量新上界和预处理步骤，将模型中变量数减少65%以上。Expósito等[4]设计了一种基于智能策略的分支定界算法，通过探索底层树中最有希望的节点对Caserta等[1]提出的模型进行求解。Tanaka等[5]提出一个新的翻箱次数下界，构建了效率更高的分支界定算法。Tanaka等[6]提出一种精确算法解决非限制翻箱问题，设计三种优势属性消除搜索树中不必要节点，改进了分支界定下界。Tricoire等[7]引入新的分支界定下界设计元启发式框架提高算法运行效率。Q. Zeng等[8]以最小化总翻箱数为目标，建立集装箱组内集装箱翻箱模型调整提箱顺序，提出五种启发式算法求解模型。B. G. Zweers等[9]针对预编组和翻箱问题设计一个最优分支界定算法，提出了一种基于规则的贝内集装箱移动次数估计方法。

综上所述，关于装船时翻箱问题研究，主要有数学模型构建、基于分支界定限定翻箱次数的上下界、挖掘启发式规则等。多数文献研究对象为顺岸式堆场单贝位装船翻箱问题，且对于场桥作业时间通常按操作次数衡量为定值，较少区分场桥大车行走、吊具平移和起升[10]。非限制翻箱启发式规则一般针对存在压箱现象的栈顶集装箱的多次翻箱。

不同于顺岸式码头水平搬运车辆进入堆场、场桥线边装卸，垂岸式码头堆场箱区和场桥大车轨道垂直于岸线布局，不同装船周期出口箱在海侧箱区多贝位混堆，场桥多贝位移动取箱，大车带箱行走至箱区端部对水平搬运车辆进行装卸，装船翻箱具有多贝位翻箱决策特征，问题规模大且需考虑大车移动路径对作业效率影响等。本文以垂岸式自动化码头堆场为研究对象，研究装船时堆场箱区多贝位翻箱问题，考虑场桥大车多贝位翻箱取箱行走、吊具贝内平移和起升时间，提出栈顶集装箱非必要翻箱规则，以场桥单箱平均操作时间最小为目标进行优化决策。与现有研究相比，具有以下显著特点：(1)考虑非必要翻箱对场桥作业时间和次数的影响；(2)设计的非必要翻箱启发式规则约束少。同时，对多贝位落箱位选择进行优化减少二次翻箱操作；(3)构建贪婪和禁忌两阶段算法进行求解，算例规模符合自动化码头生产实际。

1 垂岸式堆场出口箱装船翻箱模型

垂岸式堆场出口箱装船翻箱可以描述为堆场多贝位初始堆存状态和装船发箱顺序已知的情况下，优化场桥取箱、翻箱操作序列、同时在多个贝位内优化决策翻出集装箱的落箱位，在当前装船周期内以尽可能少的操作时间完成海侧箱区出口箱装船，同时控制单次取箱的最大翻箱次数和作业时间，保证装船作业的流畅性。图1为多贝位集装箱堆存状态示意图，包括当前拟装船箱和非当前拟装船箱，数字表示发箱顺序，灰度越深发箱顺序越靠前，经处理后每个发箱顺序对应一个集装箱。

图1 堆场贝位堆存状态及发箱顺序标识

1.1 模型假设条件

(1)集装箱均为20英尺箱，水平搬运设备数量充足，不考虑场桥等待时间；

(2)一次只考虑一个装船作业周期拟装船箱，且装船过程中无集港箱进入堆场；

(3)一个箱区配置一台场桥，不考虑满载和空载区别，场桥路径为曼哈顿距离。

1.2 符号说明

(1)集合

N为所有集装箱发箱顺序集合N=Npre∪Nnext，其中：Npre为当前拟装船箱发箱顺序集合，Nnext为非当前拟装船箱发箱顺序集合；B为贝位号集合；S为栈号集合；H为层号集合。

(2)参数

(3)变量

Anbshm是0-1变量，第m次操作发箱顺序为n的集装箱位于b贝s列h层时为1，否则为0；xnbshm是0-1变量，场桥第m次操作发箱顺序为n的集装箱落箱位是b贝s列h层时为1，否则为0，若为取箱操作，落箱到AGV上，令xn0s1m=1。

1.3 模型约束及目标函数

目标函数:

(λbb+λss)(|xnbshm+1-Anbshm+1|+|Anbshm+1-xnbshm|))

(1)

约束：

(2)

(3)

(4)

(5)

Anbshm+xnbshm<2,∀b∈B,s∈S,h∈H,n∈N

(6)

Anbshm+1=Anbshm(1-xnbmsmhmm),∀b∈B,s∈S,h∈H,n∈N

(7)

1≤Mt+1-Mt+1≤UBt+1,∀t∈Npre

(8)

(9)

目标函数式(1)表示当前装船周期场桥单箱平均操作时间最小。式(2)约束单个集装箱堆放箱位唯一，当前拟装船箱在M次操作内只会被取走一次。式(3)约束集装箱不可悬空。式(4)约束在当前装船周期，拟装船箱均会装船。式(5)约束当目标箱位于贝位最上层，直接取箱装船。式(6)约束拟落箱的箱位为空。式(7)表示集装箱箱位状态变化关系。式(8)限制提取目标箱时场桥最大操作次数。式(9)为堆场初始状态的堵塞率计算公式。

2 基于贪婪禁忌搜索算法模型求解

考虑对当前和非当前所有拟装船箱进行翻箱及取箱操作，设计贪婪算法完成必要翻箱决策求解，嵌套禁忌搜索算法执行局部非必要翻箱操作，以满足必要翻箱即时决策，减少当前水平搬运设备等待时间。当最小发箱顺序集装箱位于贝内堆栈顶部时直接提取，否则判断非必要翻箱次数是否达到上界，若超过上界，对目标箱上的堵塞箱建立移动箱位候选解集，选择评价函数最小的空箱位依次对堵塞箱进行翻箱操作；若未超过上界，根据非必要翻箱规则构建候选解集，从候选解集选择不在禁忌表内且优于历史最优解的解，并更新最优解和禁忌表，达到迭代次数时，更新非必要翻箱次数和评价函数，依次搜索所有当前拟装船箱，直到所有任务完成，输出操作序列和操作时间。

2.1 编码方式

集装箱装船发箱及翻箱决策旨在形成优化的装船时场桥翻箱和取箱操作序列。编码包括堆场箱位位置及箱位内集装箱的发箱顺序，如表1。其中：箱位位置用坐标(b,s,h)表示，b,s,h分别为箱位所在堆场贝位、贝位内栈和层，贝位为0时，表示集装箱落箱堆放到AGV上被装船；n表示箱位内集装箱的发箱顺序，空箱位对应的n为0。

2.2 评估函数与翻箱规则构建

禁忌搜索求解非必要翻箱操作采用式(10)对堆场布局的优劣进行评估，以扩大必要翻箱的解搜索空间。贪婪算法需要场桥在满足操作时间最短的情况下将目标箱的堵塞箱尽可能翻到不堵塞其余箱的列上，采用式(11)进行评估。

f=βgoodmgood+βemptymempty

(10)

其中，mgood，mempty分别表示能使所翻箱不堵塞其余箱的列数和箱区内空列数。βgood，βempty是各子目标的权重系数，取值范围为[0,1]，两者之和为1。

基于STM32的嵌入式远程视频监控系统设计………………………………马跃辉, 冀保峰, 程一淼,等(52)

(11)

f(c)=dif(n,b,s)×OP_Time

(12)

其中，式(11)评价落箱位对后续操作产生的影响，nminbs>n，发箱顺序为n的集装箱不会阻塞b贝s列的集装箱；nminbs

针对必要翻箱操作设计规则1，针对非必要翻箱操作设计规则2，落箱箱位的选择遵循贝内优先的原则，以便减少集装箱取箱时场桥的移动。

规则1目标箱位于最上层时直接取箱装船；当目标箱不在最上层且非必要翻箱次数达到上界时，将堵塞箱移动到离目标箱和堆场海侧最近的可用列上。

规则2目标箱不在最上层、非必要翻箱次数未达到上界，且箱区内存在堵塞箱时，选择目标箱最近且堵塞率最高的列顶部箱进行翻箱，落箱位选择离目标箱和堆场海侧最近的不堵塞其余箱的列；目标箱不在最上层、非必要翻箱次数未达到上界，且箱区不存在堵塞箱时，选择目标箱最近且集装箱最少的列顶部箱进行翻箱，落箱位选择离目标箱和堆场海侧最近的不堵塞其余箱的列。

表1 编码方式

2.3 禁忌表与终止条件设置

将待操作箱原箱位和拟移入箱位进行交换实现领域移动，是否执行交换决策受模型约束限制。领域集合由原箱位和空箱位组成，无阻塞箱或迭代次数达到最大时停止交换。禁忌对象(nm,b,s,h,bm,sm,hm)表示集装箱nm在预设迭代次数内不能被分配到箱位(b,s,h)和箱位(bm,nm,hm)。禁忌表为禁忌对象组成的队列，禁忌长度为问题规模的十分之一。

表2 TG算法与LL-Heuristric(LLH)算法求解结果对比

3 算例实验

3.1 算法有效性

为验证算法有效性，选用LL-Heuristric(LLH)算法[10]及算例与本文的TG算法进行对比。Lin[10]提出的启发式规则考虑了场桥大车行走、吊具起升和吊具平移的速度差异，未考虑非必要翻箱过程，落箱位选择基于最小化翻箱次数进行评估，目标函数为时间和操作次数的加权和。验证结果如表2所示，本文算法单箱平均耗时提升17.19%以上，单箱平均操作次数(含翻箱和取箱)较LLH算法多，但增值控制在8%以内。使用Python软件进行编程求解，普通笔记本电脑运算时间在15s以内，符合码头操作需求。

3.2 算法规则对比和适用性分析

垂岸式堆场多贝位非必要翻箱过程与堵塞率和非当前周期集装箱占比相关。结合垂岸式码头箱区实际大小，设定既定箱区为5贝6列2层、8贝10列5层两种规模，结合码头生产实际，堵塞率分别为5%、8%、11%、17%、20%，非当前周期集装箱占比为5%和10%。每种组合设计100个算例，共计2400个算例。组合规则为规则1、2的组合，包含非必要翻箱过程，规则1不包含非必要翻箱过程，通过与随机落箱规则对比验证非必要翻箱过程的合理性和适用性。场桥大车行走、吊具平移、吊具起升速度分别为1.2米/秒、1.7米/秒、0.7米/秒。非必要翻箱操作次数上界设为2次。计算结果如表3。

(1)非必要翻箱过程对必要翻箱过程的作用受箱区规模影响较小。在两种箱区规模情况下，组合规则和规则1单箱操作时间与单箱操作次数偏差在3%以内，说明非必要翻箱次数上界为2时，规则2对规则1影响不大，规则2具有合理性。

(2)利用本文的翻箱规则进行合理预整理能减少堆场装船翻箱操作时间和操作次数，并且随着堵塞率和堆场规模的上升，改进效果越明显。堆场布局为6列5贝2层时，翻箱操作时间改进比例范围为1%～9%，翻箱次数改进比例范围为0%～7%；堆场布局为8列10贝5层时，翻箱操作时间改进比例范围为17～23%，翻箱次数改进比例范围为21～26%。堵塞率相同情况下，随着下一周期集装箱占比减少，当前周期场桥装船操作时间和操作次数增加，算法适合于当前周期集装箱占比不同的堆场翻箱问题。

表3 两种规模情况下各种规则结果对比

4 结论

针对垂岸式集装箱码头出口箱装船堆场翻箱，考虑非必要翻箱对场桥作业时间和次数的影响，建立数学模型，提出翻箱规则，设计贪婪禁忌搜索算法，通过与LLH算法对比，验证模型和翻箱规则的有效性，结合堆场实际规模设计两种箱区规模算例，验证翻箱规则的适用性。结果表明适当的非必要翻箱能有效改善装船翻箱的箱区布局，减少场桥操作总时间，提高作业效率。由于场桥作业受水平搬运作业效率影响，下一步研究需要考虑场桥翻箱与水平搬运设备的协同，提出的翻箱规则需要在动态环境中进行测试。