一种出口集装箱码头堆存空间调度方法

技术领域

本发明涉及物流港口技术领域，尤其是涉及一种出口集装箱码头堆存空间调度方法。

背景技术

集装箱码头堆场在港口业务中是装卸进出口集装箱的场所，其具有吞吐量大、运输调度 成本高、灵活性差等特点。随着港口集装箱吞吐量增加，堆场资源调度面临严峻的考验，其 场区、场桥、集卡等内部资源如因利用不当，会造成场区堆存空间利用率低下，场桥移动次 数过多，集卡运输时造成堆场拥塞。高效合理的堆场资源调度对合理安排船舶装卸计划，减 少船舶在港时间，减小设备使用成本等具有极大影响。高效的堆场调度能够体现港口的业务 能力，而出口箱堆存分配是港口堆存空间分配的核心环节之一。港口堆存空间分配问题所面 临的主要问题包括：堆场堆存资源有限、集装箱和船舶到港时间等不确定性因素。具体集装 箱的集港或取箱具有随机性和动态性，集装箱在堆场内的堆存时间跨度大，通常从几小时到 几天。集装箱具有体积和重量大的特征，需要大型设备进行搬运装卸，场桥等大型机械不易 频繁往复调动以及应尽量避免发生作业冲突等因素限制了集装箱的随机存取。同时，堆存空 间分配问题是一个大规模解空间问题，难于用传统的数学模型求解。高效的出口箱堆存空间 分配能避免：集装箱集港期因选择箱位不合理而造成箱区之间负载不均衡，集装箱进场、装 船时因装卸设备使用次数多而造成成本过高，船舶因等待装船而造成在港时间过长等。

国内外学者对出口箱堆存空间分配问题提出了很多方法和策略，其中典型的求解方法有： 基于数学模型求解、基于启发式算法求解和基于智能算法求解。

（1）基于数学模型求解：例如混合整数线性规划模型。将堆存空间分配问题分为两阶段 进行研究。第一阶段为不同船舶集装箱分配倍位，并提出了混合整数规划模型解决该问题； 第二阶段在第一阶段完成的前提下进行集装箱箱位分配，并提出了混合堆存算法。模型以最 小化箱区与泊位之间的距离、不同箱区之间的负载均衡以及装船时的翻箱率为优化目标。当 堆存空间分配模型较简单时，数学模型能求解堆存分配问题，但是堆存空间分配问题本身是 大规模解空间问题，因此用数学模型求解受到限制。混合整数规划模型在堆场规模扩大，或 者是求解范围增大时，将会限制模型的应用，故其有一定局限性。

（2）基于启发式算法求解：提出为预集港船舶制定计划方式来进行堆存空间分配。考虑 到港口业务规则的复杂性、堆场内相关子系统的相互联系以及堆场中不确定因素，提出了几 点箱区分配规则：出口箱区尽量分配在距离泊位近的地方；尽量避免箱区内同时装船；尽量 避免箱区内集港同时有装船作业；箱区内存放的箱量有一定限制，不能过多也不能过少。由 于启发式算法依赖于实际问题和经验，不能保证求得最优解，并且求解结果不稳定，有时会 造成计算结果不可信，因此具有一定局限性。

（3）基于智能算法求解：例如遗传算法、模拟退火算法等。采用遗传算法求解堆存空间 分配问题，多以最小化船舶和泊位的距离以及箱区负载为决策目标。由于遗传算法在染色体 编码时，若选择编码方式不合理，则会造成解空间范围不准确，或者陷入局部最优解。而交 叉变异等操作方法多样化，不同操作会导致遗传算法的寻优能力不同。目前比较主流的堆存 空间分配调度模型算法大致包含启发式信息与具体求解算法相结合思路，以期能够加快求解 速度。但由于启发式信息依赖于经验信息，并且其无法保证收敛速度，故也存在一定局限性。

随着堆场装卸运输设备和硬件可靠性的提高，不确定环境下堆场调度成为制约集装箱运 输效率提高的瓶颈问题。为此，找到更有效的方法，构建在不确定环境下有良好性能的堆场 空间分配决策，使得整个港口的堆场作业得到优化、资源调度合理化、堆场作业节能化，对 一个港口竞争力的提高有重大的影响。因此，不确定环境下的集装箱码头堆场空间分配决策 的研究具有重要的现实意义。

发明内容

本发明以集装箱港口堆场空间利用率作为研究对象，通过从计划分配到动态选位的策略， 实现以提高堆场空间利用率，降低堆场成本为目标的堆存空间分配模型。

本发明的技术方案为一种出口集装箱码头堆存空间调度方法，包括为区位计划阶段、倍 位计划阶段和集装箱进场选位阶段，

区位计划阶段建立基于生态中性理论的区位分配模型，所述区位分配模型将箱区抽象为 岛屿，将箱组抽象为物种，将箱组分配到箱区的过程转化为将若干物种对岛屿进行生态选择； 基于区位分配模型进行以下流程，

Step2,开始进行生态中性理论迭代求解最优解，执行以下子步骤，

Step2.1,针对每个分组进行以下操作；

Step2.1.1,将分组内的箱区看作若干个岛屿，将箱组看作若干物种；根据船舶长 度计算需要分配的箱区数，作为岛屿数目；

Step2.1.2,进行物种分配操作；

Step2.1.3,进行组内中性算法迭代；判断是否满足迭代结束条件，未满足则转 Step2.1.4，满足则转Step4；

Step2.1.4,进行随机杀死操作；

Step2.1.5,进行后代产生操作；

Step2.1.6,进行修正操作；

Step2.1.7,进行组内物种迁移；

Step2.2,保存最优解；

Step2.3,进行组间物种迁移操作；

Step2.4,保存最优解,判断是否满足迭代结束条件，未满足则则转Step2.1，满足则转 Step3；

Step3,产生最优解；

Step4,算法结束；

倍位计划阶段和集装箱进场选位阶段提出组合元胞自动机模型，所述组合元胞自动机模 型将倍位计划抽象为外元胞模型，将集装箱进场选位抽象为内元胞模型；外元胞模型采用元 胞状态转换规则，根据中心元胞及其左右邻居的当前状态决定下一时刻元胞的状态；内元胞 模型采用优先队列的分支限界法进行求解。

而且，Step2.1.3中，进行组内中性算法迭代根据下式实现，

$\mathrm{fitness}=\underset{\theta =1}{\overset{6}{\Sigma }}\Phi ((f_{\theta }-u{f}_{\theta })/\sigma f_{\theta }),0\le \mathrm{fitness}\le 6$

其中，uf_θ为目标函数的期望，σf_θ为目标函数的方差；

f₁＝max{u₁/σ₁}

$f_2=\max \left\{\frac{1}{{\Sigma }_{p=1}^{L_n}{\Sigma }_{i=1}^{S_n}{\Sigma }_{j=1}^{S_n}\left(\mathrm{di}{s}_{i,j}{\delta }_{i,p}{\delta }_{j,p}\right)}\right\}$

$f_3=\max \left\{\frac{1}{{\Sigma }_{p=1}^{L_n}{\Sigma }_{i=1}^{S_n}\left(n_i{\delta }_{i,p}{d}_p\right)}\right\}$

$f_4=\max \left\{\frac{1}{{\Sigma }_{p=1}^{L_n}\left(\left({\Pi }_{i=1}^{S_n}{\delta }_{i,p}\right){\mathrm{cll}}_p\right)}\right\},(s.t.{\delta }_{i,p}=1)$

