瓊州海峽客滾船渡海車輛配載優(yōu)化決策研究

陳 寧，呂 鵬，胡 斌

(1.武漢理工大學(xué) 交通與物流工程學(xué)院，湖北 武漢 430063；2.武漢理工大學(xué)海南研究院，海南 三亞 572025；3.華中科技大學(xué) 管理學(xué)院，湖北 武漢 430071)

隨著海南省自由貿(mào)易港建設(shè)的持續(xù)推進(jìn)，作為海南省與內(nèi)地交流的“黃金水道”，瓊州海峽的客貨運(yùn)量未來將會激增，而作為瓊州海峽運(yùn)輸體系中的一種重要運(yùn)輸方式——客貨滾裝運(yùn)輸，將扮演越來越重要的角色。雖然當(dāng)前一些智能化售票手段已經(jīng)運(yùn)用到客滾輪渡的日常業(yè)務(wù)管理中，但客滾運(yùn)輸業(yè)務(wù)中的客滾船配載決策過程多依賴人工經(jīng)驗(yàn)，其配載效率有待進(jìn)一步提高，無法滿足節(jié)假日和極端天氣影響下的疏港要求及智慧港口的發(fā)展要求。

客滾船配載有其獨(dú)特性，其裝載對象為社會渡海車輛和過海旅客，在此僅考慮車輛的配載問題，渡海車輛的種類和車型繁雜，各類車輛尺寸相差較大，配載時(shí)為充分利用船艙面積，需考慮車輛的長寬，客滾船在配載約束上呈現(xiàn)矩形件排樣特性，因此筆者引入矩形件排樣優(yōu)化理論，已有的滾裝船配載優(yōu)化理論對于客滾船配載優(yōu)化決策難以沿用。目前，國外對于客滾船渡海車輛配載優(yōu)化研究較少，大多是針對客滾船配載安全性、裝卸效率、客滾船裝卸載硬件系統(tǒng)的開發(fā)等方面進(jìn)行研究[1-2]。國內(nèi)對于滾裝船配載研究有一定的理論基礎(chǔ)，但是大多數(shù)是針對傳統(tǒng)滾裝船的配載優(yōu)化及優(yōu)化配載系統(tǒng)的實(shí)現(xiàn)[3]、多層滾裝船的配載優(yōu)化[4]，多裝卸貨港的滾裝船配載[5]；而在客滾船研究方面，吳兵等[6]對客滾船載運(yùn)電動汽車火災(zāi)風(fēng)險(xiǎn)進(jìn)行了相關(guān)研究，并結(jié)合客滾船的特點(diǎn)，提出相應(yīng)的安全管理對策；張煜等[7-8]認(rèn)為客滾船配載帶有二維裝箱特性，分別對離線和在線兩個(gè)狀態(tài)下的客滾船配載優(yōu)化進(jìn)行研究，實(shí)現(xiàn)了不同規(guī)模下客滾船的有效配載；ZHANG等[9]基于客滾船配載的二維裝箱特性，考慮車輛的復(fù)雜旋轉(zhuǎn)特性及安全航行的情況下的客滾船配載方法。對于矩形排樣優(yōu)化理論研究也較為成熟，在服裝排料[10]、港口堆場布局[11]等問題上均有應(yīng)用。

故筆者結(jié)合客滾船配載實(shí)際及其矩形件排樣特性，構(gòu)建客滾船配載優(yōu)化決策模型，設(shè)計(jì)融合最低水平線算法和基于K-鄰域搜索的遺傳算法的求解方案，通過模擬不同場景下的配載過程來驗(yàn)證模型及求解方案的有效性，為瓊州海峽新海港客滾船配載的優(yōu)化決策提供參考。

1 問題描述

客滾船配載問題與矩形件排樣問題如圖1所示，將車輛視為矩形件，客滾船船艙甲板視為長寬固定的板材，客滾船配載的矩形件排樣特性體現(xiàn)在：①待渡車輛進(jìn)入船艙時(shí)，不用考慮車輛高度對于配載的影響，只需考慮車長和車寬的影響，且無需考慮預(yù)設(shè)的車道線對于車輛位置的限制，呈現(xiàn)二維約束限制，與矩形件排樣優(yōu)化問題在維度上保持一致；②車輛間無干涉，同一位置僅能停放一輛車輛，與矩形件排樣優(yōu)化問題中矩形件之間無干涉放置規(guī)則保持一致；③客滾船的單層甲板長度固定，且僅能裝載部分待渡車輛進(jìn)入甲板，直至甲板面積得到充分利用，與矩形件排樣優(yōu)化問題選取物品的規(guī)則及目標(biāo)一致。

