鄭斯斯

（惠州學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，廣東 惠州 516007）

1 研究背景

伴隨全球貿(mào)易保護(hù)主義的抬頭態(tài)勢，國際物流市場持續(xù)萎靡，港口需要提高效率以吸引更多的航班掛靠；此外，船舶大型化的發(fā)展趨勢也對集裝箱碼頭的裝卸效率提出了更高的要求.面對新的挑戰(zhàn)，世界范圍內(nèi)的集裝箱港口運(yùn)營商紛紛利用物流自動(dòng)化技術(shù)來提升港口的效率和競爭力.在集裝箱碼頭，集裝箱的翻箱率是衡量碼頭作業(yè)效率的關(guān)鍵因素.假設(shè)碼頭的年吞吐量為40 萬TEU，翻箱作業(yè)成本為20 元/TEU，翻箱時(shí)間為4min/TEU，則翻箱率每降低3%，碼頭每年可以節(jié)約作業(yè)成本達(dá)84 萬元，節(jié)約作業(yè)時(shí)間達(dá)800 h.因此，減少翻箱數(shù)量能大幅度節(jié)約作業(yè)成本和作業(yè)時(shí)間.翻箱率的高低在很大程度上是由箱位調(diào)度的效果所決定，科學(xué)合理的箱位調(diào)度策略能有效減少翻箱率.盡管越來越多的自動(dòng)化集裝箱碼頭投入運(yùn)營，但關(guān)于集裝箱碼頭從傳統(tǒng)向自動(dòng)化轉(zhuǎn)型中出現(xiàn)的集裝箱的箱位調(diào)度、翻箱等關(guān)鍵科學(xué)和實(shí)際問題的研究有待深入開展.

學(xué)者們針對自動(dòng)化集裝箱碼頭的研究主要集中在碼頭布局和自動(dòng)化設(shè)備2 個(gè)方面，筆者結(jié)合學(xué)術(shù)界已有的研究成果，對其研究現(xiàn)狀進(jìn)行簡要梳理.早期針對自動(dòng)化集裝箱碼頭的研究著重于碼頭布局方面，結(jié)合現(xiàn)場作業(yè)特點(diǎn)可知，自動(dòng)化碼頭有垂岸式布局和水平式布局2 種形式，垂岸式布局不但可以減少水平運(yùn)輸車輛的行駛距離，而且可以提高堆場的利用率，因此這種布局更適合自動(dòng)化碼頭［1-4］. 針對碼頭的自動(dòng)化程度，劉廣紅等［5］對半自動(dòng)化碼頭、AGV 全自動(dòng)化碼頭、跨運(yùn)車全自動(dòng)化碼頭和立體分配全自動(dòng)化碼頭的布局、裝卸流程、港區(qū)內(nèi)交通組織和環(huán)保性能等多方面進(jìn)行分析與對比.王施恩等［6］對歐美幾個(gè)大型的自動(dòng)化碼頭的平面布置、堆場特征等方面進(jìn)行分析，研究結(jié)果表明：垂岸式布局能有效將海側(cè)自動(dòng)化車流和陸側(cè)人工駕駛車輛分離，有利于港區(qū)的交通組織.裝卸設(shè)備主要有自動(dòng)化堆碼起重機(jī)（ASC）、自動(dòng)化軌道式龍門吊起重機(jī)（ARMG）、輪胎式龍門吊起重機(jī)（ARTG），對起重機(jī)進(jìn)行合理調(diào)度以避免沖突是國內(nèi)外學(xué)者的研究重點(diǎn).其中，針對ARTG 調(diào)度的研究較少，Rizaldi 等［7］以集卡停留時(shí)間和ARTG 的能源消耗為評價(jià)指標(biāo)，用仿真方法對3 種場橋調(diào)度方案進(jìn)行比較.針對ARMG 調(diào)度的研究較多，以雙ARMG協(xié)調(diào)調(diào)度為主.魏晨等［8］研究了接力式作業(yè)的ARMG 調(diào)度問題；裴磊磊和萇道方［9］考慮了2臺(tái)ARMG之間的協(xié)調(diào)性和緩存區(qū)的容量限制；周靜嫻和胡志華［10］對雙ASC執(zhí)行任務(wù)的序列進(jìn)行優(yōu)化，提出規(guī)避沖突后的最優(yōu)作業(yè)序列.李敏和韓曉龍［11］考慮了集裝箱任務(wù)組的時(shí)間窗約束，并且提出了8 條優(yōu)先權(quán)規(guī)則來解決同一貝位上任務(wù)的沖突.Han等［4］總結(jié)了4 種起重機(jī)運(yùn)作模式，以最小化作業(yè)時(shí)間為優(yōu)化目標(biāo)，構(gòu)建了混合整數(shù)規(guī)劃模型并設(shè)計(jì)了遺傳算法進(jìn)行求解.

