基于网络流的自动化集装箱码头堆场空间分配

梁承姬 贾 茹 盛 扬

(上海海事大学物流研究中心 上海 201306)

0 引 言

随着经济的发展，码头的集装箱处理量大幅增长，但堆场的面积却相对有限。同时，由于人工成本快速上涨、船舶大型化加速，码头自动化成为业界关心的话题。由于船边作业的干扰因素较多，堆场的自动化就成为自动化码头重点关注的领域。本文以2017年试运营的洋山港四期全自动化集装箱码头为背景，对自动化集装箱码头的堆场堆存问题进行研究。

国内外对堆存计划的研究大多是针对传统集装箱码头的。李建忠等[1]为平衡堆场的集装箱数量和最小化集卡的运输作业距离，建立堆场空间动态分配模型，并应用数学规划法求解。王孟昌[2]将堆场箱位动态分配问题分为箱区分配和箱位选择。在计算箱区分配时，建立平衡箱区间作业量模型和最小化箱区泊位间距模型。接着，以翻箱量最少为目标建立了箱位选择模型，并采用启发式算法和模拟退火算法求解。Joörg Wiese 等[3]分别研究了平行分布和垂直分布的箱区运输通道的资源优化问题，提出了关于堆场布局的整数线性规划问题，并用一种启发式算法求解。Nils[4]研究了自动化轨道吊对堆场箱区作业效率的影响，使用仿真的方法模拟了堆场箱区的作业情况，并评估比较了四种具有不同自动化轨道吊的堆场箱区对集装箱码头性能的影响。Yu等[5]针对进场集装箱的空间分配问题提出了一个优化方法，提高检索进场集装箱的操作效率，减少预期的外部集卡的等待时间。周鹏飞等[6]为优化卸船箱箱位分配，减少翻箱率，考虑客户提箱顺序的随机和不确定性，建立船舶卸载箱位整数规划模型，采用启发式算法来求解。结果表明能有效减少翻箱率。对于网络流问题，赵礼峰等[7]给出了一种求解网络最小费用最大流的新方法，令该算法易于理解，且能够避免最小费用路算法需要对剩余网络进行增广的不足之处，提升了算法效率。Han等[8]提出基于不确定性理论框架去解决一个不确定网络中的最大流问题。

目前国内外将自动化集装箱码头的堆存问题按其特点转化为网络流问题进行研究的较少。自动化集装箱码头的箱区呈垂岸式分布，进出口箱混堆模式。从箱区的布局图1中可以看出，按两台起重机的作业范围可分为海侧，交换和陆侧作业区域。由于集装箱只能从箱区两端进出，在这三个区域流入与流出的集装箱量均相等。因此在制定堆存计划时需要考虑所有箱区之间的作业量和单个箱区作业的进出口箱量的平衡，以满足箱区海侧起重机作业的重进重出。本文提出基于网络流的自动化集装箱码头堆场空间动态分配的模型，并用禁忌搜索算法来求解，突出了自动化集装箱码头堆场的布局特征以及在制定堆存计划时的特点。

图1 箱区示意图

1 问题描述

自动化集装箱码头的堆场堆存计划可以视为一个具有时间和空间维度的网络优化问题。如图2所示，本文将具有相同属性的集装箱归并为一个集装箱组k。这里的相同属性可以是箱子重量、箱子种类和箱子的目的港等。起始节点和结束节点分别标注为Sk和Tk。集装箱组k在时间点ak到达码头，并在时间点bk离开堆场。它的停留期间是从ak到bk，每一个时段都有m个备选的堆场箱区来存储这一组集装箱。从起始节点到结束节点的路径对应这组集装箱到达泊位以后在堆场的堆存计划。泊位和堆场之间的弧形虚线箭头代表码头和堆场之间的移动，堆场箱区之间的弧形虚线箭头代表连续时间段内的集装箱组的再分配。弧形的成本取决于两个节点之间的作业距离与作业成本。图2中实线箭头表示的路径显示了一组集装箱的一个可行的泊位配置和堆存计划。如图2所示，集装箱组k到达泊位1，从进港船舶上卸载后分配给堆场1，然后停留在堆场1中直到时间点bk-1被重新分配给堆场2，最后一直停留在堆场2直到时间点bk被分配到虚拟节点2，即被外集卡装走。

图2 箱区网络节点示意图

2 模型建立

本模型意在实现集装箱组在泊位-箱区间、箱区-箱区间的运输总成本最小以及集装箱组在堆场箱区的合理分散。

2.1 模型假设

(1) 已知某一天进港船舶预靠的泊位；

(2) 已知船舶各时间段要完成的进口箱组数量和出口箱量组数量；

(3) 时间段t内装卸移动的集装箱组均在该时段完成作业；

(4) 已知每个集装箱组包含的集装箱数量；

