現(xiàn)實約束下的多掛靠港滾裝船舶配載優(yōu)化

姜彥寧, 徐 奇, 金燕燕, 靳志宏*

(1.大連海事大學 交通運輸管理學院,遼寧 大連 116026; 2.交通運輸部 科技司,北京 100736)

現(xiàn)實約束下的多掛靠港滾裝船舶配載優(yōu)化

姜彥寧1,2, 徐 奇1, 金燕燕1, 靳志宏*1

(1.大連海事大學 交通運輸管理學院,遼寧 大連 116026; 2.交通運輸部 科技司,北京 100736)

在分析滾裝船舶配載特點的基礎(chǔ)上,考慮了船舶穩(wěn)性、配載效率以及航次收益等現(xiàn)實約束,針對多掛靠港的滾裝汽車運輸新模式下的配載優(yōu)化問題進行建模,并基于該問題多階段、多維約束、多背包組合優(yōu)化的特點,開發(fā)了遺傳算法對所構(gòu)建模型進行求解.對于小規(guī)模數(shù)值算例實驗,運用所設(shè)計遺傳算法的求解結(jié)果與 lingo 軟件所得到的精確解比較,平均誤差率約為 1.4%;對于大規(guī)模仿真算例,遺傳算法的求解質(zhì)量則明顯優(yōu)于現(xiàn)實調(diào)度策略,顯示出本算法較好的魯棒性.在此基礎(chǔ)上開發(fā)了基于 VB 的配載信息系統(tǒng),實現(xiàn)了配載過程及配載方案的可視化,為實時配載決策奠定了基礎(chǔ).

綜合交通運輸;滾裝船配載;多掛靠港;決策可視化

1 引 言

滾裝船配載要在保證船舶航行安全的前提下,進行裝船車輛的合理選擇和安排,是一個典型的離散組合優(yōu)化問題.隨著船舶大型化趨勢的加劇,滾裝船 配 載 優(yōu) 化 問 題 (ro-ro ship loading problem, RRSLP)已發(fā)展為大規(guī)模、高復雜度的組合優(yōu)化問題.同時,伴隨著這種船舶大型化的趨勢,滾裝船舶的運輸也改變了原來的兩港間的直航(無中途?？扛?運輸模式,出現(xiàn)了多掛靠港的滾裝運輸新模式.據(jù)調(diào)查,目前并無針對這種新滾裝運輸模式的配載優(yōu)化的相關(guān)文獻.

國內(nèi)外學者對集裝箱船配載優(yōu)化進行了比較深入的研究[1,2],而對滾裝船舶配載優(yōu)化的研究還不是十分深入.孫玉昌等[3]對船載車輛橫搖及車輛停放時滾裝船穩(wěn)性問題進行核算,并提出了合理化建議.李冬梅[4]指出滾裝船在積載系固方面存在的問題,并給出了車輛的積載和系固方面的要求.宋振洪[5]從保證船舶穩(wěn)性的角度出發(fā),通過最小化船舶平衡力矩來選擇裝船車輛.Jia[6]探討了如何使?jié)L裝船上的車輛不需系固也可保證安全,以提高停放車輛的數(shù)量.靳志宏與金燕燕[7]考慮了船舶穩(wěn)性、配載效率及航次收益等現(xiàn)實約束與配載目標,對滾裝船配載優(yōu)化問題進行建模,開發(fā)了以貪婪算法為基礎(chǔ)的兩階段啟發(fā)式算法.目前該研究僅限于單一裝貨港與單一卸貨港的直達運輸模式,沒有考慮多裝貨港和卸貨港,即有中途掛靠港的情形.

本文在參考文獻[7]的基礎(chǔ)上,將兩港間的直航模式擴展到多掛靠港的滾裝運輸新模式;設(shè)計實用優(yōu)化算法以求解所構(gòu)建的船舶配載優(yōu)化模型,開發(fā)配載管理信息系統(tǒng),進而實現(xiàn)智能與可視化配載.

2 問題描述

2.1 問題歸結(jié)

本文研究的船舶配載是多類型成品車的多裝貨港多卸貨港的多階段配載問題,根據(jù)裝貨港的不同劃分成不同階段,對每個階段進行配載.滾裝船配載優(yōu)化問題可歸結(jié)為特殊的離散優(yōu)化的背包問題.其特殊性體現(xiàn)在:

