在線環(huán)境下客貨滾裝船多目標(biāo)動(dòng)態(tài)配載決策

張 煜 熊得鵬 馬少康 賀利軍 李 斌

(武漢理工大學(xué)交通與物流工程學(xué)院1) 武漢 430063) (福建工程學(xué)院交通運(yùn)輸學(xué)院2) 福州 350118) (中交集團(tuán)智慧研究院3) 武漢 430000) (武漢理工大學(xué)韶關(guān)研究院4) 韶關(guān) 512100)

0 引 言

客貨滾裝(以下簡(jiǎn)稱(chēng)“客滾”)運(yùn)輸是一種旅客和渡海車(chē)輛相混合的運(yùn)輸模式，客滾船配載作為客滾碼頭生產(chǎn)作業(yè)的核心環(huán)節(jié)，其配載效率和決策水平直接關(guān)系港口運(yùn)作效率及其收益.與一般滾裝船配載相比，客滾船配載對(duì)象涉及小車(chē)、貨車(chē)和客車(chē)，且配載具有二維裝箱[1]、兩階段、實(shí)時(shí)動(dòng)態(tài)等特點(diǎn).

已有研究聚焦一般滾裝船配載問(wèn)題(以規(guī)格尺寸相近的商品車(chē)為主)，將船舶配載視為背包問(wèn)題[2]或者二維裝箱問(wèn)題[3]，未具體考慮車(chē)輛在船艙中的擺放位置，不適用于客滾船配載場(chǎng)景.Zhang等[4]假設(shè)配載時(shí)所有渡海車(chē)輛信息已知，針對(duì)問(wèn)題存在的兩階段、二維裝箱等特點(diǎn)，以船艙面積利用率最大為目標(biāo)，設(shè)計(jì)了偏隨機(jī)密鑰混合算法.但在實(shí)際港口運(yùn)作過(guò)程中，渡海車(chē)輛到港與船舶配載同步進(jìn)行，配載時(shí)車(chē)輛信息是逐步獲取且無(wú)法完全已知.因此，客滾船配載還具有實(shí)時(shí)動(dòng)態(tài)特點(diǎn)，需要引入在線決策，可借鑒在線車(chē)間調(diào)度[5]、在線裝箱[6-7]等方面的研究成果.

文中基于客滾船配載的現(xiàn)實(shí)需求，考慮問(wèn)題的實(shí)時(shí)動(dòng)態(tài)特點(diǎn)，將整個(gè)配載過(guò)程劃分為多個(gè)決策階段，構(gòu)建基于車(chē)輛滾動(dòng)窗口的客滾船多目標(biāo)在線配載決策模型，設(shè)計(jì)了融合灰熵并行分析和混合遺傳算法的多階段動(dòng)態(tài)決策框架及其算法，通過(guò)多組對(duì)比實(shí)驗(yàn)來(lái)驗(yàn)證模型和算法的有效性.

1 問(wèn)題描述

客滾船配載的兩階段是指配載前中期車(chē)輛需全部裝入船艙，記為主體配載階段(main stowage planning phase, MSPP)；配載后期挑選部分車(chē)輛裝船，記為補(bǔ)充配載階段(supplemental stowage planning phase, SSPP)，此階段允許小車(chē)旋轉(zhuǎn)放置.二維裝箱是指配載作業(yè)的維度、規(guī)則和目標(biāo)與二維裝箱問(wèn)題的裝箱維度、裝箱規(guī)則和裝箱目標(biāo)一致.此外，配載時(shí)還需考慮船舶穩(wěn)性和車(chē)輛間的安全距離，以保證船舶安全航行.以瓊州海峽為例，客滾船配載過(guò)程中，港方動(dòng)態(tài)獲取抵港車(chē)輛信息，實(shí)時(shí)配載客滾船，直至船艙裝滿或達(dá)到額定載重量的90%，停止配載.以往研究中，針對(duì)此類(lèi)在線決策問(wèn)題，多采用滾動(dòng)策略進(jìn)行求解[8].為此，本文設(shè)計(jì)了一種滾動(dòng)推進(jìn)策略，將一個(gè)完整的配載過(guò)程劃分為多個(gè)耦合的決策階段，根據(jù)每個(gè)階段的車(chē)輛信息生成一個(gè)滾動(dòng)窗口，進(jìn)行局部最優(yōu)求解，并將上一階段的船艙最終狀態(tài)作為下一階段的初始狀態(tài)，利用車(chē)輛到港數(shù)量驅(qū)動(dòng)窗口信息更新和決策階段前進(jìn)，見(jiàn)圖1.

