随着集装箱运输需求的不断增长，越来越多港口为了提高堆场利用率和通过能力，开始在集装箱码头堆场采用进、出口箱混合存放模式，如釜山港、香港港、上海港等。进/出口箱同场区存放的混合模式可以充分利用堆场箱位，提高了堆场资源利用率和通过能力。但混合存放模式的作业管理复杂，龙门吊堆取箱作业容易相互干扰，龙门吊作业的箱位优选需要考虑相关堆取箱作业的协调以及干扰影响。

集装箱码头堆场龙门吊根据堆、取箱任务序列依次到作业点(箱位)执行作业，堆箱作业箱位点的选择影响龙门吊作业成本，混合存放作业下还将影响关联取箱作业等其他任务的执行。针对混合存放作业的堆场箱位选择问题研究主要有：Gambardella等利用线性混合整数规划为到港船舶配置岸桥、混合存放箱区及其龙门吊，减少设备冲突和等待时间，此研究未涉及箱区内的作业和压箱量优化^[1]。Zhang等针对混合存放箱区提出分配策略，并在此基础上构建了箱区分配模型^[2]，类似地，Bazzazi等提出了考虑按箱属性分组的箱区分配模型^[3]。康海贵等构建了混合存放箱区的进口箱位分配整数规划模型，优化拖车行驶距离和同组箱占用箱区数^[4]。陶经辉等将混合存放箱区分配问题分解为两阶段：阶段Ⅰ平衡箱区作业量和阶段Ⅱ平衡箱组，构建模型并进行了仿真对比分析^[5]。杨曼等以平衡箱区间作业量和最小化泊位到堆场的运距为目标建立了混合存放作业下箱区分配优化模型^[6]。郝聚民等基于图搜索和模式识别方法建立了随机条件下的混合存放作业贝位优选模型^[7]。郑红星等根据集装箱混合存放作业规则设定了集装箱优先级，以集装箱新增压箱数最小为目标，提出了箱位分配优化方法^[8]。考虑出口集装箱到港时间的不确定性，周鹏飞等提出了出口集装箱位分配的两级调度策略，建立了数学规划模型优化堆场起吊设备作业成本和翻箱量，并基于禁忌搜索开发了启发式算法^[9]。综上可看出：1) 现有混合存放作业堆场研究主要以平衡箱区作业量为目标，为进出口箱指定箱区或贝位，未考虑箱区内作业成本与翻箱量影响^[1-7]；2) 具体箱位优选问题研究考虑了堆箱优先级和箱重等因素，未考虑不确定干扰发生后的响应与处理以及混合存放作业下对关联作业的干扰影响^[8-9]。

混合存放模式的集装箱位优选主要依据堆场收发箱任务计划(客户的提箱和交箱任务)，客户任务容易发生干扰和偏差，造成实际作业成本上升，设备等待，甚至冲突等，因此混合存放模式堆场的箱位优选需建立有效的任务扰动恢复机制以降低干扰影响。干扰管理是由Clausen等提出的新兴管理方法^[10]，其核心思想是针对干扰事件，利用干扰管理模型和算法获得干扰恢复方案，以较小的成本应对干扰事件，近年来已在航班计划^[11]、设备调度^[12]等多个领域得到成功应用。针对集装箱码头生产管理领域的泊位分配和岸桥调度问题，曾庆成等^[13]、杨春霞等^[14]和林庆福等^[15]分别提出了干扰管理方法，实验分析显示了较好的调度性能。利用干扰管理的思想来处理堆场收发箱任务计划的扰动，优选干扰发生后箱位恢复方案可减少堆场作业的干扰成本。

本文将针对混合存放作业堆场的出口收箱作业的箱位优选问题，考虑进口提箱和翻箱作业的干扰影响，构建干扰管理模型，并针对模型特点开发禁忌搜索算法，提高堆场龙门吊作业的抗干扰能力。

1 干扰识别与度量