已有研究文獻(xiàn)對論文開展提供了良好的理論與技術(shù)支持，但仍有待解決的問題：大多數(shù)研究假設(shè)提箱過程中沒有新進(jìn)集裝箱，箱位調(diào)度時(shí)并沒有結(jié)合集裝箱的進(jìn)場和離場；較少研究關(guān)注動(dòng)態(tài)模式下，集裝箱同時(shí)進(jìn)出場的情況.因此，有必要進(jìn)行深入探討，進(jìn)而提出相應(yīng)的調(diào)度方案.作者在該領(lǐng)域也做了部分研究，在Zheng 等［12-16］、鄭斯斯和王愛虎［17-18］等文獻(xiàn)中分別研究了集裝箱碼頭的翻箱問題、箱位選擇問題等.本文將在已有研究基礎(chǔ)上對集裝箱調(diào)度問題進(jìn)行研究，分別分析集裝箱的進(jìn)場和出場情況，并在動(dòng)態(tài)模式下考慮集裝箱同步進(jìn)場和離場，構(gòu)建雙層目標(biāo)規(guī)劃模型，開發(fā)集裝箱綜合調(diào)度的路徑優(yōu)化算法（POA）研究滿足理論與現(xiàn)實(shí)的雙重需求，在理論上為我國集裝箱碼頭的自動(dòng)化和智能化建設(shè)提供方法論，在實(shí)踐上為集裝箱碼頭成本的降低、效率的提升和管理水平的改善提供決策依據(jù)和指導(dǎo).

2 集裝箱的綜合調(diào)度模型

2.1 基本問題描述及符號定義

在堆場中，根據(jù)集裝箱的不同屬性通常會(huì)分成不同的箱區(qū)，每個(gè)箱區(qū)包括多個(gè)貝，每個(gè)貝有垂直堆放的多個(gè)棧，每個(gè)?？梢远讯舛鄬蛹b箱.在集裝箱碼頭堆場，最便捷的裝卸設(shè)備是軌道龍門吊，龍門吊的走動(dòng)包括水平方向以及垂直方向.其中，水平方向的走動(dòng)由龍門吊大車完成，是指在不同貝位之間的操作；垂直方向的走動(dòng)由龍門吊小車完成，是指同一貝位不同棧之間的操作.本文所用的基本符號見表1.

表1 集裝箱調(diào)度問題的符號說明

（續(xù)表1）

2.2 模型構(gòu)建

集裝箱調(diào)度包括：集裝箱進(jìn)場和出場，集裝箱調(diào)度的目標(biāo)是減少壓箱或翻箱數(shù)量，為此構(gòu)建集裝箱的綜合調(diào)度模型，目標(biāo)函數(shù)和約束條件如下：

約束條件由上至下分別表示每次作業(yè)中，任意集裝箱只能放在一個(gè)箱位中；任意箱位slot（m，n，k）最多只能放一個(gè)集裝箱；龍門吊的初始位置在第1貝；每一貝的集裝箱數(shù)量不超過該貝位的具體容量；任意集裝箱均不允許懸空放置；集裝箱a 和b分別放在箱位slot（m，n，k）和slot（m，n，k-z），且有P（a）＜P（b），即優(yōu)先級更高的集裝箱a箱位比集裝箱b低層，則移走集裝箱a時(shí)，需先移走集裝箱b，記一次翻箱，即Rmn（k-z）=1（m=1，2，…，M；n=1，2，…，N；k=1，2，…，K）.

3 集裝箱的綜合調(diào)度算法

3.1 調(diào)度策略

