張艷偉，馬佳樂

（武漢理工大學物流工程學院，湖北武漢430063）

截至2019 年，我國集裝箱吞吐量已增至26 107萬TEU（國際標準箱）。集裝箱貿(mào)易量的不斷增長促進了海運船舶的大型化發(fā)展以及碼頭前沿裝卸設備的更新?lián)Q代。其中，雙40 ft（1 ft=30.48 cm）岸橋為雙吊具設計，通過吊具伸縮，單側吊具可以吊取1個40 ft 箱、2 個20 ft 箱或1 個20 ft 箱（艏艉裝卸）。船舶配載情況良好時，雙吊具同時使用，一次裝卸2個40 ft箱，若岸橋吊具對位亦滿足要求，最多一次裝卸4個20 ft箱。即理論上最多可以在一次作業(yè)中完成2 個40 ft 集裝箱或4 個20 ft 集裝箱的裝卸，在降低船舶周轉時間和提升碼頭裝卸效率方面具備突出優(yōu)勢［1］，陸續(xù)被各大集裝箱碼頭投入使用。

為充分發(fā)揮雙40 ft 岸橋的效率，需盡可能保證岸橋雙吊具的常見作業(yè)工況［2］，避免其余工況因頻繁調(diào)節(jié)吊具浪費時間，但雙40 ft 岸橋受其自身的限制，無法實現(xiàn)將2 個40 ft 集裝箱同時裝載到集裝箱船不同層的兩個箱位，因此，雖然雙40 ft岸橋能夠加快碼頭作業(yè)的速度，但同時亦對集裝箱船配載計劃提出了更高的要求。本文旨在提出適合多港口雙40 ft 岸橋裝卸的配載策略和模型，為船舶掛靠港雙40 ft岸橋裝卸提供條件，同時適用于普通岸橋作業(yè)。

多港集裝箱船配載主貝計劃問題（MP-MBPP），旨在將不同屬性的集裝箱劃分箱組，實現(xiàn)箱組到船舶具體貝位的一一匹配，并運往后續(xù)港口，同時需兼顧船舶穩(wěn)性、容量等條件。Wilson 等［3］為高效制定配載計劃，提出采用分階段法研究船舶全航線配載問題，并通過在目標函數(shù)中加入啟發(fā)式規(guī)則得到較優(yōu)配載方案，由于數(shù)學規(guī)劃求解效率較低，僅得到了局部最優(yōu)結果。Wilson等［4］提出了一種多港口運輸集裝箱船配載計劃生成方法，同時考慮了各港口并行作業(yè)普通岸橋數(shù)量最大化問題。張維英等［5］采用多階段法研究非混裝情況下20 ft及40 ft標準箱的配載問題，在主貝計劃中以貝位占用數(shù)量最少、倒箱量最少和集裝箱船載箱率最高為目標，通過基于二叉搜索樹算法求解得到了船舶預配載方案。Pacino 等［6］提出一種生成近似最優(yōu)配載計劃的兩階段方法，以最小化倒箱為目標，使用CPLEX 求解器求解混裝策略下的主貝計劃（MBPP）問題。Monaco等［7］研究了面向碼頭的船舶配載規(guī)劃問題，以最小化集裝箱運輸時間和堆場移動次數(shù)為目標建立了二元整數(shù)模型，其設計的禁忌搜索算法能夠在較短時間內(nèi)找到近似最優(yōu)解，但該模型忽略了堆棧的穩(wěn)定性約束。Ambrosino等［8-9］將MBPP擴展為多港口主貝計劃（MP-MBPP）問題，考慮了艙蓋對配載的影響，以最小化船舶在港停泊時間為目標建立了新型混合整數(shù)規(guī)劃模型，能夠在較短時間內(nèi)求解可容納超大型船舶的配載計劃。Li等［10］研究了集裝箱班輪運輸配載規(guī)劃問題，以20 ft和40 ft普通箱為研究對象，通過基于啟發(fā)式算法的貪婪隨機自適應搜索算法求解MBPP問題。

以上對多港口主貝計劃問題的研究很少考慮雙40 ft岸橋裝卸對配載的要求，且配載箱型較為單一，難以適應大型港口裝卸設備更新?lián)Q代的趨勢。本文考慮雙40 ft 岸橋裝卸對配載的要求，以20 ft 和40 ft普通箱和冷藏箱為配載對象，以岸橋裝卸次數(shù)（雙40 ft岸橋適合率最高）與倒箱最小為總目標，考慮船舶穩(wěn)性等限制構建多港口主貝計劃配載模型，通過基于啟發(fā)式規(guī)則的裝箱算法驗證可滿足雙40 ft岸橋裝卸的配載策略，同時驗證模型的有效性。

