基于属性分类的出港集装箱箱位分配问题研究
[摘要]在对出港箱按属性分类并定义组、簇、批的基础上研究出港集装箱的箱位分配问题，从优化物流输入环节来减少装船时的倒垛数。通过引进批的位置变量、组与垛关系变量和每个位置的倒垛变量，并以组与垛的关系、箱位使用原则和状态、批的箱量守恒以及不同批间倒垛关系为约束对该问题建立非线性整数规划模型，目标是实现装船时各街区箱量均衡、集卡运输距离最短和装船时一定发生倒垛的集装箱数最少。利用等价变换将该模型转化为优化软件可直接求解的线性模型，并实例验证模型的有效性。
[关键词]出港集装箱；属性分类；箱位分配；集成模型
[中图分类号]F224.0；U169.6 [文献标识码]A [文章编号]1005-152X（2017）06-0078-07
1引言
近年来随着全球化和经济一体化的快速发展，国内和国际货物的运输量不断增长，这种增长趋势对为货物的运输、装卸、包装、仓储、配送及信息管理提供相应服务并保证货物安全准时到达的物流业提出了更高的要求。港口作为货物海陆联运的枢纽，是物流体系中一个不可替代的重要节点。在港口中堆场空间是一种稀缺资源，在集装箱的货流量不断增加的环境下，如何管理码头堆场系统，为每个集装箱分配合理的箱位进而提高装卸效率和码头服务水平，成为码头管理者和学术界关注的热点问题。
合理分配出港箱在存入堆場时的箱位可以提高堆场中集装箱的装船效率，从而缩短船的在港时间。集装箱堆场箱位分配问题包括两个阶段，第一阶段（宏观层面）是空间分配阶段，用来决策分配到每个街区的箱量；第二阶段（微观层面）是具体位置分配阶段，用来决策每个箱的具体箱位（由街区号、贝号、行号和层号确定），使得在提取过程中总倒垛数最少，所以也将第二阶段问题称为倒垛问题。
对于第一阶段的空间分配问题，Bazzazi等{Bazza-zi，2009#7}使用遗传算法求解具有不同类型的进港箱的空间分配问题，目标是街区间的工作量平衡。徐亚等对出口箱空间分配问题提出以集卡运输距离最短和工作量平衡为目标的多目标规划模型，并采用改进的线性功效系数法将模型转化为单目标整数规划模型进行求解。严南南和崔景云以箱区贝位间作业量的平衡和龙门吊的使用数量最小为目标建立两层数学模型，确定不同尺寸集装箱分配到各箱区贝位中的具体数量。檀财茂等从考虑码头资源紧缺的角度将堆场空间分配问题分解成两个连续的问题：第一个问题模型以最大化箱区的空间利用率来确定箱区航线配对组合情况；第二个问题模型将第一阶段已经配对好的航线组合指派到堆场中的具体箱区。
对于第二阶段的具体位置分配问题，Wan等对静态倒垛问题（当一个贝位的初始堆垛状态及集装箱的提取顺序给定时，如何决策倒垛箱在该贝位中的位置使得提取过程中总倒垛数最少）首次建立整数规划模型，然后提出多种启发式算法验证算法的有效性。徐亚等对同样的问题提出启发式算法及其改进算法，并通过仿真实验验证算法的有效性。Caserta等首次证明了静态倒垛问题是NP难问题。Zehendner和Feillet首次使用基于数学规划的branch and price方法来解决静态倒垛问题。Tang等对Wan等提出的整数规划模型进行改进，并提出有效的启发式规则。
本文的主要贡献在于通过对出港集装箱按属性分类并引入组、簇、批的定义，从一个新的角度将空间分配问题和具体箱位分配问题这两个阶段集成起来解决堆场箱位分配问题，从而在物流输入环节控制影响装船效率的因素。针对出港集装箱的箱位分配问题，引进与组和批相关的决策变量，建立非线性0-1整数规划模型来达到提高装船效率的目标。通过等价变换，将其转化为线性规划模型并利用优化软件CPLEX进行有效求解。
2出港集装箱的分类及问题描述
集装箱码头为了有效地提高堆场空间利用率，通常采取将多个集装箱按垂直方向向上堆垛的方式进行堆存。集装箱的这种堆放方式虽然具有高密度和高空间利用率的特点，但在提箱的过程中有可能产生不必要的倒垛而影响提箱的效率。如果待提取的目标箱上面放有其他箱，那么就产生了压箱。为了要提出该目标箱，必须先将压在其上面的箱暂时移到其他箱位，这种临时的集装箱移动称为倒垛。堆场中无论任何时段任何操作都不希望有倒垛发生，因为倒垛操作大大降低了工作效率，增加了操作成本，因此有效减少倒垛数是集装箱码头操作中另一个研究热点。
由于出港集装箱可以根据所属船舶、箱型、到港站、重量级别等属性进行分类，且所有属性均相同的出港箱在装船时可以相互替换，因此根据配载计划进行装船时，通过提取属性相同的箱中压箱数最少的箱可以减少倒垛的发生，提高装船效率。因此当出港箱由外部集卡运进堆场时，采用按属性归类后再分配其在堆场中箱位的方法可以从物流输入的源头上控制装船的倒垛量。假设所有出港箱的箱型都相同，图1为出港箱根据所属船舶、到港站、重量级别分类的示意图。将要装上同一条船的出港箱定义为一组（group）。为了操作方便和避免倒垛，在实际的堆场操作中，不同船的箱不会混放到同一垛中，因此不同组的箱不能放在同一垛中；然后对同一组中的箱根据到港站的不同进行分类，将同组且到港站相同的箱定义为一簇（family）；最后对同一簇中的箱根据重量级别的不同进行分类，将同簇中重量级别相同的箱定义为一批（batch）。根据上述定义，同批中的箱由于属性完全相同，即使放在同一垛中也不会发生倒垛，因此倒垛操作只能发生在同组但不同批的箱之间。对出港集装箱引入批的概念后，不需要决策某个具体箱是否放在某个箱位，而只需决策某一批中的箱是否放在某个箱位。因此，通过引入与批相关的决策变量后，堆场箱位分配问题中用来决策每个箱位置的位置变量就会明显减少，便于建模求解。
根据集装箱船的基本配载原则可以确定不同批的出港集装箱装船时的先后顺序。首先，为了避免在集装箱船上发生倒垛，要求集装箱船上到港站远的箱不能压在到港站近的箱上面，因此装船时要先装到港站远的箱再装到港站近的箱；其次，为了保证集装箱船的稳定性，配载时要将重量级别高（重）的箱放在船的下面，因此装船时要先装重量级别高的箱再装重量级别低的箱。
根据上面出港集装箱的分类及不同类别集装箱的装船顺序，基于属性分类的出港集装箱箱位分配问题描述如下：在某一给定的时段，堆场的初始堆垛状态非空且已知，该时段内外部集卡向堆场运进出港箱的数量已知，这些出港箱在运进堆场时其所属船舶、到港站和重量级别等信息便可以获得。该时段内到港的船泊数量及停靠的泊位已知，并且每条船的停靠泊位与堆场中每个街区的距离给定。根据每个箱的属性可以按照上面的分类原則将其分批。我们的问题就是要决策分批后的集装箱在堆场中的具体箱位，目标是各街区的工作量均衡、装船时集卡在街区和船间运输的总距离最短和发生倒垛的集装箱数最少，从而保证装船效率。
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的箱对应的所有重量级别的集合；
W：所有箱的重量级别集合，其中W=∪Wj；
d：到港站的编号；
Dj：船j的箱对应的所有到港站的集合；
|Dj|：船j的箱对应的所有到港站的总数；
D：所有箱的到港站集合，其中D=∪Dj；
|Wdj|.对应于船j且到港站为d的重量级别的总数；
X0wdsp：堆场的初始堆垛状态，若初始状态时重量级别为w，目的港为d的箱在s垛p层，则X0wdsp=1，否则X0wdsp=0；
Cwd：由外部卡车运到堆场重量级别为w，到港站为d的出港箱数量；
Iwd：初始状态时，堆场中重量级别为w，到港站为d的出港箱数量；
Ajb：船j与街区b之间的距离；
M：无限大的数；
δ1：目标中与各街区的工作量均衡相关的权重；
δ2：目标中与集卡的运输距离最短相关的权重；
δ3：目标中与倒垛数最少相关的权重。
3.2决策变量
基于属性分类的出港集装箱的箱位分配问题中的决策变量定义如下：
模型（IP）的特点在于：一方面该模型将空间分配阶段与具体位置分配阶段进行集成来研究出港集装箱的箱位分配问题；另一方面这里的集成并不是将两阶段的已有模型直接合并，而是通过将出港箱按属性分类后定义批的概念，并在模型中引入与批相关的决策变量来实现宏观的空间分配与微观的倒垛的兼容。引入组、簇、批的概念后，根据船的基本配载要求，压箱关系只存在于同组但不同批的箱之间，从而装船时堆场中每个位置的箱是否需要倒垛更容易快速地判断。
由于模型中使用街区间最大工作量与最小工作量的差最小化这种非线性表达来实现街区间工作量平衡的目标，因此无法直接利用优化软件CPLEX进行求解。下面利用等价变换将目标中非线性部分转化为线性的。首先引入新变量E和F：
于是基于属性分类的出港集装箱箱位分配问题的模型（IP）可以等价地转化为如下的线性规划模型（LIP）：
约束（14）和（15）用来反映新变量E和F的定义，通过定义新的变量及引入新的约束，线J生模型（uP）完全等价于原来的模型（IP），因此可以使用优化软件CPLEX直接求解。
4实例
通过优化软件CPLEX 11.0对该实例进行最优求解，得到出港箱在堆场中的最优存储箱位，图4中浅色的数字和字母组合表示将外部集卡运进的出港箱分配到堆场中的最优分配状态。该模型的目标函数值为80.9，目标中第一部分的值为1.5，即堆场中街区间最大工作量与最小工作量的差为5；目标第二部分的值为78.6，即集卡运输距离为262；目标中第三部分的值为0.8，即将堆场中的所有出港箱都装上船时一定会发生倒垛的集装箱数为2，这说明使用我们提出的模型为由外部集卡运进的出港箱分配堆场中的存储位置时没有产生额外的压箱。从图4的最终分配结果可以看出，距离船近的两个街区1和2分配了较多的箱，但总体上各街区间的工作量还是比较均衡的，同时并没有因为有新的出港箱进入堆场而增加装船时的倒垛。可以看出在堆场的初始堆垛状态给定的情况下，通过合理地为进入堆场中的出港箱分配箱位可以减少装船时的倒垛数，从优化物流输入环节的存储位置分配来提高装船时的效率。5结语
本文从实际出发，针对集装箱码头堆场箱位分配问题，在对出港箱按其所属船舶、重量级别和到港站分类并引入组、簇、批概念的基础上，将空间分配阶段与具体箱位分配阶段集成来研究出港箱在堆场中的箱位分配问题。根据装船时的倒垛只可能发生在同组但不同批的箱之间的这个特征，通过引入与批相关的决策变量，以各街区的箱量均衡、集卡运输距离最短和装船时一定发生倒垛的集装箱数最少为目标建立非线性0-1整数规划模型，实现从物流输入环节提高出港箱的装船效率。利用上确界和下确界的定义，以及引进新的变量和约束的方式将所建立的模型转化为与其等价的线性规划模型，并使用标准优化软件CPLEX求解实例来验证该模型的有效性。