由于集裝箱調(diào)度問題是一個(gè)NP-hard 問題，模型很難求出精確解.因此，作者在現(xiàn)場調(diào)研的基礎(chǔ)上，提煉多個(gè)調(diào)度策略并構(gòu)建規(guī)則庫，設(shè)置啟發(fā)式算法以減少一些非優(yōu)的調(diào)度路徑.以下調(diào)度策略將有助于在調(diào)度過程中，選取最優(yōu)箱位.

（1）同貝優(yōu)先，鄰貝次之原則（Same Bay First &Neighboring Bays Second，SFNS）.針對阻塞箱落箱位置的選取，優(yōu)先考慮移到同貝箱位，同貝箱位已滿時(shí)，再考慮移到鄰貝.

（2）阻塞箱較少原則（Least-Obstructive Heuristic，LOH）.當(dāng)阻塞箱在同貝位內(nèi)搜尋落箱位置時(shí)，根據(jù)集裝箱的優(yōu)先級，比較阻塞箱與同貝位內(nèi)不同棧集裝箱的優(yōu)先級.棧內(nèi)阻塞箱越少，造成壓箱或翻箱數(shù)量就越小.

（3）就近原則（Nearest-Slot Heuristic，NSH）.為了操作便捷，經(jīng)常將阻塞箱放在同貝位且離原箱位最近棧的空箱位上.龍門吊移動(dòng)距離越小，作業(yè)時(shí)間越短.

（4）最矮棧原則（Lowest-Slot Heuristic，LSH）.出于安全考慮，經(jīng)常將集裝箱放在同貝位內(nèi)最矮棧，保證平均高度最矮.堆垛高度越低，發(fā)生事故概率越低.

（5）重心穩(wěn)定原則（stable core Heuristic，SCH）.在多貝位的箱位分配中，優(yōu)先將集裝箱放在低層，保持重心穩(wěn)定.

3.2 算法框架

構(gòu)建規(guī)則庫并將多個(gè)規(guī)則嵌入集裝箱調(diào)度，設(shè)計(jì)多個(gè)規(guī)則并行使用下的算法.集裝箱進(jìn)場的路徑優(yōu)化算法（Path Optimum Algorithm，簡稱進(jìn)場POA）的步驟詳見算法1，該算法使得集裝箱進(jìn)場作業(yè)更加科學(xué)合理.

算法1：集裝箱進(jìn)場的路徑優(yōu)化算法（進(jìn)場POA）

輸入：進(jìn)場序列；集裝箱總數(shù)量；

變量：A表示一個(gè)進(jìn)場序列，矩陣規(guī)模為1行s列；B 表示最終輸出的箱位矩陣；B（bay，stack，tier）表示集裝箱的箱位，其中（bay，stack，tier）=（m，n，k），當(dāng)m=1，B（bay，stack，tier）可以簡單記為B（stack，tier）；s 表示總的集裝箱數(shù)量；rth container 表示集裝箱的優(yōu)先級，即第r 號集裝箱；N（sm）表示箱區(qū)中集裝箱移動(dòng)的總次數(shù)；N（sy）表示箱區(qū)中集裝箱壓箱的總次數(shù)；

輸出：集裝箱移動(dòng)的總次數(shù)；集裝箱壓箱的總次數(shù)；最優(yōu)分配路徑；運(yùn)行時(shí)間.

1：設(shè)置初始進(jìn)場序列A規(guī)模是1行s列，并開始計(jì)時(shí)

2：初始設(shè)置N（sm）←0，N（sy）←0，rth container←1，G（n）←1 {重置計(jì)數(shù)器}

3：for 分配的集裝箱數(shù)量＜=s do

4： if Bay的數(shù)量m=1 then

5： 矩陣B（stack，tier）的最底層與矩陣A 第1至第n列一致

6： for 集裝箱數(shù)量=（n+1）：s do {依次判斷第（n+1）至第s個(gè)集裝箱的箱位}

7： 執(zhí)行規(guī)則一：壓箱數(shù)量最少.壓箱數(shù)是指要放入的元素，與當(dāng)前列中所有元素相比，如果要放入元素的優(yōu)先級更小，記為1，一共小幾個(gè)，記為幾，如果該列最高層已放滿，則記為inf，比較各列的壓箱數(shù)量，選擇最少的一列，記壓箱數(shù)N（sy）=w