1 問題描述

集裝箱船的多港口配載問題旨在為航線經(jīng)營商指定的特定航線的集裝箱船制訂配載計劃，其目標是滿足服務需求并縮短船舶在各個港口的停留時間［11］。空船自初始港裝載起航，途經(jīng)各港口p，分別完成卸載當前目的港的集裝箱組并裝載一組帶有目的港d屬性的集裝箱，行至最終港卸下所有集裝箱。集裝箱船的貨艙以若干具有防漏結構的艙蓋劃分為甲板和艙內(nèi)兩部分，一塊艙蓋可覆蓋其下幾個相鄰貝位。假設將某一艙蓋的甲板和艙內(nèi)位置都分配給一個目的地，采用此配載方式可以避免艙蓋的多次抬放并提高裝卸效率［12］。海船結構如圖1 所示，一般使用連續(xù)的奇數(shù)01、03、05……表示船舶奇數(shù)貝，用奇數(shù)貝之間的偶數(shù)02、06、10……表示船舶偶數(shù)貝。

船舶配載時，首先需重點考慮雙40 ft 岸橋?qū)ε漭d的要求，劃分箱組時盡量保證可以滿足雙40 ft 岸橋常見滿載裝卸工況，發(fā)揮雙40 ft 岸橋裝卸優(yōu)勢。其次需盡量避免冷藏箱倒箱，且冷藏集裝箱僅可堆存于安裝有電源插頭的特殊箱位，同時需考慮船舶全航線穩(wěn)性［13］。

圖1 船舶結構Fig.1 Ship structure

2 數(shù)學模型

基于以下假設建立MP-MBPP模型：

（1）航線各掛靠港中待裝集裝箱的屬性信息已知，如集裝箱的類型、尺寸、目的港、數(shù)量、質(zhì)量等。

（2）集裝箱船結構已知，包括船舶貝位數(shù)量、各貝容量、編號等信息。

（3）僅考慮20 ft 和40 ft 干貨箱和冷藏箱，忽略超限箱和危險箱等。

2.1 集合

P為集裝箱船航線經(jīng)過的港口集合。

S 為集裝箱尺寸集合，?s∈S={1，2}，1 表示集裝箱尺寸為20 ft，2表示集裝箱尺寸為40 ft。

T 為集裝箱類型集合，T={τ1，τ2}，τ1、τ2分別表示集裝箱為普通干貨箱和冷藏箱。

H 為船舶艙蓋集合，H=HP∪HA=HL∪HR，其中HP為船舶船首艙蓋集合，HA為船舶船尾艙蓋集合，HL為船舶左舷艙蓋集合，HR為船舶右舷艙蓋集合。

Hpc為岸橋在p港服務的艙蓋子集。

Q(p)為港口p的（o，d）對集合（o表示初始港，d表示目的港），Q(p)={a|o，p，d ∈P，a=(o，d)}。

2.2 參數(shù)

2.3 變量

xh，sτ(a)為在艙位h 裝載的尺寸為s、箱型為τ 且滿足初始港為o，目的港為d（即滿足(o，d)對）的集裝箱 數(shù) 量。xh，sτ(a)=x_hh，sτ(a)∪x_dh，sτ(a)，其中，x_hh，sτ(a)與x_dh，sτ(a)分別代表艙內(nèi)與甲板上裝載的尺寸為s、箱型為τ 且滿足初始港為o，目的港為d的集裝箱數(shù)量，a=(o，d)∈Q(p)。

y_hh，sτ(p)、y_dh，sτ(p)分別表示在港口p、艙內(nèi)與甲板完成裝卸后的集裝箱量，是一個狀態(tài)變量。

zh(p)為0—1變量，艙位h在p港不為空則為1，否則為0。

z_dh(p)、z_hh(p)為0—1變量，表示艙位h的甲板或艙內(nèi)不為空則為1，否則為0。

rh，sτ(a)為在艙位h 產(chǎn)生的艙蓋倒箱量（產(chǎn)生倒箱的艙蓋之上的所有集裝箱的數(shù)量）。

fp，h為如果發(fā)生艙蓋倒箱，則為1，否則為0。

2.4 多目標優(yōu)化模型

多目標優(yōu)化模型如表1所示。

