1. 堆场堆存区域决策场景

在整个集装箱码头调度优化中，堆存区域决策属于计划层优化，即需要依据堆场当前堆存状态以及未来计划作业信息，在实际作业发生前，对各作业场景（集港、卸船、转堆）下的集装箱集（具有相同属性信息，例如箱型、进出口类型、流向、提单号等的集装箱组成的集合，本质上为需要集中堆存在一起的集装箱构成的集合），进行堆存区域的指派，指派精度到贝位，以保证堆场堆存空间的高利用率；
例如，如下图所示：为待集港的两个集装箱集（均为700个20FT，预计堆存时长为20210626100000-20210628010000），事先指定在堆场的堆存范围分别为为贝A0-11到贝A0-23贝，以及贝A1-1到A1-13（贝规格统一为10*6，且初始状态均为空栈）；而由于堆存计划具有周期性，因此上述指派方案仅在时长20210626100000-20210628010000有效，而在该时长以外的时刻，贝A0-11到贝A0-23以及贝A1-1到A1-13的堆存区域可供其他集装箱集堆存使用；即指派方案的有效性与时间强关联；

堆存区域决策问题的具体描述如下：
（1）同一堆存区域在任意相同时刻最多仅供一组集装箱集使用，且同一集装箱集内的集装箱需要连续存储，不能进行拆分；
（2）指派维度需要精确到贝位，指派过程需要满足：
（2.1）贝位与集装箱的属性匹配；
（2.2）堆存容量上限；
（3）航线相同的集装箱集尽量放置在同一区块，中转箱和进口箱不混堆在同一区块等堆存约束；
（4）指派目标为，在满足所有待作业集装箱集堆存需求的前下，堆存空间利用率最高；

2.问题转化

从资源调度视角出发，上述场景中待指派的资源包括堆场各区块的物理空间，以及堆场的占用时间；待指派任务为各集装箱集的放置位置；那么，若以X轴表示区块的物理空间，Y轴表示时间轴，可得到堆存空间*时间资源的资源矩形；同时，对任意集装箱集，以占用时长(时刻)为矩形的宽，在堆场的放置范围为矩形的长，可得到具体任务矩形；此时，原问题转化为决策多个任务矩形指派到多个资源矩形中的放置位置，且使资源矩形利用率最高；易知，该问题即为经典的二维矩形装箱问题，如下图所示，三组集装箱集堆存量分别为Q1，Q2，Q3，占用时刻分别为t11-t12，t21-t22，t31-t32；将其放置到区块A0的和A1的堆存空间中，即为原问题的一组可行解；

具体的，将各资源矩形（长x宽：区块总容量x计划周期）定义为装箱问题中的不同规格大箱；任务矩形（长x宽：堆存量x堆存时长）定义为小箱，则上述转化后的问题具有基本二维装箱问题的约束要求如下，其中，每个箱子放置的位置定义为箱子左下角点的坐标：
约束1：放入大箱中的小箱的长度/宽度之和不能超出大箱的范围；
约束2：任意两个小箱的放置不允许出现重合（X轴上/Y轴上）；
此外，结合堆场计划层场景实际需求，该问题还具有以下约束要求：
约束3：多个小箱的放置存在禁止放置在同一大箱，尽量放置在同一大箱、尽量不放置在同一大箱三类约束；
约束4：每个小箱放置的Y坐标已知；
约束5：某些小箱（初始时刻已堆存或有人工指定堆存位置的集装箱集）的放置位置（X、Y坐标）已知；
约束6：小箱的放置过程不允许出现翻转，且均为正交放置；

3.建模方法

将堆存区域决策场景转化为上述具有（1）-（6）约束要求的二维装箱问题后可知，若将小箱在大箱里的排样方式（上图例中：{Q1放置位置,Q2放置位置}和{Q3放置位置}即为两组排样方式）的指派作为待决策变量，即可构造排样方式与大箱的指派关系模型，而排样方式为全集时，该模型可获取到问题最优解，随着问题规模的扩大，可进一步引入列生成技术将该模型作为主问题，排样方式的构造作为子问题进行求解；
整理相关术语定义如下：
1）大箱：一个堆存区段的容量（X坐标）*计划周期（Y坐标）视为一个大箱；
2）小箱：一个集装箱集的堆存量（X坐标）*堆存时长时刻（Y坐标）视为一个小箱；
3）小箱放置位置：小箱左下角点在大箱中的坐标；
4）排样方式：针对一个大箱，一组满足约束1-6要求放置的小箱及放置位置构成的集合；

3.1 数据预处理

建模前，除了定义大箱和小箱之外，还需进行如下预处理：
（1）Y轴坐标设置
由于船舶的在泊时长的最小计量单位为1分钟，因此Y轴刻度0（代表当前时刻）到T（计划周期），步长为1；则每个刻度即可对应现实中的一个具体时刻；
（2）X轴坐标设置
为保证堆存容量的正确映射，X轴坐标的刻度表示区段block-贝bay-栈s-层h的箱位，则多个连续（升序）刻度即可表示为某奇数贝的堆存容量情况；同时X轴升序方向定义为区段面向海侧时，奇数贝的升序编号方向；eg；若区块A0包含2个奇数贝A0-01和A0-03, 且各包含2个栈，堆高均为2层，无预留箱位，则定义如下图所示的X轴坐标；

（3）堆场已堆存集装箱的处理
针对已堆存的集装箱，通过类似坐标轴X中贝bay-栈s-层h连续组合划分的方式将加入待指派集装箱集，并指派固定放置位置；具体为：
Step0: 顺序遍历上述集装箱，并将具有如下性质的多个集装箱视为一组待指派集装箱集：
性质1：从当前时刻起，集装箱的堆存结束时间一致；
性质2：堆存箱位按X轴坐标所设置的方箱递增，且步长为1；
Step1：若堆存结束时间为t，首个集装箱的X轴坐标为x，集装箱个数为m，则定义构造的集装箱集对应的小箱放置位置为当前区块，位置为：{[0, t]; [x, x+m]};

3.2 指派模型

令 $K$ 表示待指派的集装箱集， $R$ 表示堆场区块集，排样方式为 $C$
决策参数：
$a_{ij}$ ：表示堆场区块对应的大箱 $i$ $\in$ $R$ 否放置排样方式 $j$ $\in$ $C$ ;
$s_{ij}$ ：表示堆场区块对应的大箱 $i$ $\in$ $R$ 放置排样方式 $j$ $\in$ $C$ 时的目标得分；
$b_{jk}$ ：表示排样方式 $j$ $\in$ $C$ 中，集装箱集 $k$ $\in$ $K$ 的被排样数次；
决策变量：
$x_{ij}$ ：布尔变量，若排样方式 $j$ $\in$ $C$ 放置到堆场区块对应的大箱 $i$ $\in$ $R$ 则取1，否则取0；
构造如下形式的主问题模型Primal：

$\begin{array}{c} min \sum_{i}\sum_{j}s_{ij}a_{ij}x_{ij} \\ \sum_{i}\sum_{j}x_{ij}a_{ij}b_{jk}=1 &\forall_k\in_K \\ \sum_{i}\sum_{j}x_{ij}a_{ij}\leq_1 &\forall_i\in_R \end{array}$