8： 執(zhí)行規(guī)則二：最近原則.依次判斷要放入元素與每一列的橫向距離，與第一列距離1，第二列記為2，第三列記為3，直至最后一列，如果該列最高層已放滿，則記為inf，比較與各列的距離，選擇最近的一列

9： 執(zhí)行規(guī)則三：最矮原則.依次判斷要放入元素與每一列的縱向距離，如果第一列已有元素2個(gè)，記為2，如果第二列已有元素為3，記為3，如果該列最高層已放滿，則記為inf，比較各列的已有元素，選擇最少一列

10： 依次執(zhí)行規(guī)則一至規(guī)則三，比較各列已有元素，選擇最少一列，將目標(biāo)箱放在第n棧（n=1，2，…，N）第k層（k=1，2，…，K），并繼續(xù)判斷下一個(gè)集裝箱

11： N（sm）←N（sm）+1

12： N（sy）←N（sy）+w

13： end for

14： else {Bay的數(shù)量m＞=1}

15： 貝的數(shù)量為m，棧的數(shù)量為（n/m），層的數(shù)量為k

16： 第1貝矩陣B（1，stack，tier）的最底層與矩陣A 第1 至第（n/m）列一致，第2 貝矩陣B（2，stack，tier）的最底層與矩陣A第（n/m+1）至第（2n/m）列一致，第m 貝矩陣B（m，stack，tier）的最底層與矩陣A 第［（m-1）*n/m+1］至第n列一致

17： for 集裝箱數(shù)量=（n+1）：s do {依次判斷第（n+1）至第s個(gè)集裝箱箱位}

18： 依次判斷規(guī)則一至三后，繼續(xù)判斷規(guī)則四：重心穩(wěn)定堆垛原則，當(dāng)該貝最底層已滿，跳到下一貝安排箱位，并繼續(xù)判斷下一個(gè)集裝箱

19： N（sm）←N（sm）+1

20： N（sy）←N（sy）+w

21： end for

22： end if

23：end for

24：直到系統(tǒng)內(nèi)沒有目標(biāo)箱

25：返回集裝箱移動(dòng)的總次數(shù)；集裝箱壓箱的總次數(shù)；最優(yōu)箱位分配路徑；運(yùn)行時(shí)間.

26：結(jié)束計(jì)時(shí)

集裝箱離場的路徑優(yōu)化算法（簡稱離場POA）的步驟詳見算法2，該算法能使得翻箱作業(yè)更有效率，加快運(yùn)行速度.

算法2：集裝箱離場的路徑優(yōu)化算法（離場POA）

輸入：箱位矩陣（任一狀態(tài)）；集裝箱總數(shù)量；

變量：B表示一個(gè)三維矩陣；B（bay，stack，tier）表示集裝箱的箱位；S表示總的集裝箱數(shù)量；rth container表示集裝箱的優(yōu)先級，即第r 號集裝箱；N（sm）表示箱區(qū)中集裝箱移動(dòng)的總次數(shù)；N（sr）表示箱區(qū)中集裝箱翻箱的總次數(shù)；G（n）為決策變量，等于1時(shí)表示移動(dòng)到其它貝位，等于0時(shí)表示其它.

輸出：集裝箱移動(dòng)的總次數(shù)；集裝箱翻箱的總次數(shù)；最優(yōu)翻箱路徑；運(yùn)行時(shí)間.

1：設(shè)置初始三維矩陣B規(guī)模是M×N×K（即M貝N棧K層），并開始計(jì)時(shí)

2：初始設(shè)置N（sm）←0，N（sr）←0，rth container←1，G（n）←1{重置計(jì)數(shù)器}

3：for 棧的數(shù)量＜=（N-1）do

4： 決定是否需要將阻塞箱移動(dòng)到其它貝位

5： ifB（bay，n，tier）=0 then

6： 將阻塞箱放在該貝位的第n棧（n=1，2，…，N），并繼續(xù)判斷下一個(gè)集裝箱

7： else

8： 判斷該貝位中其它棧是否有空箱位

9： ifG（n）==1{該貝位中的其它棧沒有空箱位可用于放置阻塞箱，該阻塞箱需要移動(dòng)到其它貝位}

10： ifbay＞1 or bay＜mthen

11： fora=1：1：（bay-1）or b=（bay+1）：1：mdo

12： 判斷第a貝位或第b貝位中是否有空箱位