(5) 所有集装箱组包含的集装箱不分类型，统一尺寸定为20尺。

2.2 符号说明

参数：M：箱区

N：泊位

T：时间周期

K：集装箱组

ak：集装箱组的到达时间，ak∈T

bk：集装箱组的离开时间，bk∈T

qk：集装箱组k包含的集装箱数量

ok：卸载集装箱组k的进口船

dk：卸载集装箱组k的进口船

rk：集装箱组k允许在堆场箱区间重新分配的最大次数

αkl：如果集装箱组k和l从相同的进口船被卸载则为1，反之则为0，k,l∈K

βkl：如果集装箱组k和l衩装卸到相同的进口船则为1，反之则为0，k,l∈K

γkl：如果集装箱组k的进口船和l的进口船相同则为1，反之则为0，k,l∈K

δ：岸边和箱区之间允许行驶的最大行驶成本

ω1：箱区重进重出的权重系数

ω2：箱区作业量平衡的权重系数

h：平衡箱区作业成本和箱量的权重系数

决策变量：

2.3 目标函数及约束条件

目标函数：

Z=min(Z1+h×Z2)

(1)

约束：

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

式(1)的目标函数表示的是最小化泊位和箱区，箱区和箱区之间的运输成本;平衡单个箱区和所有箱区的进出口箱量。

式(2)约束了开始节点的流出需求。式(3)约束了结束节点的流入需求。式(4)表示箱区之间的流量守恒。式(5)、式(6)定义了决策变量Z、U、V之间的关系以及箱区里进、出口箱量的定义。式(7)、式(8)定义了决策变量U、V、X之间的关系，表明从泊位i到箱区j的集装箱组必然从箱区j移动到箱区i。从箱区i到泊位j的集装箱组在前一个时段必然从箱区j移动到箱区i。式(9)、式(10)指定了泊位和箱区之间的行驶成本要求，确保堆存的箱区离船舶的距离不会过远。式(11)、式(12)、式(13)定义了代表集装箱位置的决策变量W，箱区之间的位置；出口箱在离开时的位置；在泊位作业的进口箱和出口箱。式(14)表示同一时段内所有集装箱组需要的存储空间不能超出箱区存储能力。式(15)表示同一时段内所有集装箱组需要的处理量不能超出泊位处理能力。式(16)表示同一时段内所有集装箱组需要的处理量不能超出箱区处理能力。式(17)定义了集装箱组的重新分配次数不能超过最大允许重新分配次数。式(18)定义了有相同进口船或出口船的集装箱组的泊位分配约束。式(19)定义了决策变量的范围。

3 基于禁忌搜索算法模型求解

禁忌搜索算法通过采用禁忌表来记录被禁止的对象，避开局部最优解从而找到总体最优解。被放入禁忌表的是属于被禁止的局部最优解。进入禁忌表的对象在接下来的若干个迭代次数内被禁止，从而避免陷入局部最优解的循环。本文的禁忌长度数值为一个常数，具体数值根据问题的规模大小来确定。

3.1 禁忌搜索算法的使用

将自动化集装箱码头堆场的堆存计划转化为网络流问题，得到泊位与箱区之间、箱区与箱区之间的集装箱堆存总成本以及堆场箱区的“重进重出”和作业量均衡。

禁忌算法的初始解可以通过随机生成得到，但是通过改进初始解的生成可以提高搜索效率。在堆存策略制定的初始阶段，本文采用指派模型来生成初始解，通过该方法生成的初始解来进行搜索可以提高整体的运算效率。堆存计划的集装箱组分配的初始解采用贪婪算法获得，在贪婪算法中，按次序将待分配的集装箱组依次分配到满足容量的距离最近的堆场箱区。

图3展现了一个在三个时间段中两个集装箱组分配到两个箱区的例子。堆场容量被假设为是相同的，都为Q。在网络容量充足的情况下，集装箱组1首先被装载到网络，它的最小成本路径：S1→(2,1)→(2,2)→(1,3)→T1，如图3(a)中实线箭头所示。然后，网络的装载能力被更新，如图3(b)所示，集装箱组2被装载到网络中。由于装载能力有限，集装箱组只有一个可行路径：S2→(1,2)→(2,3)→T2。最后，网络剩余量如图3(c)所示，并且通过相加两个路径的成本，可以得到目标函数值。必须注意的是：对集装箱不同的装载次序会导致不同的解决方案和目标值。

图3 网络节点示意图

如何选择一个好的次序将集装箱装载到网络中去是一个非常关键的问题，通过这样可以得到一个近似最佳方案。在这一阶段中，禁忌搜索方法被用作去寻找好的装载次序。一个装载次序可以影响集装箱装载到网络中的次序。越先被运输的集装箱组就会有越大的网络容量。这表明越先装载的集装箱组，其优先级就越大。在每一次邻域搜索循环中产生邻域方案，并且在循环中评估它。

