随着经济全球化的不断深入, 我国的进出口贸易不断增长, 随之带来港口集装箱吞吐量的急剧增长, 尤其在上海、广州、重庆等这样的大港, 业务量更是几年前的好几倍.然而由于整体规划以及资金的考量, 集装箱堆场码头的面积和工作区域并没有明显的扩大.如何在有限的条件下提高码头的运作效率, 便成为了当务之急.

在过去十几年, 集装箱吞吐量并不大的时候, 码头多采用轮胎式龙门机作为调运集装箱的起重机.该起重机起重量、跨距均较小, 移动速度快, 方便灵活, 很适合中小码头的运作.随着科技的发展以及集装箱吞吐量的增长, 轮胎式龙门机的弊端也显现出来:无法满足大贝位垛堆集装箱的移动, 运行成本、维修成本较高, 轨道式龙门机应运而生.比起轮胎式龙门机跨中只能堆放6列集装箱, 轨道式龙门机场地利用率更高, 跨中一般可堆放8-15列集装箱.因此越来越多的码头开始采用该起重机作为调运集装箱的工具.

为了提高码头的运作效率, 除了采用更为先进的设备外, 减少提箱过程中集装箱倒箱次数也是一个重要的因素.在集装箱堆场中, 竖直摆放的一列集装箱叫作一个栈, 并排摆放的几列栈称为一个贝.若将要提出发箱的集装箱不在栈的最高层, 必须先把积压在其上的所有集装箱移动到其他栈, 此移动的过程称为倒箱.许多实例表明, 贝位内集装箱数量越多, 倒箱就越多.倒箱给提取集装箱装船带来了很多不必要的工作, 浪费了大量的时间和金钱精力.为了解决这一困扰码头工作人员许久的难题, 不少学者开始研究它.

1997年Kim^[1]提出倒箱量估计方法, 研究了码头进口箱区堆存高度与倒箱量之间的关系, 并针对不同进口箱到达模式, 建立了最小化期望倒箱量为目标的数学模型; 2006年Kim和Hong^[2]利用分支定界和启发式算法研究了提箱过程中翻到集装箱落箱位置的确定问题; 范磊^[3]建立了轮胎式龙门机取箱作业数学模型, 基于6条倒箱落位原则, 以倒箱量最少为目标, 运用启发式算法对模型进行求解; 徐亚^[4]对阻塞箱落箱位置的确定问题以及如何减少二次倒箱进行了研究, 提出了一种启发式算法H及其改进算法IH; 金鹏^[5]以最小化翻箱总次数为优化目标, 运用多人爬山算法进行求解.

本文研究了贝位内的取箱作业问题, 给每一个箱子赋予一个优先级别, 数字越小的集装箱越优先被提取出贝位.在设计启发式算法步骤时, 创新地引入阻塞箱与栈内优先级最高的箱子的差的绝对值这一概念, 并且将空栈单独列出作为考量.通过大规模算例验证, 算法具有较好的可行解和时效性.

贝位的初始状态和各集装箱的发箱顺序已知, 数字越小说明发箱优先级越高, 如顺序为1的集装箱是最先发箱的.问题转化为按照各箱子发箱的优先级别依次取箱, 如何使得整个发箱过程倒箱量最少.

根据文献[8]中所提到的重庆寸滩港每一个贝位有20栈(2栈作为倒箱缓冲, 实际装箱为18栈), 5层, 因此本文算例为20栈, 6层, 稍大于实际规模.贝位初始状态见表 1, 其中数字表示集装箱发箱顺序.

(1) 贝位初始状态和集装箱发箱顺序已知;

(2) 倒箱过程只在一个贝位内进行, 且仅对待提箱上方的阻塞箱进行倒箱操作;

(3) 不允许有新的集装箱进入贝位;

(4) 层数为 $m$时, 贝位内至少有 $m-1$个空位留作倒箱使用.