(1) 多階段配載問題,現(xiàn)行研究針對的是兩港間的直航(無中途?？扛?運輸模式,本文將其擴展到多掛靠港的滾裝運輸新模式;

(2) 多維約束問題,如載重量約束、空間尺寸約束、船舶穩(wěn)性約束等;

(3) 多背包問題,即同時進行配載的背包數(shù)(各層甲板、以及每層甲板的車道的條數(shù))是多個.

綜上,該優(yōu)化問題可以歸結(jié)為多階段、多維約束、多背包組合優(yōu)化問題.

2.2 現(xiàn)實約束

為了增強配載方案的實用性,本文考慮了如下現(xiàn)實約束:

(1)所有待裝船到達某一個卸貨港的車輛所占用的車道長度,不能超過分配給這個卸貨港的車道長度;

(2) 所有裝載到同一條車道上的車輛總長度(包括車輛之間的安全距離)不能超過這條車道的固定長度;

(3) 裝載車輛的總重量不能超過船舶允許的最大載重量;

(4) 為保證船舶整體航行穩(wěn)定性,裝載方案必須保證船舶橫傾力矩和縱傾力矩位于允許的范圍內(nèi).

3 現(xiàn)實約束下的配載優(yōu)化建模

3.1 前提與假設(shè)條件

(1) 將船頭至船尾方向的中心線看成船舶的縱軸 y,船舶從左到右的方向看成船舶的橫軸 x.俯視看,船頭是上方,船尾是下方,船舶的左面是左方,右面是右方.船舶的坐標軸示意如圖1 所示.

圖1 船舶坐標軸示意圖Fig.1 Illustration of the coordinate for a ship

(2) 第一個裝貨港只裝不卸,最后一個卸貨港只卸不裝.

(3)甲板的形狀是矩形.

(4) 分配給航線上各中途卸貨港的車道條數(shù)是整數(shù)條.

3.2 符號說明

Z ——完成船舶裝載車輛總的航次收益;

I——待裝車輛總數(shù);

J ——航線上掛靠港數(shù)量;

W ——船艙允許的最大載重噸;

t——第 t個裝車港,即配載的階段數(shù),如 t=1就是第一個裝車港和第一個配載階段,以此類推;

T ——配載階段數(shù);

Wt-1——前一個裝貨港船艙已裝車輛的總重量減去在t階段卸船的車輛的重量;

K ——每層甲板車道的總數(shù);

Totalj——航線上到 j港卸貨的車輛總數(shù);

L ——每條車道的固有長度;

k ——車道的索引,k=1,2,…,K;

i——車輛的索引;

j——目的港的索引;

vij——車輛 i到港口 j的運價;

Kj——分配給 j港口的車道數(shù);

wi——車輛 i的自重;

li——車輛 i的長度;

Lj——分配給 j港口的車道長度;

(hqx1,hqx2) ——船艙沿 x 軸上的橫傾力矩安全范圍要求;

(zqy1,zqy2) ——船艙沿 y 軸上的縱傾力矩安全范圍要求;——配載階段 t 到達目的地港口 j的車輛 i配載在車道k上;

(xi,yi) ——車輛 i在船艙中的重心坐標;

(Luxi,Luyi):車輛 i在船艙內(nèi)的左下角坐標;

(Rdxi,Rdyi):車輛 i在船艙內(nèi)的右上角坐標.

3.3 優(yōu)化模型

目標函數(shù)

約束條件

其中 式(1)為最大化滾裝船所裝載車輛的總航次收益;式(2)確保在第 t個裝車港裝車時船艙所裝載車輛的總噸數(shù)不超過此時刻船艙容許的最大載重噸;式(3)保證在第 t階段所有到 j港口的裝船車輛總長度不超過分配給第 j港口車道的總長度;式(4)確保每條車道上所裝載的車輛總長度不超過車道的固有長度;式(5)、式(6)確保船艙中所裝的車輛的總橫傾力矩、總縱傾力矩不超過給定的范圍;式(7)、式(8)用于計算車輛 i在船艙中的橫坐標和縱坐標;式(9)、式(10)計算分配給到達 j港的車道數(shù)量和總長度;式(11)確保車輛 i不能同時重復裝載.

4 算法設(shè)計

針對多階段、多維約束、多背包組合優(yōu)化問題的特點,本文設(shè)計了針對該特殊背包問題的染色體編碼方法:將待求解的變量 X 的每一維度表示成長度為待裝車輛總數(shù) I的字符串 x[n],n=1,…, I,n 按照所有待裝車輛的卸貨港的順序 j,j=1,…,J 排列,且 x[n]=0 表示車輛 n 不配載,x[n]= 1 表示放入第一個車道,x[n]=2 表示放入第二車道,以此類推.例如:對于 x[n] 為 112001102……000112 的一個編碼,第三個位置上的 x[n]=2,表明車輛3是裝載在 k=2的車道上,j值代表車輛3將會在第 j個目的港卸載;另外,卸貨港 j,j=1,…, J 與配載階段 t,t=1,…,T,即裝貨港順序相互關(guān)聯(lián),其內(nèi)在聯(lián)系可表示為 t=j+1,此時的 x[n]=2意味著 i=3,j=1,k=2,t=2.

在此基礎(chǔ)上,設(shè)計的遺傳算法流程如下.

步驟1初始化.

步驟1-1讀入相關(guān)信息,如所裝車輛的重量weight[j] 、長度 length[j] 、 收 費 profit[j] 和 車 道的最大載重量 contain 及長度 L,其中 j=0,1,…, lchrom-1,lchrom 為染色體長度.

步驟1-2取 x[j]=u(0,1,…,n),j=0,1,…,lchrom-1,其中 u(0,1,…,n) 表示 0 至 n 間的均勻分布整數(shù)函數(shù).

若不滿足模型的約束條件,則由步驟1-2 重新生成新的染色體個體 chrom;若產(chǎn)生的染色體可行,則將其作為種群的一個個體,經(jīng)過有限次抽樣后,得到 popsize 個可行的染色體 chrom,形成新的種群.

步驟1-3置種群的代數(shù) gen=0.

步驟2計算個體適應(yīng)度及統(tǒng)計種群適應(yīng)度.

步驟2-1計算種群中個體適應(yīng)度:

步驟2-2基于步驟2-1,計算種群的總體適應(yīng)度,.并且通過排序統(tǒng)計出種群中的最大、最小適應(yīng)度的染色體個體.

步驟3選擇操作.

步驟3-1生成 隨機數(shù) rand_Number(0 ＜rand_Number ＜ 1).

步驟3-2按照賭輪法選擇個體.

步驟3-3重復兩次操作步驟3-1、步驟3-2,生成兩個個體作為交叉操作的父代.

步驟4交叉操作.

步驟4-1生成[0,1]的隨機數(shù) pp,若 pp ＜pc(pc為交叉概率),則進行步驟4-2;否則將該父代保留為下一代的兩個個體.

步驟4-2隨機生成 [0,lchrom-1] 的整數(shù)作為交叉點,對兩個父代個體交叉生成兩個新個體.

步驟4-3重復 pop_size/2 次步驟4-1、步驟4-2便可生成 pop_size 個個體組成新的種群.

步驟5變異操作.

步驟5-1生成[0,1]的隨機數(shù) pp,若 pp ＜pm(pm為變異概率),進行步驟5-2 變異操作,否則不變異.

步驟5-2若原基因為 0,則新基因變異為 1;若原基因為 1,則新基因變異為 2……;原基因為n,則新基因變異為 0.

步驟6演化.

步驟6-1按步驟2 的方法計算新種群的適應(yīng)度情況,并找出新種群中適應(yīng)度最大和最小的個體.

步驟6-2若舊種群的最大個體適應(yīng)度優(yōu)于新種群的最大個體適應(yīng)度,將舊種群中適應(yīng)度最大的個體代替新種群中適應(yīng)度最小的個體,否則進行步驟6-3.

步驟6-3種群的代數(shù) gen=gen+1,若 gen＞ Maxgen,結(jié)束種群演化,否則轉(zhuǎn)到步驟2.

步驟7多階段配載.

t=t+1,進入下一配載階段,初始化下一階段船艙的剩余容量、每條車道的剩余長度等,轉(zhuǎn)到步驟1.

5 數(shù)值實驗

5.1 小規(guī)模問題與最優(yōu)解的對比

為考察本文提出的解決小規(guī)模問題算法的魯棒性,用 lingo 的求解結(jié)果和本文的算法得出的解相比較.具體算例:航線上有 3 個港口,第 1 個港口有 n=15 候選車輛,每條車道長 L=45,允許最大載重噸 W=68,進行配載的車道條數(shù) k=2;第 2 個港口有 n=10 候選車輛,車道長 L1=35,L2=30,允許最大載重噸分別是 W1=60,W2=45,進行配載的車道條數(shù) k=2;第 3 個港口是末端港口,不進行裝貨.所裝船的車輛種類分別用 1-6 表示,依次按車型大小(重量大小、長度大小)從小到大進行排列.對 n=15,k=2 的小規(guī)模配載問題進行隨機的 30次試驗, 最終結(jié)果和 lingo 最優(yōu) 解相比 較, 如表1所示.

可以看出,用本文的遺傳算法與 lingo 軟件所得到的精確解比較,平均誤差率約為 1.4%.且在近三分之一的情況下,兩者得到的目標函數(shù)值相同,顯示出本算法較好的魯棒性能.

表1 仿真算例的實驗結(jié)果Table1 The experimental results of the simulation examples

5.2 大規(guī)模問題與現(xiàn)實調(diào)度規(guī)則的對比

由于目前尚無這方面的實驗數(shù)據(jù)可以進行直接文獻比較,本文以現(xiàn)場通常采用的實用調(diào)度規(guī)則所產(chǎn)生的調(diào)度方案作為比較對象.具體包括:按先到先服務(wù)原則配載、按裝載盡可能多的車輛數(shù)配載、按待裝車輛重量大小配載和按待裝車輛收費高低配載.

大規(guī)模問題算例設(shè)計如下:滾裝船舶每層甲板車道條數(shù)為 6 條,航線上共?？?4 個港口,第 1 個港口是裝貨港,第 4 個港口是卸貨港,中間兩個是掛靠港,既有車輛裝船也有車輛卸船,且每個可卸貨的港口至少都有一條車道的車輛進行卸載,所以最終分配給某個卸貨港的車道條數(shù)介于1～4條之間.但滾裝船配載還要保證船舶的穩(wěn)性,所以當遇到車道條數(shù)為單數(shù)時,要將單數(shù)車道一分為二,則對于到達某個卸貨港的車輛進行裝船時,同時進行裝載的車道條數(shù)最小是 2 條,最大是 4 條.候選裝船的車輛數(shù)隨機產(chǎn)生,到達的同一類型的車輛的重量也在一定的范圍內(nèi)隨機產(chǎn)生,分別進行 100 次的隨機數(shù)值實驗.

分別對車道數(shù)為 2、4 的大規(guī)模配載問題與實用調(diào)度規(guī)則進行對比,以驗證本文算法的有效性.對比結(jié)果如圖2、圖3 所示.

圖2 300 輛車 2 條車道配載結(jié)果對比Fig.2 The loading results comparison based on 300 vehicles and 2 lanes

圖3 300 輛車 4 條車道配載結(jié)果分析Fig.3 The loading results analysis based on 300 vehicles and 4 lanes

由上述結(jié)果可以看出,本文遺傳算法的求解質(zhì)量明顯優(yōu)于其它常用調(diào)度策略,并且運算速度很快.隨著車道數(shù)的增加,這種優(yōu)越性更加明顯,顯示了良好的實用性及魯棒性,可以有效地解決現(xiàn)實規(guī)模的滾裝船配載優(yōu)化問題.

6 滾裝船舶配載可視化系統(tǒng)實現(xiàn)

6.1 車輛定位的啟發(fā)式規(guī)則

現(xiàn)實中常用的啟發(fā)式規(guī)則有:為保證裝船穩(wěn)性,將到達同一港口的車輛在船艙中左右對稱擺放;最先卸載的車輛盡量擺放在外側(cè),最后卸載的車輛盡量擺放在內(nèi)側(cè);最先卸載的車輛擺放在前,最后卸載的車輛則擺放在后;到達同一港口的車輛安排在同一條車道上;盡量不要拆分分配給同一港口的雙數(shù)車道;如分配給某一港口的車道數(shù)是雙數(shù)n,就左右各 n/2,如果是單數(shù),就將其一分為二;同類車輛排在一起.同一列車道上不同種類車輛的排列順序要兼顧大小車型盡量均衡的原則,防止船舶發(fā)生縱傾;到達同一港口的車輛,在對稱位置上擺放時,車型的擺放順序也是對稱的;當分屬于兩個港口的半條車道組成同一條車道時,車型的擺放順序應(yīng)上下對稱等.

6.2 配載可視化

基于上述規(guī)則,本文采用 Visual Basic 語言開發(fā)了滾裝船配載車輛定位軟件,以實現(xiàn)配載的可視化.通過輸入滾裝船所裝車輛的基本信息(裝貨港、卸貨港、車型、車長、車重、運輸價格等),就可以生成配載方案,如圖 4 所示.其中,車道背景不同代表著其各自不同的卸貨港,矩形圖案不同代表不同的車輛類型.

圖4 展示界面Fig.4 Display interface

同時,也可以針對不同的配載方案、車輛定位,輸出此時滾裝船的橫傾力矩、縱傾力矩以隨時查看,保證船舶的穩(wěn)性,如圖5 所示.進而實現(xiàn)配載可視化.

圖5 力矩輸出界面Fig.5 The torque output interface

7 研究結(jié)論

本文在建立成品車多裝貨港、多卸貨港的多階段配載模型的基礎(chǔ)上,設(shè)計了遺傳算法對其進行求解,并通過仿真算例顯示了模型的有效性及算法的魯棒性.并進一步根據(jù)實用的啟發(fā)式車輛定位規(guī)則,開發(fā)了滾裝船舶配載信息管理系統(tǒng),實現(xiàn)了裝載的過程透明化、智能化,以及車輛在船艙內(nèi)配置的可視化,提高了裝卸效率及準確性,有助于提高滾裝船運輸?shù)陌踩?

