出口集装箱堆场箱位分配问题(Slots Allocation Problem for Outbound Containers)

关于集装箱码头的那些事

- 集装箱码头堆场箱位分配 -

集装箱箱位分配问题

（Slots/Space Allocation Problem，简称SAP）

是集装箱码头运作优化的关键问题之一

在该问题中要求

在指定堆存区中完成一批集装箱的箱位安排

每个集装箱有各自唯一的编号

箱区堆位也有一定的容量与及高度限制

一个集装箱只能选择一个箱位进行堆存

在箱位分配阶段

每个集装箱在箱位被取走到岸边交接过程消耗的

堆垛机工作时间、集卡运输及等待时间都不一样

主要决策是为每一个集装箱具体分配一个箱位

实现取箱和存箱作业效率提升

出口集装箱箱位分配问题

（Slots Allocation Problem for Outbound containers，简称OB-SAP）

是SAP中针对出口集装箱的特性

进行具体性研究的一类问题

它在常见SAP问题的基本约束上

多了出口集装箱随机到港及按顺序上船的约束

除了给每个集装箱分配存箱具体箱位

还考虑后续装船时所产生的移箱（翻箱）操作

接下来将给大家简单介绍OB-SAP问题

我们还会列出一些经典数学模型哦

一、问题介绍

当货主/货代公司将一批需要出口到国外的集装箱运输到码头的时候，码头堆场管理员需要给每一个箱子安排一个箱位（slot）作为临时存放点。

可能有些小伙伴对海运不太了解，在详细分析问题之前，小编先给大家简单介绍一个集装箱码头的工作流程。在码头系统中，堆场（Yard）处于中间位置，对接着陆侧和水侧，划分出堆存箱区为进口箱以及出口箱等提供位置进行临时存放，堆场内有内集卡对接岸边。当出口集装箱被外集卡送到码头后，在箱区近陆侧经由场桥堆垛起重机负责卸下并堆垛好，当装船任务触发时，场内集装箱被堆垛机取出，在交接区装载到内集卡上运输到岸边由岸桥起重机装船。进口集装箱流程则反之。

自动化集装箱码头布局

上图提到了一个自动化集装箱码头的概念，本文后续的所有问题都是以自动化码头为基础背景做分析的，为了更好地理解，下面为大家介绍一下自动化码头与普通码头在布局上以及交接规则上的差异。

在一个典型的自动化集装箱码头中，一般由多个集装箱区（Block）组成堆场为需要在此码头周转的集装箱提供临时存放的场所，堆场通常堆放着大量的集装箱。在布局规划中，为了减少非储存性面积的使用，自动化的箱区相比于传统码头的箱区减少了箱区两侧的缓冲区，在前端与末端设置了近水侧交接区和近陆侧交接区，详见下图。

自动化集装箱码头交接区差异

布局上的差异主要对堆垛起重机的移动路径有影响，在普通码头当中，因为集卡交箱可随意停靠在目标贝位两侧，堆垛机的移动路径是在任意两个集卡停靠的贝位之间自由往返；在自动化码头中，堆垛机和集卡的交接只能在前端与末端的交接区进行交接，堆垛机移动路径是近水侧/近陆侧交接区<-->贝位之间。

堆场内部的三维结构

从上面这张图我们大概就能知道集装箱存放的状态是怎样的了，在码头当中，它的三维结构都有着专业的名称，堆场（Yard）被划分成多个箱区（Block），通常为进口箱区、出口箱区、中转箱区等，而一个箱区内部则划分成贝位（Bay）、堆栈（Stack）、层高（Tier）,所以一个箱位（Slot）的位置信息必定包含了箱区号、贝位、堆栈、层高的信息。

所以OB-SAP问题的决策内容是：

将一批需要在堆场存放的出口集装箱合理分配一个箱位

二、数学模型

通过上面的介绍

您是否已经大概猜到建立OB-SAP问题的数学模型时候

涉及到哪一些参数条件了吧

在实际研究中，可以把箱位分配问题分割成两个阶段

先在箱区中找到要存放的贝位，再在贝位内具体化箱位

我们一起来看一下吧！

1	第一阶段模型（堆场贝位分配） （注：模型来源于作者自行整理） 关键词：内集卡运输距离、场桥移动距离 目标函数（1）表示堆场箱位分配的目标的内集卡运输距离和场桥起重机移动距离的最小； 约束（2）表示每一个集装箱只能选择一个贝位； 约束（3）是对每个贝位分配量的计算； 约束（4）表示贝位分配量不能超过贝位的最大容量； 约束（5）规定了决策变量的取值范围； 注：以上列举的模型是出口集装箱单箱区的贝位分配中最基本约束，对于复杂化的多泊位、多箱区模型会在以后关于此问题的拓展中分享给大家。
2	第二阶段模型（具体箱位分配） Source: Gharehgozli,A.et.al.(2018) 关键词：移箱/翻箱 在获得贝位分配量以后，接下来就是要确定集装箱堆存的具体位置，也就是要计算出一个集装箱该存放在哪一个堆栈和哪一层。建模的难点是在于要按照一定的取箱顺序，准确模拟出箱子所在堆位的上下关系，这直接决定了该箱子取箱时是否需要“翻箱”。 至于每一个堆位的箱子被堆垛机取走时的取箱“时间成本”，Gharehgozli,A.et.al.(2018)[文献6]通过模拟计算出堆垛机到每个堆位的取箱时间损耗，见下图（蓝色越深，耗时越短；红色越深，耗时越长）：