混合存放的集装箱区允许在同一时间内存放进口箱和出口箱，堆场龙门吊操作任务包括堆场收箱(堆放箱)、发箱(提取箱)以及堆场内的翻倒箱等。龙门吊作业任务的优先权不完全相同，比如临近船舶到港时出口集装箱的收箱作业(堆放箱)通常具有较高优先级，在其作业间隙允许发箱以及翻倒箱等。制定出口收箱作业计划时通常要考虑节约堆场龙门吊作业成本，减少装船时的翻倒箱等。如果客户交箱(码头收箱)次序确定，堆场出口收箱作业计划可转化为以客户交箱次序为已知条件，为计划进场的出口集装箱优选分配箱位的问题。客户交箱次序可利用客户预约或集卡位置信息进行估计，由于客户预约和集卡信息具有动态性，比如客户预约的取消或交通拥堵造成的延迟等，因此估计的交箱次序容易发生改变和干扰。如果交箱次序改变，而堆场作业仍按原计划执行，将造成龙门吊等待、作业成本增加、外集卡的服务时间窗延长等问题，同时也影响其他作业计划的执行，如提箱作业计划等。图 2是箱位计划(图 1所示)的作业干扰影响、重调度和干扰管理的示例。可以看出：箱4延迟和箱13提前，如果仍按原箱位分配方案执行将造成龙门吊大车移动增加4贝距离；如果采用重调度方法重新分配箱位，龙门吊大车的移动总距离为10贝；如果采用干扰管理方法，龙门吊大车的移动总距离为4贝，较重调度方法减少了6贝距离。

出口集装箱位优选问题的干扰事件主要原因是客户交箱预约的取消、交箱时间的延迟或提前等，上述干扰事件的单次影响较小但累积影响较大。考虑混合存放模式堆场的出口集装箱位优选问题特点，提出了基于堆场收箱次序偏移的干扰识别方法，来识别需要处理的干扰事件。堆场收箱次序如图 3所示，可选取干扰发生后收箱次序改变的总箱量作为偏移度量，表示为ΔN。对出口集装箱位优选问题来说，堆场收箱次序的关键是出口集装箱装船优选级属性的次序，因此收箱次序偏移度量也可用相应次序上的集装箱属性值的偏差总和来表示，即${D_1} = \sum\limits_\mu ^{N\prime } {\left| {{c_i}\prime - {c_i}} \right|} ,N\prime $是计划执行的总箱量，c_i和c′_i是干扰前、后第i个到港集装箱的装船优先级。

2 出口集装箱位优选干扰管理模型 2.1 模型假设

1) 进口集装箱和出口集装箱可在堆场的同贝位不同堆栈内存放，龙门吊按计划优先作业出口箱；

2) 干扰事件发生前的堆场作业计划(包括取箱、翻倒箱和收箱)和出口箱位分配方案已知。

3) 出口箱位分配引起的压箱量计算根据长途重箱优先装船原则计算：装船优先级c=d×w_max+w，w是箱重级别，d是目的港次序，w_max是最大箱重级别，c越大越早装船。

2.2 干扰恢复的关联成本度量

混合存放模式下出口集装箱位优选问题的干扰恢复目标考量包括龙门吊作业成本、压箱量、以及作业箱位调整引发的关联作业成本，后者与干扰箱的贝位有关，用干扰事件前后的贝位距离差度量，即：${B_{ia}} = \sum\limits_{i = 1}^{N\prime } {|{b_i} - {b_i}\prime |,} {b_i}、{b_i}\prime $是第i个到港集装箱分配的计划箱位和干扰恢复箱位所在的贝位。

2.3 模型构建

利用干扰管理思想构建干扰事件发生后的出口集装箱位分配计划的恢复模型。干扰关联成本表达式为$\sum\limits_{i = 1}^{N\prime } {|{b_i} - {b_i}\prime |} $。干扰恢复模型的目标函数可表示为

