基于限制条件的港口集装箱码头出口集装箱堆存定位研究

胡碧琴， 江 伟 （上海海事大学，上海 200135）

基于限制条件的港口集装箱码头出口集装箱堆存定位研究

胡碧琴， 江 伟 （上海海事大学，上海 200135）

采用限制条件满足的方式，对出口集装箱的堆存空间进行配置。出口集装箱堆场空间位置预分配可以提高集装箱装船效率。以内集卡和场吊效率最大化为目标，根据实际集装箱码头的堆存操作，提出相关限制条件。最后用实验数据验证该方法的效果。

CPS；出口集装箱；空间配置

0 引 言

集装箱码头操作主要由卸箱操作 （进口集装箱从到港船卸下）、装箱操作 （出口集装箱装上离港船）、发箱操作 （从堆场提取进口集装箱）、收箱操作 （出口集装箱进入堆场）。装箱操作和卸箱操作被统一称作 “ship operation”，以优化服务水平为目标，通过加快 “ship operation”速度以减少集装箱船舶在港逗留时间和外集卡逗留时间。图1是集装箱堆场图，集装箱码头的出口集装箱装箱操作由装箱计划员在船舶到港前安排就绪。船公司在装船前几天告知码头公司船舶记载图，在记载图上，每个slot根据重量、目的地、集装箱型号安排同类集装箱。由于船舶中的每个位置区域都会被指定堆放一类集装箱，堆场以满足最快装船为目标合理安排集装箱堆存区域和位置，形成最优装箱顺序表。装船计划者在对集装箱进行排序时，通常试图最小化桥吊和场吊时间。决策制定的过程被称为堆场顺序图，出口集装箱在堆场中的位置是否合理直接决定着装箱顺序是否有效。本文主要的是以最大化装船效率为目标提出有效地出口集装箱堆场空间提前合理配置的方法。

为得到有效地装箱顺序，在堆场空间配置计划过程中必须通过考虑以下内容。图2展示的是集装箱船的平面积载图，也被称为BAY位图，图中显示集装箱根据重量和目的地两因素分类。集装箱堆场空间计划操作中一条普遍原则就是：集装箱船对应的出口集装箱被堆放在靠近该船泊位的堆场区域。此外，另一条堆场空间计划的普遍原则是基于堆场操作机械提出的：举例来说，不同类别的出口集装箱不应该同时堆放在同一个yard-bay中。这条原则仅适用非直接转运堆场系统，即堆场的主要操作机械为场吊、跨车。出口集装箱的装船作业过程中，同一类别的集装箱应就近堆放 （如图2所示），这样便于持续性的装船作业。对于非直接转运堆场系统来讲，同一类别集装箱集中堆放，可以减少场吊等机械的移动距离，提高装卸效率。其他一些堆场计划遵循的原则将在下面几部分进行论述。

1 国内外研究现状

目前对于集装箱码头的研究较多。Kim[1]提出以翻箱次数最小为目标，决定出口集装箱的堆存位置。Cao and Uebe[2]提出基于非线性限制条件的运输模型以得到安排堆场空间位置。然而，这些研究都没有考虑时间轴的集装箱流动态变化因素。Kozan[3]提出用网络模型来描述集装箱流在集装箱码头的动态情况，这个模型试图对集装箱流进行分类，以减小操作成本。Roll and Rosenblatt[4]提出分类堆存策略的概念类似于集装箱空间配置问题，他们采取的堆存策略类似于仓库的堆存策略。Tsang[5]详细描述堆存问题中的限制条件。Zhang[6]探讨了集装箱堆场的空间配置问题，将空间配置问题拆分成两个层次，第一层次试图平衡各BLOCK间的箱量，第二个层次最小化bay位到船舶的距离。Kim and Park[7]提出多货物最小成本流程模型来解决空间配置问题，用次级梯度优化技术解决该问题。

目前有关空间配置问题的研究，目标函数定义明确，容易得到可行解，然而在实际的码头操作过程中，很多复杂的限制条件需要满足。因此，找到一个可行解是十分困难的问题。这就是为什么需要将CSP技术应用到集装箱码头空间资源配置的原因。

2 出口集装箱空间资源配置问题

这个问题的前提是空间配置按期进行。配置的时期根据不确定性和计算时间，可能是一天、24小时，6小时，由于时期不一致，我们统一将进行空间资源配置的一个决策期间称为一个 “stage”。对到达的出口集装箱根据尺寸、船、目的港进行分类。假设不同类型的集装箱不堆放在相同的yard-bay中。下一时期的集装箱到达之前堆存空间已经被预先安排。然而，如果下一阶段的决策没有考虑到堆场未来会发生的变化，将导致很难找到持续阶段的可行解。研究考虑下一阶段决策对未来阶段的影响。在本文中，CPS技术将应用于空间配置研究。