$f_5=\max \left\{\frac{1}{{\Sigma }_{p=1}^{L_n}\left(\left({\Pi }_{i=1}^{S_n}{\delta }_{i,p}\right){\mathrm{clc}}_p\right)}\right\},(s.t.{\delta }_{i,p}=1)$

$f_6=\max \left\{\frac{1}{{\Sigma }_{p=1}^{L_n}{\Sigma }_k({\mathrm{lm}}_{p_k}+{\Sigma }_{i=1}^{S_n}{\delta }_{i,p}{m}_{i,k}{n}_i-c_p)}\right\}$

计算时考虑以下约束条件，

$\underset{p=1}{\overset{L_n}{\Sigma }}\left(\underset{i=1}{\overset{S_n}{\Pi }}{\delta }_{i,p}\right)=B_n$

${\mathrm{lm}}_{p_k}+\underset{i=1}{\overset{S_n}{\Sigma }}\left({\delta }_{i,p}{m}_{i,k}{n}_i\right)\le c_p$

式中，u₁、σ₁分别为箱区中分配箱量的均值和方差，S_n为物种数量，L_n为岛屿数量，δ_i,p为决 策变量，dis_i,j用于描述两个物种之间的捕食关系，n_i为箱组i的集装箱箱量，d_p为箱区p与 泊位之间的距离，cll_p表示箱区p内两个船舶同时装船的冲突值，clc_p表示箱区p内一条船舶 正在装船而另外一条船舶正在集港的冲突值，m_i,k为在第k阶段箱组i累计来箱，c_p为箱区p 的空闲箱量，表示箱区p在某阶段k的预测箱量，B_n为需要进行区位计划的船舶预先分 配的箱区数目。

而且，将倍位计划抽象为外元胞模型包括进行如下定义，

元胞，表示箱区中倍位；

元胞空间，是箱区中全部倍位集合；

元胞状态，若某一倍位α已被分配则用A_α表示已分配的箱位数目，若该倍位未被分配则 用C_α表示该倍位可被分配的空闲箱位数目；则当前时刻t元胞状态定义为用来表示该元 胞是否被激活，时该元胞被杀死，时该元胞被激活；

元胞邻居，包括中心元胞的左右节点，如果用表示当前元胞节点，则其邻居节点为和

元胞状态转换规则，考虑中心元胞与其左右邻居的当前状态，根据三者的状态决定下一 时刻t+1元胞的状态，表示为$(S_{\alpha -1}^{t+1},S_{\alpha }^{t+1},S_{\alpha +1}^{t+1})=f(S_{\alpha -1}^t,S_{\alpha }^t,S_{\alpha +1}^t).$

而且，将集装箱进场选位抽象为内元胞模型包括进行如下定义，

元胞，表示倍位中的箱位；

元胞空间，是已分配倍位集合中所有空闲箱位集合；

元胞状态，采用用来表示当前时刻t元胞α是否被激活，时该元胞被杀死， 该元胞被激活；

元胞邻居，包括中心元胞的上、下、左、右、左上、右上、右下、左下相邻八个元胞；

元胞状态转换规则，以元胞的一列为单位，从左至右，统计每一列的平均重量级，将平 均重量级调整为越靠近集卡车道，平均重量级越大。

而且，组合元胞自动机模型中有关定义如下，

元胞，将倍位分配和进场选位两阶段的任一组合可行解作为一个元胞；

元胞空间，是C×C的四方格网络，支持同时进行C×C组元胞变换；其中，C为CAOI 模型元胞空间尺寸；

元胞状态，设P_l表示当前中心元胞自身变换最优解，l为相应节点编号；P_g表示中心元胞 的邻居节点中最优解，g为相应节点编号；定义当前时刻t的两种元胞状态，和

元胞邻居，包括中心元胞的上、下、左、右、左上、右上、右下、左下相邻八个元胞；

下一时刻t+1的元胞状态转换规则为

$S_l^{t+1}\left(P_g\right)=f(S_l^t\left(P_l\right),S_{l+{\omega }_1}^t\left(P_{l+{\omega }_1}\right),S_{l+{\omega }_2}^t\left(P_{l+{\omega }_2}\right)...S_{l+{\omega }_n}^t\left(P_{l+{\omega }_n}\right)),$其中l+ω_x，1≤x≤8表示中 心元胞的邻居节点，ω_x表示中心元胞的邻居节点编号；设表示中心元胞的适应值， 则状态转换规则为，

