徐 進(jìn) 張 煜 李 俊

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

0 引 言

集裝箱船全航線配載作為集裝箱運(yùn)輸?shù)暮诵沫h(huán)節(jié)，在保障船舶安全航行、貨物安全運(yùn)輸，以及營(yíng)運(yùn)效率中扮演著重要角色.目前，國(guó)內(nèi)外學(xué)者對(duì)集裝箱船配載研究，主要集中在模型構(gòu)建和算法開發(fā)等方面，涉及單港口和全航線等船舶配載問(wèn)題.在單港口船舶配載方面，樂美龍等[1]構(gòu)建了集裝箱船配載問(wèn)題模型，設(shè)計(jì)啟發(fā)式算法求解；李俊等[2]設(shè)計(jì)了吱呀輪-混合演算策略兩階段算法，求解帶有堆場(chǎng)發(fā)箱順序約束的船舶配載問(wèn)題；李坤等[3]建立最小化裝船時(shí)間和Bay位重量差的多目標(biāo)規(guī)劃模型，設(shè)計(jì)兩階段啟發(fā)式算法求解模型；Maria 等[4]從碼頭角度考慮集裝箱配載問(wèn)題，并設(shè)計(jì)兩階段啟發(fā)式算法最小化集裝箱運(yùn)輸時(shí)間的堆場(chǎng)翻箱次數(shù)；Eliseu等[5]將船舶配載決策視作三維裝箱問(wèn)題，最小化掛靠港裝卸操作次數(shù)和船舶非穩(wěn)性，并提出帕累托聚類搜索(Pareto clustering search)算法求解模型.在全航線配載方面，Alberto[6]建立全航線配載的整數(shù)規(guī)劃模型和約束規(guī)劃模型，使用CPLEX和Gecode軟件分別對(duì)模型進(jìn)行求解；Dario[7]從翻倒箱量和岸橋利用率出發(fā)，建立全航線配載的整數(shù)規(guī)劃模型，采用大鄰域搜索算法進(jìn)行求解；Daniela等[8]設(shè)計(jì)啟發(fā)式算法對(duì)全航線船舶配載問(wèn)題進(jìn)行求解，最小化船舶駐港總時(shí)間；Daniela等[9]又以全航線集裝箱配載為研究對(duì)象，建立考慮標(biāo)準(zhǔn)箱、冷藏箱、上開口箱及艙蓋板的混合整數(shù)規(guī)劃模型，并以MIP Solver進(jìn)行驗(yàn)證；Ding等[10]以最小化全航線翻箱率為目標(biāo)建立全航線配載模型，并設(shè)計(jì)啟發(fā)式算法對(duì)其進(jìn)行求解.Opher等[11]針對(duì)全航線集裝箱配載倒箱量最小而設(shè)計(jì)一種基于緊湊而高效編碼方式的遺傳算法，搜索模型最優(yōu)解.

以上船舶配載相關(guān)研究均針對(duì)海運(yùn)展開，基本都是將船舶的整貝或單個(gè)箱位作為存儲(chǔ)單元設(shè)計(jì)模型和算法[12-13].由于內(nèi)河集裝箱船舶船體較小、船方更加強(qiáng)調(diào)艙容利用率，本文將內(nèi)河集裝箱船各個(gè)貝劃分為不同粒度的存儲(chǔ)單元，結(jié)合數(shù)學(xué)規(guī)劃方法，構(gòu)建基于粒度劃分策略的內(nèi)河集裝箱船全航線配載模型，實(shí)現(xiàn)航線同目的港集裝箱在內(nèi)河船舶存儲(chǔ)單元的集中堆放，進(jìn)而提高船舶利用率.結(jié)合長(zhǎng)江真實(shí)運(yùn)輸場(chǎng)景設(shè)計(jì)多組算例，通過(guò)算例驗(yàn)證模型的有效性.

1 問(wèn)題描述

集裝箱船全航線配載問(wèn)題可歸為多港主貝計(jì)劃問(wèn)題(multi-port master bay plan problem，MP-MBPP)，是根據(jù)航線各個(gè)掛靠港集裝箱的尺寸、質(zhì)量等級(jí)、目的港、數(shù)量等信息，將各個(gè)掛靠港集裝箱集合有效劃分并分配到船舶各個(gè)貝內(nèi)，需要保證船舶穩(wěn)性、強(qiáng)度、容量等約束，避免翻倒箱，提高船舶全航線裝載率.內(nèi)河集裝箱船全航線配載，見圖1.各掛靠港按遍歷順序組成多個(gè)航段，集裝箱流向O-D(起始港-目的港)以一段有向弧a表示.在內(nèi)河支線集裝箱船全航線配載決策中，船舶船體更小(多為3 000～5 000 t級(jí)船型)，沒有艙蓋板，強(qiáng)調(diào)艙容利用率.