13： ifG（n）==0then

14： 該阻塞箱可放于第a貝位或第b貝位

15： end if

16： end for

17： end if

18：N（sm）←N（sm）+1

19：N（sr）←N（sr）+1

20： end if

21： end if

22：end for

23：N（sm）←N（sm）+1

24：N（sr）

25：直到系統(tǒng)內(nèi)沒有集裝箱

26：返回集裝箱移動(dòng)的總次數(shù)；集裝箱翻箱的總次數(shù)；最優(yōu)翻箱路徑；運(yùn)行時(shí)間.

27：結(jié)束計(jì)時(shí)

根據(jù)集裝箱綜合調(diào)度的詳細(xì)流程（圖1），將多個(gè)規(guī)則嵌入算法，從而得到集裝箱綜合調(diào)度路徑優(yōu)化算法（簡稱綜合調(diào)度POA），由此得到優(yōu)化調(diào)度路徑、移箱數(shù)量、壓箱數(shù)量、翻箱數(shù)量、運(yùn)行時(shí)間.

圖1 集裝箱綜合調(diào)度的詳細(xì)流程圖

集裝箱綜合調(diào)度POA 的優(yōu)點(diǎn)表現(xiàn)在：算法可適用于單貝、多貝的箱位調(diào)度和動(dòng)態(tài)模式下的進(jìn)出場綜合調(diào)度；啟用規(guī)則庫，多個(gè)規(guī)則并行使用，對集裝箱的移動(dòng)路徑進(jìn)行多層篩選；有助于排除大量非優(yōu)的集裝箱選擇方案，從而減少了計(jì)算復(fù)雜度；針對集裝箱的不同初始狀態(tài)，只需要改變初始輸入矩陣，就能求解問題，并且運(yùn)行的代碼改變得越少，箱位選擇決策時(shí)間越短，越符合高速運(yùn)轉(zhuǎn)的集裝箱碼頭.

4 算例分析

4.1 集裝箱進(jìn)場

數(shù)值實(shí)驗(yàn)的第一部分將測試集裝箱進(jìn)場的性能，數(shù)值測試基本場景為：箱區(qū)內(nèi)有M貝N棧K層，一共有1 到S號集裝箱需放入該箱區(qū).要求S≤M×N×K-（K-1），使得箱區(qū)內(nèi)有足夠的空箱位便于后續(xù)翻箱使用.隨機(jī)生成100組M×N×K-（K-1）個(gè)集裝箱的進(jìn)場序列，執(zhí)行進(jìn)場POA并記錄對應(yīng)數(shù)據(jù).

由在單貝和多貝不同利用率下的集裝箱平均壓箱數(shù)量和計(jì)算機(jī)平均運(yùn)行時(shí)間（見表2、表3）可知：使用進(jìn)場POA可以合理分配單貝或多貝集裝箱，控制集裝箱的壓箱數(shù)量，作業(yè)效果優(yōu)于人工作業(yè)；使用進(jìn)場POA能在短時(shí)間內(nèi)為集裝箱分配合適箱位；當(dāng)箱區(qū)規(guī)模為10貝16棧9層，最大容量達(dá)到1 440 TEU的情況下，計(jì)算機(jī)的運(yùn)行時(shí)間仍舊控制在0.2 s以內(nèi).

表2 單貝不同利用率下的集裝箱平均壓箱數(shù)量和計(jì)算機(jī)的平均運(yùn)行時(shí)間

表3 多貝不同利用率下的集裝箱平均壓箱數(shù)量和計(jì)算機(jī)的平均運(yùn)行時(shí)間

4.2 集裝箱離場

數(shù)值實(shí)驗(yàn)的第二部分將測試集裝箱離場的性能，數(shù)值測試基本場景為：箱區(qū)內(nèi)有M貝N棧K層，一共有1到S號集裝箱在該箱區(qū)內(nèi).要求S≤M×N×K-（K-1），使得箱區(qū)內(nèi)有足夠的空箱位便于翻箱使用.生成M×N×K-（K-1）個(gè)集裝箱，并且每個(gè)集裝箱的提箱序列已經(jīng)給定.隨機(jī)生成100組初始狀態(tài)下的三維矩陣實(shí)例，執(zhí)行離場POA并記錄對應(yīng)數(shù)據(jù).