通过预测集装箱的到达情况，估计下一阶段和未来阶段的每类集装箱空间需求，一类集装箱的空间需求被称作一个SDU （Space Demand Unit）。一个SDU的空间需求量以20英寸一个BAY或40英寸两个BAY为需求单位。基于预计的集装箱到达情况，下一阶段与未来阶段的SDU数的空间需求量必须被指定。

其次，空间的供应位置必须确定。一个堆放出口集装箱的集装箱堆场通常可分为若干个yard-bay。每个yard-bay包含20～30个堆放位在跨车堆场系统或6～7个堆放位在场吊堆场系统。在本文研究中，一个yard-bay被认为是一个空间配置单位SAU。图3说明本文空间配置问题的概念表示，空间配置为一个SDU指定1～2个可用SAU。但是一个SAU不能指定给多个SDU。

空间配置问题的难点在于空间配置决策的效果评价只有当装船操作实际进行时才可以得知。然而，装船操作的效率依靠于空间配置和装船顺序。由于出口集装箱装船顺序也是一个复杂的决策问题，因此空间配置面临有较多复杂的限制条件。

本文探讨如何将CSP（constraint satisfaction problem）技术应用于空间配置问题。下面将解释实际集装箱港口中采集来的限制条件，大部分限制条件与制定有效装船的堆存计划所采用的原则有关。

限制1 出口集装箱的堆放位置与将对于船停靠的泊位的距离小于指定的最大限制要求。这个约束对减少集装箱在堆场与码头前沿的运输距离是必要的。

限制2 同船集装箱在不同BLOCK间的最大距离小于制定值。这个限制条件对减少场吊的行驶距离是有效的。

限制3 同船集装箱应堆放同一箱区的同一排位置。这个限制的提出在于场吊在箱区的长度方向容易移动，在宽度方向不容易移动。限制4 不同船对应的出口集装箱不能同时同箱区进行收箱操作。这个限制条件是防止场吊在同一箱区堵塞。限制5 箱区内集装箱对应的不同船总数不能超过规定限制 （NVmax）。这一限制同时约束了一艘船对应的最大箱区数和一个箱区内堆放的一艘船最小集装箱数。

限制6 装上同一艘船的集装箱被堆放的箱位总数不超过规定限制 （NBmax）。如果一艘船的集装箱被堆放在多个箱区，堆场机械的移动距离将增加。

限制7 一个40英尺集装箱所需要的堆存空间相当于两个20英尺集装箱所需要的堆存空间。除了上述限制条件，在不大幅度修改搜索算法的基础上，研究将考虑其他限制因素。

3 堆存空间配置中CSP技术的应用

图4说明空间配置问题的开发程序结构。如图所示，这个系统由中间层、限制说明层、搜索层。在中间层，将对变量进行定义。对于堆场空间配置问题，SDU对应的变量，为每个SDU安排的SAU也适用于这些变量。限制说明层，限制条件将以等式的形式在程序中体现。变量模型，在指定函数值的情况下可以被应用于解决堆场空间配置模型。

Fig.4 The structure of the program developed for the space allocation

以下将说明空间配置研究的搜索程序：

第1步 定义变量和变量范围，每个变量的设定值范围。

第2步 如果不存在任何变量就停止执行程序。否则，选择下一个变量执行。

第3步 选择下一个值，将指定值赋值给变量。如果所有变量都被赋值，那么停止执行。否则，进入第4步。

第4步 减少问题。在这一步，剩余变量所赋予的值没有满足至少一个限制条件，将会从变量集合中移除。确定是否变量集合已经为空集合。如果是，继续执行第5步，如果不是，执行第2步。

第5步 确定是否还有剩余值4赋给当前变量，如果有，继续执行第3步，如果不是，将当前变量转为过去变量，再继续执行第3步。

4 算例实验

算例实验的目的是验证搜索方法的可行性和有效性，同时找到最优搜索决策。

4.1 算例实验输入数据

本文采用的算法将应用于解决一个实际大型集装箱码头——釜山港的空间配置问题 （PECT:Pusan Eastern Container Terminal）。对大量的搜索策略的速度和效果进行验证。应用的搜索策略所给予的原则是变量顺序原则，赋值顺序原则和限制条件顺序原则。算例的问题可分成2个阶段，84个SDUs变量相当于15（vessels）×2（sizes）×3（destination ports），对应于箱区bay位数的600个SAUs值。数据来源于15 vessels and 24 blocks,and 4 berths的实际集装箱操作数据。第二部分实验中将考虑所有上述7个限制条件。限制5和限制6的参数定义如下：NVmax=3 and NBmax=3。

4.2 验证变量顺序策略的实验和结果分析

以下3个标准将用于指定变量：

（1）SDU的时期：SDU的早期阶段优于其后期阶段； （2）SDU对应集装箱的尺寸大小：40英尺集装箱对应SDU级别高于20英尺集装箱对应SDU级别； （3）SDU对应船：SDU的顺序是对应船按时间顺序进行先后排列。

通过这3个标准的综合分析，3个指定变量的规则设立如下：