圖1 全航線配載示意圖

文中對(duì)內(nèi)河集裝箱船全航線配載決策進(jìn)行研究，基于粒度劃分策略，將內(nèi)河集裝箱船的存儲(chǔ)空間(由貝-堆棧-箱位組成)劃分為不同數(shù)量、不同大小的多個(gè)存儲(chǔ)單元，進(jìn)而構(gòu)建內(nèi)河集裝箱船全航線配載的多粒度數(shù)學(xué)規(guī)劃模型.此處，粒度是用來(lái)描述船舶存儲(chǔ)單元大小的.最粗粒度的船舶存儲(chǔ)單元對(duì)應(yīng)船舶偶數(shù)貝箱位集合，中間粒度的船舶存儲(chǔ)單元對(duì)應(yīng)船舶偶數(shù)貝多個(gè)相鄰堆棧的箱位集合，最細(xì)粒度的船舶存儲(chǔ)單元對(duì)應(yīng)船舶偶數(shù)貝堆棧的箱位集合.通過(guò)以上靈活定義，粒度越粗的數(shù)學(xué)規(guī)劃模型，其約束和變量減少，可以有效提高模型求解效率.同時(shí)，基于粒度劃分策略構(gòu)建啟發(fā)式算法，還可以在求解精度和運(yùn)算效率間獲得平衡.

2 模型構(gòu)建

基本參數(shù)：H為航線港口集合；B為船舶貝集合；B(k),BP(k),BA(k)，BL,l(k),BR,l(k)分別為k粒度下船舶整體、船舶前半部、船舶后半部、船舶貝l∈B左半部和右半部的存儲(chǔ)單元集合；Pt(i),Ps(i),P(i)為航線上港口i對(duì)應(yīng)的O—D副集合，Pt(i)={a|o,i,d∈H,o

決策變量：xbg(a)為港口副流向a分配到船舶存儲(chǔ)單元b的g質(zhì)量等級(jí)集裝箱的數(shù)量；yb(i)為0-1變量，若在港口i船舶存儲(chǔ)單元b被占用，則y為1，否則為0；zb(a)為0-1變量，若船舶存儲(chǔ)單元b被a副流向下集裝箱占用，則z為1，否則為0.

1) 粒度計(jì)算

「‖Nrow‖/2j?>1)+2，j為自然數(shù)

(1)

Nk=「‖Nrow‖/2m-k?，k=1,2,…,m

(2)

‖|B(k)‖=‖Nbay‖·Nk，k=1,2,…,m

(3)

式(1)為最細(xì)粒度；式(2)為k粒度下船舶貝內(nèi)存儲(chǔ)單元數(shù)量；式(3)為k粒度下船舶存儲(chǔ)單元數(shù)量.

2)k粒度下的混合整數(shù)規(guī)劃模型，記為MIP(k)

f=min(∑i∈H∑b∈B(k)yb(i)/

((‖H‖-1)×‖B(k)‖))

(4)

s.t. ∑b∈B(k)xbg(a)=Ng(a)

?i∈H,a∈Ps(i),g∈G

(5)

zb(a1)+zb(a2)≤1?i∈H,b∈B(k),

(a1,a2)∈D(i)

(6)

∑a∈P(i)∑g∈Gxbg(a)≤CTeub

?i∈H,b∈B(k)

(7)

∑a∈P(i)∑g∈Gwg·xbg(a)≤CTonb

?i∈H,b∈B(k)

(8)

|∑a∈P(i)∑g∈G∑b∈BL,l(k)(wg·xbg(a))-

ΔGh?i∈H，?l∈B

(9)

0≤∑a∈P(i)∑g∈G∑b∈BA(k)wg·xbg(a)-

∑a∈P(i)∑g∈G∑b∈BP(k)wg·xbg(a)≤ΔGc

?i∈H

(10)

yb(i)≤∑a∈P(i)zb(a)≤yb(i)·M

?i∈H,b∈B(k)

(11)

zb(a)≤∑g∈Gxbg(a)≤zb(a)·M

?i∈H,b∈B(k),a∈P(i)

(12)

目標(biāo)函數(shù)(4)最小化船舶存儲(chǔ)單元在全航線配載的平均使用數(shù)量，使被占用的存儲(chǔ)單元盡可能多裝箱，即提升船舶存儲(chǔ)單元利用率；約束(5)確保任一掛靠港待裝集裝箱都裝船；約束(6)確保不同目的港集裝箱不混裝；約束(7)和(8)分別確保船舶在任一掛靠港裝完后滿足存儲(chǔ)單元最大容量和最大載荷要求；約束(9)和(10)分別確保船舶在各掛靠港裝載完成后滿足橫傾和縱傾力矩允許的重量偏差要求；約束(11)和(12)定義了三個(gè)決策變量之間的關(guān)系.

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