$S_l^{t+1}\left(P_g\right)=\min {\left\{\mathrm{fit}\right(S}_l^t\left(P_l\right)),{\mathrm{fit}(S}_{l+{\omega }_1}^t\left(P_{l+{\omega }_1}\right)),{\mathrm{fit}(S}_{l+{\omega }_2}^t\left(P_{l+{\omega }_2}\right))...\mathrm{fit}(S_{l+{\omega }_n}^t\left(P_{l+{\omega }_n}\right)).$

而且，基于组合元胞自动机模型进行以下流程，

步骤1，初始化C×C的四方网络型元胞空间；

步骤2，初始化元胞空间中的元胞；

步骤3，迭代求解最优解，每次迭代包括对每个元胞执行外元胞模型，在外元胞模型内执行内 元胞模型，按下式计算目标函数值；如果计算结果收敛则退出循环，

f＝min{f₁+f₂+f₃+f₄}

其中，

$f_1=\frac{{\mathrm{cb}}_p-{\mathrm{cb}}_{p,\min }}{{\mathrm{cb}}_{p,\max }-{\mathrm{cb}}_{p,\min }}$

$f_2=\frac{{\mathrm{tre}}_p}{{\Sigma }_{\beta =1}^{{\mathrm{cb}}_p}{\mathrm{re}}_{{\pi }_{\beta },\max }}$

$f_3=\frac{{\mathrm{dist}}_{\alpha }-{\mathrm{dist}}_{p,\min }}{{\mathrm{dist}}_{p,\max }-{\mathrm{dist}}_{p,\min }}$

$f_4={\Sigma }_{\beta =1}^{{\mathrm{cb}}_p}{\mathrm{px}}_{{\pi }_{\beta }}/{\mathrm{cb}}_p$

计算时考虑以下约束条件，

式中，cb_p为箱区p中选择的倍位数目，cb_p,max用来表示箱区p内最多分配的倍位数，cb_p，min用 来表示箱区p内最少分配的倍位数目，tre_p为箱区p中N_p个集装箱落箱后的压箱数，为 箱区p中选择的倍位集合内某倍位π_β的最小压箱数，dist_α表示箱区p中N_p个集装箱所耗 费的运输距离，dist_p,max表示箱区p内集装箱的最大运输距离，dist_p,min表示箱区p内集装 箱的最小运输距离，为选择一个倍位π_β后的代价值，R_n为倍位的排数目，T_n为倍位的层 数目，为决策变量。

而且，Step1中，通过最优子种群遗传算法将所有出口的箱区划分为L_n/G_n个分组时，确 保分组之间的箱量差和到泊位距离差最小，记为min{σ₁²+σ₂²}，

其中，

$u_1={\Sigma }_{e=1}^{L_n/G_n}{\Sigma }_{p=1}^{G_n}{d}_p/L_n/G_n$

$u_2={\Sigma }_{e=1}^{L_n/G_n}{\Sigma }_{p=1}^{G_n}{c}_p/L_n/G_n$

${{\sigma }_1}^2={\Sigma }_{e=1}^{L_n/G_n}{({\Sigma }_{p=1}^{G_n}{d}_p-u_1)}^2/L_n/G_n$

${{\sigma }_2}^2={\Sigma }_{e=1}^{L_n/G_n}{({\Sigma }_{p=1}^{G_n}{c}_p-u_2)}^2/L_n/G_n$

式中，d_p为箱区p与泊位之间的距离，c_p为箱区p的空闲箱量。

本发明将堆存空间分配问题划分为两个子问题：区位分配问题和“倍位分配—进场选位” 问题。为求解区位分配问题，本发明研究生态中性理论模型，并在此基础上进行改进并应用 到集装箱码头出口箱区位计划。生态中性理论认为一切生物个体都在经历完全随机的生灭过 程，因此通过生态选择达到生态平衡来求解最优解具有全局寻优能力，并且适合于区位计划 模型。本发明以集装箱码头出口集装箱的区位计划作为研究对象，在保证堆存利用率以及装 船效率的同时，以最小化各船舶与堆存区段的总体距离和尽量避免区段内多条船舶同时装船 的情况为优化目标。为求解“倍位分配—进场选位”问题，本发明研究组合元胞自动机模型， 用于求解倍位分配问题和进场选位问题，进行双目标优化。本发明在外元胞模型中提出4种 元胞状态转换规则，用于演化求解倍位分配问题；在内元胞模型中提出基于优先队列的分支 限界法，用于求解进场选位问题。内—外元胞之间通过代价函、判断函数进行互相制约影响， 判断函数用于外元胞模型选择倍位时判断选择倍位的代价，代价函数用于计算内元胞模型进 行进场选位后的代价值。实验证明本发明的模型具有良好的最优解。

附图说明

图1是集装箱码头堆场布局图。

图2是本发明实施例的SBAP问题描述示意图。

图3是本发明实施例的倍位堆存示意图。

图4是生态中性理论模型描述示意图。

图5是本发明实施例的生态中性理论改进模型描述示意图。

图6是本发明实施例的基于UNTBB模型的BAP问题求解过程示意图。

图7是本发明实施例的历史累计集装箱到港趋势图。

图8是本发明实施例的SBAP问题抽象示意图。

图9是本发明实施例的判断函数使用场景描述示意图。

图10是本发明实施例的MKGA算法主要操作示意图。

图11是本发明实施例的CAOI模型描述示意图。

图12是本发明实施例的CAO模型抽象示意图。

图13是本发明实施例的CAO模型描述示意图。

图14是本发明实施例的CAI模型抽象示意图。

图15是本发明实施例的CAI模型描述示意图。

图16是本发明实施例的CAI元胞状态转换规则示例示意图。

图17是本发明实施例的排相似描述示意图。

图18是本发明实施例的三组组合可行解示意图。

具体实施方式

以下结合附图和实施例详细说明本发明技术方案。

传统预分配—动态分配思想采取三阶段模型，将堆存空间分配问题划分为区位计划 （Block Allocation Problem，简称BAP）、倍位计划（Yard Bay Allocation Problem，简称YBAP）、 集装箱进场选位（Space Allocation Problem，简称SAP）。三阶段分配模型中集装箱进场选位 依赖于预先分配的箱位，为集装箱进场选位提供指导作用。而在实际堆场中，不确定性因素 会加大堆存分配难度，预先分配的粒度越小，则箱位选择的灵活性越小。因此，本发明在BAP 问题基础上，将YBAP与SAP问题组合求解（本发明将该组合问题定义为SBAP），增大集 装箱箱位选择空间，尽量减少因不确定性因素对堆存分配造成的影响。

本发明的主要研究内容包括：

（1）区位计划阶段提出基于生态中性理论的区位分配模型。模型将箱区抽象为岛屿， 将箱组抽象为物种，则将箱组分配到箱区的过程转义为将若干物种对岛屿进行生态选择。基 于此模型，本发明针对区位计划问题特点，对该模型进行优化，提出了改进的生态中性理论 模型。实验结果表明，本发明模型具有良好表现。

（2）倍位分配和进场选位阶段，提出组合元胞自动机模型。模型将倍位分配抽象为外 元胞模型，进场选位抽象为内元胞模型。

（3）外元胞模型提出二进制元胞状态转换规则，根据元胞及其邻居当前状态决定下一 时刻元胞的状态。

（4）内元胞模型采用优先队列的分支限界法进行求解。算法性能较高，可在秒级时间 内求取结果。

（5）本发明对基于生态中性理论的区位分配模型和基于组合元胞自动机的“倍位分配— 进场选位”模型进行有效性验证。

BAP问题描述：

BAP问题是出口箱堆存空间分配问题的第一步，BAP用于求解将预到港船舶的集装箱 箱组分配至指定箱区中。如图1所示，箱区由倍位组成，5个集装箱箱组A、B、C、D、E 经过BAP求解后，被分配至3个箱区中。

BAP问题致力于解决：

（1）满足装船时配置多条集装箱运输作业路，避免在装船时，场区运输阻塞；

（2）最小化箱区与泊位之间的距离，减小装船时，集卡运输距离，加快运输效率，减 小船舶在港时间；

（3）避免同一个箱区内既有集港作业又有装船作业，造成箱区装卸设备繁忙；

本发明针对BAP问题做出如下假设：

（1）文中仅针对出口箱堆存空间分配问题进行研究。由于进、出口箱业务流程不同， 而其中出口箱业务最为复杂，本发明的研究范围是出口集装箱堆存分配问题。出口箱与进口 箱不混合堆存在一个箱区内。

（2）泊位计划已知，即在船舶到港时，已知船舶停靠在哪个泊位。

（3）堆场历史集港装船信息已知，该信息可用于指导区位计划。

（4）箱区内集装箱来箱趋势可从历史数据中获取。

（5）将集装箱根据重量划分为若干重量级，用以减小集装箱之间的差异，缩小研究规 模。重量级根据集装箱重量分布而定。如表1所示，39.25%的集装箱重量在6-10吨之间，因 此处于该重量范围内的集装箱成为重量级2。

表1集装箱箱重与重量级之间关系

（6）属于同一箱型、同一尺寸、同一船舶、同一卸货港、同一重量级的集装箱称为一 个箱组。

（7）同一箱组尽量分配至同一箱区内，用以确保装箱的连续性。

（8）重量级相近的两个箱组称为相邻箱组，如表1，重量级1与重量级2的箱组称为相 邻箱组。

SBAP问题描述：

由于集港集装箱的个数、到港时间不确定，船舶到港的时间不确定，倍位计划中为船舶 预留的箱位无法满足根据堆场现状动态落箱的需求。因此，本发明研究对倍位计划和进场选 位进行双目标组合优化，文中定义为SBAP问题。SBAP结合预分配步骤中倍位计划与动态 分配箱位过程，利用两者之间互相约束、同步演化，从而求解组合优化结果。

如图2中(a)所示，在选定箱区后，需要通过一定优化策略选出某一倍位作为集装箱进场 时的堆存位置。其中，假设来箱序列为A₁、E₅、D₄、C₃、B₂、A₁、E₅（字母A-E代表箱组代 号，字母下标的阿拉伯数字代表箱组对应的箱重等级）。则一个可行的堆存方案如图2中(b) 所示。

SBAP问题致力于求解：

（1）在指定箱区内选择若干倍位，作为集装箱进场选位时的可选箱位，且最大化倍位 利用率；

（2）最小化集装箱到泊位的运输距离；

（3）最小化所选倍位内压箱数，压箱数越小，则装船时翻箱可能性越小，可以加快装 船效率。

本发明针对SBAP问题做出如下假设：

（1）文中仅针对出口箱堆存空间分配问题进行研究。由于进、出口箱业务流程不同， 而其中出口箱业务最为复杂，本发明的研究范围是出口集装箱堆存分配问题。

（2）进、出口集装箱分开存放，且不会混合存放在同一箱区。

（3）区位计划已知。即堆场管理者已为预到港船舶制定区位计划，该船舶所有集装箱 被划分为若干箱组，且经过BAP模型决策后，将箱组分配至某几个箱区。

（4）泊位计划已知。即预到港船舶停靠的泊位已预先分配。

（5）某条船舶集港期间来箱次序已知。由于集港期间，某条船舶的集装箱来箱次序不 确定，若要在不确定环境下进行建模，则选择当前箱位时，无法预知未来来箱次序。因此本 发明中针对任一随机来箱序列进行建模，通过实验证明模型对求解任一随机来箱序列均有效。

（6）文中所提到的集装箱是普通干货集装箱（General Purpose），且尺寸相同。

（7）集港期间，为集装箱选择箱位时，尽可能保证轻箱在下，重箱在上的原则，否则 会造成在装船时有大量的翻箱操作。因此，倍位内堆存效率通常是通过倍位内压箱数来定义。 如图3中(a)所示倍位示意图，如图3中(b)所示，排1和3中压箱数为0，排2、4、5压箱数 分别为3、1、1。

（8）通常倍位中需要保留一定数目的箱位，用作翻箱。本发明实施例中所研究的倍位 是6排，4层，且预留箱位数为3。因此，一个倍位中最多可存放21个集装箱。

（9）船舶的某一箱组在同一时间段装船，且按照重箱先装船，轻箱后装船的顺序。

BAP模型建模：

本发明研究生态中性理论模型（The Unified Neutral Theory of Biodiversity and  Biogeography，简称UNTBB），并在此基础上进行改进并应用到BAP问题。将箱区抽象为岛屿， 将箱组抽象为物种，则将箱组分配到箱区的过程转义为将若干物种对岛屿进行生态选择。由 于本发明研究对象是将指定船舶的箱组分配到箱区中，箱组是最小单位，故在生态中性理论 建模时，将一个箱组看作一个物种，一个物种仅有一个个体。生态中性理论模型描述：

用岛屿模拟一个箱区，每个箱组（抽象为不同的物种）占领若干个倍位，且箱区大小固 定。如图4中(a)所示，每个个体被涂成了不同的标记（黑色圈、白色圈、阴影圈）表示不同的 物种，假设生态演化过程中周期性重复以下三个步骤：

（1）如图4中(b)所示，从全部生物个体中随机选中若干个体杀死，这样会多出若干空位；

（2）如图4中(c)所示，随机从活着的生物个体中选择若干个体作为母代，产出若干子代， 填补空位，同时母代的基因（即同一种标记）遗传给子代；

（3）在步骤（2）的生育过程中以一定概率发生生物变异，进而形成新物种，如此，使 得子代颜色与母代不同，即模拟发生突变过程。

利用该模型求解时，当箱区数量较多的情况下会导致提前陷入局部最优解，故本发明采 取分组策略，将箱区划分为等价的若干组，引入组内物种迁移和组间物种迁移概念，如图5， 包括以下步骤：

1.岛屿分组

2.采用基本生态中性理论模型，包括以下子步骤，

2.1.物种对岛屿进行随机选择，采用贪心策略实现

2.2.随机杀死若干个体，可以大概率杀死捕食关系中任一物种

2.3.生育子代、子代变异

3.组内物种迁移

4.组间物种迁移

组内物种迁移是指将物种从岛屿A上迁移到同组的岛屿B中，保证物种经过初始选择岛 屿后能够被分配到同组其他的岛屿中，避免物种在一个岛屿中被杀死后导致灭绝，即零和生 态漂变；组间物种迁移是指岛屿A上的所有物种变迁生存岛屿至其他分组的岛屿B，保证所有 物种都有机会选择适合条件的岛屿进行生态选择。同时物种采取贪心策略选择生存岛屿；岛 屿内物种之间存在捕食关系时，则大概率杀死任一物种，尽量使其分离。

例如，假设堆场有4个箱区记为岛屿1、岛屿2、岛屿3、岛屿4，且有5个箱组A、B、C、 D、E需要分配到这4个箱区中。则根据UNTBB模型，该BAP问题可转化为如图6所示。(a)中 随机杀死一定数目个体；(b)中产生下一代个体，包括遗传和变异过程；(c)中修正岛屿物种状 态。

生态中性理论中提出群体中每个独立个体的出生、死亡以及变异的概率全部相同，而与 个体所属的物种无关，物种间的差异仅和物种当前拥有的个体数量有关。本发明实施例个体 数为1，通过一定代数的迭代生存进化，岛屿上会形成一个稳态，这也是本发明BAP问题求解 的最优解。

实施例符号定义：

BAP问题中相关参数定义如表2所示。本发明实施例将BAP问题转换为UNTBB模型进行 求解，UNTBB模型参数定义如表3所示。

表2BAP问题参数定义

表3UNTBB模型参数定义

目标函数：

BAP问题处于预分配堆存空间阶段，因此在求解目标函数中需要考虑到后续即将到港箱 量对当前决策的影响。为满足BAP问题求解目标，本发明实施例从以下几个方面选取目标函 数，以期能够在BAP阶段求解时，为后续SBAP问题做铺垫。

（1）满足装船时配置多条作业路的需求，则要求箱组均匀分布在箱区内，并且相邻箱 组尽可能分布在不同箱区。

首先计算箱区中分配箱量是否为均匀分布，式（1）计算均值u₁，式（2）计算方差σ₁²：

$u_1={\Sigma }_{i=1}^{S_n}{n}_i/B_n$

${{\sigma }_1}^2=\frac{{\Sigma }_{p=1}^{L_n}{(\left({\Sigma }_{i=1}^{S_n}{\delta }_{i,p}{n}_i\right)-u_1)}^2}{B_n-1},(s.t.{\Sigma }_{i=1}^{S_n}{\delta }_{i,p}{n}_i>0)---\left(1\right)$

                                           f₁＝max{u₁/σ₁}  （2）

使得f₁＝max{u₁/σ₁}即可。为了保证相邻箱组尽可能分布在不同箱区，则引入捕食关 系dis_i,j，其评价的目标函数为：

$f_2=\max \left\{\frac{1}{{\Sigma }_{p=1}^{L_n}{\Sigma }_{i=1}^{S_n}{\Sigma }_{j=1}^{S_n}\left({\mathrm{dis}}_{i,j}{\delta }_{i,p}{\delta }_{j,p}\right)}\right\}---\left(3\right)$

其中，i≠j。

（2）最小化箱区与各船舶之间的距离。在船舶装船期间，场桥将集装箱取出，并放置到 集卡上，由集卡运送至岸边。该目标函数旨在减小船舶在港时间。

$f_3=\max \left\{\frac{1}{{\Sigma }_{p=1}^{L_n}{\Sigma }_{i=1}^{S_n}\left(n_i{\delta }_{i,p}{d}_p\right)}\right\}---\left(4\right)$

（3）避免箱区内多条船舶同时装船。例如船舶2的箱组选择了箱区p，同时船舶1的箱组 已经选择了箱区p，并且满足：lt_1,0＜{lt_2,0 or lt_2,1}＜lt_1,1。其中，lt_1,0表示船舶1开始装船时 间，lt_1,1表示船舶1结束装船时间，lt_2,0表示船舶2开始装船时间，lt_2,1表示船舶2结束装船时间。

$f_4=\max \left\{\frac{1}{{\Sigma }_{p=1}^{L_n}\left(\left({\Pi }_{i=1}^{S_n}{\delta }_{i,p}\right){\mathrm{cll}}_p\right)}\right\},(s.t.{\delta }_{i,p}=1)---\left(5\right)$

（4）避免箱区内船舶装船时有其他船舶的集港作业。例如船舶2的箱组选择箱区p，同 时船舶1的箱组也选择箱区p，且满足lt_1,0＜{ct_2,0 or ct_2,1}＜lt_1,1。其中，ct_2,0表示船舶2开 始集港时间，ct_2,1表示船舶2结束集港时间。

$f_5=\max \left\{\frac{1}{{\Sigma }_{p=1}^{L_n}\left(\left({\Pi }_{i=1}^{S_n}{\delta }_{i,p}\right){\mathrm{clc}}_p\right)}\right\},(s.t.{\delta }_{i,p}=1)---\left(6\right)$

（5）避免箱区内计划放置的集装箱量超过箱区容量。

$f_6=\max \left\{\frac{1}{{\Sigma }_{p=1}^{L_n}{\Sigma }_k({\mathrm{lm}}_{p_k}+{\Sigma }_{i=1}^{S_n}{\delta }_{i,p}{m}_{i,k}{n}_i-c_p)}\right\}---\left(7\right)$

其中，m_i,k为在第k阶段箱组i累计来箱。

（6）目标函数

本发明实施例采取将以上6个目标函数f₁、f₂、f₃、f₄、f₅、f₆投影到正态分布函数上， 从而将各个目标归一化。本发明首先随机产生1000个可行解，然后根据f₁-f₆进行评价，分别得 到其期望uf_θ和方差σf_θ，1≤θ≤6。则经过归一化后的目标函数定义如下：

$\mathrm{fitness}={\Sigma }_{\theta =1}^6\Phi ((f_{\theta }-u{f}_{\theta })/\sigma f_{\theta }),0\le \mathrm{fitness}\le 6---\left(8\right)$

约束条件

（1）箱区约束，选择的箱区数不能超过船舶预定选择的箱区数。

${\Sigma }_{p=1}^{L_n}\left({\Pi }_{i=1}^{S_n}{\delta }_{i,p}\right)=B_n---\left(9\right)$

（2）箱量约束，箱区内任意阶段存放的集装箱数目不能超过其容量。箱区内箱量包含 两部分，一部分是p箱区在k时间段(即第k阶段)的预测箱量，一部分是k时间段即将到港箱量。

${\mathrm{lm}}_{p_k}+{\Sigma }_{i=1}^{S_n}\left({\delta }_{i,p}{m}_{i,k}{n}_i\right)\le c_p---\left(10\right)$

SBAP模型建模：

本章节主要描述如何将倍位分配与进场选位两阶段进行归并建模求解。模型通过组合元 胞自动机，对倍位分配和进场选位分别建模，通过归一化目标函数，使得最终解集为双目标 最优解。

经过区位计划求解，将堆场空间分配问题规模缩小为：在某一箱区内，选择若干倍位， 堆放即将到场的若干集装箱。如图8中(a)所示，箱区内一共有12个倍位，倍位中空闲箱位数目 如图中方格所示，分别为21、19、15、21、21、10、21、21、21、16、9、12。该箱区内需要 为65个集装箱分配箱位。假设已选择4个倍位（图8的(a)中阴影方格）。如图8中(b)所示，接下 来需要在4个倍位中选择合适箱位，堆放65个集装箱。

元胞自动机（Cellular Automaton,CA）模型中，中心元胞会根据周围邻居的状态而改变 自身状态，如此反复，最终达到一个动态演化过程。而本发明研究的堆场是一个三维模型， 当前决策状态会影响到后续决策，这种决策关系与元胞自动机中元胞变换规则相似，因此， 本发明采取元胞自动机建模。

为求解该问题，本发明提出组合元胞自动机模型（本文将其定义为CAOI），且定义外层 元胞模型（CAO）用作求解倍位分配问题，内层元胞模型（CAI）用作求解进场选位问题。 CAO模型在组合可行解中，用于对倍位分配进行优化，且模型是一维元胞空间；CAI模型针 对集装箱进场选位进行优化，且模型是二维元胞空间。CAOI的目标函数值是CAO与CAI 归一化后的叠加值：fit_oi＝fit_o+fit_i。其中，fit_oi是CAOI的综合目标函数值，fit_o是CAO 模型目标函数值，fit_i是CAI模型目标函数值。fit_o与fit_i互相约束，其双目标优化后的结果 则为CAOI模型的最优解。同时CAOI模型本身也是由可行解构成的二维元胞模型，根据一 定局部状态改变规则进行元胞状态改变，这样可以加快CAOI模型求解速度。

实施例符号定义：

SBAP问题中相关参数定义如表4所示。本发明将SBAP问题转换为CAOI模型进行求解， CAOI模型参数定义如表5所示。

表4SBAP问题参数定义

表5CAOI模型参数定义

目标函数：

SBAP问题实际将倍位预分配与集装箱动态进场选位相结合，通过组合元胞自动机模型 对两个目标进行同步演化求解。为了达到组合优化效果，CAOI模型中外元胞CAO与内元胞 CAI之间通过一个判断函数（本发明实施例将其定义为gx）作为结合点，以下将会详述。

（1）最小化分配的倍位数目。

堆场中堆存资源是紧缺资源，大型港口往往面临堆存空间紧张问题。因此本发明在倍位 分配时尽可能使用最少的倍位堆存最多的集装箱，从而最大化倍位利用率。假设箱区p中有N_p个集装箱需要分配箱位。

分配倍位时，箱区p中选择的倍位集合集合初始化为，令箱区p中选择的倍位数目 cb_p＝0。经过策略后，若决策变量满足：即表明编号为α的倍位被选中， 则将编号为α的倍位加入到集合中，同时将cb_p取值增加1。如此循环遍历b_p个倍位，则可 求得与cb_p。例如，假设经过决策后选择了编号为1、2、3、5的倍位，则且cb_p＝4。利用最大最小归一化方法，将该目标函数归一化如式11所示：

$f_1=\frac{{\mathrm{cb}}_p-{\mathrm{cb}}_{p,\min }}{{\mathrm{cb}}_{p,\max }-{\mathrm{cb}}_{p,\min }}---\left(1\right)$

（2）最小化已选择箱位内的压箱数。

由于堆场中压箱带来的翻箱成本较大（场桥需要经过翻箱操作，将被压集装箱取出，这 样会消耗一定时间成本和机器操作成本），因此在集装箱进场选位时，尽可能减小落箱后的压 箱数，从而提高装船效率。

由式（11）的推导可知是经过决策选择的倍位集合。则该倍位集合内经过集装箱进 场选位后，造成的压箱数目为：利用最大最小化归一方法， 将该目标函数归一化如式（12）所示：

$f_2=\frac{{\mathrm{tre}}_p}{{\Sigma }_{\beta =1}^{{\mathrm{cb}}_p}{\mathrm{re}}_{{\pi }_{\beta },\max }}---\left(12\right)$

其中，表示倍位π_β内的最大压箱数。

（3）最小化集装箱的运输距离。

集装箱的运输距离如dist_α定义，最小化集装箱的运输距离有利于较小集卡运输距离，提 高装船效率，从而较小船舶在港时间，使得船舶按计划离港，故不会因为装船延迟影响其他 船舶的装船计划。

由式（11）的推导可知是经过决策选择的倍位集合。假设用Al_β来表示倍位π_β（β∈[1,cb_p]）中预分配给即将集港的集装箱箱位数目。则：例如且cb_p＝4，假设分配给倍位1、2、3、5的箱量分别为20、21、21、10， 那么dist_α＝1×20+2×21+3×21+4×10＝165。利用最大最小归一化方法，将该目标 函数归一化如式13所示：

$f_3=\frac{{\mathrm{dist}}_{\alpha }-{\mathrm{dist}}_{p,\min }}{{\mathrm{dist}}_{p,\max }-{\mathrm{dist}}_{p,\min }}---\left(13\right)$

（4）最小化惩罚函数值。

SBAP问题将倍位分配与集装箱进场选位相结合求解，则无法避免经CAOI模型决策选 出的倍位中存在其他船舶的集装箱，因此需要将这部分的代价转换为惩罚函数值，计算到目 标函数中，促使CAOI模型尽可能选择惩罚函数值最小的倍位。

本发明实施例定义gx为判断函数，用以描述选择一个倍位时的判断值，具体描述如下： 如图9中(a)所示，倍位中已经堆存船舶V₁的4个集装箱O₁、O₅、O₄、O₁，若船舶V₂的来箱 序列为A₁、E₅、D₄、C₃、B₂的集装箱经过决策后堆存位置如图9(b)所示。

如图9中(a)所示，若CAOI模型中选择该倍位，将面临以下两个问题：①当前集港阶段 船舶V₂的集装箱可能与船舶V₁的集装箱的装船时间发生冲突。②决策选择哪个倍位时，也 需要结合当前倍位内的堆存情况，即当前倍位中空闲箱位数目（或者是计算当前倍位中已堆 存计划外的集装箱数目）。若CAOI模型在考虑到①②两点后，仍然选择该倍位，那么其将会 面临：③当前集港阶段船舶V₂的集装箱与倍位内船舶V₁的集装箱混堆存放，且造成压箱， 如A₁和O₄。

本发明实施例在决策是否选择一个倍位前，需要考虑①②，则定义判断函数gx_α（α为倍 位编号）为(g₁+g₂)/2。g₁表示当前集装箱与倍位内已堆存的集装箱装船时间差。假设当前 集装箱的装船时间段为t1，倍位内已堆存的集装箱的装船时间段为t2，若t1>t2，则表明当 前集装箱的装船时间晚于倍位已堆存集装箱，则令若t1<t2，则表明当前集装箱 的装船时间早于倍位已堆存集装箱，因此不会影响装船时的翻箱操作，则令g₁＝0。例如图9 中(a)所示，假设t1=4，t2=2，则g₁=1/(4-2)=0.5。g₂表示当前集装箱落箱前，倍位内已堆存的 集装箱数目。假设用z表示倍位内已堆存的集装箱数目，若z！=0，则g₂=1/z；若z=0，则g₂=0。 例如图9中(a)所示，g₂=1/4=0.25。

本发明实施例在决策选择一个倍位后，需要计算选择该倍位的代价，即代价函数，具体 实施时，本发明技术人员可执行设定代价函数。本发明实施例将其定义为px_α（α为倍位编号）， 令px_α＝gx_α+g₃。g₃表示当前集装箱与倍位内已堆存的集装箱之间压箱数。如图9中(b)所 示，2排1层已堆存O₁集装箱，同时，2排的C₃、B₂集装箱压在O₁集装箱上，则2排内的 压箱值记为2，假设用rr_γ来表示该值，γ为排编号，取值为从1到R_n。根据此规则， 图9(b)中g₃值为1/(0+2+1+0+0+1)=0.25，因此根据px_α＝gx_α+ g₃=(0.5+0.25)/2+0.25=0.625，该值表示若CAOI模型决策时，选择该倍位并且集装箱落箱后， 代价将会是0.625。

总结以上，gx_α用于判断CAOI模型是否选择一个倍位，px_α用于计算选择一个倍位后的 代价值。则目标函数最小化惩罚函数值可表述为：

$f_4={\Sigma }_{\beta =1}^{{\mathrm{cb}}_p}{\mathrm{px}}_{{\pi }_{\beta }}/{\mathrm{cb}}_p---\left(14\right)$

（5）目标函数

本发明实施例在求解SBAP问题时，不仅考虑了式11至13所示目标函数，同时也将惩 罚函数（式14所示）列入最终目标函数中。通过惩罚函数的约束，可使求解SBAP问题时， 算法会结合真实堆场情况进行决策。例如，当算法决策出倍位中某一箱位时，若箱位下面有 其他船舶集装箱，且装船时间先于当前集装箱，那么使用惩罚函数，可使算法在演化过程中 尽量避免这种决策，使得整体目标函数结果符合实际预期。

                                     f＝min{f₁+f₂+f₃+f₄}   （15）

约束条件：

倍位内箱量约束，倍位内总箱量不能超过Rn×Tn-3，该值3根据倍内翻箱时所需要空位 的经验值得出。

基于以上建立的模型，下面对实施例的实现过程进行说明：

BAP模型实现：

基于改进UNTBB的BAP模型实现

本发明在利用UNTBB模型求解BAP问题时，考虑到BAP问题自身特点，诸如相邻箱 组尽量分配到不同箱区，最小化箱区到泊位的距离等目标函数，本发明采取改进的随机杀死 物种过程和选择岛屿过程。再者，UNTBB模型是一个完全随机的过程，其达到生态平衡需耗 费很长时间，因此，本发明对UNTBB模型进行适用于BAP问题的改进，经过改进的UNTBB 模型具体算法中包含有以下操作步骤：

（1）初始化分组：利用现有技术中的最优子种群遗传算法（Monkey King Genetic  Algorithm,MKGA），将所有出口箱箱区划分为若干组，确保每组之间的目标函数值（最小化 所有箱区到泊位的距离，同时保证箱区的空闲箱量分布均匀）的差尽可能小，从而保证分组 公平。该操作是为了缩小求解范围。

$u_1={\Sigma }_{e=1}^{L_n/G_n}{\Sigma }_{p=1}^{G_n}{d}_p/L_n/G_n---\left(17\right)$

$u_2={\Sigma }_{e=1}^{L_n/G_n}{\Sigma }_{p=1}^{G_n}{c}_p/L_n/G_n---\left(18\right)$

${{\sigma }_1}^2={\Sigma }_{e=1}^{L_n/G_n}{({\Sigma }_{p=1}^{G_n}{d}_p-u_1)}^2/L_n/G_n---\left(19\right)$

${{\sigma }_2}^2={\Sigma }_{e=1}^{L_n/G_n}{({\Sigma }_{p=1}^{G_n}{c}_p-u_2)}^2/L_n/G_n---\left(20\right)$

                                           min{σ₁²+σ₂²}   （21）

式（17）、（19）分别表示分组内箱区到船舶停靠泊位距离的期望和方差，式（18）、（20） 表示分组内箱区空闲箱量的期望和方差。式（21）表示要确保分组之间的箱量差和到泊位距 离差最小，同时也是最优子种群遗传算法进行分组的评价函数。

例如，L_n＝20，Ｇ_n＝5，则20个岛屿可以划分为4个分组。图10中(a)描述MKGA算 法中染色体编码过程，共有5个染色体（每个染色体含4个基因），20个基因分别标为1、2、 3、4、5、6、7、8、9、10、11、12、13、14、15、16、17、18、19、20。图10中(b)描述染 色体杂交过程，其中猴王染色体、父代染色体、子代染色体、修正后的染色体分别如图。图 10中(c)描述染色体变异过程，其中父代染色体、子代染色体、修正后的染色体分别如图。。

（2）物种分配：利用贪心策略在组内岛屿中随机选择若干个岛屿作为物种生存岛屿， 将物种分配到选定的岛屿内，确保目标函数值较优。

（3）随机杀死：对分组内选中的岛屿上的物种进行随机杀死操作，如有存在捕食关系 物种则大概率杀死任一物种，为了保证相邻箱组尽量不分配在一个岛屿。

（4）后代产生：后代产生包含两部分——变异和遗传。变异操作，则在同组其他岛屿 上的物种中随机选择一个物种，作为变异的下一代；遗传操作，则在本岛屿上杀死的物种中 进行随机选择，作为遗传的下一代。由于后代产生操作后，可能导致组内岛屿上物种数量超 过物种限制，则进行修正操作。

（5）修正操作：检查同组岛屿内没有相同的物种，检查同组岛屿内的物种数与原始物 种保持一致。

（6）组内物种迁移（Within-Group Stragety）：遍历已经分配了物种的所有岛屿，将该岛 屿上的随机一个物种迁移到一个岛屿。

（7）组间物种迁移（Among-Group Stragety）：遍历所有分组，在分组内随机选择一个 已经分配了物种的岛屿，将其物种集体迁移到其他分组的一个岛屿上。

实施例中基于改进UNTBB的流程步骤：

Step1:通过最优子种群遗传算法将所有出口箱区划分为L_n/G_n个组。

Step2:开始进行生态中性理论迭代求解最优解。

Step2.1:针对每个分组进行以下操作：

Step2.1.1:将组内的箱区看作若干个岛屿，将箱组看作若干物种。根据船舶长度 计算需要分配的箱区数(由港口船舶泊位与岸桥、岸桥与箱区之间的对应关系确定， 具体实现为现有技术)，也就是岛屿数目。

Step2.1.2:物种分配操作

Step2.1.3:根据式（8）进行组内中性算法迭代。判断是否满足迭代结束条件， 如果迭代未结束，则转Step2.1.4，否则转Step4

Step2.1.4:随机杀死操作

Step2.1.5:后代产生操作

Step2.1.6:修正操作

Step2.1.7:组内物种迁移

Step2.2:保存最优解

Step2.3:组间物种迁移操作

Step2.4:保存最优解,判断是否满足迭代结束条件，如果迭代未结束，则转Step2.1，否 则转Step3

Step3:产生最优解

Step4:算法结束

具体实施时，可由本领域技术人员设定迭代结束条件，例如设定迭代次数阈值。

SBAP模型实现：

基于组合元胞自动机的SBAP模型描述：

本发明提出基于组合元胞自动机的SBAP问题求解模型，文中定义为CAOI模型。同时， 定义外层元胞模型（CAO）用作求解倍位分配问题，内层元胞模型（CAI）用作求解进场选 位问题。如图11所示，CAOI模型求解分为2步，首先在箱区中选择若干倍位存放集装箱（即 CAO模型）；然后再在选择的倍位内堆放集装箱（即CAI模型）。如图11中(a)，65个集装箱 选择空闲箱量为21、10、21、16（图11(a)中阴影方格）的4个倍位，如图11中(b)所示，65 个集装箱集港时堆存在上述选中的4个倍位中。

CAO模型求解倍位分配问题

CAO用于求解倍位分配问题。倍位分配问题是在指定箱区内寻找若干倍位，满足倍位 之间负载均衡，且装船时集卡到泊位的运输距离最小。如图12所示，CAO是针对该箱区中 所有倍位进行元胞自动机建模，用于解决SBAP问题中步骤1所描述的子问题。12个倍位的 倍位编号为1、2、3、4、5、6、7、8、9、10、11、12。

如图13所示，CAO模型中研究对象为倍位，决策目标为倍位是否分配，以及分配的箱 位数目是多少。其中，用0表示不分配，1表示分配。CAO元胞模型采取一维元胞，其定义 如下：

元胞：箱区中倍位，图13中每个倍位都是一个元胞。

元胞空间：箱区中全部倍位集合。元胞空间的边界采取周期型边界。

元胞状态：若某一倍位α已被分配，则用A_α表示已分配的箱位数目；若该倍位未被分配， 则用C_α表示该倍位可被分配的空闲箱位数目。则当前时刻t元胞状态定义为：用来表示 该元胞是否被激活。该元胞被杀死（则表示未选择该倍位）；该元胞被激活 （则表示选择当前倍位）。

元胞邻居：中心元胞的左右节点，如果用表示当前元胞节点，则其邻居节点为：和

元胞状态转换规则：考虑中心元胞与其左右邻居的当前状态，根据三者的状态决定下一 时刻t+1的元胞状态，表示为：由于每个元胞只有2种 状态（0和1），因此该规则可根据自变量映射出8组元胞状态，如下表6。

表6CAO元胞状态转换规则

由于在CAO模型中元胞状态转换时，可选择从左至右开始转换，也可选择从右至左开 始转换，亦或者是两者相结合，因此本发明提出可采用以下4种元胞状态转换规则次序：（1） Front-End（FE）：从左至右进行CAO元胞空间规则转换。（2）End-Front（EF）：从右至左进 行CAO元胞空间规则转换。（3）FEEF：先从左至右，再从右至左进行CAO元胞空间规则转 换。（4）EFFE：先从右至左，再从左至右进行CAO元胞空间规则转换。

CAI模型求解进场选位问题

CAI用于求解进场选位问题。进场选位问题是在已分配的倍位中寻找合适箱位，堆放即 将到场的集装箱，满足倍位内压箱数总和最小，场桥移动次数最小。如图14所示，CAI是针 对已分配的倍位中所有空闲箱位进行元胞自动机建模，用于解决SBAP问题中步骤2所描述 的子问题。

如图15所示，CAI模型中研究对象为具体的箱位，决策目标为当前到港集装箱堆放在哪 个倍位中的箱位。CAI元胞模型采取二维元胞，其定义如下：

元胞：倍位中的箱位（通过排、层来描述一个箱位），图15中每个箱位都是一个元胞。

元胞空间：已分配倍位集合中所有空闲箱位集合。元胞空间的边界采取周期型边界。

元胞状态：用来表示当前时刻t元胞α是否被激活。该元胞被杀死（则表示未 选择该箱位）；该元胞被激活（则表示选择当前箱位）。

元胞邻居：本发明实施例采取Moore型邻居，即中心元胞的上、下、左、右、左上、右 上、右下、左下相邻八个元胞。

元胞状态转换规则：以元胞的一列为单位（即倍位的一排），从左至右，统计每一列的 平均重量级（即该列中所分配的集装箱平均重量级），将平均重量级调整为越靠近集卡车道， 平均重量级越大，如图16所示，有7个重量级。CAI元胞状态转换时，按列计算平均重量级， 转换后，平均重量级从左至右依次减小。

LCBB算法求解进场选位问题

本发明采用现有技术中基于优先队列的分支限界法（简称LCBB）进行元胞的初始化。 具体实施可参考相关文献，为便于实施参考起见，提供说明如下：

（1）优先队列策略

按照优先队列中规定的优先级选取优先级最高的活结点成为当前扩展节点。在本发明实 施例中，提出两种优先队列的优先级计算方法。以下符号定义用来描述优先队列优先级计算 策略：

表7LCBB算法参数定义

①LCBB优先队列策略一（ST1）

ST1＝(r+1)/idx，仅考虑编号为idx的集装箱落箱后，造成已经落箱的idx个集装箱 中，压箱所占的比例。

②LCBB优先队列策略二（ST2）

在ST1的基础上，预测后续（N-idx）个集装箱落箱后，会造成 的压箱比例。

（2）剪枝策略：在分支扩展过程中，一旦发现一个节点的压箱数不小于当前已找到的 最小压箱数，则剪去以该节点为根的子树。

（3）求解过程：

步骤①减小搜索空间。由于分支限界法是基于广度优先搜索，当分支节点数目较多时， 会消耗较大内存，且解空间较大。因此本发明实施例在研究倍位的特性基础上，提出一种可 用于减小搜索空间的策略。

如图17所示，本发明实施例提出一种排相似定义，如果两个排中堆存情况一致（同时 为空，或者堆放的集装箱重量级完全相同），则称为两个排相似。例如图17所示，排1、5、 6都是空排，则它们互为相似；排3、4堆存有相同重量级的集装箱，则它们也互为相似；排 2与其他排都不相似。

步骤②分支节点扩展。假设倍位初始状态如图17所示，基于排相似定义，符合排相似 的箱位被去重（例如排3、4,相似，则选择箱位时，取任一排的空闲箱位即可，比如箱位（3,2））， 则扩展第一个节点时，可选箱位为（1,1）、（2,1）、（3,2）。

步骤③扩展节点入优先队列。按照步骤②进行节点扩展后，按照本发明实施例提出的优 先队列策略（ST1或者ST2）分别计算每个节点的优先级，将节点加入优先队列。

以上算法结束条件：本发明在倍位中求解进场选位问题，当优先队列第一次搜索到最终 结果时，即返回结果。本发明基于实际堆场应用进行研究，如果采用分支限界搜索最优解， 那么在某些复杂用例下，算法耗时将会巨大。故本发明折中求解较优解。

提供算法求解示例：假设来箱序列为2、5、1、2、6、1（该数字表示集装箱的重量级） 的集装箱堆存在一个空倍位中。

本实施例中按照ST1优先策略计算优先级。则根据LCBB算法的求解步骤如表8所 示，计算结果如表9所示。表8中PUSH表示入队操作，POP表示出队操作。

表8LCBB算法求解步骤

表9LCBB算法求解结果

（4）算法性能：算法的理论复杂度为O(2ⁿ)，但通过限界策略，并没有搜索子集树中的 所有结点，且由于每次都是选取最接近最优解的结点扩展，所以一旦搜索到最终节点时算法 就可结束。实验证明本发明算法可在秒级时间求出较优解。

实施例采用CAOI模型求解SBAP模型说明如下：

CAOI模型中有关定义如下：

元胞：将倍位分配和进场选位两阶段的任一组合可行解（本发明定义为Solution）作为 一个元胞。图18中包含3组组合可行解，例如Solution3中选择倍位3、4、5、6，并分别堆 存13、21、21、10个集装箱。

元胞空间：C×C的四方格网络，则可同时进行C×C组元胞变换。元胞空间的边界采 取周期型边界。

元胞状态：P_l表示当前中心元胞自身变换最优解，l为相应节点编号；P_g表示中心元胞的 邻居节点中最优解，g为相应节点编号。文中定义当前时刻t的两种元胞状态，和用于描述在当前时刻t，中心元胞自身变换最优解状态；用于描述当前时刻t，中 心元胞邻居节点中最优解状态。和根据式（22）所述状态转换规则进行状态改变。

元胞邻居：本发明实施例采取Moore型邻居，即中心元胞的上、下、左、右、左上、右 上、右下、左下相邻八个元胞。

下一时刻t+1的元胞状态转换规则：

$S_l^{t+1}\left(P_g\right)=f(S_l^t\left(P_l\right),S_{l+{\omega }_1}^t\left(P_{l+{\omega }_1}\right),S_{l+{\omega }_2}^t\left(P_{l+{\omega }_2}\right)...S_{l+{\omega }_n}^t\left(P_{l+{\omega }_n}\right)),$其中l+ω_x，(1≤x≤8)表示 中心元胞的邻居节点。ω_x表示中心元胞的邻居节点编号。如果用表示中心元胞的 适应值，则状态转换规则为：

$S_l^{t+1}\left(P_g\right)=\min \{\mathrm{fit}\left(S_l^t\left(P_l\right)\right),\mathrm{fit}\left(S_{l+{\omega }_1}^t\left(P_{l+{\omega }_1}\right)\right),\mathrm{fit}\left(S_{l+{\omega }_2}^t\left(P_{l+{\omega }_2}\right)\right)...\mathrm{fit}\left(S_{l+{\omega }_n}^t\left(P_{l+{\omega }_n}\right)\right)$

（22）

CAOI模型框架如表10所示：

表10CAOI模型框架

本发明区位计划决策目标是将不同船舶的箱组分配到箱区，不仅要获取最优解，同时要 保证解的可行性和灵活性。经典的生态中性理论模型是一个完全随机的过程，其认为个体具 有同等生存权利，群体通过完全随机的生灭过程来达到生态平衡，这与本发明研究的区位计 划具有相同之处。本发明研究生态中性理论模型，在此基础上进行改进并应用到集装箱码头 堆场中区位分配问题，并且建立数学模型和算法来实现该问题。实验表明本发明提出的基于 生态中性理论的区位计划模型在耗费一定计算时间的代价下，对于解决港口中区位分配问题 有一定优化。本发明针对BAP问题的主要研究结果如下：

（1）提出分组策略。为了在全局范围内搜索解，本发明在尽量满足区位计划业务规则 和相关约束条件下，对基本中性理论模型进行改进，提出了分组生态理论模型。

（2）构建存在捕食关系的物种间大概率杀死其中任一物种的策略，使得满足约束条件： 相邻箱组尽量不分配在一个箱区中。从而令生态选择更有趋向性。

（3）贪心策略选择岛屿等改进措施，使得生态选择更有趋向性，便于发展最优解。

（4）根据实验结果确定UNTBB模型中各个参数取何值时，算法能取得最优解。

本发明提出基于组合元胞自动机模型针对SBAP问题进行求解。CAOI模型负责对外元 胞CAO模型、内元胞CAI模型进行组合优化，CAO模型用于求解倍位分配问题，CAI模型 用于求解集装箱进场选位问题。CAI模型采取基于优先队列的分支限界法（LCBB）求解进场 选位问题，为了尽快求取结果，LCBB算法一旦寻找到最终路径则会终止循环，返回结果。 CAO模型采取二进制状态转换求解倍位分配问题，本发明提出四种二进制状态转换规则，分 为FE、EF、FEEF、EFFE。CAO、CAOI模型采取元胞空间循环演化方式求解。本发明针对 SBAP问题的主要研究结果如下：

（1）提出CAOI模型用于求解SBAP问题，将倍位分配—进场选位过程进行双目标优 化。

（2）CAOI模型由CAO外元胞模型和CAI内元胞模型组成，CAO模型与CAI模型通 过判断函数和代价函数关联，实现组合优化的效果。

（3）CAO模型中提出二进制元胞状态改变策略——EFFE策略；CAI模型中提出基于 ST1优先策略的分支限界法求解进场选位问题。

（4）通过大量实验证明，CAOI模型中参数取何值时能求得最优解，CAOI模型求解与 本发明实验中的来箱序列分布无关，CAOI模型在堆场随机初始化状态下，表现良好。

本发明中所描述的具体实施例仅仅是对本发明精神作举例说明。本发明所属技术领域的 技术人员可以对所描述的具体实施例做各种各样的修改或补充或采用类似的方式替代，但并 不会偏离本发明的精神或者超越所附权利要求书所定义的范围。