不確定箱重下內(nèi)河集裝箱班輪航線配載決策

李 俊，張 煜*，計三有，程 昭，馬 杰

(武漢理工大學(xué)a.物流工程學(xué)院；b.航運學(xué)院，武漢430063)

0 引言

集裝箱運輸需求的增加對班輪航線配載決策提出了更高要求.內(nèi)河集裝箱班輪由于體型較小，船舶穩(wěn)性對配載計劃十分敏感，少量集裝箱堆放位置變化或重量偏差可能導(dǎo)致配載計劃失效.對于內(nèi)貿(mào)箱而言，貨主提供箱重信息的不確定性導(dǎo)致內(nèi)河集裝箱班輪航線配載決策變得更加復(fù)雜.

已有的航線配載決策研究大多圍繞集裝箱海運展開，往往假設(shè)航線上各港口節(jié)點的集裝箱信息已知，采用的方法包括啟發(fā)式算法[1-3]、遺傳算法[4]、整數(shù)規(guī)劃[5]、帕累托聚類搜索[6]等.這些研究未考慮不確定因素對航線配載決策影響，且主要針對海運展開.內(nèi)河集裝箱班輪運輸與海運相比往往更強調(diào)艙容利用率，船舶穩(wěn)性對配載計劃脆性較強.同時航線配載決策會受到集港過程中不確定箱重影響，已有研究配載效率退化明顯，無法適應(yīng)內(nèi)河集裝箱班輪航線配載決策需求.

內(nèi)河集裝箱班輪航線運輸中，內(nèi)貿(mào)箱箱重信息具有不確定性，采用隨機變量描述，約束條件中包含隨機變量的航線配載決策問題屬于隨機規(guī)劃問題.目前，與集裝箱運輸相關(guān)的隨機規(guī)劃研究主要關(guān)注班輪航線規(guī)劃[7]、集裝箱艙位分配[8]、堆場容量需求[9]等.已有研究表明隨機規(guī)劃可有效應(yīng)對不確定因素干擾，提高方案抗干擾能力.

本文考慮內(nèi)河集裝箱班輪運輸中內(nèi)貿(mào)箱不確定箱重影響，對班輪航線配載決策進(jìn)行研究，構(gòu)建隨機規(guī)劃和隨機機會約束規(guī)劃模型，并設(shè)計混合鄰域搜索算法求解.最后通過算例研究和蒙特卡羅隨機模擬驗證算法的有效性.

1 問題描述

內(nèi)河集裝箱班輪航線配載決策中，當(dāng)前港口輸出的配載計劃將作為制定下一港口配載計劃的輸入，如圖1所示.班輪在航行過程中順序遍歷多個港口節(jié)點，在到達(dá)各港口節(jié)點之前，船方利用貨主提供的訂艙信息完成當(dāng)前節(jié)點的預(yù)配計劃和后續(xù)節(jié)點箱位預(yù)留.當(dāng)前節(jié)點結(jié)合集裝箱實際集港信息，基于船方制定的預(yù)配計劃完成船舶實配計劃.針對內(nèi)貿(mào)箱而言，實際中為了降低運輸成本，貨主在向船方訂艙時存在瞞報集裝箱重量信息的情況，導(dǎo)致實際箱信息發(fā)生變化.而船方利用貨主提供的箱信息進(jìn)行配載，使配載計劃隱含極強脆性.

圖1 內(nèi)河集裝箱班輪航線配載決策Fig.1 Inland container liner route stowage planning decision

因此，對于內(nèi)貿(mào)箱而言，需要考慮集港過程中不確定箱重對航線配載決策的影響，在滿足船舶穩(wěn)性、強度及容量等約束前提下，綜合考慮航線各港口節(jié)點之間的運輸需求，制定航線各掛靠港的配載計劃.考慮到內(nèi)河集裝箱班輪運輸?shù)莫毺匦?，航線配載決策的目標(biāo)為最小化航線班輪堆棧占用數(shù)量，實現(xiàn)被占用堆棧的高效利用，保證船舶的艙容利用率.

2 模型構(gòu)建

2.1 假設(shè)條件

針對內(nèi)河集裝箱班輪航線運輸?shù)奶攸c，考慮現(xiàn)實約束，做出以下假設(shè)：

(1)考慮同一尺寸的普通箱；

(2)貨主在向船方訂艙時存在瞞報集裝箱重量信息的情況；

