基于粒度劃分的內河集裝箱船全航線配載研究*

徐 進 張 煜 李 俊

(武漢理工大學物流工程學院 武漢 430063)

0 引 言

集裝箱船全航線配載作為集裝箱運輸的核心環(huán)節(jié)，在保障船舶安全航行、貨物安全運輸，以及營運效率中扮演著重要角色.目前，國內外學者對集裝箱船配載研究，主要集中在模型構建和算法開發(fā)等方面，涉及單港口和全航線等船舶配載問題.在單港口船舶配載方面，樂美龍等[1]構建了集裝箱船配載問題模型，設計啟發(fā)式算法求解；李俊等[2]設計了吱呀輪-混合演算策略兩階段算法，求解帶有堆場發(fā)箱順序約束的船舶配載問題；李坤等[3]建立最小化裝船時間和Bay位重量差的多目標規(guī)劃模型，設計兩階段啟發(fā)式算法求解模型；Maria 等[4]從碼頭角度考慮集裝箱配載問題，并設計兩階段啟發(fā)式算法最小化集裝箱運輸時間的堆場翻箱次數；Eliseu等[5]將船舶配載決策視作三維裝箱問題，最小化掛靠港裝卸操作次數和船舶非穩(wěn)性，并提出帕累托聚類搜索(Pareto clustering search)算法求解模型.在全航線配載方面，Alberto[6]建立全航線配載的整數規(guī)劃模型和約束規(guī)劃模型，使用CPLEX和Gecode軟件分別對模型進行求解；Dario[7]從翻倒箱量和岸橋利用率出發(fā)，建立全航線配載的整數規(guī)劃模型，采用大鄰域搜索算法進行求解；Daniela等[8]設計啟發(fā)式算法對全航線船舶配載問題進行求解，最小化船舶駐港總時間；Daniela等[9]又以全航線集裝箱配載為研究對象，建立考慮標準箱、冷藏箱、上開口箱及艙蓋板的混合整數規(guī)劃模型，并以MIP Solver進行驗證；Ding等[10]以最小化全航線翻箱率為目標建立全航線配載模型，并設計啟發(fā)式算法對其進行求解.Opher等[11]針對全航線集裝箱配載倒箱量最小而設計一種基于緊湊而高效編碼方式的遺傳算法，搜索模型最優(yōu)解.

以上船舶配載相關研究均針對海運展開，基本都是將船舶的整貝或單個箱位作為存儲單元設計模型和算法[12-13].由于內河集裝箱船舶船體較小、船方更加強調艙容利用率，本文將內河集裝箱船各個貝劃分為不同粒度的存儲單元，結合數學規(guī)劃方法，構建基于粒度劃分策略的內河集裝箱船全航線配載模型，實現(xiàn)航線同目的港集裝箱在內河船舶存儲單元的集中堆放，進而提高船舶利用率.結合長江真實運輸場景設計多組算例，通過算例驗證模型的有效性.

1 問題描述

集裝箱船全航線配載問題可歸為多港主貝計劃問題(multi-port master bay plan problem，MP-MBPP)，是根據航線各個掛靠港集裝箱的尺寸、質量等級、目的港、數量等信息，將各個掛靠港集裝箱集合有效劃分并分配到船舶各個貝內，需要保證船舶穩(wěn)性、強度、容量等約束，避免翻倒箱，提高船舶全航線裝載率.內河集裝箱船全航線配載，見圖1.各掛靠港按遍歷順序組成多個航段，集裝箱流向O-D(起始港-目的港)以一段有向弧a表示.在內河支線集裝箱船全航線配載決策中，船舶船體更小(多為3 000～5 000 t級船型)，沒有艙蓋板，強調艙容利用率.

圖1 全航線配載示意圖

文中對內河集裝箱船全航線配載決策進行研究，基于粒度劃分策略，將內河集裝箱船的存儲空間(由貝-堆棧-箱位組成)劃分為不同數量、不同大小的多個存儲單元，進而構建內河集裝箱船全航線配載的多粒度數學規(guī)劃模型.此處，粒度是用來描述船舶存儲單元大小的.最粗粒度的船舶存儲單元對應船舶偶數貝箱位集合，中間粒度的船舶存儲單元對應船舶偶數貝多個相鄰堆棧的箱位集合，最細粒度的船舶存儲單元對應船舶偶數貝堆棧的箱位集合.通過以上靈活定義，粒度越粗的數學規(guī)劃模型，其約束和變量減少，可以有效提高模型求解效率.同時，基于粒度劃分策略構建啟發(fā)式算法，還可以在求解精度和運算效率間獲得平衡.

2 模型構建