3.2 编码方式

L=(p1,p2,…,p|k|)，集装箱组pi是第i个被装载到网络中的。例如：L=(2,3,1)，表示集装箱组2是在网络装载能力充足时第一个被装载到网络中的，集装箱组3是第2个被装载的，集装箱组1是最后一个。

3.3 邻域结构

禁忌搜索算法是一种基于邻域搜索技术的算法，本文采用两两交换来实施操作。这种方法是通过随机选择任意两个对象并交换其数值的操作方式。具体的操作方式如图4所示。

图4 交叉操作示意图

3.4 适应度评价

根据集装箱组被装载到网络中的次序，采用表1的方法来计算适应度。在该算法中，最重要的一个步骤就是去寻找集装箱组的一个最小成本路径。由于节点的容量有限，所允许的再分配的次数会限制到路径的选择。

表1 适应度评价方

阶段变量：时间t∈T

阶段变量：节点(i,t)

最优值：L(n,i,t):从源点Sk经过几次再分配到达节点(i,t)的最小成本，P(i,t)：t时段在节点i的重进重出最优值。

递归函数：

L(n,i,t+1)=

λ2minP(i,t) ∀i∈N∪M,t∈T,ak≤t

边界条件：

L(n,ok,ak)=0 ∀n=0,…,rk,P(i,t)=0

最优解：

min{L(n,dk,bk) ∀n=0,…,rk},minP(i,t)=0

上述递归函数表示：如果没有进行重新分配，节点(i，t)与节点(i，t-1)的成本是一样的，因为没有操作成本的产生。但是，当重新分配必须进行时，后一节点的成本是前边在同一路径的所有节点成本的总和。在我们结算当前节点成本之前，应该对约束限制进行检查。只有满足能力需求时，节点的成本才能被递归函数计算。式中的P(i,t)则是用来评价堆场箱区中堆存集装箱的重进重出，即节点中进出口集装箱数量关系的一个评价标准。

当迭代次数达到预先设定的最大迭代次数时，进行终止操作。

4 算例分析

在本文中会展现算例实验的设计和结果，分别采用CPLEX求解器和禁忌搜索算法对模型进行求解，然后会对CPLEX和禁忌搜索算法结果的区别进行比较。

4.1 算例实验

自动化集装箱码头堆场的布局与传统集装箱码头差异较大，并且上海洋山深水港四期自动化集装箱码头仍在建设阶段，无法获得现实数据，因此算例的数据主要来自于实际项目研究的结果以及国外自动化集装箱码头现实情况的数据。

在选取算例数据时，本文采用3个泊位，9个箱区的码头布局来进行实验计算，然后通过改变时间周期的长短以及集装箱组数量的大小来产生不同的实验数据。在一台装有Intel 双核P8600@2.6 GHz处理器和2 GB内存的个人电脑上用MATLAB软件编写本文提出的禁忌搜索算法来求解算例。

具体的输入数据的信息如船舶信息，集装箱信息，泊位到箱区的距离等等如表2-表6所示。

表2 船舶相关信息

表3 t=1时船舶进口箱信息

表4 t=1时船舶出口箱信息

表5 泊位与箱区的距离

表6 各箱区其他信息

4.2 计算结果

通过使用禁忌搜索算法对问题进行求解，运算20次得到的平均最优值为4 131。t=1时的堆场箱区分配结果如图5所示，各箱区堆存的集装箱量如表7所示。进口集装箱和出口箱进入堆场到离开堆场的分配结果如表8和表9所示。禁忌搜索算法的收敛结果如图6所示，各时间段各箱区工作量如图7所示，t=1时堆场箱区作业的进出口箱量比例如图8所示。

图5 时间段t=1时堆场箱区分配图

船号进口箱出口箱11(2W)、2(2E)、3(1W)、4(2W)1(1L)、2(2L)、3(3L)、4(3E)21(5W)、2(5W)、3(6W)、4(4W)、5(3W)1(3L)、2(4L)、3(5L)、4(6L)31(4W)、2(5E)、3(4E)、4(3W)1(5E)、2(4L)、3(6L)、4(6E)41(7W)、2(7E)、3(8W)、4(8E)1(7L)、2(8E)、3(7E)、4(8L)51(9W)、2(8W)、3(7E)1(9E)、2(9L)、3(8L)、4(7L)注:W表示箱区的海侧区域,E表示箱区的交换区域,L表示箱区的陆侧区域;1(2W)表示箱区2的海侧区域堆存了船舶的1号进口/出口集装箱组

表8 进口箱组分配结果

续表8

表9 出口箱组分配结果

图6 TS的收敛图