圖1 客滾船配載問題與矩形件排樣問題

實(shí)際上，為了保證船舶航行安全和裝載車輛的安全，客滾船在配載過程中必須充分考慮船舶的穩(wěn)性安全、船舶額定載重量、車輛間及車輛與艙壁間的安全距離等現(xiàn)實(shí)約束。

此外，為解決港口在極端天氣影響下導(dǎo)致的車輛積壓問題，將車輛和旅客盡可能地高效疏港，在考慮配載決策時(shí)，以船艙滿艙為目標(biāo)，不僅能夠提高疏港效率，同時(shí)可以在一定程度上保證單航次收益。故筆者基于矩形件排樣優(yōu)化特性并保證船舶安全航行的現(xiàn)實(shí)約束條件下，以船艙甲板面積利用率最大為目標(biāo)，構(gòu)建客滾船配載優(yōu)化模型。

2 模型構(gòu)建

2.1 問題假設(shè)

(1)假設(shè)客滾船船艙及渡海車輛均為形狀規(guī)則、質(zhì)量均勻的矩形，且已知所有渡海車輛的信息。

(2)假設(shè)以客滾船舶的船艙俯視圖可配載區(qū)域的左下角為原點(diǎn)建立如圖2所示的xOy坐標(biāo)系，船頭左端點(diǎn)為O點(diǎn)，船頭至船尾為y軸，船舶從左至右為x軸。車輛以左下角坐標(biāo)為位置標(biāo)識，即車輛配入船艙后，車輛左下角的坐標(biāo)(xi,yi)。

圖2 船舶坐標(biāo)系示意圖

2.2 模型建立

(1)集合。以渡海車輛從閘口進(jìn)入待渡場的順序進(jìn)行標(biāo)號排序，I={i|i=1,2,…,|I|}。

(3)變量。Eij為0-1變量，車輛i在車輛j的左側(cè)則為1，否則為0，即xi+wi≤xj；Fij為0-1變量，車輛i在車輛j的下側(cè)則為1，否則為0，即yi+li≤yj；zi為0-1變量，選擇第i輛車配入船艙為1，否則為0。

因此，構(gòu)建如下客滾船配載優(yōu)化模型：

(1)

Eij+Eji+Fij+Fji+(1-zi)+(1-zj)≥1

?i≠j,i，j∈I

(2)

xi+wi≤xj+R(1-Eij+2-zi-zj)

?i≠j,i，j∈I

(3)

yi+li≤yj+R(1-Fij+2-zi-zj)

?i≠j,i，j∈I

(4)

xi+wi≤W+R(1-zi)

(5)

yi+li≤L+R(1-zi)

(6)

(7)

(8)

(9)

xi,yi∈N+?i∈I

(10)

Eij,Fij∈{0,1} ?i≠j,i，j∈I

(11)

zi∈{0,1} ?i∈I

(12)

(13)

(14)

式(1)為目標(biāo)函數(shù)，配載上船的所有車輛的總面積與客滾船船艙可裝載的甲板區(qū)域面積的比值，即模型目標(biāo)使得客滾船船艙可裝載的甲板區(qū)域面積利用率最大。式(2)～式(6)為矩形件排樣約束：式(2)～式(4)保證車輛頭部均與船頭同向，順直停放在甲板上，同時(shí)車輛與車輛間無干涉，獨(dú)立停放；式(5)及式(6)保證車輛完全停放在車艙內(nèi)，無溢出現(xiàn)象。式(7)～式(9)為現(xiàn)實(shí)約束，即保證船舶安全航行：式(7)保證所有裝入船艙的車輛的總重量應(yīng)小于船舶額定載重量的90%；式(8)及式(9)保證在裝入所有車輛后，船舶的縱橫傾約束在安全的額定范圍內(nèi)。式(10)～式(12)為變量取值范圍，式(13)為所有上船渡海車輛面積累加所得的總面積不超過船艙甲板可載面積，式(14)為所有上船渡海車輛的總價(jià)值。

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