基本參數：H為航線港口集合；B為船舶貝集合；B(k),BP(k),BA(k)，BL,l(k),BR,l(k)分別為k粒度下船舶整體、船舶前半部、船舶后半部、船舶貝l∈B左半部和右半部的存儲單元集合；Pt(i),Ps(i),P(i)為航線上港口i對應的O—D副集合，Pt(i)={a|o,i,d∈H,o

決策變量：xbg(a)為港口副流向a分配到船舶存儲單元b的g質量等級集裝箱的數量；yb(i)為0-1變量，若在港口i船舶存儲單元b被占用，則y為1，否則為0；zb(a)為0-1變量，若船舶存儲單元b被a副流向下集裝箱占用，則z為1，否則為0.

1) 粒度計算

「‖Nrow‖/2j?>1)+2，j為自然數

(1)

Nk=「‖Nrow‖/2m-k?，k=1,2,…,m

(2)

‖|B(k)‖=‖Nbay‖·Nk，k=1,2,…,m

(3)

式(1)為最細粒度；式(2)為k粒度下船舶貝內存儲單元數量；式(3)為k粒度下船舶存儲單元數量.

2)k粒度下的混合整數規(guī)劃模型，記為MIP(k)

f=min(∑i∈H∑b∈B(k)yb(i)/

((‖H‖-1)×‖B(k)‖))

(4)

s.t. ∑b∈B(k)xbg(a)=Ng(a)

?i∈H,a∈Ps(i),g∈G

(5)

zb(a1)+zb(a2)≤1?i∈H,b∈B(k),

(a1,a2)∈D(i)

(6)

∑a∈P(i)∑g∈Gxbg(a)≤CTeub

?i∈H,b∈B(k)

(7)

∑a∈P(i)∑g∈Gwg·xbg(a)≤CTonb

?i∈H,b∈B(k)

(8)

|∑a∈P(i)∑g∈G∑b∈BL,l(k)(wg·xbg(a))-

ΔGh?i∈H，?l∈B

(9)

0≤∑a∈P(i)∑g∈G∑b∈BA(k)wg·xbg(a)-

∑a∈P(i)∑g∈G∑b∈BP(k)wg·xbg(a)≤ΔGc

?i∈H

(10)

yb(i)≤∑a∈P(i)zb(a)≤yb(i)·M

?i∈H,b∈B(k)

(11)

zb(a)≤∑g∈Gxbg(a)≤zb(a)·M

?i∈H,b∈B(k),a∈P(i)

(12)

目標函數(4)最小化船舶存儲單元在全航線配載的平均使用數量，使被占用的存儲單元盡可能多裝箱，即提升船舶存儲單元利用率；約束(5)確保任一掛靠港待裝集裝箱都裝船；約束(6)確保不同目的港集裝箱不混裝；約束(7)和(8)分別確保船舶在任一掛靠港裝完后滿足存儲單元最大容量和最大載荷要求；約束(9)和(10)分別確保船舶在各掛靠港裝載完成后滿足橫傾和縱傾力矩允許的重量偏差要求；約束(11)和(12)定義了三個決策變量之間的關系.

3 算法設計

針對內河集裝箱船全航線配載問題，結合內河運輸特征，設計基于多粒度配載模型的啟發(fā)式算法，算法包括存儲單元動態(tài)劃分及分支定界算法求解單一粒度下配載模型兩部分.其中，存儲單元動態(tài)劃分即根據粒度確定貝內存儲單元數量，均勻地將各貝劃分為多個存儲單元.為船舶配載主貝計劃的制定確定最小裝載單元，及橫、縱向重量差計算方式；分支定界算法即在執(zhí)行過程中將全部可行解空間不斷分割為越來越小的子集(稱為分支)，并為每個子集內的解的值計算一個下界或上界(稱為定界)，從其中尋得最佳解.模型中通過CPLEX優(yōu)化軟件調用分支定界算法對單個粒度下的配載模型進行求解.算法具體搜索流程見圖2.

圖2 啟發(fā)式算法搜索流程

4 算例驗證

4.1 算例設計

根據文獻[14]選取集裝箱船，其參數見表1.

根據以上船舶參數，構建不同船型，不同掛靠港的36組算例驗證模型.算例以S(船型:1,2,3)、P(掛靠港口數量:4,6)、R(TEU/FEU箱數量比例：1～5∶5,2～7∶3)、W(輕、中、重箱數量比例：1～6∶3∶1,2～3∶6∶1,3～3∶4∶3)組合來標識.例如，S2P4R1W2表示該算例采用2號船舶且航線依此掛靠四個港口，在各掛靠港TEU/FEU箱數量比約為5∶5，輕、中、重箱數量比約為3∶6∶1.

表1 集裝箱船裝載參數

4.2 模型驗證

以算例S1P4R2W3為例，依據式(1)～(3)可求得四個粒度，基于多粒度配載模型，結合CPLEX優(yōu)化軟件對各個粒度進行仿真分析，驗證模型的可行性.算例求解結果見表2，結果顯示粒度劃分越細，約束及變量個數越多，求解時間越長，模型復雜度呈指數增長.通過多組算例驗證顯示上述結論針對所有算例均成立，多粒度配載模型通過對存儲單元粒度的不斷細分可優(yōu)化存儲單元占用率，細粒度下模型求解時間最長，復雜度最高.但最細粒度下的解并不一定是最優(yōu)解，具體結果見模型性能分析部分.

