集装箱堆场出口箱堆存问题学习1综述集装箱在堆场位置的分配是集装箱堆场管理的重要环节，对缩短集装箱船在港停泊时间，提高集装箱码头作业效率有着重要意义。
目前，国际上关于集装箱的对方问题一般遵循PSCW原则，即将对应的同一目的港（port），同一尺寸（size），同一种类（category）以及同一重量级（weight）的集装箱堆放在同一bay中。
集装箱堆场出口箱位置的分配就是为每个到达堆场的出口集装箱确定最佳的堆放位置以便于装船。
出口集装箱有“随机抵达，整批离港”的鲜明特点。
堆场出口箱堆存优化可以降低集装箱堆场翻箱次数，提高堆场机械设备的作业效率，节约堆场管理成本。
同时可以缩短出口箱装船时间和船舶在港停泊时间，避免给船公司和港口企业造成较大的时间损失。
堆场出口箱的堆存问题一直以来都是各国物流方面专家学者[1]们的研究热点。
郝聚民，纪卓尚等（2000）提出了混合顺序堆场作业的概念，并且基于图搜索技术及模式识别理论提出了混合顺序作业贝位优化模型。
张维[2]英，林焰等（2006）建立了龙门式起重机小车取箱作业优化模型，以龙门式起重机取箱作业时倒箱数量最少为目标对出口箱堆场取箱作业进行了优化。
李建[3]中，丁以中等（2007）运用数学规划的方法，从平衡箱区贝位箱量和最小化集卡行驶距离入手，在滚动计划的基础上，建立了集装箱堆场空间资源动态配置模[4]型。
卫家骏（2010）提出了一种优化出口集装箱堆场位置的启发式优化算法，在保证装船质量的同时，有效提高集装箱码头装船效率。
WenbinHu，Huan Wang[5]等（2014）提出了一种基于内外混合细胞自动机的出口集装箱存储分配算法。
与通常的两阶段法不同，他们把贝位分配和具体箱位选择作为一个整体目标进行优化，求取全局最优解。
2基本概念2.1集装箱堆场集装箱堆场即用于临时堆存进出口集装箱的场地，它给出口箱装船作业和收货人提箱作业提供了一个可以缓冲的时间段，同时可以实现集装箱重箱(内部装有货物)及空箱(内部无货物)的交接、货运、检验和修理、承揽货源等功能。
2.2堆场集装箱种类堆场的集装箱按照不同状态可分为4种类型：进口箱（D）型，尚在船上的进口箱，等待卸船，被运到堆场进行堆存；提箱（P）型，已经在堆场上等待客户提走的进口箱；进箱（G）型，尚未分配到堆场的出口箱，等待被运进堆场堆存；出口箱（L）型，已经在堆场上等待装船的出口箱。
这4中状态集装箱的堆存情况都会影响集装箱码头作业效率。
但是这里我们只考虑出口箱（L）型在堆场的堆存问题。
2.3集装箱出口流程集装箱出口流程为：集装箱进港——堆场堆存——场桥装载——拖车运输——岸桥装载——船舶离港。
2.4堆场箱位表示方法堆场箱位是指集装箱在堆场的物理位置。
集装箱堆场划分为不同的区（block），每个区由多个bay组成，每个bay由若干排或列（row）和层（tier）组成。
所以场箱位由箱区、贝位、排和层组成。
如A10111表示该箱在：A1区01贝位第一排第一层；A10133表示该箱在A1箱区01贝位第三排第三层。
Bay中排和层的数量由堆场大小及其所采用堆场机械的类型所决定的。
而贝位内在竖直方向堆放的一个或多个集装箱称为栈（stack）。
在我国，大多数集装箱码头中使用轮胎龙门吊，一般情况下最常见的每个bay由6排、4层组成，即一个bay中能堆装24个集装箱，如图1所示。
Bay1栈43Tier(层)21654321Row(排) 图1、集装箱堆场中某一Bay位示意图 2.5堆场集装箱常用堆存方案不同的集装箱装卸工艺会影响集装箱的堆放。
目前国内外用得较多的装卸工艺是龙门起重机-牵引车-岸桥方案。
这种方案具有单位面积堆存量大、堆场面积利用率高、营运及维护费用低、易于实现自动化操作和管理等优点。
按照取箱方式，目前常用的堆存方案有：水平顺序作业堆场、垂直顺序作业堆场，如图2中（a）、（b）所示。
但事实证明，混合顺序作业方式相对于水平顺序作业和垂直顺序作业方式而言可以提高集装箱的装船效率。
目前，中国许多集装箱堆场采取混合顺序作业方式，如图3。
其中每一格代表一个集装箱，格中的数字表示集装箱的理想装船顺序。
数字越小表示越早被移出贝位进行装船。
为了保证船舶的稳性，堆场集装箱的堆放应该遵循“重箱在上，轻箱在下”的原则。
水平顺序作业是指按照bay 中层的顺序自近车道一侧向远离车道一侧依次取箱装船；垂直顺序作业是指按照bay中列的顺序自上向下取箱装船。
在堆场中某一bay 的装箱顺序已知，集装箱装船是按照配载图进行的，一旦配载图确定后，集装箱的装船顺序也就确定了。
1215345913176217826141891011102212牵引车1519233711车载箱1617181314151620244812222324192021(b)垂直顺序作业堆场(a)水平顺序作业堆场图2、常用集装箱堆存方式136101418259131721Tier (层)481216202371115192224Row(排) 图3、某一Bay位混合取箱方式示意图 2.6装船前预翻箱和装船时翻箱操作装船前预翻箱是指在集装箱船舶未到港口的情况下，对集装箱码头堆场集装箱堆存状态不符合发箱顺序的箱子进行预先翻动操作的过程，使得整理后的集装箱堆放顺序与发箱顺序一致，以尽可能地降低或者消除装船时翻箱操作的出现次数，从而达到提高装船时作业效率的目的。
预翻箱作业发生在配载计划结束之后及装船之前的一段时间内。
装船时翻箱操作是一个动态过程，即翻箱过程中，bay内集装箱是逐渐从贝位移动到船舶上的，贝内集装箱的总数量逐渐减小。
在翻箱的过程中不断的有集装箱被集卡运走。
装船时翻箱和装船前预翻箱的不同在于装船前进行预翻箱操作时堆场贝位中的集装箱总数是不变的，而装船翻箱操作时堆场贝位中的集装箱是不断移动到靠泊的船上的。
由于大多数集装箱码头通常在船舶到港前数小时就结束集港，且大部分集港的集装箱在结港前一段时间均己到港。
因此，可以充分利用结港后至装船前的时间段，甚至可以在尚未结港但大部分集港箱己到港、多数计划贝位已经堆满的情况下，对已结束集港的贝位进行预翻箱整理操作。
预翻箱和翻箱操作的区别如表1。
而装船前预翻箱和装船时翻箱操作都要考虑堆场龙门吊在翻箱操作过程中的移动距离，以提高堆场作业机械设备利用效率。
表1、预翻箱和翻箱操作区别预翻箱操作翻箱操作发生时间装船前装船时产生原因利用结港后至装船前的时段对无足够设备和时间完成预翻箱、预已经结束集港的bay进行预翻翻箱后堆存状态又有改变或者船舶箱整理配载计划改变达到目的尽可能保证整理后的堆存状态符合尽可能按发箱顺序完成取箱装船操发箱顺序要求作取箱发生时间发生在预翻箱整理完毕后与翻箱整理同时发生 Bay内箱子总数量保持不变由于取箱操作，箱子数量不断减少目标最小化从初始堆存状态到最终堆存最小化取箱装船过程中所需要的翻状态所需要的翻箱总次数箱操作总次数3具体问题分析3.1装船前预翻箱问题（不考虑龙门吊移动距离） 3.1.1基本假设根据集装箱堆场现实运作过程知，出口箱装船作业流程是从收箱作业开始进行的。
由于出口箱到达堆场的时间和数量等信息具有很大的随机性，一般是未知的。
而堆场出口箱要装载到哪个船上，此船舶到港时间以及相应的船上集装箱配载图是提前已知的。
为了便于建立模型，结合实际情况先对预翻箱操作进行以下假设：（1）预翻箱整理操作的完成状态是，先装船的集装箱均堆存在后装船的集装箱箱上方，不需要将某个集装箱的最终箱位固定到某具体位置上。
（2）堆存贝位为多排多层直接堆躲形式，贝位内只允许堆放相同尺寸的集装箱，即不考虑20ft和ft尺集装箱混堆的情况。
（3）预翻箱开始时，贝中所有集装箱的初始堆放状态己知，各集装箱的装船顺序已被唯一确定。
（4）预翻箱操作只在发生在同一个贝内，即不考虑大车的移动。
（5）堆存贝位如果有k层堆存位，则贝位内至少留k个空箱位作为翻箱操作使用。
3.1.2符号说明S Bay的最大栈数，也等于Bay中的排数 T Bay的最高层数 NBay内集装箱总数 M事先规定的翻箱操作的最终阶段，这个值是一个假定的值，这个值比实际需要翻箱 M N操作需要的阶段大，即 C 大数，是个可以设定的常数。
i,k贝的堆栈索引 j,l贝的层数索引 n集装箱索引，对应集装箱的权重。
索引越小，权重越高，发箱优先级越高，即越早装船。
m 从初始状态（m=1）到无翻箱状态（m=M）的阶段索引。
规定一个阶段就是从一个贝位堆存状态和从这个堆存状态提起一个集装箱至即将落下贝位内的某个箱位的过程。
x(i,j)(k,l) 如果阶段m集装箱n从箱位移动到箱位，则为1；否则为0 ijklnm b(i,j) 如果m阶段集装箱n占用箱位,则为1；否则为0 ijnm 3.1.3模型目标函数：STSTNM minx (1)约束条件：1,...,ijkln1)m ijnmm ijnm或者，或者公式（1）目标函数是最小化贝位内翻箱操作的总次数。
公式（2）-（12）为约束条件，其中（2）是保证集装箱不悬空，即当贝中的箱位被占用的话，则箱位必定也被占用。
约束（3）保证预翻箱过程中的任意阶段m，贝(i,j)位内的集装箱的总数量是固定不变的，始终为N。
这个约束描述了在预翻箱进行的过程中，不允许新到集装箱在作业贝位内进行堆放，也不允许集卡将贝位中的集装箱移走。
约束（4）保证任意阶段m任意箱位至多被一个集装箱占用。
(i,j)约束（5）保证任意阶段至多存在一次翻箱操作。
这是因为每个阶段是按照一次集装箱翻箱操作而划定的。
约束（6）保证若任意阶段m 不存在翻箱操作，则紧后阶段m+1也不存在翻箱操作。
约束（7）保证最后阶段M对于贝内任意一个栈，要么没有集装箱，要么只有一个集装箱，若有两个及两个以上集装箱，则下面的集装箱的编号比上面的集装箱的编号大，即此阶段不需要翻箱操作。
这是由于M已经规定为预翻箱最终阶段。
约束（8）和（9）保证任意阶段m 如果存在翻箱操作，则翻箱集装箱的对应位的上方必须为空。
此约束保证了每次翻箱操作仅发生在贝位内堆存栈的最上层。
当贝位的上层有集装箱时不可能直接将下层的集装箱移出；同理，也不可能把一个集装箱直接移入贝位中另一个集装箱的下方。
即:将某集装箱从某桟的最上层移出，而后直接堆存在其他各栈集装箱的上方。
约束（10）是预翻箱操作过程中，任意阶段m任意贝内箱位的流平衡约束。
(i,j)此约束体现了从一种状态通过合理的集装箱翻箱移动转变到另一种状态的过程。
约束(11)和(12)定义变量为0-1变量. 3.2对参考文献[5]所研究的问题进行改进： 3.2.1、问题描述：文章主要考虑堆场出口箱箱位分配问题。
试图通过合理分配出口箱在堆场的具体位置减少贝内翻箱次数，并且使堆场集卡、龙门吊等机械设备在装船过程中的移动距离尽可能的小，以提高堆场作业效率，节约堆场管理成本。