圖1 客貨滾裝船在線動(dòng)態(tài)配載決策

為實(shí)現(xiàn)滾動(dòng)推進(jìn)策略的數(shù)學(xué)化描述，定義以下概念：車(chē)輛序號(hào)集合I為按到港順序依次編號(hào)，I={i|i=1,2,…,|I|}；I1為MSPP車(chē)輛序號(hào)集合，I1={i|i=1,2,…,|I1|}；I2為SSPP車(chē)輛序號(hào)集合，I2=I-I1；Sd(t)為第t階段滾動(dòng)窗口中的車(chē)輛集合；H為滾動(dòng)窗口最大長(zhǎng)度即Sd(t)中的車(chē)輛數(shù)量.配載過(guò)程可描述為：初始，渡海車(chē)輛依次到港進(jìn)入滾動(dòng)窗口，當(dāng)車(chē)輛數(shù)量達(dá)到H時(shí)，開(kāi)始配載；在MSPP的第一個(gè)窗口決策階段，從Sd(1)中挑選車(chē)輛登船配載；后續(xù)車(chē)輛補(bǔ)充進(jìn)入滾動(dòng)窗口形成Sd(2)，通過(guò)不斷配載并更新Sd(t)，船艙狀態(tài)不斷向前推進(jìn)(記為S-1階段).為符合配載兩階段性，MSPP臨近進(jìn)入SSPP階段前，增設(shè)過(guò)渡階段，將MSPP剩余車(chē)輛全部裝船(記為S-2階段)；進(jìn)入SSPP，先按照S-1階段配載作業(yè)，直至船艙裝滿或達(dá)到載重量要求時(shí)停止配載(記為S-3階段).此外，船艙是否裝滿取決于S-3階段配載完成后是否有車(chē)輛能夠繼續(xù)裝入.因此，為高效利用船艙面積，增設(shè)延遲驗(yàn)收階段，在S-3階段配載完成后，等待Q輛車(chē)，判斷是否有車(chē)輛能夠裝入船艙(記為 S-4階段).

在線動(dòng)態(tài)配載問(wèn)題在各窗口決策階段，整體配載尚未完成，無(wú)法以船艙面積利用率最大為目標(biāo)，但各階段均追求車(chē)輛擺放高度低且形成的配載面平滑；同時(shí)，由于貨車(chē)收費(fèi)遠(yuǎn)高于小車(chē)和客車(chē)，以航次收益為目標(biāo)會(huì)導(dǎo)致優(yōu)先選擇貨車(chē)，不合港口服務(wù)宗旨.因此，本文以各決策階段的客滾船配載面高度最低和平滑度最高為目標(biāo)，采用多目標(biāo)優(yōu)化策略使各階段配載車(chē)輛盡量緊湊且配載面盡量平滑，其落腳點(diǎn)仍在于船艙面積利用率的最大化.

2 客滾船多目標(biāo)在線動(dòng)態(tài)配載決策模型

2.1 基本假設(shè)

1) 以船舶可配載區(qū)域的左下角建立xoy坐標(biāo)系，見(jiàn)圖2.

2) 假設(shè)船艙和車(chē)輛為質(zhì)量均勻的矩形.

3) 將船艙劃分成若干網(wǎng)格，進(jìn)行離散化描述，單元格采用二元組(j,k)進(jìn)行標(biāo)識(shí)，j、k分別表示第j列和第k行.

4) 假設(shè)待配載車(chē)輛數(shù)大于船舶最大容量，車(chē)輛信息未知.

圖2 船艙狀態(tài)離散化描述

2.2 符號(hào)及變量說(shuō)明

符號(hào)與集合：DIt,DIst,DIbt為當(dāng)前決策窗口t中的車(chē)輛序號(hào)集合、小車(chē)序號(hào)集合、大車(chē)(客車(chē)和貨車(chē))序號(hào)集合；i為待配載車(chē)輛序號(hào)，i∈DIt；j,k為船艙單元格的橫、縱坐標(biāo)；

其他參數(shù)：mi為車(chē)輛i的質(zhì)量，t；R為一個(gè)大數(shù)；G為船舶的額定載重量，t；Gt為在t階段，船舶的載重量，t；Ttx為在t階段，船舶的橫傾力矩，kN·m；Tty為在t階段，船舶的縱傾力矩，kN·m；Tx為船艙在x軸方向的最大橫傾力矩，kN·m；Ty為船艙在y軸方向的最大縱傾力矩，kN·m；N1為每次配載的車(chē)輛數(shù)；C1為過(guò)渡階段剩余車(chē)輛數(shù).