图7 各时间段各箱区工作量折线图

图8 t=1时堆场箱区作业的进出口箱量比例

为了验证禁忌搜索算法的有效性，本文设计了10个算例，如表10所示，船舶数量从5到40，集装箱组数量从40到240，分别采用3个泊位9个箱区和5个泊位15个箱区的码头布局。用CPLEX和禁忌搜索算法进行计算，计算结果如表11所示，比较可以看出，禁忌搜索算法可以在更短的时间内找到一个较优的解，算例1-8中的最优值与增均值的平均差距小于5%，而在算例9-10中，由于算例规模较大，CPLEX不能找到可行解，而禁忌搜索算法可以找到较优的解。

表10 算例数据

表11 CPLEX和禁忌搜索算法计算结果的比较

续表11

4.3 结果分析

从图5和图7可以看出，在同个时间段内作业的进口箱和出口箱均衡地分配在堆场的箱区中，虽然集装箱的运输距离较长，但是各个箱区之间的作业量差距比较平缓，且每个箱区都尽量做到了让同一时间段内作业的进口箱和出口箱数量的差值最小化，从而满足堆场箱区的“重进重出”。从图8可以看到在时间段t=1时堆场各个箱区作业的进口箱和出口箱量的比例，当比例数值越相近时则表明该时间段内箱区起重机的利用率越高，空载率越少，即最大化的满足了“重进重出”这一要求。最后分别采用CPLEX方法和禁忌搜索算法对相同算例进行求解，实验结果表明，禁忌搜索算法在求解速度上较为占优。虽然与CPLEX求得的最优解平均有5%左右的差距，但是在较大规模的问题上，CPLEX无法找到可行解而禁忌搜索算法可以实现。

5 结 语

本文主要研究自动化集装箱码头的实际堆场空间分配问题，以上海洋山深水港四期在建的自动化集装箱码头项目为研究背景进行研究，提出了一个基于网络流的自动化集装箱码头堆场空间动态分配模型，通过网络流的形式体现一个个集装箱组在堆场和堆场箱区中的移动状态来反映堆场实际的作业过程。通过将集装箱按某些共同属性归为一组进行统一作业可以更好地管理码头堆场的堆存作业。通过考虑“重进重出”可以更好地利用堆场箱区起重机，减少起重机的作业负担，达到最大化的利用率。

[1] 李建忠,丁以中,王斌.集装箱堆场空间动态配置模型[J].交通运输工程学报,2007,7(3):50-55.

[2] 王孟昌.集装箱码头堆场箱位动态分配优化策略研究[D].武汉:武汉理工大学,2007.

[3] Wiese J,Suhl L,Kliewer N.Mathematical models and solution methods for optimal container terminal yard layouts[J].OR Spectrum,2010,32(3):427-452.

[4] Kemme N.Effects of storage block layout and automated yard crane systems on the performance of seaport container terminals[J].OR Spectrum,2012,34(3):563-591.

[5] Yu Mingzhu,Qi Xiangtong.Storage space allocation models for inbound containers in an automatic container terminal[J].European Journal of Operational Research,2013,226(1):32-45.

[6] 周鹏飞,李丕安.集装箱堆场不确定提箱次序与卸船箱位分配[J].哈尔滨工程大学学报,2013,34(9):1119-1123.

[7] 赵礼峰,白睿,宋常城.求解最小费用最大流的新方法[J].计算机技术与发展,2012,22(5):94-96.

[8] Han Shengwei,Peng Zixiong,Wang Shunqin.The maximum flow problem of uncertain network[J].Information Sciences,2014,265(5):167-175.

[9] Lee B K,Kim K H.Optimizing the yard layout in container terminals[J].OR Spectrum,2013,35(2):363-398.

[10] 陈宇.集装箱码头基于作业路的堆场空间分配策略研究[D].上海:上海海事大学,2010.

[11] 毛钧,李娜,靳志宏.基于混堆模式的集装箱码头堆场空间资源配置优化[J].大连海事大学学报,2014,40(1):117-122.

[12] Kim K H,Lee J S.Satisfying Constraints for Locating Export Containers in Port Container Terminals[C]//International Conference on Computational Science and Its Applications,2006:564-573.

[13] Fu Z,Li Y,Lim A.Port Space Allocation with a Time Dimension[J].Journal of the Operational Research Society,2007,58(6):797-807.

[14] Gao Y.Uncertain models for single facility location problems on networks[J].Applied Mathematical Modelling,2012,36(6):2592-2599.

[15] Gao Y.Shortest path problem with uncertain arc lengths[J].Computers & Mathematics with Applications,2011,62(6):2591-2600.

[16] Myung Y S,Moon I.A network flow model for the optimal allocation of both foldable and standard containers[J].Operations Research Letters,2014,42(6):484-488.