表2 CPLEX優(yōu)化多粒度配載模型相關參數

注：*為通過刪除約束(6)所求得該粒度下的最優(yōu)解.

為進一步驗證模型的可行性，以算例S1P4R2W3最優(yōu)解為集裝箱配載方案繪制最優(yōu)粒度下船舶存儲單元在各掛靠港裝載情況見圖3.圖中每個單元格對應一個存儲單元，格中數字分別對應該存儲單元裝載的集裝箱數量及其總重.其中由兩個或兩個以上圖標組合標識的為多個掛靠港集裝箱混裝結果，如在掛靠港2，左下角存儲單元由左斜線圖標及網格圖標組合標識，表示在掛靠港2，該存儲單元裝載掛靠港1發(fā)往后續(xù)港口的集裝箱和掛靠港2發(fā)往后續(xù)港口的集裝箱(各區(qū)域面積并不代表裝箱數量).各掛靠港依次占用存儲單元數量為15，15，15，該航次中船舶存儲單元平均占用率為83.33%，各存儲單元裝載率高，符合最小化存儲單元占用原則.此外，通過計算，各掛靠港船舶橫向重量差和縱向重量差均滿足船舶營運安全性約束.綜上所述，多粒度配載模型在一定程度上能夠有效細化裝載空間，提高集裝箱船利用率，獲得滿足集裝箱配載要求的最優(yōu)解.此外，粒度與模型復雜度的關系使得建模者可在時間及優(yōu)化解之間做出權衡，亦可從較粗粒度的快速求解特性出發(fā)快速產生初始解用于拓展其他優(yōu)化算法.

圖3 案例S1P4R2W3各掛靠港存儲單元占用情況

4.3 模型性能分析

以啟發(fā)式算法結合CPLEX優(yōu)化軟件對36組算例進行求解，考慮細粒度下求解時間較長，設定各粒度的優(yōu)化時間限值為30 min，各算例求解結果見表3.由表3可知，36組算例平均橫向質量差、平均縱向質量差分別為14.93，16.92 t，均滿足船舶航行安全性約束；36組算例平均求解時間為290.64 s，平均gap值為6.16%，求解時間及求解結果均在可允許范圍內.

表3 36組算例仿真結果

續(xù)表3

注：--表示無該參數(粗粒度下以整貝為存儲單元，此時不考慮貝內橫傾；對粒度求均值無意義)；gap值由CPLEX求解模型時給出，為最優(yōu)粒度模型的下界值;*表示該均值計算剔除無效數據，采用所有有效數據進行計算.

作為船舶配載的重要影響因素，船舶橫、縱向重量差的變化也是檢驗模型的一項重要指標，本文將啟發(fā)式算法求得各掛靠港船舶各貝橫向重量差及船舶縱向重量差作箱形圖見圖4.

圖4 質量差箱形圖

圖4a)橫向質量差箱形圖中垂線下端點對應某一算例中各掛靠港船舶各貝中最小橫向質量差，垂線上端點對應最大橫向質量差，矩形框上邊緣對應某一算例中船舶橫向質量差上四分位點，下邊緣對應下四分位點，三角形位置代表中位值，圖4b)類似.

由圖4a)可知，各案例船舶貝內橫向質量差波動范圍較均勻，均在0～26 t.根據中位數的定義可知多個算例的船舶在各掛靠港、各貝的橫向質量差多數處于0～20 t.由圖4b)可知，多個案例在各掛靠港船舶整體縱向質量差(尾傾)小于25 t，整體處于5～23 t.故多粒度配載模型求解結果降低船舶橫向質量差、保留適當尾傾，保證了集裝箱船舶的適航性.

綜上所述，多粒度配載模型可有效完成存儲空間的劃分，實現(xiàn)內河集裝箱緊湊的堆存方式，可準確、快速得出集裝箱船配載方案.此外，根據細粒度下并非最優(yōu)的結論，通過對粒度的合理選取可減少解空間，加快模型求解速率.

5 結 束 語

文中針對內河集裝箱船全航線配載問題展開研究，構建了基于粒度劃分的船舶全航線配載模型，并設計啟發(fā)式算法對模型進行求解.結合長江真實運輸場景設計多組算例，驗證了多粒度配載模型的有效性.多組算例表明粒度的劃分程度直接影響模型計算的復雜度，粒度劃分越細，獲得解最優(yōu)的概率越大，但最優(yōu)解確不一定出現(xiàn)在最細粒度.故通過粒度的合理選擇可實現(xiàn)模型求解中目標和時間的均衡，且通過較粗粒度的快速求解特性可較快產生初始可行解，有利于開發(fā)靈活高效的算法.