針對(duì)內(nèi)河集裝箱船全航線配載問(wèn)題，結(jié)合內(nèi)河運(yùn)輸特征，設(shè)計(jì)基于多粒度配載模型的啟發(fā)式算法，算法包括存儲(chǔ)單元?jiǎng)討B(tài)劃分及分支定界算法求解單一粒度下配載模型兩部分.其中，存儲(chǔ)單元?jiǎng)討B(tài)劃分即根據(jù)粒度確定貝內(nèi)存儲(chǔ)單元數(shù)量，均勻地將各貝劃分為多個(gè)存儲(chǔ)單元.為船舶配載主貝計(jì)劃的制定確定最小裝載單元，及橫、縱向重量差計(jì)算方式；分支定界算法即在執(zhí)行過(guò)程中將全部可行解空間不斷分割為越來(lái)越小的子集(稱為分支)，并為每個(gè)子集內(nèi)的解的值計(jì)算一個(gè)下界或上界(稱為定界)，從其中尋得最佳解.模型中通過(guò)CPLEX優(yōu)化軟件調(diào)用分支定界算法對(duì)單個(gè)粒度下的配載模型進(jìn)行求解.算法具體搜索流程見圖2.

圖2 啟發(fā)式算法搜索流程

4 算例驗(yàn)證

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

根據(jù)文獻(xiàn)[14]選取集裝箱船，其參數(shù)見表1.

根據(jù)以上船舶參數(shù)，構(gòu)建不同船型，不同掛靠港的36組算例驗(yàn)證模型.算例以S(船型:1,2,3)、P(掛靠港口數(shù)量:4,6)、R(TEU/FEU箱數(shù)量比例：1～5∶5,2～7∶3)、W(輕、中、重箱數(shù)量比例：1～6∶3∶1,2～3∶6∶1,3～3∶4∶3)組合來(lái)標(biāo)識(shí).例如，S2P4R1W2表示該算例采用2號(hào)船舶且航線依此掛靠四個(gè)港口，在各掛靠港TEU/FEU箱數(shù)量比約為5∶5，輕、中、重箱數(shù)量比約為3∶6∶1.

表1 集裝箱船裝載參數(shù)

4.2 模型驗(yàn)證

以算例S1P4R2W3為例，依據(jù)式(1)～(3)可求得四個(gè)粒度，基于多粒度配載模型，結(jié)合CPLEX優(yōu)化軟件對(duì)各個(gè)粒度進(jìn)行仿真分析，驗(yàn)證模型的可行性.算例求解結(jié)果見表2，結(jié)果顯示粒度劃分越細(xì)，約束及變量個(gè)數(shù)越多，求解時(shí)間越長(zhǎng)，模型復(fù)雜度呈指數(shù)增長(zhǎng).通過(guò)多組算例驗(yàn)證顯示上述結(jié)論針對(duì)所有算例均成立，多粒度配載模型通過(guò)對(duì)存儲(chǔ)單元粒度的不斷細(xì)分可優(yōu)化存儲(chǔ)單元占用率，細(xì)粒度下模型求解時(shí)間最長(zhǎng)，復(fù)雜度最高.但最細(xì)粒度下的解并不一定是最優(yōu)解，具體結(jié)果見模型性能分析部分.

表2 CPLEX優(yōu)化多粒度配載模型相關(guān)參數(shù)

注：*為通過(guò)刪除約束(6)所求得該粒度下的最優(yōu)解.

為進(jìn)一步驗(yàn)證模型的可行性，以算例S1P4R2W3最優(yōu)解為集裝箱配載方案繪制最優(yōu)粒度下船舶存儲(chǔ)單元在各掛靠港裝載情況見圖3.圖中每個(gè)單元格對(duì)應(yīng)一個(gè)存儲(chǔ)單元，格中數(shù)字分別對(duì)應(yīng)該存儲(chǔ)單元裝載的集裝箱數(shù)量及其總重.其中由兩個(gè)或兩個(gè)以上圖標(biāo)組合標(biāo)識(shí)的為多個(gè)掛靠港集裝箱混裝結(jié)果，如在掛靠港2，左下角存儲(chǔ)單元由左斜線圖標(biāo)及網(wǎng)格圖標(biāo)組合標(biāo)識(shí)，表示在掛靠港2，該存儲(chǔ)單元裝載掛靠港1發(fā)往后續(xù)港口的集裝箱和掛靠港2發(fā)往后續(xù)港口的集裝箱(各區(qū)域面積并不代表裝箱數(shù)量).各掛靠港依次占用存儲(chǔ)單元數(shù)量為15，15，15，該航次中船舶存儲(chǔ)單元平均占用率為83.33%，各存儲(chǔ)單元裝載率高，符合最小化存儲(chǔ)單元占用原則.此外，通過(guò)計(jì)算，各掛靠港船舶橫向重量差和縱向重量差均滿足船舶營(yíng)運(yùn)安全性約束.綜上所述，多粒度配載模型在一定程度上能夠有效細(xì)化裝載空間，提高集裝箱船利用率，獲得滿足集裝箱配載要求的最優(yōu)解.此外，粒度與模型復(fù)雜度的關(guān)系使得建模者可在時(shí)間及優(yōu)化解之間做出權(quán)衡，亦可從較粗粒度的快速求解特性出發(fā)快速產(chǎn)生初始解用于拓展其他優(yōu)化算法.