由箱區(qū)不同利用率下的集裝箱平均翻箱數(shù)量、計(jì)算機(jī)平均運(yùn)行時(shí)間以及龍門吊移動(dòng)的曼哈頓距離（表4）可知：使用離場POA能在最大程度上控制集裝箱的翻箱數(shù)量，且作業(yè)效果將遠(yuǎn)遠(yuǎn)優(yōu)于僅僅依賴人工作業(yè)經(jīng)驗(yàn)，翻箱數(shù)量越少，作業(yè)速度越快，作業(yè)效率越高；使用離場POA 能將計(jì)算機(jī)的運(yùn)行時(shí)間保持在一個(gè)穩(wěn)定的較低水平；使用離場POA能在最大程度上控制龍門吊移動(dòng)的曼哈頓距離，且作業(yè)效果將遠(yuǎn)遠(yuǎn)優(yōu)于僅僅依賴人工作業(yè)經(jīng)驗(yàn)以及僅僅采用單一的翻箱策略，當(dāng)龍門吊移動(dòng)的曼哈頓距離越少，龍門吊的損耗越少，并且作業(yè)成本越低.

表4 箱區(qū)不同利用率下的集裝箱平均翻箱數(shù)量、計(jì)算機(jī)平均運(yùn)行時(shí)間以及龍門吊移動(dòng)的平均曼哈頓距離

4.3 集裝箱綜合調(diào)度

數(shù)值實(shí)驗(yàn)的第三部分將測試集裝箱綜合調(diào)度的性能，數(shù)值測試基本場景為：1個(gè)箱區(qū)內(nèi)有M貝N棧K層，有多個(gè)集裝箱需要進(jìn)入或離開箱區(qū).這里隨機(jī)生成一組示例，執(zhí)行綜合調(diào)度POA 并記錄對應(yīng)數(shù)據(jù)，便于觀察算法的運(yùn)行結(jié)果.分2 種情況進(jìn)行討論：第1 種情況是進(jìn)場和提箱序列確定的情況下，為集裝箱分配合適箱位后，再將這些集裝箱提出堆場，這2個(gè)過程是分離的，而且進(jìn)場和離場過程中沒有新進(jìn)集裝箱；第2種情況是進(jìn)場和提箱序列已定，且集裝箱進(jìn)場和離場是同步進(jìn)行的，2個(gè)過程不再分離.綜合調(diào)度POA實(shí)現(xiàn)了從理論模型到實(shí)際場景的改進(jìn)，實(shí)現(xiàn)集裝箱同步進(jìn)出場的調(diào)度，拉近理論研究與實(shí)踐應(yīng)用之間的距離，向管理實(shí)踐靠攏.

5 小結(jié)

該文以集裝箱碼頭轉(zhuǎn)型升級為背景，探討動(dòng)態(tài)模式下集裝箱的綜合調(diào)度問題，融入實(shí)踐經(jīng)驗(yàn)元素的調(diào)度策略，并行使用多個(gè)規(guī)則，對集裝箱的移動(dòng)路徑進(jìn)行多層篩選.在此基礎(chǔ)上，實(shí)現(xiàn)集裝箱同步進(jìn)出場的調(diào)度，讓進(jìn)場和出場不再分離，拉近理論研究與實(shí)踐應(yīng)用之間的距離，向管理實(shí)踐靠攏.數(shù)值測試結(jié)果表明：本文提出的綜合調(diào)度POA 適用于單貝或多貝下的集裝箱調(diào)度問題，集裝箱可以隨意進(jìn)場和出場，算法實(shí)現(xiàn)在多個(gè)規(guī)則篩選下為集裝箱分配合適的箱位，有效減低翻箱率和壓箱數(shù)量，提高作業(yè)效率.實(shí)現(xiàn)了集裝箱進(jìn)場和出場同步進(jìn)行的箱位調(diào)度，也提煉出適用于集裝箱調(diào)度問題的共性策略，達(dá)到了優(yōu)化作業(yè)的目標(biāo)，但這些研究是在一定假設(shè)條件下進(jìn)行的，所以得到的結(jié)論仍舊存在不足之處.為使研究更全面，更適應(yīng)集裝箱碼頭的作業(yè)場景，進(jìn)一步研究方向可以考慮不確定因素.