$ \begin{array}{l} \min \left\{ {{c_1}\sum\limits_{i = {N_1} + 1}^{{N_1} + {N_2}} {{R_i}} + {c_2}\left[ {\left| {\sum\limits_{k = 1}^B {k\left( {y_{{N_1} + 1}^k - b_{{N_1}}^k} \right)} } \right| + } \right.} \right.\\ \left. {\sum\limits_{i = {N_1} + 2}^{{N_1} + {N_2}} {\left| {\sum\limits_{k = 1}^B {k\left( {y_i^k - y_{i - 1}^k} \right)} } \right|} } \right] + {c_3}\sum\limits_{{N_1} + 1}^{{N_1} + {N_2}} {\left| {\sum\limits_{k = 1}^B {k \cdot y_i^k - {b_i}} } \right|} \end{array} $

(1)

式中：c₁、c₂和c₃分别是压箱成本、龙门吊大车移动成本，以及箱位偏移成本的单位值。目标函数中前两项为总压箱量和龙门吊总移动距离，$\sum\limits_{k = 1}^B {(k·y_i^k)} $)表示箱i的贝为k，$\left| {\sum\limits_{k = 1}^B k \cdot(y_i^k - y_{i - 1}^k)} \right|$表示相邻进场集装箱的贝位差，第三项为干扰恢复方案的关联影响成本。

约束可表示为

$ \begin{array}{*{20}{c}} {{x_{ij}} = {x_{ji}}\;\;\;i > j,\;\;i \in \left\{ {{N_1} + 1,} \right.\left. {{N_1} + 2, \cdots ,{N_1} + {N_2}} \right),}\\ {j \in \left\{ {1,2, \cdots ,{N_1} + {N_2}} \right\}} \end{array} $

(2)

$ \sum\limits_{j = 1,j \ne i}^{{N_1} + {N_2}} {{x_{ij}} \le T - 1} \;\;\;\;\;i \in \left\{ {{N_1} + 1,{N_1} + 2, \cdots ,{N_1} + {N_2}} \right\} $

(3)

$ \sum\limits_{j = 1,j \ne i}^{{N_1}} {{a_{ij}}} + \sum\limits_{j = {N_1} + 1,j \ne i}^{{N_1} + {N_2}} {{x_{ij}} \le T - 1} \;\;\;\;\;i \in \left\{ {1,2, \cdots ,{N_1}} \right\} $

(4)

$ \begin{array}{*{20}{c}} {{a_{ij}} + {x_{ih}} + {x_{jh}} \ne 2\;\;\;i < j < h\;\;\;\;i \in \left\{ {1,2, \cdots ,{N_1}} \right\}}\\ {h \in \left\{ {{N_1} + 1,{N_1} + 2, \cdots ,{N_1} + {N_2}} \right\}} \end{array} $

(5)

$ \begin{array}{*{20}{c}} {{x_{ih}} + {x_{jh}} + {x_{ij}} \ne 2\;\;\;i < j < h\;\;\;i \in \left\{ {1,2, \cdots ,{N_1} + {N_2}} \right\}}\\ {j,h \in \left\{ {{N_1} + 1,{N_1} + 2, \cdots ,{N_1} + {N_2}} \right\}} \end{array} $

(6)

$ \sum\limits_{k = 1}^B {y_i^k = 1} \;\;\;\;i \in \left\{ {{N_1} + 1,{N_1} + 2, \cdots ,{N_1} + {N_2}} \right\} $

(7)

$ \sum\limits_{i = 1}^{{N_1}} {b_i^k} + \sum\limits_{i = {N_1} + 1}^{{N_1} + {N_2}} {y_i^k} \le {V_k}\;\;\;k \in \left\{ {1,2, \cdots ,B} \right\} $

(8)

$ \begin{array}{*{20}{c}} {\sum\limits_{k = 1}^B {\left( {y_i^k \cdot y_j^k} \right) + \left( {1 - {x_{ij}}} \right)M} > 0\;\;i > j}\\ {i,j \in \left\{ {{N_1} + 1,{N_1} + 2, \cdots ,{N_1} + {N_2}} \right\}} \end{array} $

(9)

$ \begin{array}{*{20}{c}} {\sum\limits_{k = 1}^B {\left( {y_i^k \cdot b_j^k} \right) + \left( {1 - {x_{ij}}} \right)M} > 0\;\;\;j \in \left\{ {1,2, \cdots ,{N_1}} \right\}}\\ {i \in \left\{ {{N_1} + 1,{N_1} + 2, \cdots ,{N_1} + {N_2}} \right\}} \end{array} $

(10)

$ \left( {1 - {R_i}} \right)\sum\limits_{j \in {D_i}} {{x_{ij}} = 0} \;\;\;\;i \in \left\{ {{N_1} + 1,{N_1} + 2, \cdots ,{N_1} + {N_2}} \right\} $

(11)

