關(guān)于集裝箱碼頭的那些事

- 集裝箱碼頭堆場(chǎng)箱位分配 -

集裝箱箱位分配問題

（Slots/Space Allocation Problem，簡(jiǎn)稱SAP）

是集裝箱碼頭運(yùn)作優(yōu)化的關(guān)鍵問題之一

在該問題中要求

在指定堆存區(qū)中完成一批集裝箱的箱位安排

每個(gè)集裝箱有各自唯一的編號(hào)

箱區(qū)堆位也有一定的容量與及高度限制

一個(gè)集裝箱只能選擇一個(gè)箱位進(jìn)行堆存

在箱位分配階段

每個(gè)集裝箱在箱位被取走到岸邊交接過程消耗的

堆垛機(jī)工作時(shí)間、集卡運(yùn)輸及等待時(shí)間都不一樣

主要決策是為每一個(gè)集裝箱具體分配一個(gè)箱位

實(shí)現(xiàn)取箱和存箱作業(yè)效率提升

出口集裝箱箱位分配問題

（Slots Allocation Problem for Outbound containers，簡(jiǎn)稱OB-SAP）

是SAP中針對(duì)出口集裝箱的特性

進(jìn)行具體性研究的一類問題

它在常見SAP問題的基本約束上

多了出口集裝箱隨機(jī)到港及按順序上船的約束

除了給每個(gè)集裝箱分配存箱具體箱位

還考慮后續(xù)裝船時(shí)所產(chǎn)生的移箱（翻箱）操作

接下來將給大家簡(jiǎn)單介紹OB-SAP問題

我們還會(huì)列出一些經(jīng)典數(shù)學(xué)模型哦

一、問題介紹

當(dāng)貨主/貨代公司將一批需要出口到國外的集裝箱運(yùn)輸?shù)酱a頭的時(shí)候，碼頭堆場(chǎng)管理員需要給每一個(gè)箱子安排一個(gè)箱位（slot）作為臨時(shí)存放點(diǎn)。

可能有些小伙伴對(duì)海運(yùn)不太了解，在詳細(xì)分析問題之前，小編先給大家簡(jiǎn)單介紹一個(gè)集裝箱碼頭的工作流程。在碼頭系統(tǒng)中，堆場(chǎng)（Yard）處于中間位置，對(duì)接著陸側(cè)和水側(cè)，劃分出堆存箱區(qū)為進(jìn)口箱以及出口箱等提供位置進(jìn)行臨時(shí)存放，堆場(chǎng)內(nèi)有內(nèi)集卡對(duì)接岸邊。當(dāng)出口集裝箱被外集卡送到碼頭后，在箱區(qū)近陸側(cè)經(jīng)由場(chǎng)橋堆垛起重機(jī)負(fù)責(zé)卸下并堆垛好，當(dāng)裝船任務(wù)觸發(fā)時(shí)，場(chǎng)內(nèi)集裝箱被堆垛機(jī)取出，在交接區(qū)裝載到內(nèi)集卡上運(yùn)輸?shù)桨哆呌砂稑蚱鹬貦C(jī)裝船。進(jìn)口集裝箱流程則反之。

自動(dòng)化集裝箱碼頭布局

上圖提到了一個(gè)自動(dòng)化集裝箱碼頭的概念，本文后續(xù)的所有問題都是以自動(dòng)化碼頭為基礎(chǔ)背景做分析的，為了更好地理解，下面為大家介紹一下自動(dòng)化碼頭與普通碼頭在布局上以及交接規(guī)則上的差異。

在一個(gè)典型的自動(dòng)化集裝箱碼頭中，一般由多個(gè)集裝箱區(qū)（Block）組成堆場(chǎng)為需要在此碼頭周轉(zhuǎn)的集裝箱提供臨時(shí)存放的場(chǎng)所，堆場(chǎng)通常堆放著大量的集裝箱。在布局規(guī)劃中，為了減少非儲(chǔ)存性面積的使用，自動(dòng)化的箱區(qū)相比于傳統(tǒng)碼頭的箱區(qū)減少了箱區(qū)兩側(cè)的緩沖區(qū)，在前端與末端設(shè)置了近水側(cè)交接區(qū)和近陸側(cè)交接區(qū)，詳見下圖。