3.1 算法整體架構(gòu)

基于客滾船配載問題特性，設(shè)計(jì)K-鄰域搜索的遺傳算法，以此確定渡海車輛的上船順序，以及最低水平線算法，確定車輛停放在船艙甲板上的具體位置，融合最低水平線算法和K-鄰域搜索的遺傳算法作為客滾船配載優(yōu)化決策問題的求解算法，具體算法流程如圖3所示。

圖3 客滾船配載優(yōu)化決策算法流程圖

3.2 K-鄰域搜索的遺傳算法

遺傳算法局部空間搜索能力較差,導(dǎo)致進(jìn)化后期搜索效率偏低，解質(zhì)量不高，故引入局部搜索算法解決遺傳算法的早熟收斂問題，從而提高解的質(zhì)量?；贙-鄰域搜索的混合遺傳算法是綜合遺傳算法和鄰域搜索算法各自優(yōu)勢的全局搜索算法，它一方面保留了遺傳算法的全局搜索能力，同時(shí)基于鄰域搜索提高了遺傳算法的局部搜索能力。

(1)編碼。選用整數(shù)順序編碼的方法，以車輛到達(dá)待渡場的順序?qū)γ恳惠v待渡車輛進(jìn)行編號，假設(shè)生成的染色體為56412387，則表示車輛上船的順序依次為5、6、4、1、2、3、8、7。

(2)種群初始化。種群初始化的策略采用隨機(jī)生成法及經(jīng)驗(yàn)選擇兩種初始化種群策略結(jié)合的方法。

(5)交叉及變異操作。分別采用順序交叉法(OX)及逆序變異法，交叉概率pc和變異概率pm通過多次實(shí)驗(yàn)和前人經(jīng)驗(yàn)來確定。

(6)K-近鄰域搜索。①鄰域搜索。當(dāng)算法迭代停滯若干代或者迭代完成后并生成一個(gè)最優(yōu)解時(shí)，對最優(yōu)解進(jìn)行鄰域搜索，對最優(yōu)解的所有渡海車輛的編碼依次進(jìn)行減一、加一操作，并對新個(gè)體逐個(gè)判斷，觀察其適應(yīng)度，對比原個(gè)體對應(yīng)解的適應(yīng)度是否提高了，若新個(gè)體對應(yīng)解的適應(yīng)度大于原最優(yōu)解的適應(yīng)度，則舍棄原最優(yōu)解，保留新的最優(yōu)解，否則保留原最優(yōu)解。鄰域搜索能夠有效改善遺傳算法對于局部搜索能力差的不足之處。②K-近鄰點(diǎn)集。利用遺傳算法對NPC問題進(jìn)行求解時(shí)，在對遺傳算子進(jìn)行不同的改進(jìn)后，解的質(zhì)量大多能夠得到有效提高，然而，其求解效率比較低，特別是當(dāng)問題規(guī)模增大，算法迭代尋求最優(yōu)解的時(shí)間也在不斷增加，為提高基于鄰域搜索的混合遺傳算法迭代尋求最優(yōu)解的效率，參考文獻(xiàn)[12]，結(jié)合K-近鄰點(diǎn)集進(jìn)一步對算法進(jìn)行優(yōu)化，經(jīng)多次試驗(yàn)，當(dāng)K取10時(shí)，問題求解效果較好。

(7)終止條件。重復(fù)以上的各種遺傳進(jìn)化操作后，直到適應(yīng)度函數(shù)值達(dá)到期望值，即當(dāng)前客滾船配載方案中船艙的面積利用率達(dá)到了期望值，即算法終止，輸出最佳客滾船配載方案。

3.3 最低水平算法

筆者引入矩形件排樣問題中矩形件的定位算法確定待渡車輛在船艙甲板的具體位置，基于客滾船實(shí)際選擇采用最低水平線算法為車輛定位算法。具體算法流程如下。

