基于属性分类的出港集装箱箱位分配问题研究

姜 伟，毛诗敏

（浙江师范大学 工学院，浙江 金华 321004）

基于属性分类的出港集装箱箱位分配问题研究

姜 伟，毛诗敏

（浙江师范大学 工学院，浙江 金华 321004）

在对出港箱按属性分类并定义组、簇、批的基础上研究出港集装箱的箱位分配问题，从优化物流输入环节来减少装船时的倒垛数。通过引进批的位置变量、组与垛关系变量和每个位置的倒垛变量，并以组与垛的关系、箱位使用原则和状态、批的箱量守恒以及不同批间倒垛关系为约束对该问题建立非线性整数规划模型，目标是实现装船时各街区箱量均衡、集卡运输距离最短和装船时一定发生倒垛的集装箱数最少。利用等价变换将该模型转化为优化软件可直接求解的线性模型，并实例验证模型的有效性。

出港集装箱；属性分类；箱位分配；集成模型

1 引言

近年来随着全球化和经济一体化的快速发展，国内和国际货物的运输量不断增长，这种增长趋势对为货物的运输、装卸、包装、仓储、配送及信息管理提供相应服务并保证货物安全准时到达的物流业提出了更高的要求。港口作为货物海陆联运的枢纽，是物流体系中一个不可替代的重要节点。在港口中堆场空间是一种稀缺资源，在集装箱的货流量不断增加的环境下，如何管理码头堆场系统，为每个集装箱分配合理的箱位进而提高装卸效率和码头服务水平，成为码头管理者和学术界关注的热点问题。

合理分配出港箱在存入堆场时的箱位可以提高堆场中集装箱的装船效率，从而缩短船的在港时间。集装箱堆场箱位分配问题包括两个阶段，第一阶段(宏观层面)是空间分配阶段，用来决策分配到每个街区的箱量；第二阶段(微观层面)是具体位置分配阶段，用来决策每个箱的具体箱位(由街区号、贝号、行号和层号确定)，使得在提取过程中总倒垛数最少，所以也将第二阶段问题称为倒垛问题。