Source: Gharehgozli,A.et.al.(2018)

Gharehgozli,A.et.al.(2018)[文献6]在获知每个堆位的取箱时间损耗基础上，以总取箱时间最少为目标，建立具体箱位分配数学模型如下：

（变量符号续前表）

目标函数（1）最小化场桥堆垛机总取箱时间；

约束（2）确保每个位置最多只能存放一个集装箱；

约束（3）表示每个箱子只能选择一个箱位；

约束（4）确保比箱子i先取走的箱子必须堆存在箱子i的上面；

约束（5）表示当一个箱子不是堆放最底层时则必定有一个箱子被它压着；

约束（6）确定了决策变量的取值；

到这里，OB-SAP问题的建模就做完了！

可是，不是说关键词是移箱，翻箱吗？

通过以上对出口箱箱位分配问题的建模，我们也大概能了解到OB-SAP问题的算法复杂度了，Gharehgozli,A. et.al.(2018)[文献6]也证明了该问题是Np-complete问题。

其实在实际的集装箱箱位分配当中，后续提箱可能出现的翻箱是需要考虑的问题，因为实际中不能完全保证最先上船的箱子位于最上层或不被其他箱子压着，但想要通过数学式子来计算出实际取箱过程中的翻箱，这可就超出了小编的能力范围啦。下图能简单给大家描述一下翻箱过程。

这是一个贝位堆存状态的横截面，现需要把集装箱按编号取出，读取1号集装箱的位置信息后，发现其上层有6号集装箱压箱，则需要先把6号集装箱移到其他堆栈，再把1号箱取出。海运中通常把移动6号箱这样的操作称为翻箱。

像以上第一阶段、第二阶段模型都是假设在理想状态了，并没有将翻箱作为其中一个函数在模型中列出来，不过Kim et.al.（1999）；Yu et.al.（2013）文献[10-11]曾经用公式推算过当一个贝位中按照一定顺序把集装箱全部取出所产生的翻箱次数，有兴趣的小伙伴可以自行去查阅一下。

总结

以上只是对出口箱箱位分配问题做一个简单的介绍，内容大部分为小编与导师通过整理文献所得，目的是想让更多的人了解到海运当中的这一个经典问题哦！对于该问题的拓展与延伸，小编没有给大家详细列举，若有错误之处，欢迎大家指正。

由于篇幅问题，关于OB-SAP问题今天就为大家介绍到这里啦；如果大家有兴趣想要了解更多，小编下次还会给大家分享一些解决该问题常见的方法和一些经典的算例。

集装箱海运相关文献

[1]Kim, K.H., Günther, H.O.,2007. Container terminals and terminal operations. Container Terminals and Cargo Systems. OR Spectrum 28(4)437-445. 

[2]Stahlbock, R., Vob, S.,2008. Operations research at container terminals: a literature update. Or Spectrum 30(1):p.1-52.

[3]Steenken, D., Vob, S., Stahlbock, R., 2004. Container terminal operation and operations research ― a classification and literature review. Or Spectrum 26(1):3-49.

[4]Carlo, H.J., Vis, I.F.A., Roodbergen, K.J., 2014. Storage yard operations in container terminals: Literature overview, trends, and research directions. European Journal of Operational Research 235(2):412-430.

02

OB-SAP

[5]Kim, K.H., Lee, J.S., 2006. Satisfying constraints for locating export containers in port container terminals. International Conference on Computational Science & Its Applications/ICCSA 2006,PT3,3982,pp.564-573.

[6]Gharehgozli, A., Nima, Z., 2018. Stacking Outbound Barge Containers in an Automated Deep-Sea Terminal. European Journal of Operational Research S0377221717311748.

[7]Jiang, X., Lee, L.H., Chew, E.P., et.al. 2012. A container yard storage strategy for improving land utilization and operation efficiency in a transshipment hub port. European Journal of Operational Research 221(1):64-73.

[8]Chen, L., Lu, Z., 2012. The storage location assignment problem for outbound containers in a maritime terminal. International journal of production economics 135(1):pp.73-80.

[9]Zhang, C., Chen, W., Shi, L.,et. al. 2010. A note on deriving decision rules to locate export containers in container yards. European Journal of Operational Research 205(2):483-485.

03

Rehandle estimation

[10]Kim, K.H., Kim, H.B., 1999. Segregating space allocation models for container inventories in port container terminals. International Journal of Production Economics 59(1-3):415-423.

[11]Yu, M., Qi, X., 2013. Storage space allocation models for inbound containers in an automatic container terminal. European Journal of Operational Research 226(1):32-45.