(1)對于在待渡場等待上船的待渡車輛的序列I={I1，I2，…，In}，要將它們引導(dǎo)至客滾船甲板上，并安排合理的位置，客滾船可配載區(qū)域長為L，寬為W，其中第i輛車的長度和寬度分別為li,wi，i=1,2,…,n。甲板左下角即為原點(diǎn)，坐標(biāo)(0，0)，車輛在甲板上的具體位置由車輛左下角坐標(biāo)唯一確定。

②產(chǎn)品展示形象生動。以GIS地圖作為展示應(yīng)用平臺，各類氣象信息產(chǎn)品由圖片轉(zhuǎn)變?yōu)镚IS圖層展現(xiàn)應(yīng)用，在Web瀏覽器中實(shí)現(xiàn)了產(chǎn)品圖像的透明化處理及放大、漫游、定位、測距、地理信息查詢等空間查詢應(yīng)用功能，并實(shí)現(xiàn)了展現(xiàn)內(nèi)容隨圖像放大逐步細(xì)化顯示的功能。

(2)在引導(dǎo)車輛上船前，首先初始化甲板最低水平線集合。設(shè)水平線集合為λ={λ1,λ2,…,λn}，水平線用λi=(ri,si,ti)表示，ri表示水平線λi的左端端點(diǎn)，si表示水平線λi的右端端點(diǎn)，ti表示水平線λi的高度，即水平線λi與x軸的垂直距離。

(3)初始狀態(tài)下，集合λ中僅有一個(gè)元素，即甲板的內(nèi)艙壁，此時(shí)為最低水平線，λ1=(0，W,0)。在第一次裝車時(shí)，選擇待渡車輛的序列中的第一輛車I1，從水平線λi集合中選擇λ1，將車輛I1的寬度與水平線λi的寬度進(jìn)行比較，若wi≤W，表明車輛I1可以停放在水平線λ1后。

(4)當(dāng)車輛I1停放好后，將車輛I1的車尾處的水平線λ2更新至λ集合中，并將車輛I1從I={I1，I2，…，In}剔除，此時(shí)λ集合中含有兩個(gè)元素，即兩條水平線λ1，λ2，λ1=(w1,W,0)，λ2=(0，w1,l1)。

(5)在配載第二輛車的時(shí)候，從所有待渡車輛選擇第二輛渡海車輛I2進(jìn)行配載時(shí)，從λ水平線集合中選擇高度最低的一條水平線λ1，λ1為λ水平線集合高度最小的水平線，比較渡海車輛I2的車身寬度w2和λ1的寬度W-w1的大小，若w2≤W-w1，即代表渡海車輛I2可以放在新的水平線λ1的后，并停放在水平線λ1的最左端；

(6)如圖4(a)所示，在對車輛Ii選擇合適位置時(shí)，當(dāng)前水平線集合為λ={λ1,λ2,λ3,λ4,λ5}，λ1=(r1,s1,t1)，λ2=(r2,s2,t2)，λ3=(r3,s3,t3)，λ4=(r4,s4,t4)，λ5=(r5,s5,t5)，車輛Ii的長寬為li、wi。首先選擇5條水平線中高度最低的水平線λ5，將車輛Ii的寬度wi與s5-r5進(jìn)行比較。若wi≤s5-r5，則將車輛Ii停放在水平線λ5處；若wi>s5-r5，則舍棄水平線λ5，則從λ={λ1,λ2,λ3,λ4,λ5}挑選高度次低的水平線λ2。繼續(xù)將車輛Ii的寬度wi與水平線λ2的寬度s2-r2進(jìn)行比較，若wi≤s2-r2，則將車輛Ii停放在水平線λ2處；若wi>s2-r2，則舍棄水平線λ2，則從λ={λ1,λ2,λ3,λ4,λ5}挑選高度再次低的水平線λ4，繼續(xù)將車輛Ii的寬度wi與水平線λ4的寬度s4-r4進(jìn)行比較，經(jīng)過比較，車輛Ii的寬度wi與水平線λ4的寬度s4-r4滿足wi≤s2-r2的條件，即將車輛Ii停放在水平線λ4后，并靠左放置，如圖4(b)所示。

圖4 車輛Ii選擇適當(dāng)位置圖