(3)參考國家交通運輸部發(fā)布的《載貨集裝箱累加計算法重量驗證指南》，集裝箱箱重在貨主提供重量的基礎(chǔ)上最大偏差設(shè)為1 t.

2.2 模型建立

為了方便建模，將班輪貝位內(nèi)堆棧按前半部、后半部、左半部、右半部分成不同的堆棧集合，如圖2所示.

圖2 內(nèi)河集裝箱班輪結(jié)構(gòu)Fig.2 Structure of inland container liner

模型參數(shù)設(shè)置如下：

(1)集 合.

P——航線港口集合；

Q(p)——航線上港口p的OD副集合，Q(p)=Qt(p)?Qs(p),?p∈P；

Qt(p)——航線上途徑港口p的OD副集合，Qt(p)={a|o,p,d∈P,o＜p＜d,a=(o,d)}；

Qs(p)——航線上從港口p始發(fā)的OD副集合，Qs(p)={a|o,p,d∈P,o=p＜d,a=(o,d)}；

G——集裝箱重量等級集合(輕、中、重)，G={1,2,3}；

J——班輪堆棧集合，J=JF?JA=JL?JR；

JF、JA——班輪前、后半部堆棧集合；

JL、JR——班輪左、右半部堆棧集合.

(2)參 數(shù).

Ng(a)——港口p流向后續(xù)港口d的重量等級為g的待裝船集裝箱箱量(TEU)，?a=(o,d)∈Qs(p),p∈P,g∈G；

wg——重量等級為g的集裝箱平均重量(t)，g∈G；

——重量等級為g的集裝箱隨機重量(t)，g∈G；

ΔCG、ΔLG——班輪允許的最大橫、縱向重量差(t)；

STj——班輪堆棧j的最大箱位容量(TEU)，?j∈J；

SWj——班輪堆棧j的最大載重量(t)，?j∈J；

L——一個大數(shù).

(3)變 量.

xjg(a)——班輪堆棧j內(nèi)OD副a流向下重量等級為g的集裝箱箱量(TEU)，?g∈G,j∈J,a∈Q(p),p∈P；

yj(a)——0-1變量，若班輪堆棧j被OD副a流向下的集裝箱占用則為1，否則為0，?j∈J,a∈Q(p),p∈P.

隨機規(guī)劃模型(Stochastic Programming Model,SPM)為

式(1)為目標(biāo)函數(shù)，表示最小化航線班輪堆棧占用數(shù)量；式(2)～式(11)為約束條件.式(2)保證任意港口的集裝箱均可裝船.式(3)保證任意OD副流向下的集裝箱至少占用1個堆棧.式(4)保證任意堆棧至多被1種OD副流向下的集裝箱占用，避免出現(xiàn)阻塞箱.式(5)定義決策變量xjg(a)、yj(a)關(guān)系，若xjg(a)＞0，則說明堆棧j內(nèi)堆放有OD副a流向下的集裝箱，此時yj(a)=1；反之，若xjg(a)=0，則yj(a)=0.式(6)和式(7)保證任意堆棧均滿足容量和載重量約束.式(8)和式(9)保證班輪在任意港口均滿足橫、縱向重量差約束.式(10)和(11)定義決策變量的取值范圍.

將模型SPM中與隨機重量相關(guān)的約束式(7)～式(9)松弛，得到原問題的下界模型(Lower Bound Model，LBM)為

由于式(7)～式(9)均為隨機約束，模型SPM無法直接求解.基于隨機規(guī)劃理論，采用機會約束描述隨機約束，轉(zhuǎn)化得到隨機機會約束規(guī)劃模型(StochasticChance-constrainedProgrammingModel,SCPM)為

式(12)～式(14),式(10),式(11)}

式中：α為置信水平，α=0.95.

3 混合鄰域搜索算法

模型SCPM無法通過已有數(shù)學(xué)規(guī)劃軟件求解，參考文獻(xiàn)[10]中混合智能算法，設(shè)計混合鄰域搜索算法(Hybrid Neighborhood Search Algorithm，HNS)求解.該算法包含蒙特卡羅隨機模擬、神經(jīng)元網(wǎng)絡(luò)訓(xùn)練及鄰域搜索啟發(fā)式3個部分.

3.1 蒙特卡羅隨機模擬

由式(12)～式(14)得到不確定函數(shù)U:x→(U1(x),U2(x),U3(x))，其中：