（Rule 1）SDUs的顺序根据计划阶段进行安排； （Rule 2）SDUs的顺序根据集装箱尺寸进行安排； （Rule 3）SDUs的顺序首先根据计划阶段，其次根据船的先后顺序； （Rule 4）SDUs的顺序首先根据计划阶段，其次根据船的先后顺序，最后根据集装箱尺寸。

SDUs的顺序在以上4条规则下仍无法区分的情况下，按随机顺序。值的排列顺序是BAY ID的递增次序。基于10个初始分布的集装箱解决该问题。Table1中结果显示耗费多少CPU时间找到10个问题的可行解。通过数据测试，在3个零值假定下，规则4的计算时间没有比由于因置信度为1%而被拒绝的其他3条规则长。零值测试结果说明，规则4相较于其他规则计算时间较短。

Table 1 The computational time for various variable-ordering rules （in seconds）

4.3 验证两个赋值顺序策略

按照不同的赋值顺序进行实验，规则3是变量顺序策略。两个赋值顺序策略进行相互比较。第一个规则是SAU的顺序按bay ID的字母表顺序，被称作 “bay ID rule”。第二个规则是SAU顺序是靠近对应船只泊位的bay ID具有优先顺序，被称作 “closest-to berth rule”。在第一个实验中，10个不同初始分布的集装箱堆存问题的解答结果如下Table 2所示。通过数据测试，得出结论在置信度为1%的情况下， “closest-to berth rule”的计算时间优于 “bay ID rule”的计算时间。

4.4 验证多种限制条件的顺序策略

集装箱空间配置问题的可行解必须满足多种限制条件，搜索过程中限制条件的逐级递推顺序极大地影响了计算时间，考虑限制1、限制2、限制3、限制6、限制7。假设NVmax=3 and NBmax=3，变量顺序规则遵循规则3，赋值顺序规则遵循bay ID规则，每个限制条件的顺序在10个不同初始分布的集装箱问题中进行实验。Table 3说明不同限制顺序的10次不同问题的计算平均时间，实验结果说明限制条件的顺序极大影响计算时间，限制5应该在搜索过程中首先满足。

5 结 论

将CSP技术应用于出口集装箱堆场空间资源配置问题。开发基于CSP概念的程序应用于出口集装箱堆场空间资源配置。介绍了出口集装箱堆场空间资源配置问题的限制条件。用来源于上海洋山港的数据，通过进行算例实验验证所应用算法的有效性，比较不同的变量顺序规则的计算时间。实验结果显示，空间需求安排的顺序依次是阶段原则、船舶原则、尺寸原则的情况下计算时间最少，同时也说明赋值顺序将极大影响计算时间。最后，比较搜索过程不同限制顺序，搜索过程中限制条件顺序将极大影响空间配置的计算时间。

Table 2 The computational time for two value-ordering rules （in seconds）

Table 3 The computational time for different sequences of constraints

[1] Kim,K.H.,Park,Y.M.,and Ryu,K.R..Deriving Decision Rules to Locate Export Containers in Container Yard[J].European Journal of Operational Research,2000,124:89-101.

[2] Cao,B.and Uebe,G..Solving Transportation Problems with Nonlinear Side Constraints with Tabu Search[J].Computers Ops Res,1995,22(6):593-603.

[3] Kozan,E..Optimizing Container Transfers at Multimodal Terminals[J].Mathematical and Computer Modelling,2000,31:235-243.

[4] Roll,Y.and Rosenblatt,M.J..Random versus Grouped Storage Policies and Their Effect on Warehouse Capacity[J].Material Flow,1983(1):199-205.

[5] Tsang,E..Foundations of Constraint Satisfaction[M].Academic Press Limited,UK,1993.

[6] Zhang,C.,Liu,J.,Wan,Y.-W.,Murty,K.G.and Linn,R.J..Storage Space Allocation in Container Terminals[J].Transportation Research,2003,37B:883-903.

[7] Kim,K.H.and Park,K.T..Dynamic Space Allocation for Temporary Storage[J].International Journal of Systems Science,2003,34:11-20.

Yard Space Allocation for Locating Export Container with Satisfying Constrains

HU Bi-qin,JIANG Wei (Shanghai Maritime University,Shanghai 200135,China)

With satisfying constraints,yard space for export containers is allocated.Yard space is preassigned to improve container loading efficiency.With maximize the efficiency of inter-truck and YC,the paper presents the related constraints according to container terminal yard operation.Finally,testify the effects of the CPS methods with experiment data.

CPS;export container;space allocation

U169.6

A

1002-3100(2010)12-0015-05

2010-10-12

上海市科委创新行动项目，项目编号：08170511300。

胡碧琴（1986-），女，浙江宁波人，上海海事大学硕士研究生，研究方向：物流管理与工程；江 伟（1985-），男，四川遂宁人，上海海事大学硕士研究生，研究方向：采购与供应链管理。