$ \sum\limits_{j \in {D_i}} {{x_{ij}} - {R_i} \ge 0} \;\;\;\;i \in \left\{ {{N_1} + 1,{N_1} + 2, \cdots ,{N_1} + {N_2}} \right\} $

(12)

$ \begin{array}{*{20}{c}} {\sum\limits_{m = 1}^T {\left[ {\left( {\sum\limits_{k = 1}^{{N_1}} {\left( {h_i^m \cdot b_i^k} \right)} + \sum\limits_{i = {N_1} + 1}^{{N_1} + {N_2}} {\left( {h_i^m \cdot y_i^k} \right)} } \right)/m} \right]} \le S}\\ {k \in \left\{ {1,2, \cdots ,B} \right\}} \end{array} $

(13)

$ \sum\limits_{m = 1}^T {m \cdot h_i^m} = \sum\limits_{\begin{array}{*{20}{c}} {j = 1}\\ {j \ne i} \end{array}}^{{N_1} + {N_2}} {{x_{ij}} + 1} \;\;\;i \in \left\{ {{N_1} + 1,{N_1} + 2, \cdots ,{N_1} + {N_2}} \right\} $

(14)

$ \sum\limits_{m = 1}^T {m \cdot h_i^m} = \left( {1 + \sum\limits_{\begin{array}{*{20}{c}} {j = 1}\\ {j \ne i} \end{array}}^{{N_1}} {{a_{ij}}} } \right) + \sum\limits_{\begin{array}{*{20}{c}} {j = {N_1} + 1}\\ {j \ne i} \end{array}}^{{N_1} + {N_2}} {{x_{ij}}} \;\;\;i \in \left\{ {1,2, \cdots ,{N_1}} \right\} $

(15)

$ \sum\limits_{m = 1}^T {h_i^m} = 1\;\;\;\;i \in \left\{ {1,2, \cdots ,{N_1} + {N_2}} \right\} $

(16)

$ {R_i},h_i^m,{x_{ij}},y_i^k \in \left\{ {0,1} \right\} $

(17)

式中：N₁、N₂为干扰事件发生时已进场和计划进场的集装箱总量；B、S、T为混合存放箱区的总贝位数、列数和栈高；V_k为贝k的额定存放箱量；b_i为第i个进场的出口集装箱的贝位；D_i为同堆栈时，与箱i有压箱关系的集装箱集合；a_ij：=1，如果箱i和j同堆栈；=0，否则, i, j∈{1, 2, …N₁}；b_i^k：=1，如果箱i的贝为k；=0，否则, i∈{1, 2, …N₁}；R_i(中间变量)：=1，若箱i为压箱，即提箱时需翻倒；=0，否则；i∈{N₁+1, N₁+2, …N₁+N₂}；h_i^m(中间变量)：=1，若箱i所在堆栈有m个箱；=0，否则，i∈{1, 2, …N₁+N₂}, m∈{1, 2, …T}；x_ij(决策变量)：=1，若箱i和箱j被分配到同堆栈；=0，否则，i∈{N₁+1, N₁+2, …N₁+N₂}, j∈{1, 2, …N₁+N₂}或i∈{1, 2, …N₁}，j∈{N₁+1, N₁+2, …N₁N₂)；y_i^k+(决策变量)：=1，若箱i所分配贝为k；=0，否则，i∈{N₁+1, N₁+2, …N₁+N₂}。

约束(2) 要求集装箱i和j位置关系对称；约束(3) 与(4) 为集装箱堆垛高度约束；约束(5) 与(6) 要求两个集装箱位置具有传递关系；约束(7) 要求集装箱只能存放到单个贝；约束(8) 为贝内最大允许总箱量约束；约束(9) 与(10) 要求同栈箱一定位于同贝位；约束(11) 与(12) 为压箱关系约束，即：当$\sum\limits_{i \in D} {{x_{ij}}} = 0$时R_i=0，当$\sum\limits_{j \in D} {{x_{ij}}} \ne 0$时R_i=1；约束(13) 为贝位内的堆栈总数约束；约束(14)、(15) 与(16) 要求中间变量h_i^m的取值符合变量关系；约束(17) 为变量0~1取值约束。

3 改进禁忌搜索算法