采用蒙特卡羅隨機模擬為U:x→(U1(x),U2(x),U3(x))產(chǎn)生輸入輸出數(shù)據(jù)，w?g按g∈G={1,2,3}分別服從[6,8]、[13,15]、[20,22]的均勻分布.

Step 1構(gòu)建無目標(biāo)優(yōu)化模型(CSM1){f=0:式(2)～式(6),式(10),式(11)}，確定待裝船集裝箱組與班輪堆棧之間的對應(yīng)關(guān)系；

Step 2設(shè)置訓(xùn)練樣本數(shù)量，N0=3 000；

Step 3調(diào)用Gurobi求解模型CSM1產(chǎn)生輸入數(shù)據(jù)；

Step 4循環(huán)模擬(N1=5 000)得輸出數(shù)據(jù)，記錄輸入、輸出得到1組樣本數(shù)據(jù)；

Step 5重復(fù)Step3～Step4至達(dá)到樣本數(shù)量，結(jié)束.

3.2 神經(jīng)元網(wǎng)絡(luò)訓(xùn)練

利用樣本數(shù)據(jù)訓(xùn)練神經(jīng)元網(wǎng)絡(luò)逼近不確定函數(shù)U:x→(U1(x),U2(x),U3(x))，包含1個隱含層，采用反向傳播法更新權(quán)重.每組數(shù)據(jù)訓(xùn)練5 000次，完畢后保存網(wǎng)絡(luò).

3.3 鄰域搜索啟發(fā)式

(1)初始解構(gòu)造.

Step 1將當(dāng)前港口待裝船集裝箱按照OD副、重量等級等屬性分組得到集裝箱組.

Step 2將集裝箱組按照“OD副由近到遠(yuǎn)、重量等級由輕到重”排序.

Step 3將班輪堆棧按照從“船頭到船尾、左側(cè)到右側(cè)”的順序依次編號.

Step 4考慮堆棧箱位容量約束，將排序后的集裝箱組依次堆放至班輪堆棧中，并更新集裝箱組和堆棧狀態(tài).重復(fù)Step4至所有集裝箱組裝船完畢.由于未考慮載重量和穩(wěn)性約束，可得到每個OD副a流向下集裝箱組最少堆棧占用，記為M(a).

Step 5對于每個OD副流向a，構(gòu)建無目標(biāo)優(yōu)化模型(Container to Stack Model 2,CSM2)，如式(18)和式(19)所示，得到滿足堆棧載重量約束的初始配載計劃.若模型CSM2無法在有限時間內(nèi)求解，則更新M(a)=M(a)+1，重復(fù)Step5至得到當(dāng)前港初始配載計劃.

(CSM2){f=0:式(2)～式(6),式(18),式(19),式(10),式(11)}

模型CSM2中，式(18)保證最差情形下任意堆棧滿足載重量約束；約束(19)保證集裝箱組占用盡可能少的堆棧.

(2)初始解優(yōu)化.

將堆放在任一班輪堆棧內(nèi)所有集裝箱視為1個堆棧箱組，按集裝箱重量等級計算各堆棧重量.將班輪堆棧按前后和左右分為左前塊、右前塊、左后塊、右后塊，如圖2所示.設(shè)計3種不同的鄰域搜索策略優(yōu)化初始配載計劃，只可對當(dāng)前港裝船的堆棧箱組操作，調(diào)整后更新各堆棧重量.

策略1調(diào)整堆棧箱組所在位置，快速優(yōu)化班輪橫、縱向重量差.

①縱向重量差調(diào)整.?前半部更重，計算前、后半部重量差值的1/2(記為Δw)，從前半部選取重量最接近Δw的堆棧箱組，將其調(diào)整到后半部第1個空堆棧；?后半部更重，類似地調(diào)整.

②橫向重量差調(diào)整.為了保證已優(yōu)化的縱向重量差不被改變，調(diào)整時只可在前半部或后半部內(nèi)部的堆棧塊之間操作，其他按策略1中①方法類似調(diào)整.

策略2互換不同堆棧箱組所在位置，進(jìn)一步優(yōu)化班輪橫、縱向重量差.

若通過策略1調(diào)整后仍無法通過神經(jīng)網(wǎng)絡(luò)檢驗，則繼續(xù)調(diào)整：

①縱向重量差調(diào)整.更新Δw，從前、后半部中選取重量差值最接近Δw的2個堆棧箱組互換位置.