本文的優(yōu)化目標分別為最小化航線內(nèi)各港口倒箱量和最小化航線內(nèi)各港口岸橋裝卸次數(shù)，即滿足雙40 ft岸橋常見滿載裝卸工況的集裝箱對最多。式（3）表示所有擬裝船的集裝箱均可裝船。式（4）、（5）表示港口集裝箱船的集裝箱狀態(tài)更新。式（6）～（8）限制了集裝箱船的承重和容量。式（9）、（10）限制了船舶的穩(wěn)性公差。式（11）表示當艙蓋為空時，才可以裝入相應艙蓋的艙內(nèi)，且待裝箱量不大于艙內(nèi)容量。式（12）～（14）限定了在何種情況下可以發(fā)生艙蓋倒箱，并對倒箱總量加以限制。式（15）限制同一目的港至少相隔2個艙蓋距離分配岸橋。式（16）使航線各港口雙40 ft 岸橋的最大完工時間盡可能小，即滿足雙40 ft滿載作業(yè)工況的配載箱盡量多。

MP-MBPP 屬于三維裝箱問題，是難以精確求解的NP（non-deterministic polynomial）難問題。為避免集裝箱船配載方案搜尋空間大、耗時長，可以采用基于集裝箱分組、排序的啟發(fā)式算法［14］或構造算法［10］構造初始解，設計優(yōu)化算法進一步提高初始解質(zhì)量，以便在有效時間內(nèi)獲得較優(yōu)解。結合研究對象NP 難特點，論文根據(jù)目的港、尺寸類型等屬性將集裝箱分組，按艙蓋地址重新劃分貝位，將MPMBPP轉化為“集裝箱箱組?新貝位”裝箱問題，通過挖掘貝位剩余容量等啟發(fā)信息，設計啟發(fā)式規(guī)則，有效解決考慮雙40 ft 岸橋裝卸的多箱型集裝箱船的MP-MBPP。

由于同一箱組中的集裝箱數(shù)量可能大于待裝貝位容量，需要進一步拆分箱組，依次裝載［5］，以解決物品尺寸超過箱子容量的超尺寸裝箱問題。基于啟發(fā)式規(guī)則的超尺寸裝箱算法原理是當待裝集裝箱組大于當前港剩余容量最大的貝位，則按照剩余容量最大的貝位分割集裝箱組，依次完成各拆分部分的裝載。當待裝箱組中的集裝箱類型、尺寸存在差異時，不同的箱組分割策略將對配載結果產(chǎn)生較大影響。本文考慮貝位內(nèi)是否混裝20 ft與40 ft集裝箱，提出船舶偶數(shù)貝（40 ft 貝）內(nèi)20 ft 箱和40 ft 箱混裝、20 ft 箱和40ft 箱不混裝兩種配載策略，具體配載策略如圖2和圖3所示。

表1 多目標優(yōu)化模型Tab.1 Multi-objective optimization model

4 算例求解

4.1 案例參數(shù)

以船艙容量為1 696 TEU、艙蓋數(shù)為10的海運集裝箱船為例，驗證算法的有效性。船舶貝位信息如表2所示［15］，船舶穩(wěn)性相關參數(shù)縱傾力矩為437 383 800 N?m，橫穩(wěn)心距基線高度為12.68 m［14］。

船舶所經(jīng)航線包含5 個港口，航次中具體的貨運量如表3 所示，其中c 表示干貨箱，rc 表示冷藏箱。

表2 船舶各貝位裝載量Tab.2 Capacity of each bay of the ship

圖2 貝內(nèi)混裝策略Fig.2 Mixed loading strategy in bay

圖3 貝內(nèi)不混裝策略Fig.3 Non-mixed loading strategy in bay

由于海船的裝卸需要考慮艙蓋的影響，現(xiàn)按照該船的10 個艙蓋自艏至艉以01～11 的順序進行編號，結合船舶結構與各貝容量，重新劃分后的艙位容量信息如表4 所示，配載時將以艙蓋所在艙位所覆蓋的甲板和艙內(nèi)的容量為單位進行集裝箱組的裝卸。其中，每個艙內(nèi)容納的冷藏箱位數(shù)分別是8、16、28、32、32、32、32、32、32、22、0。

4.2 結果分析

若不使用啟發(fā)式規(guī)則，則難以在有效時間內(nèi)獲得船舶配載方案，加入此規(guī)則后，原問題最大計算規(guī)模由C6571694減少為C1622，大大加快了求解速度。實例的配載方案最優(yōu)解不存在倒箱作業(yè)，船舶偶數(shù)貝（40 ft貝）內(nèi)20 ft 箱和40 ft 箱混配、20 ft 箱和40 ft 箱不混配兩種配載策略致使船舶貝位占用率不同，同時，兩種策略下，雙40 ft 岸橋滿載作業(yè)次數(shù)及裝卸完工時間亦有不同。