進一步研究將集中于動態(tài)配載優(yōu)化方面,即在配載決策時點,待裝運車輛的信息不完全已知情形下的配載優(yōu)化問題.

[1] 靳志宏,蘭輝,郭貝貝,等.基于現(xiàn)實約束的集裝箱配載優(yōu)化及可視化[J].系統(tǒng)工程理論與實踐,2010,30 (9):1722-1728.[JIN Z H,LAN H,GUO B B,et al. Optimization and visualization of the container loading problems with realistic constraints[J]. Systems Engineering-theory & Practice, 2010, 30(9): 1722-1728.]

[2] 郭貝貝,靳志宏,石麗紅,等.現(xiàn)實約束條件下的集裝箱多箱裝載優(yōu)化[J].上海海事大學學報,2009,30 (2):8-13.[GUO B B,JIN Z H,SHI L H,et al. Optimization of multiple container loading under practical constraints[J].Journal of Shanghai Maritime University,2009,30(2):8-13.]

[3] 孫玉昌,龍熙陵. 載車狀態(tài)對滾裝船穩(wěn)性的影響[J]. 航海工程,2004,4:7-9.[SUN Y C,LONG X L. The influence of loading condition on the stability of Ro/ Ro vessels[J].Ship&Ocean Engineering,2004,4: 7-9.]