②橫向重量差調(diào)整.同樣只可在班輪前半部或后半部內(nèi)部的堆棧塊之間操作，其他按策略2中①方法類似調(diào)整.

策略3拆分堆棧箱組并調(diào)整其堆棧位置，進(jìn)一步優(yōu)化班輪橫、縱向重量差.

若通過策略2調(diào)整后仍無法通過神經(jīng)網(wǎng)絡(luò)檢驗，則繼續(xù)調(diào)整：

為了保證班輪堆棧的航線占用率，優(yōu)先選擇集裝箱目的港最近的堆棧箱組拆分，避免新占用堆棧在過多港口被占用.

①縱向重量差調(diào)整.?前半部更重，更新Δw，從前半部選擇1個目的港最近且重量大于Δw的堆棧箱組拆分，取出重量最接近Δw的若干個集裝箱形成新的堆棧箱組，堆放在后半部第1個空堆棧；?后半部更重，類似地調(diào)整.

②橫向重量差調(diào)整.上述調(diào)整時出現(xiàn)了新的堆棧箱組，為了不增加堆棧占用，首先采用策略2調(diào)整，若調(diào)整后可通過神經(jīng)網(wǎng)絡(luò)檢驗，則輸出配載計劃；若調(diào)整后仍不通過，則針對左、右半部按策略3中①方法類似調(diào)整.

4 算例研究

4.1 算例設(shè)計

根據(jù)國標(biāo)GB/T 19283-2010，選取3艘不同尺寸類型(小型、中型、大型)的長江集裝箱班輪進(jìn)行算例研究，如表1所示.基于長江實際運輸場景設(shè)計算例，考慮4條航線(表2)和3種不同的班輪裝載率(表3).采用諸如S1-L1-C45的方式來表示不同算例，其中第1部分S1表示船型，第2部分L1表示航線，第3部分C45表示裝載率.

表1 長江集裝箱班輪信息Table 1 Information of container liner on the Yangtze River

表2 班輪航線Table 2 Container liner routes

表3 班輪裝載率Table 3 Loading rates of container liner

4.2 算例求解

4.2.1 班輪航線配載結(jié)果

模型 SPM、LBM、CSM1及 CSM2均采用Gurobi 7.5.1求解.其中，模型SPM求解時其隨機重量參數(shù)按平均箱重計算.HNS采用Python 3.6編程.所有算例均在一臺4GB內(nèi)存的筆記本電腦(Intel Core I7-5500U,2.40GHz)求解.

集裝箱平均箱重分別設(shè)置為7 t、14 t和21 t.為了保證模型的求解效率，首先設(shè)置求解時間為60 s，當(dāng)結(jié)果不理想或無法求解時，調(diào)整為600 s.對不同班輪而言，模型及算法的求解結(jié)果如表4～表6所示.在表4～表6中，f表示航線班輪堆棧占用數(shù)量；T表示算例求解時間(s)；gap表示模型SPM及算法HNS對應(yīng)結(jié)果與下界模型(LBM)結(jié)果之間的偏差(%)；*表示無法在時間限制內(nèi)求得結(jié)果.

從表4和表5中可以看出，由于模型SPM找到更多下界值且gap更小，其解的質(zhì)量優(yōu)于HNS.在求解時間方面，對于班輪S1，HNS表現(xiàn)更優(yōu)；而對于班輪S2，模型SPM表現(xiàn)更優(yōu).從表6中可以看出，對于班輪S3，算例S3-L2-C85、S3-L3-C85及S3-L4-C85由于船舶體型更大、航線更長、班輪裝載率更高，導(dǎo)致模型SPM無法在有限時間內(nèi)求解.HNS求解所有算例且求解時間更短，其gap劣于模型SPM，但均小于4.5%.

表4 班輪S1-模型及算法求解結(jié)果Table 4 Results of model and algorithm for liner S1

表5 班輪S2-模型及算法求解結(jié)果Table 5 Results of model and algorithm for liner S2

表6 班輪S3-模型及算法求解結(jié)果Table 6 Results of model and algorithm for liner S3

綜上，在解的質(zhì)量方面，模型SPM優(yōu)于HNS，但由于未考慮不確定箱重對配載決策影響，無法保證當(dāng)隨機事件發(fā)生時配載計劃仍可行；與模型SPM相比，HNS在求解時間和求解數(shù)量上更優(yōu)且gap合理，尤其在求解大規(guī)模算例時表現(xiàn)更好.