圖3 案例S1P4R2W3各掛靠港存儲(chǔ)單元占用情況

4.3 模型性能分析

以啟發(fā)式算法結(jié)合CPLEX優(yōu)化軟件對(duì)36組算例進(jìn)行求解，考慮細(xì)粒度下求解時(shí)間較長(zhǎng)，設(shè)定各粒度的優(yōu)化時(shí)間限值為30 min，各算例求解結(jié)果見表3.由表3可知，36組算例平均橫向質(zhì)量差、平均縱向質(zhì)量差分別為14.93，16.92 t，均滿足船舶航行安全性約束；36組算例平均求解時(shí)間為290.64 s，平均gap值為6.16%，求解時(shí)間及求解結(jié)果均在可允許范圍內(nèi).

表3 36組算例仿真結(jié)果

續(xù)表3

注：--表示無(wú)該參數(shù)(粗粒度下以整貝為存儲(chǔ)單元，此時(shí)不考慮貝內(nèi)橫傾；對(duì)粒度求均值無(wú)意義)；gap值由CPLEX求解模型時(shí)給出，為最優(yōu)粒度模型的下界值;*表示該均值計(jì)算剔除無(wú)效數(shù)據(jù)，采用所有有效數(shù)據(jù)進(jìn)行計(jì)算.

作為船舶配載的重要影響因素，船舶橫、縱向重量差的變化也是檢驗(yàn)?zāi)Ｐ偷囊豁?xiàng)重要指標(biāo)，本文將啟發(fā)式算法求得各掛靠港船舶各貝橫向重量差及船舶縱向重量差作箱形圖見圖4.

圖4 質(zhì)量差箱形圖

圖4a)橫向質(zhì)量差箱形圖中垂線下端點(diǎn)對(duì)應(yīng)某一算例中各掛靠港船舶各貝中最小橫向質(zhì)量差，垂線上端點(diǎn)對(duì)應(yīng)最大橫向質(zhì)量差，矩形框上邊緣對(duì)應(yīng)某一算例中船舶橫向質(zhì)量差上四分位點(diǎn)，下邊緣對(duì)應(yīng)下四分位點(diǎn)，三角形位置代表中位值，圖4b)類似.

由圖4a)可知，各案例船舶貝內(nèi)橫向質(zhì)量差波動(dòng)范圍較均勻，均在0～26 t.根據(jù)中位數(shù)的定義可知多個(gè)算例的船舶在各掛靠港、各貝的橫向質(zhì)量差多數(shù)處于0～20 t.由圖4b)可知，多個(gè)案例在各掛靠港船舶整體縱向質(zhì)量差(尾傾)小于25 t，整體處于5～23 t.故多粒度配載模型求解結(jié)果降低船舶橫向質(zhì)量差、保留適當(dāng)尾傾，保證了集裝箱船舶的適航性.

綜上所述，多粒度配載模型可有效完成存儲(chǔ)空間的劃分，實(shí)現(xiàn)內(nèi)河集裝箱緊湊的堆存方式，可準(zhǔn)確、快速得出集裝箱船配載方案.此外，根據(jù)細(xì)粒度下并非最優(yōu)的結(jié)論，通過(guò)對(duì)粒度的合理選取可減少解空間，加快模型求解速率.

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

文中針對(duì)內(nèi)河集裝箱船全航線配載問(wèn)題展開研究，構(gòu)建了基于粒度劃分的船舶全航線配載模型，并設(shè)計(jì)啟發(fā)式算法對(duì)模型進(jìn)行求解.結(jié)合長(zhǎng)江真實(shí)運(yùn)輸場(chǎng)景設(shè)計(jì)多組算例，驗(yàn)證了多粒度配載模型的有效性.多組算例表明粒度的劃分程度直接影響模型計(jì)算的復(fù)雜度，粒度劃分越細(xì)，獲得解最優(yōu)的概率越大，但最優(yōu)解確不一定出現(xiàn)在最細(xì)粒度.故通過(guò)粒度的合理選擇可實(shí)現(xiàn)模型求解中目標(biāo)和時(shí)間的均衡，且通過(guò)較粗粒度的快速求解特性可較快產(chǎn)生初始可行解，有利于開發(fā)靈活高效的算法.