(7)更新水平線集合，判斷甲板剩余區(qū)域是否可以繼續(xù)停放車輛。若可以，從其余車輛挑選合適的車輛進(jìn)行配載，并重復(fù)步驟(6)；若無法繼續(xù)停放其余任何車輛，則結(jié)束配載工作，生成配載方案。算法流程如圖5所示。

圖5 最低水平線算法流程圖

4 場景模擬及分析

為了驗(yàn)證客滾船配載優(yōu)化模型和算法的有效性，分別設(shè)計(jì)一般場景和特殊場景下的仿真實(shí)驗(yàn)，實(shí)現(xiàn)客滾船配載優(yōu)化決策。

4.1 一般場景優(yōu)化決策

4.1.1 場景設(shè)置

根據(jù)對瓊州海峽客貨滾裝業(yè)務(wù)進(jìn)行分析，由于配載對象為社會渡海車輛，其出行規(guī)律有一定的社會屬性，典型渡海車輛數(shù)據(jù)參考文獻(xiàn)[13]，白天(D)小車較多，貨車較少，少量客車；晚上(N)貨車居多，小車較少，無客車。對不同時(shí)段渡海車輛的車型比例進(jìn)行假設(shè)，如表1所示。車輛間的安全距離設(shè)置為0.2 m，即dx、dy的大小為0.1。典型實(shí)驗(yàn)客滾船船型數(shù)據(jù)如表2所示。

表1 不同時(shí)段的車型比例

表2 典型實(shí)驗(yàn)客滾船船型數(shù)據(jù)

為了方便敘述，不同場景利用M/L-D/N-R的方式來表示，其中D/N表示配載業(yè)務(wù)是白天或是晚上，R表示不同情況下的各車型具體比例，M/L表示不同規(guī)格的客滾船。各類車型的渡海費(fèi)用參考有關(guān)部門制定的標(biāo)準(zhǔn)：客車為560元/輛；小車為374元/輛；貨車為計(jì)重計(jì)費(fèi)，約合40元/t。

利用MATLAB 2019a求解構(gòu)建的模型，經(jīng)多次試驗(yàn)，將算法種群規(guī)模設(shè)置為100，迭代次數(shù)設(shè)置為200，交叉概率為0.95，變異概率為0.2，模型最大求解時(shí)間設(shè)置為120 s，為避免出現(xiàn)偶然性，每個(gè)場景進(jìn)行10次方案輸出，取其平均值。

4.1.2 決策方案

16種不同場景下的實(shí)驗(yàn)結(jié)果如表3所示，f表示每個(gè)場景運(yùn)行10次客滾船船艙甲板可載區(qū)域利用率的平均值，f′表示每個(gè)場景下10次實(shí)驗(yàn)結(jié)果的標(biāo)準(zhǔn)差。

由表3可知，對于4艘不同規(guī)格的客滾船，在不同的時(shí)間、不同車輛種類及比例、不同待渡車輛規(guī)模的情況下客滾船的船舶面積利用率均達(dá)到了96%左右，標(biāo)準(zhǔn)差基本在0.005左右，證明模型算法具有良好的穩(wěn)定性，求解性能良好。

表3 不同場景下客滾船車輛配載方案

其中面積利用率在95%的場景均為小型客滾船M1、M2，由于晚間發(fā)船，小車比例少，無法填補(bǔ)貨車產(chǎn)生的空隙，造成面積的小部分浪費(fèi)，降低了船舶的面積利用率。而船型較大的客滾船L1、L2其面積利用率能夠維持在較高水平，從側(cè)面說明客滾船的大型化能夠在車型更雜的現(xiàn)實(shí)作業(yè)中提高船艙甲板的利用率。

圖6為場景M2-D-R1中的一次求解結(jié)果的配載可視化方案，客滾船船艙面積利用率達(dá)到了97.04%，該航次車輛總運(yùn)費(fèi)65 756元，車輛總重771.8 t，處于安全航行的狀態(tài)，車輛中所標(biāo)示的數(shù)字為車輛到達(dá)序號，矩形所在位置即車輛上船后停放的具體位置。

圖6 場景M2-D-R1配載方案可視化展示

4.2 特殊場景優(yōu)化決策