[4] 李冬梅. 滾裝客船承載車輛的積載、系固及其管理[J]. 中 國 海 事,2008,4:46-49.[LI D M.Stowage, securing and management of vehicles loaded onboard Ro/Ro passenger ships[J].China Maritime Safety, 2008,4:46-49.]

[5] 宋振洪. 客滾船舶車輛的動態(tài)裝載算法[J]. 計算機工 程,2004,30:522-523.[SONG Z H.Dynamic algorithm ofvehicle loading forrolling-ship[J]. Computer Engineering,2004,30:522-523.]

[6] JIA Jun-bo.Investigations of vehicle securing without lashings for Ro-Ro ships[J].J.Mar.Sci.Technol., 2007,12:43-57.

[7] 靳志宏,金燕燕. 滾裝船配載優(yōu)化算法及其軟件化實現(xiàn)[J]. 中國航海,2010,33(2):84-94.[JIN Z H,JIN Y Y.A two-phase heuristic algorithm for ro-ro ship stowage planning[J].Navigation of China,2010,33 (2):84-94.]

Optimization of Ro-Ro Ship Loading for Multiple Ports Based on Realistic Constraints

JIANG Yan-ning1,2,XU Qi1,JIN Yan-yan1,JIN Zhi-hong1
(1.College of Transportation Management,Dalian Maritime University,Dalian 116026,Liaoning,China; 2.Department of Transportation Technology Division,Ministry of Transport,Beijing 100736,China)

Based on the analysis of characteristics of ro-ro ship loading,the ro-ro ship loading problem for multiple ports is formulated as a mixed integer programming,considering realistic restrictions such as the stability of vessels,the efficiency of loading and the income of voyage.With the characteristics of multistage,multi-dimensional restrictions,multi-bag combinational optimization,a genetic algorithm(GA)is developed for solving the proposed model.As to the small-scale problems,the GA solved results are quite near to the exact solutions only by 1.4%;as to the large-scale problems,results from the GA are obviously better than those derived from practical dispatching rules,thus the robustness of the proposed algorithm is verified.Furthermore,a MIS based on Visual Basic is developed to realize the visualization of both loading process and loading patterns,which can provide some assistance for real-time decision-making.

integrated transportation; ro-ro ship loading; multiple loading/unloading ports; decision visualization

1009-6744(2014)01-0117-07

U695.2+93

A

2013-09-02

2013-10-30錄用日期:2013-11-12

國家自然科學基金(71172108,71302044);教育部博士點基金資助項目(20122125110009).

姜彥寧(1979-),女,遼寧丹東人,博士生.*通訊作者:jinzhihong@dlmu.edu.cn