不確定條件下集裝箱船混合目的港貝內排箱問題優化決策

張 煜, 程 昭, 李 俊, 田 維

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

集裝箱船舶配載優化決策可分為主貝計劃問題和貝內計劃問題，后者又可細分為單一目的港貝內排箱問題和混合目的港貝內排箱問題。其中，混合目的港貝內排箱問題是將不同目的港集裝箱放在船舶貝內具體箱位，需要滿足船舶貝內橫傾力矩和單列積載強度等要求，減少或避免后掛靠港集裝箱壓在先掛靠港集裝箱之上，確保船舶安全運輸與港口有效裝卸。目前，已有研究成果多關注確定條件下的船舶貝內排箱問題。DUBROVSKY等[1]使用遺傳算法解決船舶混合目的港貝內排箱問題。DELGADO等[2]設計遺傳算法求解帶有裝卸規則集的船舶貝內排箱問題。AZEVEDO等[3]設計遺傳算法求解船舶貝內排箱問題。 GEOERIGK等[4]設計魯棒優化方法求解船舶貝內排箱問題。PARREO等[5]提出基于貪心策略的隨機自適應搜索算法來求解船舶配載中的貝內排箱問題。張維英等[6-7]研究單一目的港和全航線的貝內排箱問題，分別用禁忌搜索和隱式圖啟發式搜索技術求解。孫曉雅等[8]采用粒子群算法求解混合目的港貝內排箱問題。田維等[9]設計了3階段啟發式算法求解船舶混合目的港貝內排箱問題。李俊等[10]考慮堆場發箱順序對船舶配載決策的影響，設計兩階段算法求解船舶配載的貝內排箱問題。實際中，海關會對外貿出口箱進行查柜，主要以電腦抽查隨機布控為主，存在集裝箱抽檢速度慢或查驗不過而導致無法裝船的甩/減箱事件，也存在因隨機抽檢而錯過原班次的集裝箱需要臨時裝船的加箱事件，以上統稱為不確定條件。因此，對不確定條件下船舶混合目的港貝內排箱問題進行研究，借鑒多階段動態決策思想，構建任意階段的數學模型，設計基于插入-分段搜索的啟發式算法，通過案例仿真對該算法進行分析和驗證。

1 問題描述

不確定條件下的船舶混合目的港貝內排箱問題，是綜合考慮海關抽檢中所出現的加箱或減箱等不確定事件，對貝內計劃進行動態調整，降低不確定事件對船舶貝內計劃的影響，提高船舶貝內計劃的魯棒性。在此，按照不確定事件發生的順序，可將貝內計劃動態調整過程轉變為多階段動態決策過程，見圖1。根據多階段動態決策的無后效性理論可知，只要確保任意階段最優，則整體最優。在圖1中：初始階段將集港箱信息(箱型、箱重、目的港)和船舶貝結構作為已知條件，輸入給數學模型，產生初始貝內計劃s0；對于任意階段t，存在不確定事件et和上一個階段的貝內計劃st-1，利用et更新當前集港箱信息，并通過模型Mt生成新的貝內計劃st。對于模型Mt，需要最小化st-1和st的差異，即貝內計劃調整最小。由于本文關注的是船舶貝內計劃中的混合目的港貝內排箱問題，借鑒多階段動態決策思想，引入階段概念，在下一節構建該問題任意階段的0～1整數規劃模型。

2 數學模型

2.1 引入集合

2.2 建立模型

任意階段t∈T的0～1整數規劃模型，記為OPM(t)，有

(1)

式(1)為最小化t∈T階段船舶貝內橫傾力矩的目標函數，是t階段船舶貝左側集裝箱和右側集裝箱所產生的橫傾力矩之差，其中：k(t)∈N(t)為在t階段待裝箱編號；p=(i,j)∈P為船舶貝第i列第j層的箱位，i∈I,j∈J；wk(t)為集裝箱k(t)的重量；xk(t)p為集裝箱k(t)是否裝到船舶貝的p∈P箱位，為0～1決策變量；d為集裝箱寬度；Δ為相鄰集裝箱間隙；g為重力加速度。

(2)

式(2)為最小化相鄰階段貝內計劃偏差的目標函數。

?p∈P

(3)

式(3)為t階段船舶貝內任意箱位最多放入一個集裝箱的約束。

?k(t)∈N(t)

(4)

式(4)為t階段任意待裝集裝箱都必須被指派一個船舶貝內箱位的約束。

?p∈P

(5)

式(5)為t階段船舶貝內集裝箱不能懸空的約束。

(6)

式(6)為t階段待裝箱按發箱順序裝船，先發箱不能置于后發箱之上的約束。

?i∈I

(7)

式(7)為t階段船舶貝內任意列的積載強度必須得到保障的約束，其中，STi為船舶貝第i列最大允許的積載強度。

?p∈P

(8)

