現實約束下的多掛靠港滾裝船舶配載優化姜彥寧;徐奇;金燕燕;靳志宏【摘要】在分析滾裝船舶配載特點的基礎上，考慮了船舶穩性、配載效率以及航次收益等現實約束，針對多掛靠港的滾裝汽車運輸新模式下的配載優化問題進行建模,并基于該問題多階段、多維約束、多背包組合優化的特點，開發了遺傳算法對所構建模型進行求解.對于小規模數值算例實驗，運用所設計遺傳算法的求解結果與lingo軟件所得到的精確解比較，平均誤差率約為1.4%;對于大規模仿真算例，遺傳算法的求解質量則明顯優于現實調度策略,顯示出本算法較好的魯棒性.在此基礎上開發了基于VB的配載信息系統，實現了配載過程及配載方案的可視化，為實時配載決策奠定了基礎.【期刊名稱】《交通運輸系統工程與信息》【年(卷)，期】2014(014)001【總頁數】7頁(P117-123)【關鍵詞】綜合交通運輸;滾裝船配載;多掛靠港;決策可視化【作者】姜彥寧;徐奇;金燕燕;靳志宏【作者單位】大連海事大學交通運輸管理學院，遼寧大連116026;交通運輸部科技司，北京100736;大連海事大學交通運輸管理學院，遼寧大連116026;大連海事大學交通運輸管理學院，遼寧大連116026;大連海事大學交通運輸管理學院，遼寧大連116026【正文語種】中文【中圖分類】U695.2+93滾裝船配載要在保證船舶航行安全的前提下，進行裝船車輛的合理選擇和安排，是一個典型的離散組合優化問題.隨著船舶大型化趨勢的加劇,滾裝船配載優化問題(ro-roshiploadingproblem,RRSLP)已發展為大規模、高復雜度的組合優化問題同時，伴隨著這種船舶大型化的趨勢，滾裝船舶的運輸也改變了原來的兩港間的直航(無中途停靠港)運輸模式，出現了多掛靠港的滾裝運輸新模式.據調查，目前并無針對這種新滾裝運輸模式的配載優化的相關文獻.國內夕卜學者對集裝箱船配載優化進行了比較深入的研究［1,2］,而對滾裝船舶配載優化的研究還不是十分深入.孫玉昌等［3］對船載車輛橫搖及車輛停放時滾裝船穩性問題進行核算,并提出了合理化建議.李冬梅［4］指出滾裝船在積載系固方面存在的問題,并給出了車輛的積載和系固方面的要求.宋振洪［5］從保證船舶穩性的角度出發，通過最小化船舶平衡力矩來選擇裝船車輛.Jia［6］探討了如何使滾裝船上的車輛不需系固也可保證安全，以提高停放車輛的數量.靳志宏與金燕燕［7］考慮了船舶穩性、配載效率及航次收益等現實約束與配載目標，對滾裝船配載優化問題進行建模，開發了以貪婪算法為基礎的兩階段啟發式算法.目前該研究僅限于單一裝貨港與單一卸貨港的直達運輸模式,沒有考慮多裝貨港和卸貨港，即有中途掛靠港的情形.本文在參考文獻［7］的基礎上,將兩港間的直航模式擴展到多掛靠港的滾裝運輸新模式；設計實用優化算法以求解所構建的船舶配載優化模型，開發配載管理信息系統，進而實現智能與可視化配載.2.1問題歸結本文研究的船舶配載是多類型成品車的多裝貨港多卸貨港的多階段配載問題,根據裝貨港的不同劃分成不同階段,對每個階段進行配載.滾裝船配載優化問題可歸結為特殊的離散優化的背包問題.其特殊性體現在：多階段配載問題，現行研究針對的是兩港間的直航(無中途停靠港)運輸模式,本文將其擴展到多掛靠港的滾裝運輸新模式；多維約束問題，如載重量約束、空間尺寸約束、船舶穩性約束等；⑶多背包問題，即同時進行配載的背包數(各層甲板、以及每層甲板的車道的條數)是多個.綜上，該優化問題可以歸結為多階段、多維約束、多背包組合優化問題.2.2現實約束為了增強配載方案的實用性，本文考慮了如下現實約束：所有待裝船到達某一個卸貨港的車輛所占用的車道長度，不能超過分配給這個卸貨港的車道長度；所有裝載到同一條車道上的車輛總長度(包括車輛之間的安全距離)不能超過這條車道的固定長度；裝載車輛的總重量不能超過船舶允許的最大載重量；為保證船舶整體航行穩定性，裝載方案必須保證船舶橫傾力矩和縱傾力矩位于允許的范圍內.3.1前提與假設條件將船頭至船尾方向的中心線看成船舶的縱軸y,船舶從左到右的方向看成船舶的橫軸乂俯視看，船頭是上方，船尾是下方，船舶的左面是左方佑面是右方.船舶的坐標軸示意如圖1所示.第一個裝貨港只裝不卸,最后一個卸貨港只卸不裝.⑶甲板的形狀是矩形.⑷分配給航線上各中途卸貨港的車道條數是整數條.3.2符號說明Z——完成船舶裝載車輛總的航次收益；I——待裝車輛總數；J——航線上掛靠港數量；W——船艙允許的最大載重噸；t——第t個裝車港，即配載的階段數,如t=1就是第一個裝車港和第一個配載階段,以此類推；T——配載階段數；Wt-1——前一個裝貨港船艙已裝車輛的總重量減去在t階段卸船的車輛的重量；K——每層甲板車道的總數；Totalj——航線上到j港卸貨的車輛總數；L——每條車道的固有長度；k 車道的索引,k=1,2,...,K;i 車輛的索引；j——目的港的索引；vij——車輛i到港口j的運價；Kj——分配給j港口的車道數；wi 車輛i的自重；li 車輛i的長度；Lj——分配給j港口的車道長度；(hqx1,hqx2) 船艙沿x軸上的橫傾力矩安全范圍要求(zqy1,zqy2)——船艙沿y軸上的縱傾力矩安全范圍要求；——配載階段t到達目的地港口j的車輛i配載在車道k上；(xi,yi)——車輛i在船艙中的重心坐標；(Luxi,Luyi):車輛i在船艙內的左下角坐標;(Rdxi,Rdyi):車輛i在船艙內的右上角坐標.3.3優化模型目標函數約束條件其中式(1)為最大化滾裝船所裝載車輛的總航次收益;式(2)確保在第t個裝車港裝車時船艙所裝載車輛的總噸數不超過此時刻船艙容許的最大載重噸;式(3)保證在第t階段所有到j港口的裝船車輛總長度不超過分配給第j港口車道的總長度;式(4)確保每條車道上所裝載的車輛總長度不超過車道的固有長度;式(5)、式(6)確保船艙中所裝的車輛的總橫傾力矩、總縱傾力矩不超過給定的范圍;式(7)、式(8)用于計算車輛i在船艙中的橫坐標和縱坐標;式(9)、式(10)計算分配給到達j港的車道數量和總長度;式(11)確保車輛i不能同時重復裝載.針對多階段、多維約束、多背包組合優化問題的特點，本文設計了針對該特殊背包問題的染色體編碼方法:將待求解的變量X的每一維度表示成長度為待裝車輛總數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=j+1,此時的x[n]=2意味著i=3,j=1,k=2,t=2.在此基礎上,設計的遺傳算法流程如下.步驟1初始化.步驟1-1讀入相關信息，如所裝車輛的重量weight[j]、長度length[j]、收費profit。]和車道的最大載重量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間的均勻分布整數函數.若不滿足模型的約束條件，則由步驟1-2重新生成新的染色體個體chrom;若產生的染色體可行，則將其作為種群的一個個體，經過有限次抽樣后，得到popsize個可行的染色體chrom,形成新的種群.步驟1-3置種群的代數gen=0.步驟2計算個體適應度及統計種群適應度.步驟2-1計算種群中個體適應度：步驟2-2基于步驟2-1,計算種群的總體適應度"并且通過排序統計出種群中的最大、最小適應度的染色體個體.步驟3選擇操作.步驟3-1生成隨機數rand_Number（0<rand_Number<1）.步驟3-2按照賭輪法選擇個體.步驟3-3重復兩次操作步驟3-1、步驟3-2,生成兩個個體作為交叉操作的父代.步驟4交叉操作.步驟4-1生成［0,1］的隨機數pp若pp<pc（pc為交叉概率），則進行步驟4-2;否則將該父代保留為下一代的兩個個體.步驟4-2隨機生成［0,lchrom-1］的整數作為交叉點,對兩個父代個體交叉生成兩個新個體.步驟4-3重復pop_size/2次步驟4-1、步驟4-2便可生成pop_size個個體組成新的種群.步驟5變異操作.步驟5-1生成［0,1］的隨機數pp,若pp<pm（pm為變異概率），進行步驟5-2變異操作,否則不變異.步驟5-2若原基因為0,則新基因變異為1；若原基因為1,則新基因變異為2......源基因為n,則新基因變異為0.步驟6演化.步驟6-1按步驟2的方法計算新種群的適應度情況，并找出新種群中適應度最大和最小的個體.步驟6-2若舊種群的最大個體適應度優于新種群的最大個體適應度,將舊種群中適應度最大的個體代替新種群中適應度最小的個體，否則進行步驟6-3.步驟6-3種群的代數gen=gen+1,若gen>Maxgen,結束種群演化，否則轉到步驟2.步驟7多階段配載.t=t+1,進入下一配載階段，初始化下一階段船艙的剩余容量、每條車道的剩余長度等，轉到步驟1.5.1小規模問題與最優解的對比為考察本文提出的解決小規模問題算法的魯棒性，用lingo的求解結果和本文的算法得出的解相比較.具體算例:航線上有3個港口，第1個港口有n=15候選車輛，每條車道長L=45,允許最大載重噸W=68,進行配載的車道條數k=2;第2個港口有n=10候選車輛,車道長L1=35,L2=30,允許最大載重噸分別是W1=60,W2=45，進行配載的車道條數k=2;第3個港口是末端港口，不進行裝貨.所裝船的車輛種類分別用1-6表示，依次按車型大小（重量大小、長度大小）從小到大進行排列.對n=15,k=2的小規模配載問題進行隨機的30次試驗,最終結果和lingo最優解相比較,如表1所示.可以看出,用本文的遺傳算法與lingo軟件所得到的精確解比較，平均誤差率約為1.4%.且在近三分之一的情況下，兩者得到的目標函數值相同,顯示出本算法較好的魯棒性能.5.2大規模問題與現實調度規則的對比由于目前尚無這方面的實驗數據可以進行直接文獻比較，本文以現場通常采用的實用調度規則所產生的調度方案作為比較對象.具體包括:按先到先服務原則配載、按裝載盡可能多的車輛數配載、按待裝車輛重量大小配載和按待裝車輛收費高低配載.大規模問題算例設計如下:滾裝船舶每層甲板車道條數為6條，航線上共停靠4個港口，第1個港口是裝貨港，第4個港口是卸貨港，中間兩個是掛靠港，既有車輛裝船也有車輛卸船，且每個可卸貨的港口至少都有一條車道的車輛進行卸載,所以最終分配給某個卸貨港的車道條數介于1~4條之間.但滾裝船配載還要保證船舶的穩性，所以當遇到車道條數為單數時，要將單數車道一分為二，則對于到達某個卸貨港的車輛進行裝船時，同時進行裝載的車道條數最小是2條，最大是4條.候選裝船的車輛數隨機產生，到達的同一類型的車輛的重量也在一定的范圍內隨機產生，分別進行100次的隨機數值實驗.分別對車道數為2、4的大規模配載問題與實用調度規則進行對比，以驗證本文算法的有效性.對比結果如圖2、圖3所示.由上述結果可以看出，本文遺傳算法的求解質量明顯優于其它常用調度策略，并且運算速度很快.隨著車道數的增加，這種優越性更加明顯顯示了良好的實用性及魯棒性,可以有效地解決現實規模的滾裝船配載優化問題.6.1車輛定位的啟發式規則上述優化模型與算法給出了決策變量,即在每一個配載階段t（也即第t個裝貨港口）給出了到達每一個目的地港口j的車輛i配載在車道k上，但卻無法給出配載所要求的進一步的在每一車道上的具體配載位置.因此，需要依據一定的啟發式規則，分配每一輛車在每一條所分配車道的具體位置.現實中常用的啟發式規則有:為保證裝船穩性，將到達同一港口的車輛在船艙中左右對稱擺放;最先卸載的車輛盡量擺放在外側,最后卸載的車輛盡量擺放在內側;最先卸載的車輛擺放在前，最后卸載的車輛則擺放在后;到達同一港口的車輛安排在同一條車道上;盡量不要拆分分配給同一港口的雙數車道;如分配給某一港口的車道數是雙數n,就左右各n/2,如果是單數,就將其一分為二同類車輛排在一起.同一列車道上不同種類車輛的排列順序要兼顧大小車型盡量均衡的原則，防止船舶發生縱傾到達同一港口的車輛，在對稱位置上擺放時，車型的擺放順序也是對稱的;當分屬于兩個港口的半條車道組成同一條車道時，車型的擺放順序應上下對稱等.6.2配載可視化基于上述規則,本文采用VisualBasic語言開發了滾裝船配載車輛定位軟件,以實現配載的可視化.通過輸入滾裝船所裝車輛的基本信息(裝貨港、卸貨港、車型、車長、車重、運輸價格等),就可以生成配載方案，如圖4所示.其中，車道背景不同代表著其各自不同的卸貨港，矩形圖案不同代表不同的車輛類型.同時,也可以針對不同的配載方案、車輛定位,輸出此時滾裝船的橫傾力矩、縱傾力矩以隨時查看，保證船舶的穩性，如圖5所示.進而實現配載可視化.本文在建立成品車多裝貨港、多卸貨港的多階段配載模型的基礎上，設計了遺傳算法對其進行求解，并通過仿真算例顯示了模型的有效性及算法的魯棒性.并進一步根據實用的啟發式車輛定位規則，開發了滾裝船舶配載信息管理系統，實現了裝載的過程透明化、智能化，以及車輛在船艙內配置的可視化，提高了裝卸效率及準確性,有助于提高滾裝船運輸的安全性.進一步研究將集中于動態配載優化方面，即在配載決策時點，待裝運車輛的信息不完全已知情形下的配載優化問題.【相關文獻】靳志宏，蘭輝，郭貝貝，等.基于現實約束的集裝箱配載優化及可視化[J].系統工程理論與實踐,2010,30(9):1722-1728.[JINZH,LANH,GUOBB,etal.Optimizationandvisualizationofthecontainerloadingproblemswithrealisticconstraints[J].SystemsEngineering-theory&Practice,2010,30(9):1722-1728.]郭貝貝，靳志宏,石麗紅，等.現實約束條件下的集裝箱多箱裝載優化[J].上海海事大學學報,2009,30:8-13.[GUOBB,JINZH,SHILH,etal.Optimizationofmultiplecontainerloadingunderpracticalconstraints[J].JournalofShanghaiMaritimeUniversity,2009,30(2):8-13.]孫玉昌,龍熙陵.載車狀態對滾裝船穩性的影響[J].航海工程,2004,4:7-9.[SUNYC,LONGXL.Theinf