自動(dòng)化集裝箱碼頭交接區(qū)差異

布局上的差異主要對(duì)堆垛起重機(jī)的移動(dòng)路徑有影響，在普通碼頭當(dāng)中，因?yàn)榧ń幌淇呻S意停靠在目標(biāo)貝位兩側(cè)，堆垛機(jī)的移動(dòng)路徑是在任意兩個(gè)集卡停靠的貝位之間自由往返；在自動(dòng)化碼頭中，堆垛機(jī)和集卡的交接只能在前端與末端的交接區(qū)進(jìn)行交接，堆垛機(jī)移動(dòng)路徑是近水側(cè)/近陸側(cè)交接區(qū)<-->貝位之間。

堆場(chǎng)內(nèi)部的三維結(jié)構(gòu)

從上面這張圖我們大概就能知道集裝箱存放的狀態(tài)是怎樣的了，在碼頭當(dāng)中，它的三維結(jié)構(gòu)都有著專業(yè)的名稱，堆場(chǎng)（Yard）被劃分成多個(gè)箱區(qū)（Block），通常為進(jìn)口箱區(qū)、出口箱區(qū)、中轉(zhuǎn)箱區(qū)等，而一個(gè)箱區(qū)內(nèi)部則劃分成貝位（Bay）、堆棧（Stack）、層高（Tier）,所以一個(gè)箱位（Slot）的位置信息必定包含了箱區(qū)號(hào)、貝位、堆棧、層高的信息。

所以O(shè)B-SAP問題的決策內(nèi)容是：

將一批需要在堆場(chǎng)存放的出口集裝箱合理分配一個(gè)箱位

二、數(shù)學(xué)模型

通過上面的介紹

您是否已經(jīng)大概猜到建立OB-SAP問題的數(shù)學(xué)模型時(shí)候

涉及到哪一些參數(shù)條件了吧

在實(shí)際研究中，可以把箱位分配問題分割成兩個(gè)階段

先在箱區(qū)中找到要存放的貝位，再在貝位內(nèi)具體化箱位

我們一起來看一下吧！

1	第一階段模型（堆場(chǎng)貝位分配） （注：模型來源于作者自行整理） 關(guān)鍵詞：內(nèi)集卡運(yùn)輸距離、場(chǎng)橋移動(dòng)距離 目標(biāo)函數(shù)（1）表示堆場(chǎng)箱位分配的目標(biāo)的內(nèi)集卡運(yùn)輸距離和場(chǎng)橋起重機(jī)移動(dòng)距離的最小； 約束（2）表示每一個(gè)集裝箱只能選擇一個(gè)貝位； 約束（3）是對(duì)每個(gè)貝位分配量的計(jì)算； 約束（4）表示貝位分配量不能超過貝位的最大容量； 約束（5）規(guī)定了決策變量的取值范圍； 注：以上列舉的模型是出口集裝箱單箱區(qū)的貝位分配中最基本約束，對(duì)于復(fù)雜化的多泊位、多箱區(qū)模型會(huì)在以后關(guān)于此問題的拓展中分享給大家。
2	第二階段模型（具體箱位分配） Source: Gharehgozli,A.et.al.(2018) 關(guān)鍵詞：移箱/翻箱 在獲得貝位分配量以后，接下來就是要確定集裝箱堆存的具體位置，也就是要計(jì)算出一個(gè)集裝箱該存放在哪一個(gè)堆棧和哪一層。建模的難點(diǎn)是在于要按照一定的取箱順序，準(zhǔn)確模擬出箱子所在堆位的上下關(guān)系，這直接決定了該箱子取箱時(shí)是否需要“翻箱”。 至于每一個(gè)堆位的箱子被堆垛機(jī)取走時(shí)的取箱“時(shí)間成本”，Gharehgozli,A.et.al.(2018)[文獻(xiàn)6]通過模擬計(jì)算出堆垛機(jī)到每個(gè)堆位的取箱時(shí)間損耗，見下圖（藍(lán)色越深，耗時(shí)越短；紅色越深，耗時(shí)越長(zhǎng)）：

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