式(8)為t階段依據重量等級船舶貝內集裝箱重不壓輕的約束，其中，θk(t)為集裝箱k(t)的重量等級。

?p∈P

(9)

式(9)為t階段船舶貝內不能出現阻塞箱的約束，即后卸船集裝箱壓在先卸船集裝箱之上，其中，dk(t)為集裝箱k(t)的目的港，π(p)∈P表示箱位p上面的緊鄰箱位。

(10)

(11)

(12)

式(12)為t階段與t-1階段的船舶貝內計劃偏差約束。

表1 模型擴展

3 算法設計

算法主要思路如下：

1) 在初始階段運用文獻[9]的3階段啟發式算法獲得初始解見圖2，解的結構見圖2a)所示，第1行是待裝船集裝箱序列，第2行是船舶貝內箱位序列，可實現集裝箱與船舶貝內箱位的匹配，例如箱位p3被指派給集裝箱c1。

2) 當不確定加箱或減箱事件發生時見圖2b)，進入下一階段t=t+1，更新集裝箱序列和船舶貝內箱位序列，減箱事件對應的集裝箱c4和箱位p6從序列中被刪除，加箱事件對應的集裝箱c7被添加到集裝箱序列。

3) 執行“插入-分段”操作見圖2c)，結合插入位參數值km，將序列劃分為兩段，插入點之前的集裝箱與箱位的匹配關系不變，插入點之后的集裝箱需要重新分配船舶貝內箱位。

綜上，算法的核心是“插入-分段”與“分段搜索”。前者通過動態調整km，可以獲得更小的搜索域，便于OPM1和OPM2模型的分段搜索與求解；后者采取兩階段思想，先通過OPM1最小化相鄰階段船舶貝內計劃的偏差，再通過OPM2最小化船舶貝內橫傾力矩，解決多目標優化問題。

算法具體流程見圖3，其中：No和Po分別為插入-分段操作中插入點之前的集裝箱集合與船舶貝內箱位集合，不參與分段搜索；Nr=N(t)No和Pr=PPo表示參與分段搜索的集裝箱集合與船舶貝內箱位集合，需要重新為Nr中的集裝箱指派Pr中的船舶貝內箱位；其他符號參見上一節的符號定義。

4 仿真試驗

通過港口調研，給出仿真試驗的基礎數據。對于船舶Bay09結構，存在36個待裝箱，船舶貝內最大允許橫傾力矩為616 kN·m；對于船舶Bay47結構，存在72個待裝集裝箱，船舶貝內最大允許橫傾力矩為752 kN·m；不確定事件涉及2個減箱和2個加箱，合計4個階段。船舶貝結構見圖4，兩種場景見表2，例如B09-N36-D3表示船舶貝結構為Bay09、待裝箱36個、待裝箱目的港數為3。每個場景隨機生成5個案例進行仿真試驗，分別采用插入-分段搜索算法和CPLEX優化包求解器進行求解，詳細仿真結果見表2。CPLEX設定2 h求解時間，在該時間內無法得到輸出結果，則在表2中用“/”表示。

表2中，隨著船舶貝結構、待裝集裝箱數目、目的港數等的增大，CPLEX在20個例子中僅能求解9個例子，插入-分段搜索算法能夠求解所有例子，表明所設計的算法適合解決不同規模算例。此外，在9個CPLEX和插入-分段搜索算法都可以求解的例子中，CPLEX獲得的z2平均值在8個例子中劣于插入-分段搜索算法，表明所設計的插入-分段搜索算法可獲得相鄰計劃調整較小的船舶貝內計劃方案，這有利于提高船舶貝內計劃的魯棒性，降低計劃編制人員工作負荷。在以上9個例子中，插入-分段搜索算法獲得的z1平均值普遍劣于CPLEX，這項指標只要小于最大允許橫傾力矩就可以滿足實際需要，插入-分段搜索算法在所有例子中的橫傾力矩都遠小于最大允許橫傾力矩。

a) BAY09船舶貝結構

5 結束語

不確定條件下集裝箱船混合目的港貝內排箱問題，引入海關隨機抽檢所引發的減箱或加箱等不確定事件，是確定條件下船舶貝內排箱或貝內計劃問題的擴展。本文借鑒多階段動態決策思想，按照事件發生的順序，將問題劃分為多個階段進行動態決策，構建任意階段的0～1整數規劃模型；結合該模型，設計插入-分段搜索的啟發式算法；通過案例仿真，表明所設計的算法滿足船舶貝內排箱的各項約束，可提高船舶貝內計劃的魯棒性，降低不確定事件對船舶貝內計劃的影響。此外，本文設計的插入-分段搜索啟發式算法，部分模塊采用CPLEX求解子模型，盡管采用插入-分段操作降低搜索域，但后續研究可以發展求解精度高的啟發式算法，予以替換，可進一步提高算法的求解效率。

表2 案例仿真試驗結果