干扰管理模型的求解具有局部性，利用模型优解的局部性特点设计局部加速的改进禁忌搜索算法，算法禁忌表记录近期搜索的解，避免迂回重复探索，保障探索的多样性，实现算法寻优的全局性。改进禁忌搜索算法的设计要点如下：

1) 禁忌搜索算法的初始解：选用干扰事件发生前的箱位计划方案作为算法搜索的初始解；

2) 探索解的适应度评价函数：探索解的优劣判别标准，利用干扰恢复模型的目标函数f(x)作为探索解适应度的评价函数，目标函数值越小越优；

3) 搜索邻域H(x)的控制：算法的搜索邻域为可交换箱位集合，包括箱与箱的位置交换和空箱位交换两种形式。搜索邻域控制规则：① 可交换箱对(i, j)中的箱i∈C，C为受干扰箱所在堆栈的计划进场的集装箱集合；② 考虑箱位交换的作业成本影响，可交换箱对(i，j)的箱i和j满足|n_i-n_j|≤D_is条件，n_i和n_j为箱i和j的客户交箱次序，D_is为搜索邻域的控制参数；③ 空箱位交换(箱位重新分配到其他栈的空位上)，用(i, z)表示，箱i和栈z满足i∈C、z∈[max{0, b_i-q}, min{B, b_i+q}]，b_i为箱i所在的贝位，q为搜索算法的控制参数。

4) 算法搜索时箱位交换的探索实施集合S(x)：算法迭代搜索时允许多对箱位同时交换可提高算法效率，但搜索邻域中的多对箱位同时进行探索交换可能产生不可行解，因此定义无冲突的交换探索实施集合(H(x)的子集)，集合中的元素满足下列条件：① 如果(i₁, j₁)与(i₂, j₂)∈S(x)，那么i₁≠j₂并且i₁≠i₂；② 如果(i₁, z₁)与(i₂, z₂)∈S(x)，那么i₁≠i₂并且z₁≠z₂；③ 如果(i，j)∈S(x)，那么交换后的适应度值不劣于当前解。

5) 禁忌表的破禁：如果被禁忌探索解的适应度优于历史最优值，那么将探索解的禁忌解除。

6) 算法终止条件：禁忌搜索的迭代次数达到设定的迭代次数后，终止搜索，并输出历史最优方案。

7) 禁忌搜索算法流程：定义x^*最优箱位优选方案，f(x^*)最优方案适应度评价值，m邻域H(x)的探索交换。算法流程如图 4所示。

4 干扰管理实验分析 4.1 干扰管理实验设计

以大连某集装箱码头数据为基础设计干扰管理实验：干扰事件前的出口集装箱位计划利用文献[9]提出的方法制定，堆场的提箱和翻箱任务根据不增加收箱作业等待的原则加入堆场龙门吊作业序列；客户实际交箱时间利用正态分布N(t_k, σ)模拟生成，t_k为箱k的客户预约交箱时间。实验硬件CPU D3.19GHz/2G，算法基于C++开发实现。模型成本参数取1:1:0.6(压箱量:龙门吊大车移动:箱位偏离)，改进禁忌搜索算法的控制参数D_is设置为20，q为1，禁忌表长度l设置为计划总箱量，算法搜索迭代最大次数设置为50。通过同组5个随机实验取平均求得每组结果数据(明确说明的除外)。

4.2 改进禁忌搜索算法性能分析

提出的干扰管理模型属于二次型，可用CPLEX求解。改进禁忌算法与CPLEX12.6的实验对比结果见表 1。CPLEX可求解小规模问题，并得到精确解，其时间消耗随着问题规模的增大而呈指数型增长，CPLEX求解19箱问题的时间消耗在9 h以上，无法满足现实要求。提出的改进禁忌搜索算法可得到小规模问题的较优近似解，精度误差值不超过0.5，算法时耗远小于CPLEX，求解120箱问题仅需3.26 s，能够满足实际要求。

4.3 干扰管理模型性能分析