Gharehgozli,A.et.al.(2018)[文獻(xiàn)6]在獲知每個(gè)堆位的取箱時(shí)間損耗基礎(chǔ)上，以總?cè)∠鋾r(shí)間最少為目標(biāo)，建立具體箱位分配數(shù)學(xué)模型如下：

（變量符號(hào)續(xù)前表）

目標(biāo)函數(shù)（1）最小化場(chǎng)橋堆垛機(jī)總?cè)∠鋾r(shí)間；

約束（2）確保每個(gè)位置最多只能存放一個(gè)集裝箱；

約束（3）表示每個(gè)箱子只能選擇一個(gè)箱位；

約束（4）確保比箱子i先取走的箱子必須堆存在箱子i的上面；

約束（5）表示當(dāng)一個(gè)箱子不是堆放最底層時(shí)則必定有一個(gè)箱子被它壓著；

約束（6）確定了決策變量的取值；

到這里，OB-SAP問題的建模就做完了！

可是，不是說關(guān)鍵詞是移箱，翻箱嗎？

通過以上對(duì)出口箱箱位分配問題的建模，我們也大概能了解到OB-SAP問題的算法復(fù)雜度了，Gharehgozli,A. et.al.(2018)[文獻(xiàn)6]也證明了該問題是Np-complete問題。

其實(shí)在實(shí)際的集裝箱箱位分配當(dāng)中，后續(xù)提箱可能出現(xiàn)的翻箱是需要考慮的問題，因?yàn)閷?shí)際中不能完全保證最先上船的箱子位于最上層或不被其他箱子壓著，但想要通過數(shù)學(xué)式子來計(jì)算出實(shí)際取箱過程中的翻箱，這可就超出了小編的能力范圍啦。下圖能簡(jiǎn)單給大家描述一下翻箱過程。

這是一個(gè)貝位堆存狀態(tài)的橫截面，現(xiàn)需要把集裝箱按編號(hào)取出，讀取1號(hào)集裝箱的位置信息后，發(fā)現(xiàn)其上層有6號(hào)集裝箱壓箱，則需要先把6號(hào)集裝箱移到其他堆棧，再把1號(hào)箱取出。海運(yùn)中通常把移動(dòng)6號(hào)箱這樣的操作稱為翻箱。

像以上第一階段、第二階段模型都是假設(shè)在理想狀態(tài)了，并沒有將翻箱作為其中一個(gè)函數(shù)在模型中列出來，不過Kim et.al.（1999）；Yu et.al.（2013）文獻(xiàn)[10-11]曾經(jīng)用公式推算過當(dāng)一個(gè)貝位中按照一定順序把集裝箱全部取出所產(chǎn)生的翻箱次數(shù)，有興趣的小伙伴可以自行去查閱一下。

總結(jié)

以上只是對(duì)出口箱箱位分配問題做一個(gè)簡(jiǎn)單的介紹，內(nèi)容大部分為小編與導(dǎo)師通過整理文獻(xiàn)所得，目的是想讓更多的人了解到海運(yùn)當(dāng)中的這一個(gè)經(jīng)典問題哦！對(duì)于該問題的拓展與延伸，小編沒有給大家詳細(xì)列舉，若有錯(cuò)誤之處，歡迎大家指正。

由于篇幅問題，關(guān)于OB-SAP問題今天就為大家介紹到這里啦；如果大家有興趣想要了解更多，小編下次還會(huì)給大家分享一些解決該問題常見的方法和一些經(jīng)典的算例。

集裝箱海運(yùn)相關(guān)文獻(xiàn)

[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.