2.3 模型建立

若將配載面上單元格看成質(zhì)點(diǎn)，則整個(gè)配載面由大量質(zhì)點(diǎn)組成，以其下方單元格坐標(biāo)作為該質(zhì)點(diǎn)的位置標(biāo)識(shí)，記為配載面質(zhì)點(diǎn)，坐標(biāo)表示為

(1)

(2)

則相鄰配載面兩質(zhì)點(diǎn)間的曼哈頓二范式距離為

(3)

相鄰配載面質(zhì)點(diǎn)在y軸方向上的浮動(dòng)程度越大，則平滑程度越低.因此利用式(3)計(jì)算相鄰配載面質(zhì)點(diǎn)的曼哈頓距離，并通過(guò)式(4)求和得到總距離來(lái)表征整個(gè)配載面的平滑程度δ.δ值越小，配載面越平滑.

(4)

由于S-1、 S-3階段的配載方式相同，針對(duì)S-1、 S-3階段的第t個(gè)滾動(dòng)窗口，構(gòu)建的基于車(chē)輛滾動(dòng)窗口的客滾船在線配載決策模型，記為SPMS-1(t)或SPMS-3(t)，具體如下：

目標(biāo)函數(shù)：

(5)

(6)

約束條件：

xijk≤ri+(1-si),?i∈

DI(s)t,j,k∈(M-Mi)

(7)

xijk≤(1-ri)+(1-si),

(8)

xijk≤(1-si)，?i∈DI(b)t,j,k∈(M-Mi)

(9)

(10)

(11)

(12)

xijk≤yij′k′+(1-ri),?i∈DI(s)t,j,

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(rili+(1-ri)wi-1-W)/2)+T(t-1)x≤Tx

(23)

(1-ri)li-1-L)/2)+T(t-1)y≤Ty

(24)

xijk,yijk∈{0,1},?i∈DIt,j,k∈M

(25)

si,ri,jri∈{0,1},?i∈DIt

(26)

S-2階段滾動(dòng)窗口中車(chē)輛數(shù)量為C1，且所有車(chē)輛經(jīng)過(guò)一次決策全部登船配載，則S-2階段的決策模型為

SPMS-2(t){f1(t),f2(t):(7)～(20),

(27)

模型目標(biāo)為式(5)～式(6)，約束條件為式(7)～式(20)和式(22)～式(27)，式(27)保證過(guò)渡階段剩余車(chē)輛全部裝船.

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

3.1 多階段動(dòng)態(tài)決策框架

針對(duì)配載的S-1階段設(shè)計(jì)首層和主體動(dòng)態(tài)配載，并結(jié)合針對(duì)S-2、S-3、S-4階段設(shè)計(jì)的過(guò)渡、補(bǔ)充動(dòng)態(tài)配載和延遲配載，形成多階段動(dòng)態(tài)決策框架實(shí)現(xiàn)求解，見(jiàn)圖3.

圖3 多階段動(dòng)態(tài)決策框架

3.2 基于灰熵并行分析的混合遺傳算法

本文基于GA算法，融合GEPA方法，設(shè)計(jì)了HGA-GEPA，算法流程見(jiàn)圖4.

圖4 HGA-GEPA尋優(yōu)流程圖

染色體編碼見(jiàn)圖5.染色體長(zhǎng)度對(duì)應(yīng)滾動(dòng)窗口長(zhǎng)度，編碼采用隨機(jī)數(shù)編碼的方式分別排序，一個(gè)染色體表征一種裝船序列.

圖5 染色體編碼

放置啟發(fā)式需要得到滿足二維裝箱和穩(wěn)性等約束且效果良好的配載方案，是算法設(shè)計(jì)中的難點(diǎn).本文的放置啟發(fā)式包括初始解構(gòu)造和穩(wěn)性調(diào)整兩部分.

1) 初始解構(gòu)造 為確定當(dāng)前決策集中車(chē)輛在船艙中的擺放位置，本文利用文獻(xiàn)[1]多階段啟發(fā)式中的評(píng)分策略評(píng)判配載優(yōu)劣，生成初始解，見(jiàn)圖6.

圖6 基于評(píng)分策略的配載方案

2) 穩(wěn)性調(diào)整 為保證配載時(shí)橫傾處于較理想的范圍，沿y軸方向?qū)⒋暗确譃樽髠?cè)和右側(cè)空間，當(dāng)裝入車(chē)輛評(píng)分為0時(shí)，若此時(shí)橫傾小于0，則將車(chē)輛放置在船艙右側(cè)空間；反之放置在左側(cè)空間.