$(i, j)$:贝内第 $i$层第 $j$栈箱位, $i=1, 2, \cdots, m;j=1, 2, \cdots, n$, 贝位由 $m$层 $n$栈的集装箱组成, 最上层为第1层, 最左栈为第1栈, 以此类推; $B_{m\times n}$:箱子优先级矩阵.矩阵中各元素代表该位置上箱子被取出的优先级, 特别地, 0元素表示空位; $b(k, i, j)$:第 $k$次搬移箱子前, 位于贝内第 $i$层和第 $j$栈的箱子的优先级, $k=1, 2, \cdots, K;i=1, 2, \cdots, m;j=1, 2, \cdots, n$. $b(k, i, j)=0$表示空位;

$ \begin{eqnarray*} &&p(k, i, j)=\left\{ \begin{aligned} &1, ~~\mbox{若第k 次搬移时某个箱子被放入到第i 层第j 栈}, \\ &0, ~~\mbox{否则}; \end{aligned} \right.\\ &&t(k, i, j)=\left\{ \begin{aligned} &1, ~~\mbox{若第k 次搬移时第i 层第j 栈的箱子被提出发箱}, \\ &0, ~~\mbox{否则}. \end{aligned} \right. \end{eqnarray*} $

$ \begin{eqnarray*} F=\min{\sum\limits_{k=1}^K \sum\limits_{i=1}^m \sum\limits_{j=1}^n p(k, i, j)}. \end{eqnarray*} $

(3.1)

式(3.1) 表示倒箱数量最少.

$ \left\{ {\begin{array}{*{20}{c}} \begin{array}{l} \sum\limits_{i = 1}^m {\sum\limits_{j = 1}^n p } (k, i, j) + \sum\limits_{i = 1}^m {\sum\limits_{j = 1}^n t } (k, i, j) = 1, k = 1, 2, \cdots, K, \\ {\text{如果}}b(k, i - 1, j) = 0{\text{& }}b(k, i, j) \ne 0, {\text{则}}p(k, i - 1, j) \le 1, \\ i = 2, \cdots, m;j = 1, \cdots, n;k = 1, \cdots, K, \\ {\text{如果}}b(k, i - 1, j) = 0{\text{& }}b(k, i, j) \ne 0, {\text{则}}t(k, i, j) \le 1, \\ i = 2, \cdots, m;j = 1, \cdots, n;k = 1, \cdots, K, \\ \sum\limits_{k = 1}^K {\sum\limits_{i = 1}^m {\sum\limits_{j = 1}^n p } } (k, i, j) + \sum\limits_{k = 1}^K {\sum\limits_{i = 1}^m {\sum\limits_{j = 1}^n = } } K, k = 1, 2, \cdots, K, \\ b(K + 1, i, j) = 0, i = 1, 2, \cdots, m;j = 1, 2, \cdots, n, \\ p(k, i, j) = 0{\text{或}}1;t(k, i, j) = 0{\text{或}}1, \\ i = 2, \cdots, m;j = 1, \cdots, n;k = 1, \cdots, K. \end{array} & {\begin{array}{*{20}{c}} {\left( {3.2} \right)}\\ {}\\ {\left( {3.3} \right)}\\ {}\\ {\left( {3.4} \right)}\\ {}\\ {\left( {3.5} \right)}\\ {\left( {3.6} \right)}\\ {\begin{array}{*{20}{c}} {\left( {3.7} \right)} \end{array}} \end{array}} \end{array}} \right. $

式(3.2) 表示每次搬移, 仅有一个箱子被移动, 要么一个箱子被提出, 要么一个箱子被放入; 式(3.3) 表示第 $k$次搬移前箱位 $(i, j)$上有箱子而 $(i-1, j)$上无箱子, 第 $k$次才可能将箱子搬移到 $(i-1, j)$; 式(3.4) 表示第 $k$次搬移前箱位 $(i, j)$上有箱子而 $(i-1, j)$上无箱子, 第 $k$次才可能将 $(i, j)$箱位的箱子提出发箱; 式(3.5) 表示箱子搬移总次数为 $K$; 式(3.6) 表示所有箱子均被发箱; 式(3.7) 表示变量属性.

步骤1  挑选其余栈中未到额定层数的空箱位作为翻出阻塞箱的堆存箱位.

步骤2  步骤1成立时, 若空箱位所在栈内现有箱子优先级比预移入阻塞箱的都低, 则该空箱位可作为翻出箱的堆存箱位.若这样的空箱位不唯一, 则计算阻塞箱与栈内优先级最高的箱子的差的绝对值, 选取绝对值最小的那一栈的空箱位作为翻出箱的堆存箱位.

步骤3  步骤1成立但步骤2不成立时, 若空箱位所在栈内优先级最高的箱子上方无阻塞箱, 则该空箱位为翻出箱的堆存箱位.若这样的空箱位不唯一, 则计算阻塞箱与栈内优先级最高的箱子的差的绝对值, 选取绝对值最小的那一栈的空箱位作为翻出箱的堆存箱位.

步骤4  步骤1成立但步骤2和3不成立时, 若空箱位所在栈内优先级最高的箱子上方只有1个阻塞箱, 则该空箱位为翻出箱的堆存箱位.若这样的空箱位不唯一, 则计算阻塞箱与栈内优先级最高的箱子的差的绝对值, 选取绝对值最小的那一栈的空箱位作为翻出箱的堆存箱位.

步骤5  只有步骤1成立时, 若空箱位所在栈内优先级最高的箱子上方有2个阻塞箱, 则该空箱位为翻出箱的堆存箱位.若这样的空箱位不唯一, 则计算阻塞箱与栈内优先级最高的箱子的差的绝对值, 选取绝对值最小的那一栈的空箱位作为翻出箱的堆存箱位.

步骤6  只有步骤1成立时, 若空箱位所在栈内优先级最高的箱子上方有3个阻塞箱, 则该空箱位为翻出箱的堆存箱位.若这样的空箱位不唯一, 则计算阻塞箱与栈内优先级最高的箱子的差的绝对值, 选取绝对值最小的那一栈的空箱位作为翻出箱的堆存箱位.

步骤7  只有步骤1成立时, 若空箱位所在栈内优先级最高的箱子上方有4个阻塞箱, 则该空箱位为翻出箱的堆存箱位.若这样的空箱位不唯一, 则计算阻塞箱与栈内优先级最高的箱子的差的绝对值, 选取绝对值最小的那一栈的空箱位作为翻出箱的堆存箱位.

对于空栈的处理:在执行上述任何一步时, 若出现空栈, 则选定目前非空栈中最上层箱子优先级最低的那一个.若该箱子不是该栈优先级最高的, 则将其移入空栈中, 再继续执行上述7个步骤; 否则, 把将要移动的阻塞箱放入空栈中, 再继续执行上述7个步骤.

运用上述启发式算法, 根据表 1的初始贝位状态, 对该20栈、6层的较大规模的集装箱堆场进行倒箱操作, 可以得到倒箱优化方案, 见表 2.

总倒箱次数为77, 算法耗时0.037s.为了进一步验证上述启发式算法的高效性, 对文献[3]中的算例进行计算, 贝位初始状态见表 3, 计算结果见表 4.

总倒箱次数为11, 与文献[3]结果一样, 但是系统记录运行时间为0.018s, 比文献[3]的0.094s快了几倍, 因此本文的启发式算法耗时更短, 时效性更好.

本文以轨道式龙门机在贝位内取箱作业过程中倒箱量最少为目标, 建立了取箱作业的数学模型, 运用MATLAB编译的启发式算法对模型进行求解.相比于同类文章只研究了小规模的集装箱倒箱问题, 本文研究的是20栈、6层的大规模问题, 更加贴近实际, 具有较好的现实意义; 单独将空栈拿出来考虑, 有利于减少二次、三次倒箱数量, 对于减少总倒箱量有很大帮助; 针对启发式算法步骤中出现候选栈不唯一的情况, 本文多增加了一个约束条件, 从而确保候选栈的唯一性, 大大减少了运算量和随机性.本文通过两个规模不同的算例对算法进行了验证, 均给出了具体的倒箱较优方案.算例1的结果对于生产实际中大港口的取箱作业有较好的帮助, 算例2的结果表明本文算法在时间上具有很大优势.事实上, 由于假设2的存在, 集装箱倒箱实际上是一个NP-hard问题, 本文提出的启发式算法属于贪心算法范畴, 求得的解可能不是全局最优解, 下一步的研究重点将放到非限制变量上.