提出的干扰管理模型与干扰事件发生后不调整方案按原计划执行、重调度模型调整计划的实验对比结果见表 2，实验中采用的重调度模型是基于文献[9]并利用干扰事件发生后的压箱量与龙门吊大车移动距离总成本最小设计。干扰管理的相对效果实验数据见表 3。上述实验结果分析可得出：客户交箱次序的干扰使得不调整方案按原计划执行的压箱量和龙门吊作业成本都大幅度增加，因此干扰事件发生后需要有针对性地动态调整原方案；当问题规模较大时，干扰管理较重调度调整方案的方法效果更优，且规模越大优势越明显，如规模大于3×6×4的算例有10%以上的平均优势和50%的最大优势，干扰管理较重调度方法的求解时间略低。由于干扰管理模型考虑了关联成本因素，干扰恢复方案调整较小，减少了指令修改给龙门吊司机的情绪影响和误操作几率。

干扰管理与重调度的对比改进分布如图 5所示，图中数据点的相对改进=(重调度成本-干扰管理成本)/重调度成本，堆场箱位空间利用率约90%。对比分布图显示，随着问题规模的增大干扰管理较重调度的改进越明显，较优算例占总算例的比率也越大，问题规模达到15×6×4时，干扰管理得到较优解的算例比率占82%。不同堆场箱位空间利用率、问题规模和进/出口箱堆栈比例条件下的模型性能对比见表 4，表中数据为10个实验算例结果的平均值。总体而言，干扰管理模型的改进效果随进/出口箱堆栈比例和问题规模的变大有增大的趋势；当问题规模达到15×6×4时，干扰管理求解问题的精度较重调度有10%以上的改进。

4.4 干扰恢复的启动分析

客户交箱次序的扰动大小决定了干扰恢复的启动。本文利用客户交箱次序的扰动偏差Dev和干扰影响的箱量ΔN来识别扰动程度，并作为干扰恢复算法启动参数。分别定义A₁{Dev≥d}, A₂{ΔN≥n}, A′₁{Dev≤d}和A′₂{ΔN≤n}为启动分析算例中满足Dev≥d, ΔN≥n, V≤d和ΔN≤n的所有实验算例的目标成本增量总和；num₁(d), num₂(n), num′₁(d)和num′₂(n)为Dev≥d, ΔN≥n, V≤d和ΔN≤n的实验算例总数；令

$ \begin{array}{l} {F_1}\left( d \right) = {A_1}\left\{ {{\rm{Dev}} \ge d} \right\}/{\rm{nu}}{{\rm{m}}_1}\left( d \right)\\ {F_2}\left( n \right) = {A_2}\left\{ {\Delta N \ge n} \right\}/{\rm{nu}}{{\rm{m}}_2}\left( n \right)\\ {{F'}_1}\left( d \right) = {{A'}_1}\left\{ {{\rm{Dev}} \le d} \right\}/{\rm{nu}}{{{\rm{m'}}}_1}\left( d \right)\\ {{F'}_2}\left( n \right) = {{A'}_2}\left\{ {{\rm{Dev}} \ge n} \right\}/{\rm{nu}}{{{\rm{m'}}}_2}\left( n \right) \end{array} $

为干扰恢复启动参数效果分析的评估指标。干扰管理效果随干扰恢复启动参数的变化趋势如图 6所示(1 200个算例，问题规模6×6×4)。干扰管理启动参数设置越小，实验的算例作业成本增幅越小，如：Dev≤16的实验算例作业成本的平均增幅1.01%，最大增幅也仅5.02%；ΔN≤6的实验算例作业成本的平均增幅和最大增幅为0.99%和5.01%。码头实际中除了调度精度还需考虑实际运作效果，如果设置过小的干扰管理启动参数势必会造成作业计划方案频繁改变，不利于生产组织和码头作业，因此港方需考虑客户交箱密度等综合因素来设置实际的干扰恢复启动参数。

5 结论

1) 出口集装箱位的干扰管理有利于减少由于干扰事件造成的关联隐性成本，实验表明：干扰管理较重调度节约总作业成本10%以上；

2) 基于局部加速的改进禁忌搜索算法通过控制探索邻域优化了算法搜索方向，并缩小了搜索空间，使其在可接受时间内能获得集装箱位优选干扰管理模型的满意解；

3) 设置较小的出口集装箱位优选干扰恢复启动阀值参数可以获得较小的干扰作业总成本，但过小的干扰恢复启动阈值不利于堆场实际的生产组织，码头需考虑具体实际来选择适用的启动参数。