適應(yīng)度評(píng)估是多目標(biāo)決策算法的關(guān)鍵步驟，GEPA[9-10]是一種新穎的適應(yīng)度評(píng)估方法，它將灰色理論和信息熵理論融合，以灰熵并行關(guān)聯(lián)度作為衡量多目標(biāo)解與理想解相似度的依據(jù)，并將其作為適應(yīng)度值指導(dǎo)算法進(jìn)化.灰熵并行關(guān)聯(lián)度越大，表示當(dāng)前解越接近于理想解，解的質(zhì)量越好.本文以GEPA作為算法的適應(yīng)度評(píng)估方法，優(yōu)化目標(biāo)有2個(gè).假設(shè)種群個(gè)數(shù)為P個(gè)，則GEPA步驟總結(jié)如下：

步驟1構(gòu)造理想解序列 以GA對(duì)種群實(shí)現(xiàn)配載面高度最低和平滑度最高的多目標(biāo)并行優(yōu)化，得到由2個(gè)目標(biāo)函數(shù)優(yōu)化值組成的理想解(參考)序列Y0={f1(0),f2(0)}.

步驟2構(gòu)造比較解序列 對(duì)當(dāng)代種群中的任意個(gè)體j，j∈{1,2,…,P}，分別計(jì)算2個(gè)優(yōu)化目標(biāo)的函數(shù)值，構(gòu)成比較解序列Yj={f1(j),f2(j)}，進(jìn)而得到種群的比較解序列Y={Y1,Y2,…,Yi,…,YP}.

步驟3灰關(guān)聯(lián)度分析 計(jì)算群體中任意個(gè)體的灰關(guān)聯(lián)度r(Y0,Yj)，j∈{1,2,…,P}.

步驟4熵值權(quán)重 計(jì)算比較解序列子目標(biāo)的信息熵ei(j)和熵值權(quán)重Wj(i)，i∈{1,2}，j∈{1,2,…,P}.

借鑒文獻(xiàn)[11]的偏隨機(jī)密鑰遺傳算法，通過(guò)復(fù)制、交叉和變異3種操作，各產(chǎn)生一定比例的群體構(gòu)成下一代種群，見(jiàn)圖7.

圖7 進(jìn)化操作

4 實(shí)驗(yàn)設(shè)計(jì)與分析

4.1 算例設(shè)計(jì)

本文參照文獻(xiàn)[1]進(jìn)行算例設(shè)計(jì)，選取兩艘典型客滾船作為實(shí)驗(yàn)對(duì)象，并分為晚間(記為N)和日間(記為D)兩個(gè)場(chǎng)景，三種車(chē)輛均考慮多種車(chē)型，客滾船具體參數(shù)(見(jiàn)表1)和兩個(gè)場(chǎng)景下的車(chē)輛比例(見(jiàn)表2)，車(chē)輛類(lèi)型和數(shù)據(jù)均與文獻(xiàn)[1]中應(yīng)用實(shí)驗(yàn)相同.為表明不同滾動(dòng)窗口長(zhǎng)度H和每次決策車(chē)輛數(shù)對(duì)配載結(jié)果的影響，設(shè)置若干組滾動(dòng)窗口長(zhǎng)度H和每次決策的車(chē)輛數(shù)(H的25%、50%和75%)，見(jiàn)表3.為保證待配載車(chē)輛數(shù)量與實(shí)際船艙可配載車(chē)輛之間的差距較小，將文獻(xiàn)[1]中p=0.9時(shí)確定的車(chē)輛數(shù)量作為此次實(shí)驗(yàn)的待配載車(chē)輛數(shù)量，并以此形成待配載車(chē)輛發(fā)生源，模擬實(shí)際客滾船配載流程.

車(chē)輛重量按實(shí)際隨機(jī)生成，車(chē)輛間安全距離設(shè)為0.2 m.采用諸如A1-N-P1-S1的方式來(lái)表示不同算例，其中A1為船型；N為晚間作業(yè)場(chǎng)景；P1為車(chē)輛的比例；S1為決策窗口狀態(tài).每個(gè)配載決策長(zhǎng)度下有24個(gè)算例，實(shí)驗(yàn)共計(jì)72個(gè)算例.

表1 實(shí)驗(yàn)客滾船信息

表2 實(shí)驗(yàn)場(chǎng)景及其車(chē)輛比例

表3 決策窗口設(shè)計(jì)