4.2.2 蒙特卡羅仿真驗證

為了進(jìn)一步驗證模型及算法的魯棒性，采用蒙特卡羅隨機模擬進(jìn)行仿真驗證.每個算例仿真1 000次，結(jié)果如圖3所示.

從圖3可以看出，由于未考慮不確定箱重對制定航線配載計劃的影響，模型SPM的魯棒性較差，僅有8個算例達(dá)到0.95的置信度水平，其他的通過率均不到0.8.而HNS均可達(dá)到0.95的置信度水平，滿足模型SCPM的置信度要求.

圖3 蒙特卡羅隨機模擬結(jié)果Fig.3 Result of Monte Carlo stochastic simulation

5 結(jié)論

本文考慮內(nèi)貿(mào)箱不確定箱重，研究內(nèi)河集裝箱班輪航線配載決策問題.以最小化航線班輪堆棧占用數(shù)量為目標(biāo)，構(gòu)建隨機規(guī)劃和隨機機會約束規(guī)劃模型.對于后者，設(shè)計混合鄰域搜索算法實現(xiàn)求解.算例研究表明：隨機規(guī)劃模型雖然求解結(jié)果更優(yōu)，但難以保證隨機事件發(fā)生時配載計劃仍可行，魯棒性較差；混合鄰域搜索算法在求解數(shù)量和求解時間上均更優(yōu)，與下界值的偏差也在合理范圍內(nèi)，且可順利通過蒙特卡洛仿真檢驗，魯棒性較好.后續(xù)，將針對內(nèi)河集裝箱班輪運輸中外貿(mào)箱箱量變化等不確定因素進(jìn)行研究.

參考文獻(xiàn)：

[1]AZEVEDO A,RIBEIRO C,SENA G,et al.Solving the 3D container ship loading planning problem by representation by rulesand meta-heuristics[J].International Journal of Data Analysis Techniques and Strategies,2014(6):228-260.

[2]DING D,CHOU M C.Stowage planning for container ship:A heuristic algorithm to reduce the number of shifts[J].European Journal of Operational Research,2015(246):242-249.

[3]AMBROSINO D,PAOLUCCI M,SCIOMACHENA A.A MIP heuristic for multi-port stowage planning[J].Transportation Research Procedia,2015(10):725-734.

[4]?；垤`,計明軍.集裝箱船舶全航線配載優(yōu)化模型與改進(jìn)遺傳算法[J].交通運輸工程學(xué)報,2014,14(5):59-67.[ZHU H L,JI M J.Optimal model and improved genetic algorithm of containership stowage on full route[J]．Journal of Traffic and Transportation Engineering,2014,14(5):59-67.]

[5]AMBROSINO D,PAOLUCCI M,SCIOMACHENA A.Computational evaluation of a MIP model for multi-port stowage planning problems[J].Soft Computing,2017(21):1753-1763.

[6]ARAúJO E J,CHAVES A A,NETO L L S,et al.Pareto clustering search applied for 3D container ship loading plan problem[J].Expert Systems with Applications,2016(44):50-57.

[7]DONG J X,LEE C H,SONG D P.Joint service capacity planning and dynamic container routing in shipping network with uncertain demands[J].Transportation Research Part B,2015(78):404-421.

[8]楊華龍,劉迪,夏秋.集裝箱班輪多港掛靠循環(huán)航次艙位分配[J].重慶交通大學(xué)學(xué)報(自然科學(xué)版),2012,31(6):1248-1251.[YANG H L,LIU D,XIA Q.Slot allocation of container liner in multi-port call cycle voyage[J].Journal of Chongqing Jiaotong University(Natural Science),2012,31(6):1248-1251.]

[9]郭子堅,許松喬,王文淵,等.集裝箱港口堆場箱位數(shù)的二階段隨機規(guī)劃方法[J].哈爾濱工程大學(xué)學(xué)報,2013,34(12):1520-1523.[GUO Z J,XU S Q,WANG W Y,et al.The two-stage stochastic programming method for determining the number of flat containers in the portyard[J].JournalofHarbin Engineering University,2013,34(12):1520-1523.]

[10]ZHAO R Q,LIU B D.Stochastic programming models for general redundancy optimization problems[J].IEEE Transaction on Reliability,2003,52(2):181-191.