不確定條件下集裝箱船混合目的港貝內(nèi)排箱問(wèn)題優(yōu)化決策

張 煜, 程 昭, 李 俊, 田 維

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

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

1 問(wèn)題描述

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

2 數(shù)學(xué)模型

2.1 引入集合

2.2 建立模型

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

(1)

式(1)為最小化t∈T階段船舶貝內(nèi)橫傾力矩的目標(biāo)函數(shù)，是t階段船舶貝左側(cè)集裝箱和右側(cè)集裝箱所產(chǎn)生的橫傾力矩之差，其中：k(t)∈N(t)為在t階段待裝箱編號(hào)；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)為最小化相鄰階段貝內(nèi)計(jì)劃偏差的目標(biāo)函數(shù)。

?p∈P

(3)

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

?k(t)∈N(t)

(4)

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

?p∈P

(5)

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

(6)

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

?i∈I

(7)

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

?p∈P

(8)

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

?p∈P

(9)

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

(10)

(11)

(12)

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

表1 模型擴(kuò)展

3 算法設(shè)計(jì)

算法主要思路如下：

1) 在初始階段運(yùn)用文獻(xiàn)[9]的3階段啟發(fā)式算法獲得初始解見(jiàn)圖2，解的結(jié)構(gòu)見(jiàn)圖2a)所示，第1行是待裝船集裝箱序列，第2行是船舶貝內(nèi)箱位序列，可實(shí)現(xiàn)集裝箱與船舶貝內(nèi)箱位的匹配，例如箱位p3被指派給集裝箱c1。

2) 當(dāng)不確定加箱或減箱事件發(fā)生時(shí)見(jiàn)圖2b)，進(jìn)入下一階段t=t+1，更新集裝箱序列和船舶貝內(nèi)箱位序列，減箱事件對(duì)應(yīng)的集裝箱c4和箱位p6從序列中被刪除，加箱事件對(duì)應(yīng)的集裝箱c7被添加到集裝箱序列。

3) 執(zhí)行“插入-分段”操作見(jiàn)圖2c)，結(jié)合插入位參數(shù)值km，將序列劃分為兩段，插入點(diǎn)之前的集裝箱與箱位的匹配關(guān)系不變，插入點(diǎn)之后的集裝箱需要重新分配船舶貝內(nèi)箱位。

綜上，算法的核心是“插入-分段”與“分段搜索”。前者通過(guò)動(dòng)態(tài)調(diào)整km，可以獲得更小的搜索域，便于OPM1和OPM2模型的分段搜索與求解；后者采取兩階段思想，先通過(guò)OPM1最小化相鄰階段船舶貝內(nèi)計(jì)劃的偏差，再通過(guò)OPM2最小化船舶貝內(nèi)橫傾力矩，解決多目標(biāo)優(yōu)化問(wèn)題。

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

4 仿真試驗(yàn)

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

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

a) BAY09船舶貝結(jié)構(gòu)

5 結(jié)束語(yǔ)

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

表2 案例仿真試驗(yàn)結(jié)果