為測(cè)試HGA-GEPA的性能，設(shè)計(jì)人工配載啟發(fā)式(Artificial Loading Heuristic，ALH)和常規(guī)HGA，將HGA-GEPA分別替換為ALH和常規(guī)HGA，作為對(duì)照組.ALH規(guī)則為：配載時(shí)先配船頭和兩側(cè)，再配船艙中間位置，優(yōu)先放置貨車(chē)，貨車(chē)留出的空隙放置小車(chē).常規(guī)HGA的初始種群個(gè)數(shù)和迭代方式與HGA-GEPA一致，不同點(diǎn)在于常規(guī)HGA在迭代尋優(yōu)時(shí)遵循以下規(guī)則進(jìn)行群體排序：所有個(gè)體首先按照f(shuō)1的值升序排列，若f1值相同，則按照f(shuō)2的值升序排列，位于前10%的為精英種群.

4.2 參數(shù)設(shè)置

每個(gè)算例運(yùn)行10次取平均值，HGA-GEPA和HGA的種群大小設(shè)為50，當(dāng)所求最優(yōu)解連續(xù)30代無(wú)改變或達(dá)到最大迭代次數(shù)100代時(shí)算法終止，精英保留率、交叉概率分別為0.1、0.7，隨機(jī)生成變異個(gè)體比例為20%.延遲驗(yàn)收長(zhǎng)度Q與配載決策長(zhǎng)度H相等.GEPA方法中灰關(guān)聯(lián)分析分辨系數(shù)ρ=0.5.

4.3 應(yīng)用實(shí)驗(yàn)結(jié)果分析

以文獻(xiàn)[1]中對(duì)應(yīng)算例的算法求解結(jié)果作為動(dòng)態(tài)在線問(wèn)題的上界(upper bound for dynamic online problems, UBDOP).表4為在H=8下應(yīng)用不同算法求解三種船型算例的結(jié)果(由于篇幅問(wèn)題H=12,16略去).基于ALH的多階段動(dòng)態(tài)決策進(jìn)行求解時(shí)由于單個(gè)滾動(dòng)窗口決策時(shí)間太短，故此處T2不再列出.

表4 算例實(shí)驗(yàn)結(jié)果(H=8)

隨著H的增大，三種算法求解結(jié)果均呈現(xiàn)上升趨勢(shì)，且與UBDOP的平均gap值呈現(xiàn)下降趨勢(shì).主要原因在于當(dāng)H增大，獲取的車(chē)輛信息量增大，信息的不確定性對(duì)于船舶配載的影響減弱.隨著H的增大，HGA和HGA-GEPA在整體求解時(shí)間上均有一定程度的上升.主要原因在于當(dāng)H增大，決策維度明顯增大，導(dǎo)致尋優(yōu)收斂代數(shù)增加，收斂時(shí)間增加.圖8為三種H下，不同算法求解24個(gè)算例的船艙整體面積利用率折線圖.由圖8可知：對(duì)于三種H，HGA-GEPA求解結(jié)果較ALH和HGA均具有明顯的優(yōu)越性，且對(duì)于同一H，其每次決策車(chē)輛數(shù)與船艙面積利用率之間無(wú)明顯規(guī)律.

圖8 面積利用率結(jié)果分析

對(duì)于不同的H，HGA-GEPA平均求解結(jié)果均達(dá)到90%以上，平均gap值保持在6%左右，均優(yōu)于ALH和HGA，且單個(gè)決策窗口求解迅速，顯示算法具有較強(qiáng)的適用性、實(shí)時(shí)性和魯棒性.

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

文中針對(duì)客滾船配載作業(yè)的實(shí)時(shí)動(dòng)態(tài)和二維裝箱等特點(diǎn)，設(shè)計(jì)了一種滾動(dòng)推進(jìn)策略，構(gòu)建了以各決策階段的客滾船配載面高度最低和平滑度最高為目標(biāo)函數(shù)的多目標(biāo)在線配載決策模型.同時(shí)，鑒于復(fù)雜特性，設(shè)計(jì)了融合HGA-GEPA的多階段動(dòng)態(tài)決策框架對(duì)問(wèn)題進(jìn)行求解，以HGA-GEPA確定各決策階段裝船車(chē)輛及其配載方案.對(duì)比實(shí)驗(yàn)驗(yàn)證了模型和多階段動(dòng)態(tài)決策框架的有效性，且框架中的HGA-GEPA要優(yōu)于人工配載啟發(fā)式和常規(guī)HGA，可以實(shí)現(xiàn)配載方案的高效評(píng)估選擇，得到較優(yōu)的船艙面積利用率.