对于第一阶段的空间分配问题，Bazzazi等[1]{Bazza-zi,2009#7}使用遗传算法求解具有不同类型的进港箱的空间分配问题，目标是街区间的工作量平衡。徐亚等[2]对出口箱空间分配问题提出以集卡运输距离最短和工作量平衡为目标的多目标规划模型，并采用改进的线性功效系数法将模型转化为单目标整数规划模型进行求解。严南南和崔景云[3]以箱区贝位间作业量的平衡和龙门吊的使用数量最小为目标建立两层数学模型，确定不同尺寸集装箱分配到各箱区贝位中的具体数量。檀财茂等[4]从考虑码头资源紧缺的角度将堆场空间分配问题分解成两个连续的问题：第一个问题模型以最大化箱区的空间利用率来确定箱区航线配对组合情况；第二个问题模型将第一阶段已经配对好的航线组合指派到堆场中的具体箱区。

对于第二阶段的具体位置分配问题，Wan等[5]对静态倒垛问题（当一个贝位的初始堆垛状态及集装箱的提取顺序给定时，如何决策倒垛箱在该贝位中的位置使得提取过程中总倒垛数最少）首次建立整数规划模型，然后提出多种启发式算法验证算法的有效性。徐亚等[6]对同样的问题提出启发式算法及其改进算法，并通过仿真实验验证算法的有效性。Caserta等[7]首次证明了静态倒垛问题是NP难问题。Zehendner和Feillet[8]首次使用基于数学规划的branch and price方法来解决静态倒垛问题。Tang等[9]对Wan等[5]提出的整数规划模型进行改进，并提出有效的启发式规则。

本文的主要贡献在于通过对出港集装箱按属性分类并引入组、簇、批的定义，从一个新的角度将空间分配问题和具体箱位分配问题这两个阶段集成起来解决堆场箱位分配问题，从而在物流输入环节控制影响装船效率的因素。针对出港集装箱的箱位分配问题，引进与组和批相关的决策变量，建立非线性0-1整数规划模型来达到提高装船效率的目标。通过等价变换，将其转化为线性规划模型并利用优化软件CPLEX进行有效求解。

2 出港集装箱的分类及问题描述

集装箱码头为了有效地提高堆场空间利用率，通常采取将多个集装箱按垂直方向向上堆垛的方式进行堆存。集装箱的这种堆放方式虽然具有高密度和高空间利用率的特点，但在提箱的过程中有可能产生不必要的倒垛而影响提箱的效率。如果待提取的目标箱上面放有其他箱，那么就产生了压箱。为了要提出该目标箱，必须先将压在其上面的箱暂时移到其他箱位，这种临时的集装箱移动称为倒垛。堆场中无论任何时段任何操作都不希望有倒垛发生，因为倒垛操作大大降低了工作效率，增加了操作成本，因此有效减少倒垛数是集装箱码头操作中另一个研究热点。

由于出港集装箱可以根据所属船舶、箱型、到港站、重量级别等属性进行分类，且所有属性均相同的出港箱在装船时可以相互替换，因此根据配载计划进行装船时，通过提取属性相同的箱中压箱数最少的箱可以减少倒垛的发生，提高装船效率。因此当出港箱由外部集卡运进堆场时，采用按属性归类后再分配其在堆场中箱位的方法可以从物流输入的源头上控制装船的倒垛量。假设所有出港箱的箱型都相同，图1为出港箱根据所属船舶、到港站、重量级别分类的示意图。将要装上同一条船的出港箱定义为一组(group)。为了操作方便和避免倒垛，在实际的堆场操作中，不同船的箱不会混放到同一垛中，因此不同组的箱不能放在同一垛中；然后对同一组中的箱根据到港站的不同进行分类，将同组且到港站相同的箱定义为一簇(family)；最后对同一簇中的箱根据重量级别的不同进行分类，将同簇中重量级别相同的箱定义为一批(batch)。根据上述定义，同批中的箱由于属性完全相同，即使放在同一垛中也不会发生倒垛，因此倒垛操作只能发生在同组但不同批的箱之间。对出港集装箱引入批的概念后，不需要决策某个具体箱是否放在某个箱位，而只需决策某一批中的箱是否放在某个箱位。因此，通过引入与批相关的决策变量后，堆场箱位分配问题中用来决策每个箱位置的位置变量就会明显减少，便于建模求解。

根据集装箱船的基本配载原则可以确定不同批的出港集装箱装船时的先后顺序。首先，为了避免在集装箱船上发生倒垛，要求集装箱船上到港站远的箱不能压在到港站近的箱上面，因此装船时要先装到港站远的箱再装到港站近的箱；其次，为了保证集装箱船的稳定性，配载时要将重量级别高(重)的箱放在船的下面，因此装船时要先装重量级别高的箱再装重量级别低的箱。

根据上面出港集装箱的分类及不同类别集装箱的装船顺序，基于属性分类的出港集装箱箱位分配问题描述如下：在某一给定的时段，堆场的初始堆垛状态非空且已知，该时段内外部集卡向堆场运进出港箱的数量已知，这些出港箱在运进堆场时其所属船舶、到港站和重量级别等信息便可以获得。该时段内到港的船泊数量及停靠的泊位已知，并且每条船的停靠泊位与堆场中每个街区的距离给定。根据每个箱的属性可以按照上面的分类原则将其分批。我们的问题就是要决策分批后的集装箱在堆场中的具体箱位，目标是各街区的工作量均衡、装船时集卡在街区和船间运输的总距离最短和发生倒垛的集装箱数最少，从而保证装船效率。

图1 出港集装箱按属性分类示意图

3 数学模型

根据出港箱的分类及组、簇和批的概念可知，倒垛只能发生在放入同一垛中的同组但不同批的箱之间，因此在箱位分配问题的模型中决策变量只需考虑到批而无需再具体到每个箱，这样会使决策变量的数量大幅减少而容易求解。首先引进与组和批相关的决策变量，对基于属性分类的出港集装箱箱位分配问题建立非线性0-1整数规划模型，然后通过等价变换将该模型转化为优化软件CPLEX可直接求解的线性规划模型。

3.1 模型参数

为了建模方便以及便于比较对应于同一条船的两个到港站的远近及两个重量级别的高低，首先将所考虑的集装箱船从1开始顺次编号，然后分别顺次对每条船的所有到港站按从近到远的顺序从1开始编号，最后分别顺次对每条船每个到港站的所有重量级别按从低到高的顺序从1开始编号，并给出如下模型参数：

j：船的编号；

J：船的集合；

|J|：船的总数；

b：堆场中街区的编号；

B：堆场中街区的集合；

|B|：堆场中街区的总数；

s：堆场中垛的编号；

S：堆场中垛的集合；

|S|：堆场中垛的总数；

Nb：街区b中垛的集合；

p：堆场中层的编号；

P：堆场中层的集合；

|P|：堆场中允许的最高层数；

w：重量级别的编号；

Wj：船j的箱对应的所有重量级别的集合；

d：到港站的编号；

Dj：船j的箱对应的所有到港站的集合；

|Dj|：船j的箱对应的所有到港站的总数；

Cwd：由外部卡车运到堆场重量级别为w，到港站为d的出港箱数量；

Iwd：初始状态时，堆场中重量级别为w，到港站为d的出港箱数量；

Ajb：船j与街区b之间的距离；

M：无限大的数；

δ1：目标中与各街区的工作量均衡相关的权重；

δ2：目标中与集卡的运输距离最短相关的权重；

δ3：目标中与倒垛数最少相关的权重。

3.2 决策变量

基于属性分类的出港集装箱的箱位分配问题中的决策变量定义如下：

3.3 模型

根据上述定义的模型参数和决策变量，建立基于属性分类的出港集装箱箱位分配问题的模型(IP)如下：

在上述数学模型中，目标函数（1）包含三部分：第一项表示堆场中具有最大工作量的街区与具有最小工作量的街区间的工作量之差，最小化这个差值来实现街区间的工作量均衡，这里街区的工作量对应该街区的总箱量；第二项表示将所有出港箱装上船时集卡的运输距离之和；第三项表示在装船时一定发生倒垛的集装箱总数。因此目标函数（1）实现在装船时作业分布均匀、内部集卡运行距离最短和发生倒垛的集装箱数最少。约束（2）-（4）给出组与垛的关系。约束（2）表示任意两个组（船）的箱不混放在同一垛位中。约束（3）保证若s垛中放组（船）j的箱则zjs=1。约束（4）保证若zjs=0则s垛上一定不放组(船)j的箱。约束（5）-（7）为箱位使用原则和堆垛状态约束。约束（5）表示将堆场的初始状态赋给变量 xwdsp，即若=1必有 xwdsp=1。约束（6）确保一个箱位至多只能放一个集装箱。约束（7）表示堆场中集装箱不能悬空，即若s垛p层有箱则s垛p-1层必有箱。约束（8）表示批的箱量守恒约束。即堆场中某一批的集装箱总数等于初始状态时该批的集装箱数加上由外部卡车运到堆场中的相同批的集装箱总数。约束（9）和（10）为不同批间倒垛关系约束。约束（9）根据船的基本配载要求给出同组但不同簇间箱的倒垛关系。其中表示被放在s垛i层且要装上船j的集装箱到港站编号，而表示被放在s垛p层且要装上船j的集装箱的到港站编号。如果要装上集装箱船j且重量级别为w，到港站为d的集装箱在到达堆场时被存放在了s垛p层（即）且存放在s垛i层箱的到港站比存放在s垛p层箱的到港站远（即），此时约束（9）变成 |Dj|ysp≥1，这迫使ysp=1，即在物流输入环节，当为将要装上同一条船的两个集装箱分配存储位置时，如果将到港站远的集装箱放在了到港站近的集装箱下方，则在装船时由于要先装到港站远的箱，这个到港站近的集装箱一定会发生倒垛；如果要装上集装箱船j且重量级别为w，到港站为d的集装箱在到达堆场时被存放在了s垛p层（即）且存放在s垛i层箱的到港站比被存放在s垛 p 层箱的到港站近（即0），于是约束（9）变成 |Dj|ysp≥Ne（其中 Ne是一个负数），此时无论ysp取0还是1约束（9）恒成立，目标中最小化总倒垛数会使ysp=0，即在物流输入环节当为将要装上同一条船的两个集装箱分配存储位置时，如果将到港站近的集装箱放在了到港站远的集装箱的下方，则在装船时由于要先装到港站远的箱，这个到港站远的集装箱不会发生倒垛；如果要装上集装箱船j且重量级别为w，到港站为d的集装箱在到达堆场时被存放在了s垛p层（即）且存放在s垛i层箱的到港站与存放在s垛p层箱的到港站相同（即），于是约束（9）变成|Dj|ysp≥0，此时无论ysp取0还是1约束（9）恒成立，目标中最小化总倒垛数会使ysp=0，即在物流输入环节，当为将要装上同一条船的两个集装箱分配存储位置时，如果将到港站相同的箱放在了同一垛中，则放在较高层的箱不会发生倒垛；如果在物流输入环节没有箱被存放在s垛p层（即）约束（9）变成这里由于，于是 ysp无论取0还是1约束（9）恒成立，目标中最小化总倒垛数会使ysp=0，此时约束（9）保证当某位置没有集装箱时就没有倒垛发生。约束（10）根据船的基本配载要求给出同簇但不同批间箱的倒垛关系。由于约束（10）中d∈Dj，对于集装箱船j某个给定的到港站d，表示被放在s垛i层且要装上船j到港站为d的集装箱的重量级别的编号，而表示被放在s垛p层且要装上船j到港站为d的集装箱的重量级别的编号。如果要装上集装箱船j且重量级别为w，到港站为d的集装箱在到达堆场时被存放在了s垛p层（即）且存放在s垛i层箱的重量级别比被存放在s垛p层箱的重量级别高（即），则约束（10）迫使 ysp=1，即在物流输入环节，当为将要装上同一条船且同一到港站的两个集装箱分配存储位置时，如果将重量级别高的集装箱放在了重量级别低的集装箱的下方，则在装船时由于要先装重量级别高的箱，这个重量级别低的集装箱一定会发生倒垛；如果要装上集装箱船j且重量级别为w，到港站为d的集装箱在到达堆场时被存放在了s垛p层（即）且存放在s垛i层箱的重量级别比被存放在s垛p层箱的重量级别低（即），于是约束（10）变成（其中 Ne是一个负数），此时无论ysp取0还是1约束（10）恒成立，目标中最小化总倒垛数会使ysp=0，即在物流输入环节，当为将要装上同一条船同一到港站的两个集装箱分配存储位置时，如果将重量级别低的集装箱放在了重量级别高的集装箱的下方，则在装船时由于要先装重量级别高的箱，这个重量级别高的集装箱不会发生倒垛；如果要装上集装箱船j且重量级别为w，到港站为d的集装箱在到达堆场时被存放在了s垛p层(即且存放在s垛i层箱的重量级别与存放在s垛p层箱的重量级别相同(即)，于是约束（10）变成，此时无论 ysp取0还是1约束（10）恒成立，目标中最小化总倒垛数会使ysp=0，即在物流输入环节，当为将要装上同一条船同一到港站的两个集装箱分配存储位置时，如果将重量级别相同的箱放在了同一垛中，则放在较高层的箱不会发生倒垛；如果在物流输入环节没有箱被存放在s垛p层(即)，约束（10）变成，这里由于，于是ysp无论取0还是1约束（10）恒成立，目标中最小化总倒垛数会使ysp=0，此时约束（10）保证当某位置没有集装箱时就没有倒垛发生。最后，约束（11），（12）和（13）保证决策变量必须为0,1整数。

模型(IP)的特点在于：一方面该模型将空间分配阶段与具体位置分配阶段进行集成来研究出港集装箱的箱位分配问题；另一方面这里的集成并不是将两阶段的已有模型直接合并，而是通过将出港箱按属性分类后定义批的概念，并在模型中引入与批相关的决策变量来实现宏观的空间分配与微观的倒垛的兼容。引入组、簇、批的概念后，根据船的基本配载要求，压箱关系只存在于同组但不同批的箱之间，从而装船时堆场中每个位置的箱是否需要倒垛更容易快速地判断。

由于模型中使用街区间最大工作量与最小工作量的差最小化这种非线性表达来实现街区间工作量平衡的目标，因此无法直接利用优化软件CPLEX进行求解。下面利用等价变换将目标中非线性部分转化为线性的。首先引入新变量E和F：

于是基于属性分类的出港集装箱箱位分配问题的模型(IP)可以等价地转化为如下的线性规划模型(LIP)：

约束（14）和（15）用来反映新变量E和F的定义，通过定义新的变量及引入新的约束，线性模型(LIP)完全等价于原来的模型(IP)，因此可以使用优化软件CPLEX直接求解。

4 实例

为了验证上面所讨论模型的有效性，给出如下具体实例。假设给定某时段有编号分别为1,2,3的三条船进港，堆场中有4个街区，每个街区分别为7垛4层。船1的箱有2个重量级别和3个到港站，船2的箱有3个重量级别和2个到港站，船3的箱有2个重量级别和3个到港站。模型中为了便于表示和计算，首先按街区编号从小到大的顺序将街区中的垛从左至右顺次编号，如图4所示；然后按船编号的顺序将每条船的重量级别从低到高顺次编号，即W1={1,2}，W2={3,4,5}，W3={6,7}；类似地将每条船的到港站从近到远顺次编号，即D1={1,2,3}，D2={4,5}，D3={6,7,8}。表1给出由外部集卡运进的各批出港箱的具体数量Cwd，表2给出初始状态时堆场中各批出港箱的数量Iwd，而每条船与各街区之间的距离Ajb见表3。

表2 Iwd的值

表3 Ajb的值

出港箱在堆场中的初始堆垛状态由图4中黑色的数字和字母组合给出，图中jWwDd表示某个批中的箱，其中该批的箱重量级别为w到港站为d且要装上船j。根据图4中给出的初始堆垛状态可以很容易地得出的值。按照上面给出的基本配载要求可知，在初始的堆垛状态下，有2个箱在装船时需要倒垛。其中一个需要倒垛的集装箱(2W3D5)的位置在16垛2层，因为在它正下方与其到港站相同但重量级别比它高的箱(2W4D5)要先装上船；另一个需要倒垛的集装箱(1W2D2)的位置在26垛2层，因为下面的箱(1W2D3)的到港站比它远。

将已知数据Cwd,Ajb,,Iwd输入模型(LIP)中，这里目标中的权重分别取δ1=0.3，δ2=0.3，δ3=0.4。由于倒垛对装船效率的影响较大，所以取相对大的权重。约束（2）-（8）如前所述。对给定的船和任意的垛，如果p层有箱(即)且该箱的到港站比其下面的i层箱的到港站近(即)，则约束（9）迫使 ysp=1(如图3中的(a)所示)，即s垛p层的箱要倒垛。而对于其他不产生倒垛的情况(图2中的(b)(c)(d))，约束（9）恒成立。对给定的船和其任一个到港站，如果p层有箱(即)且该箱的重量级别比其下面的 i层箱的重量级别低(即)，则约束（10）迫使 ysp=1(如图3中的(a)所示)，即s垛p层的箱要倒垛。而对于其他不产生倒垛的情况(图3中的(b)(c)(d))，约束(10)恒成立。

图2 对应约束（9）的堆垛状态

图3 对应约束（10）的堆垛状态

图4 模型对实例的决策结果

通过优化软件CPLEX 11.0对该实例进行最优求解，得到出港箱在堆场中的最优存储箱位，图4中浅色的数字和字母组合表示将外部集卡运进的出港箱分配到堆场中的最优分配状态。该模型的目标函数值为80.9，目标中第一部分的值为1.5，即堆场中街区间最大工作量与最小工作量的差为5；目标第二部分的值为78.6，即集卡运输距离为262；目标中第三部分的值为0.8，即将堆场中的所有出港箱都装上船时一定会发生倒垛的集装箱数为2，这说明使用我们提出的模型为由外部集卡运进的出港箱分配堆场中的存储位置时没有产生额外的压箱。从图4的最终分配结果可以看出，距离船近的两个街区1和2分配了较多的箱，但总体上各街区间的工作量还是比较均衡的，同时并没有因为有新的出港箱进入堆场而增加装船时的倒垛。可以看出在堆场的初始堆垛状态给定的情况下，通过合理地为进入堆场中的出港箱分配箱位可以减少装船时的倒垛数，从优化物流输入环节的存储位置分配来提高装船时的效率。

5 结语

本文从实际出发，针对集装箱码头堆场箱位分配问题，在对出港箱按其所属船舶、重量级别和到港站分类并引入组、簇、批概念的基础上，将空间分配阶段与具体箱位分配阶段集成来研究出港箱在堆场中的箱位分配问题。根据装船时的倒垛只可能发生在同组但不同批的箱之间的这个特征，通过引入与批相关的决策变量，以各街区的箱量均衡、集卡运输距离最短和装船时一定发生倒垛的集装箱数最少为目标建立非线性0-1整数规划模型，实现从物流输入环节提高出港箱的装船效率。利用上确界和下确界的定义，以及引进新的变量和约束的方式将所建立的模型转化为与其等价的线性规划模型，并使用标准优化软件CPLEX求解实例来验证该模型的有效性。

[1]Bazzazi M,Safaei N,Javadian N.A genetic algorithm to solve the storage space allocation problem in a container terminal[J].Computers&Industrial Engineering,2009,56(1)：44-52.

[2]徐亚,陈秋双,龙磊,刘丽芸.基于多目标规划的堆场空间分配问题研究[J].系统工程学报,2009,24(3)：365-369.

[3]严南南,崔景云.集装箱码头堆场出口箱箱区空间分配动态模型[J].重庆交通大学学报(自然科学版),2016,35(2)：163-168.

[4]檀财茂,黄有方,何军良,严伟.集装箱港口出口箱堆场空间优化分配研究[J].计算机仿真,2016,(10)：187-191.

[5]Wan Y W,Liu J Y,Tsai P C.The Assignment of Storage Locations to Containers for a Container Stack.Naval Research Logistics,2009,56(8)：699-713.

[6]徐亚,陈秋双,龙磊,杨立志,刘丽芸.集装箱倒箱问题的启发式算法研究[J].系统仿真学报,2008.20(14)：3 666-3 669.

[7]Caserta M,Schwarze S,Voss S.A mathematical formulation and complexity considerations for the blocks relocation problem[J].European Journal of Operational Research,2012,219(1)：96-104.

[8]Zehendner E,Feillet D.A branch and price approach for the container relocation problem[J].International Journal of Production Research,2014,52(24)：7 159-7 176.

[9]Tang L,Jiang W,Liu J,Dong Y.Research into container reshuffling and stacking problems in container terminal yards[J].Iie Transactions,2015,47(7)：751-766.

Study on Slot Allocation Problem of Outgoing Containers Based on Attribute Classification

Jiang Wei,Mao Shimin
(School of Technology,Zhejiang Normal University,Jinhua 321004,China)

In this paper,on the basis of the attribute-based classification of outgoing containers and the definition of group,cluster and batch,we studied the slot allocation problem of the containers so as to reduce the number of stack transfer needed in ship loading by optimizing the logistics input links.Next,through introducing in the location variable of the batch,the relational variable between the group and the stack and the stack transfer variable at every position,and with the relationship between the group and stack,the principle and status of slot utilization,the law of conservation of the container quantity for the same batch and the stack transfer relationship between different batches as the constraint,we built the nonlinear integer programming model for the problem.At the end,through equivalent transformation,we turned the model into a linear model directly solvable by an optimization software and demonstrated its validity through an empiricaltest.

outgoing container;attribute classification;slot allocation;integration model

F224.0;U169.6

A

1005-152X(2017)06-0078-07

10.3969/j.issn.1005-152X.2017.06.020

2017-03-31

浙江省自然科学基金资助项目（LQ13G020010）

姜伟（1981-），女，辽宁阜新人，博士，讲师，主要研究方向：集装箱码头等相关物流运作的建模及优化算法设计、物流设施选址设计及最优化算法。