4.2.1 不同配載策略對結果的影響

為更好地表示不同策略對雙40 ft岸橋的裝卸效率的影響，引入對二者差值進行定量分析后的比值參數(shù)α，α =（貝內(nèi)混裝策略下雙40 ft 岸橋裝卸次數(shù)-貝內(nèi)不混裝策略下雙40 ft 岸橋并行作業(yè)裝卸次數(shù)）/ 貝內(nèi)混裝策略下雙40 ft 岸橋裝卸次數(shù)×100%，表示同等條件下，不混裝策略相較于混裝策略工作效率提升的程度。由表5 可以看出，岸橋數(shù)量充足時，不混裝策略明顯優(yōu)于混裝策略，最高可提升超過30%的效率。

圖4 算法流程圖Fig.4 Flowchart of algorithm

表3 船舶貨運箱量Tab.3 Number of shipping containers

表4 艙位容量Tab.4 Hatch capacity

表5 雙40 ft岸橋并行作業(yè)各港口總裝卸次數(shù)Tab.5 Total loading and unloading times of twin-40-feet quay crane parallel operation at each port

圖5、圖6分別為各港口最多可以配備的雙40 ft岸橋的數(shù)量與船舶貝位占用率，可以發(fā)現(xiàn)非混裝策略下各港口最多可分配的雙40 ft 岸橋數(shù)量相對更多，船舶貝位占用率也更高。

4.2.2 岸橋類型對結果的影響

普通岸橋在貝內(nèi)不混裝策略下相較于貝內(nèi)混裝策略提升的效率見表6，可以發(fā)現(xiàn)，普通岸橋與雙40 ft岸橋呈現(xiàn)出相同的效率提升趨勢。

圖5 各掛靠港最多配備的雙40 ft岸橋數(shù)Fig.5 Maximum number of twin-40-feet quay cranes in each port

為體現(xiàn)不同策略下雙40 ft岸橋與普通岸橋相比可提升的裝卸效率，引入對二者差值進行定量分析后的比值參數(shù)β，β=（普通岸橋并行作業(yè)各港口總裝卸次數(shù)-雙40 ft 岸橋并行作業(yè)各港口總裝卸次數(shù)）/普通岸橋并行作業(yè)各港口總裝卸次數(shù)×100%，表示同等條件下，雙40 ft 岸橋較普通岸橋可提升的工作效率。

雙40 ft岸橋較普通岸橋可提高的作業(yè)效率見圖7。由圖7可見，貝內(nèi)不混裝策略允許并行作業(yè)的岸橋數(shù)量更多且避免了頻繁更換吊具，相比于貝內(nèi)混裝策略，能夠在不同程度上提升更多的作業(yè)效率。

圖6 貝位占用率Fig.6 Occupancy rate of bay

表6 普通岸橋可并行作業(yè)各港口總裝卸次數(shù)Tab.6 Total loading and unloading times of common quay crane parallel operation at each port

圖7 雙40 ft岸橋較普通岸橋效率提升比率Fig.7 Efficiency improvement ratio of twin-40-feet quay crane compared with common quay crane

5 結論

本文考慮雙40 ft岸橋配備及船舶艙蓋等對集裝箱船航線的影響，以20 ft和40 ft干貨箱和冷藏箱位作為配載箱型，以航線各港口裝卸次數(shù)和艙蓋倒箱最小為目標，以船舶穩(wěn)性和容量等為約束，研究了考慮多港口雙40 ft岸橋裝卸的船舶主貝計劃問題。提出了20 ft 與40 ft 集裝箱混裝和不混裝兩種裝箱策略，利用多港口主貝計劃模型設計了基于啟發(fā)式規(guī)則的超尺寸裝箱算法。結果表明，設計的模型和算法能夠為實際算例提供有效的解決方案，主要有以下兩個結論：

（1）在岸橋數(shù)量充足時，雙40 ft岸橋在貝內(nèi)不混裝策略下的裝卸效率明顯優(yōu)于貝內(nèi)混裝策略。

（2）配載模型和算法求解的配載方案能滿足配備雙40 ft 岸橋的需要，若配備雙40 ft 岸橋進行裝卸，同等條件下，較普通岸橋提升的比例在貝內(nèi)不混裝策略下呈現(xiàn)出更好的上升趨勢。

作者貢獻說明：

張艷偉：確定研究內(nèi)容，修改文稿，確定文稿。

馬佳樂：設計實驗，整理結果數(shù)據(jù)，撰寫文稿。