4.2.1 場景設(shè)置

場景一：模擬當(dāng)港口受極端天氣影響時(shí)，港口出現(xiàn)車輛積壓問題，為加快港口運(yùn)作效率，盡快發(fā)送車輛和旅客，為港口車輛配載工作提供可行且高效的配載方案。

場景二：模擬客滾運(yùn)輸業(yè)務(wù)淡季時(shí)，渡海車輛數(shù)目較少，單個(gè)航次無法滿艙時(shí)，為港口車輛配載工作提供可行的配載方案。

各待渡車輛的車型以及各項(xiàng)參數(shù)同4.1節(jié)，客滾船舶選取目前在航線“?？凇０病睜I運(yùn)的客滾船舶“紫荊二十二號”、“寶島12號”兩艘客滾船進(jìn)行場景模擬，其參數(shù)分別為：“紫荊二十二號”的船舶總長127.5 m，型寬20.88 m，額定載貨量3 150 t；“寶島12號”的船舶總長106 m，型寬19.8 m，額定載貨量1 574 t。

4.2.2 決策方案

場景一當(dāng)港口出現(xiàn)大量待渡車輛積壓在港口時(shí)，根據(jù)港口總平面布置圖，此時(shí)待渡場內(nèi)停放的貨車、小車、客車的數(shù)量分別為260輛、160輛、60輛，利用客滾船“紫荊二十二號”進(jìn)行配載作業(yè)。為了減少隨機(jī)性，分別進(jìn)行10次模擬實(shí)驗(yàn)，船艙面積利用率在97%左右，平均利用率為97.35%，標(biāo)準(zhǔn)差為0.003，說明基于模型及算法得出的優(yōu)化決策能夠一定程度上解決港口車輛的積壓問題，以實(shí)現(xiàn)在短時(shí)間內(nèi)有序地指揮調(diào)度車輛進(jìn)行登船作業(yè)，快速發(fā)送車輛。第8次的配載方案示例如圖7所示。

圖7 第8次配載方案可視化展示

場景二為客貨滾裝運(yùn)輸業(yè)務(wù)淡季時(shí)的場景，假設(shè)僅80輛待渡車輛等待渡海，各類車型以及各項(xiàng)參數(shù)同4.1節(jié)，隨機(jī)產(chǎn)生。經(jīng)求解，輸出該航次的一種較優(yōu)配載方案，其車輛總重643.2 t，如圖8所示，同種類型的渡海車輛從左至右均勻分布，保證船舶不會發(fā)生橫傾的風(fēng)險(xiǎn)，從船頭方向往船尾看，小車集中于在船頭側(cè)的甲板上，貨車及少量的客車等大型車輛偏甲板中間停放，此時(shí)船舶縱傾約為8 190 kN·m，在最大橫傾力矩范圍內(nèi)，能夠充分保證船舶的航行安全，配載方案合理。

圖8 淡季客滾船配載可視化展示

5 結(jié)論

筆者針對瓊州海峽新海港客滾船配載決策問題：①引入矩形件排樣優(yōu)化理論，并結(jié)合實(shí)際，以船艙面積利用率最大為目標(biāo)，構(gòu)建客滾船配載優(yōu)化決策模型，設(shè)計(jì)了融合基于K-鄰域搜索的遺傳算法和最低水平線算法的求解方案。②通過模擬在不同場景下客滾運(yùn)輸業(yè)務(wù)，當(dāng)渡海車輛數(shù)量充足時(shí)，船艙面積利用率能夠達(dá)到96%左右的較高水平；當(dāng)渡海車輛數(shù)量較少時(shí)，同樣能夠滿足實(shí)際場景中客滾船配載要求，輸出合理的配載方案。③配載優(yōu)化決策方法能較好地適應(yīng)不同的客滾船配載場景，對于不同場景下的客滾船智能配載決策均有一定的指導(dǎo)意義，能夠有效提升客滾運(yùn)輸業(yè)務(wù)的營運(yùn)效率，且一定程度上能夠保證港方收益。后續(xù)，將針對多層客滾船的配載以及當(dāng)無法已知全部渡海車輛信息時(shí)的動態(tài)配載進(jìn)行研究。