基于數(shù)學(xué)規(guī)劃方法的集裝箱船舶自動配載研究進(jìn)展*

牛王強(qiáng) 褚建新 張耀周 徐 濤

(上海海事大學(xué)航運(yùn)技術(shù)與控制工程交通行業(yè)重點(diǎn)實(shí)驗(yàn)室1) 上海 201306) (上海振華重工(集團(tuán))股份有限公司陸上重工設(shè)計(jì)研究院2) 上海 200125)

基于數(shù)學(xué)規(guī)劃方法的集裝箱船舶自動配載研究進(jìn)展*

牛王強(qiáng)1)褚建新1)張耀周2)徐 濤2)

(上海海事大學(xué)航運(yùn)技術(shù)與控制工程交通行業(yè)重點(diǎn)實(shí)驗(yàn)室1)上海 201306) (上海振華重工(集團(tuán))股份有限公司陸上重工設(shè)計(jì)研究院2)上海 200125)

給出了數(shù)學(xué)規(guī)劃方法處理配載問題的一般思路，從船方和碼頭方兩個(gè)角度給出了自動配載問題近十多年的研究進(jìn)展，指出大容量集裝箱船舶和新型裝卸設(shè)備的出現(xiàn)，以及實(shí)時(shí)配載策略是自動配載研究的下一個(gè)挑戰(zhàn).

集裝箱船；船舶配載；數(shù)學(xué)規(guī)劃；貝位選擇；貝內(nèi)排箱

0 引 言

集裝箱船舶配載是指確定集裝箱在船艙的最優(yōu)位置的過程[1-2].集裝箱碼頭方對配載的要求是，在滿足船方要求的基礎(chǔ)上，盡可能提高裝卸速度，提高碼頭的利用效率，從而提高碼頭的經(jīng)濟(jì)效益[3-7].

目前，文獻(xiàn)中的集裝箱船舶自動配載方法有5類：仿真方法(simulation based upon probability)、啟發(fā)式方法(heuristic driven)、數(shù)學(xué)規(guī)劃模型(mathematical programming approach)，專家系統(tǒng)(rule-based expert system)、決策支持系統(tǒng)(decision support systems)[8-10].集裝箱船舶的快速自動配載有助于減輕配載員的工作量，有助于提高船方和碼頭方的經(jīng)濟(jì)效益.

數(shù)學(xué)規(guī)劃方法的特點(diǎn)是模型準(zhǔn)確度高，可擴(kuò)展性好[11]，是目前最重要的自動配載方法.數(shù)學(xué)規(guī)劃方法處理配載問題的一般思路是，首先建立配載問題的整數(shù)規(guī)劃模型，然后設(shè)計(jì)適當(dāng)?shù)膯l(fā)式算法獲得配載的次優(yōu)解.配載的各類業(yè)務(wù)規(guī)則可以由目標(biāo)函數(shù)反映，也可以融入約束條件，也可以嵌入在啟發(fā)式搜索算法中.為了行文簡潔，以下給出各專業(yè)詞匯的英文簡寫定義：整數(shù)規(guī)劃，Integer program (IP)；0-1規(guī)劃，binary program (BIP)；混合整數(shù)規(guī)劃,mixed integer program (MIP)；非線性整數(shù)規(guī)劃,nonlinear integer program (NIP)；約束規(guī)劃，constraint programming (CP)；貝位選擇，group-to-bay (G2B)；貝內(nèi)排箱，container-to-slot (C2S).

1 船方的優(yōu)化配載

近十多年來，船方自動配載問題的一個(gè)里程碑工作是1999年英國學(xué)者Wilson和Roach提出的兩階段分塊求解策略，該工作為后續(xù)的研究奠定了基調(diào).

1999年，英國Glamorgan大學(xué)數(shù)學(xué)與計(jì)算系的Wilson和Roach[12]提出將船舶自動配載問題分為兩階段完成.他們對配載員的人工配載過程進(jìn)行了分析.指出，配載員首先利用框架性的General Arrangement Document文件完成配載的2個(gè)目標(biāo)：(1)每個(gè)目的港貨物所占的貨物空間最少；(2)每個(gè)目的港同時(shí)工作的岸橋數(shù)量最多.再根據(jù)信息更詳細(xì)的Outline Plan文件完成配載的另外3個(gè)目標(biāo)：(3)艙蓋移動的次數(shù)最少；(4)倒箱量最少(over-stows)；(5)集裝箱所占的貨物塊最少.這一階段，配載員不關(guān)注每個(gè)具體集裝箱在船艙的具體位置，而是關(guān)注集裝箱的總體分布，即將同一目的港同一類型的一群集裝箱配置到某塊船舶箱位，從而完成封面船圖.接著配載員根據(jù)最詳細(xì)的bay plan文件，完成配載的3個(gè)目標(biāo)：(6)倒箱量最少(re-handles)；(7)重下輕上；(8)不同目的港的集裝箱放在一個(gè)堆垛中的數(shù)量最少，給每個(gè)集裝箱指定具體箱位，生成各個(gè)船貝(bay)的箱位圖.

結(jié)合前人有關(guān)集裝箱成塊配載的工作，以及對配載員配載過程的分析，Wilson和Roach提出將船舶配載問題分為兩階段完成.第一階段解決艙塊選擇(group-to-block)子問題，完成集裝箱在船上的總體布置.他們將集裝箱按照目的港、類型等分成不同的群(group)，也將船貝劃分成塊(block)，按照配載員的優(yōu)化目標(biāo)(1)～(5)，將集裝箱群配置到船貝分塊.第二階段解決貝內(nèi)排箱(C2S)子問題，為每個(gè)集裝箱指定具體箱位.該階段完成配載員的優(yōu)化目標(biāo)(6)～(8)，給每個(gè)貨艙塊內(nèi)的集裝箱指定具體箱位.

研究表明，第一階段的分塊思想，使得配載可行解個(gè)數(shù)由幾千個(gè)下降到100以內(nèi)，且保存著配載問題的固有特性.同時(shí)，第二階段可行解的搜索空間也減少了許多.英國學(xué)者的分塊思想以及2階段策略奠定了后來研究的基調(diào)，后續(xù)的研究幾乎都受到他們工作的影響，不同之處主要是塊的大小、各階段的求解算法、兩階段是同步求解還是順序求解、船舶穩(wěn)性的加入等.

文獻(xiàn)中，階段一因貨艙塊大小的選取不同，有艙塊選擇(group-to-block)、船貝分塊選擇(group-to-hold[13])、貝位選擇(group-to-bay[14])等，相應(yīng)的階段二的container-to-slot問題是艙塊排箱、船貝分塊排箱、貝位排箱等提法.目前，中文文獻(xiàn)將第一階段稱為貝位選擇問題，第二階段稱為貝位排箱問題[15-16].將第二階段命名為貝內(nèi)排箱更符合Wilson和Roach的思想.

2002年，韓國科學(xué)技術(shù)院的Kang和Kim基于兩階段策略研究了船舶自動配載問題.2002年，以色列理工學(xué)院的Dubrovsky等研究了貝內(nèi)排箱問題[17].2005年，大連理工大學(xué)張維英等研究了集裝箱船舶的自動配載問題[18]，采用基于二叉搜索樹的啟發(fā)式裝箱算法求解.2007年和2011年，她們對混合目的港和單一目的港的貝內(nèi)排箱問題也進(jìn)行了研究.

2011～2012年，丹麥哥本哈根大學(xué)的Delgado等基于2階段策略研究了集裝箱船舶的快速自動配載問題.對階段一的貝位選擇問題，考慮了船舶的穩(wěn)性約束.對階段二的貝內(nèi)排箱問題，對比了BIP和CP 2種模型的求解結(jié)果.

表1給出了船方的自動配載方法綜合比較.預(yù)配圖的計(jì)算都采用了Wilson和Roach的二階段分塊策略，對9 984TEU大船的配載，最快的計(jì)算時(shí)間小于6 min，符合船方期望的10 min配載時(shí)間要求.船方自動配載的首要目標(biāo)是全航線的翻箱量少，船舶的穩(wěn)性要求一般由約束條件給出，或者融合在模型的求解算法中.求解算法都是啟發(fā)式算法，有分支限定法、禁忌搜索、基因算法等.

Wilson和Roach的二階段分塊求解策略是對配載員人工配載過程的模擬，對人工配載過程的進(jìn)一步挖掘與數(shù)學(xué)抽象是船舶自動配載的一個(gè)重要研究方向.

表1 船方的自動配載方法比較

2 碼頭方的優(yōu)化配載

碼頭方的船舶配載問題復(fù)雜度與船方的配載問題復(fù)雜度是相當(dāng)?shù)?，不同之處是碼頭方更關(guān)注的是堆場翻箱量少，裝卸設(shè)備利用率高等.Wilson和Roach的二階段分塊求解預(yù)配圖策略對碼頭方實(shí)配圖的生成仍然有著重要的借鑒作用.

2001年，德國漢堡港口及倉儲物流公司steenken等研究了給定船舶的預(yù)配圖后，堆場跨運(yùn)車的實(shí)時(shí)調(diào)度問題[19].他們將集裝箱進(jìn)行分批處理，每一批20～60箱，對每批箱子進(jìn)行1 min內(nèi)實(shí)時(shí)優(yōu)化.出現(xiàn)4類實(shí)時(shí)性影響因素時(shí)，停止當(dāng)前的集裝箱調(diào)度算法，對即將調(diào)度的20～30箱實(shí)時(shí)優(yōu)化，其余出口箱進(jìn)行全局優(yōu)化，完成集裝箱調(diào)度的實(shí)時(shí)動態(tài)調(diào)整.

2004年，意大利Genova大學(xué)的Ambrosino等研究了主貝計(jì)劃問題MBPP(master bay plan problem)，該問題實(shí)質(zhì)是考慮了裝載時(shí)間的船舶配載問題[20].他們采用了單階段策略進(jìn)行求解.但是，在設(shè)計(jì)啟發(fā)式搜索算法時(shí)，仍然采用了先貝位選擇，壓縮解空間，然后貝內(nèi)排箱的思想.

2004年，韓國釜山國立大學(xué)的Kim等研究了場橋碼頭出口箱的裝載順序問題[21].他們提出了堆場箱簇(yard-clusters)的概念.同尺寸(TEU，F(xiàn)EU)、同目的港、同類型(干箱、冷藏箱、空箱、特種箱)、同堆場貝的集裝箱構(gòu)成一個(gè)堆場箱簇.采用兩階段策略求解，第一階段的搜索確定堆場箱簇的裝載順序.第二階段的搜索確定每個(gè)堆場箱簇內(nèi)集裝箱的裝載順序.

2006年，Ambrosino等又提出了主貝計(jì)劃問題的三階段求解算法[22].第一階段進(jìn)行貝位選舉.第二階段完成貝內(nèi)排箱.第三階段，交換船貝，使得配載結(jié)果滿足船舶的穩(wěn)性要求.2006年，西班牙Pompeu Fabra大學(xué)的alvarez研究了正面吊碼頭集裝箱船舶的自動配載問題[23].2006年，日本神戶大學(xué)的Imai等研究了場橋碼頭集裝箱船舶的自動配載問題[24].

2011年，中國海洋大學(xué)楊杰敏等研究了場橋碼頭集裝箱船舶的自動配載問題.提出了船舶配載的3層規(guī)劃方法.第l層是作業(yè)路分配.即確定合理的橋吊作業(yè)計(jì)劃及每個(gè)船貝的作業(yè)時(shí)間表，目標(biāo)是最短的裝卸船完工時(shí)間.第2層是堆場動態(tài)取箱.即確定船貝分塊從堆場上哪些貝取箱，目標(biāo)是最佳的堆場作業(yè)計(jì)劃.第3層是貝內(nèi)排箱.

2014年，意大利Calabria大學(xué)的Monaco等研究了跨運(yùn)車碼頭集裝箱船舶的自動配載問題.提出用兩步啟發(fā)式算法來進(jìn)行模型的求解.第一步進(jìn)行初始可行解的構(gòu)造，第二步在初始可行解的鄰域進(jìn)行優(yōu)化搜索.

表2給出了碼頭方的自動配載方法綜合比較.對于500 TEU的配載，計(jì)算時(shí)間是1 min，目前尚沒有萬TEU大船的配載報(bào)道.碼頭方的船舶配載模型、求解方法與船方的船舶配載問題是類似的，求解算法也全是啟發(fā)式算法.碼頭方自動配載的首要目標(biāo)是堆場翻箱量少，裝卸設(shè)備利用率高(岸橋、場橋的工作時(shí)間少，行駛距離短等).

表2 碼頭方的自動配載方法比較

3 結(jié) 束 語

目前，營運(yùn)中的大型集裝箱船容量已經(jīng)達(dá)到14 770 TEU，而建造中的集裝箱船容量已經(jīng)超過18 000 TEU.2萬TEU以上大型集裝箱船舶的出現(xiàn)，進(jìn)一步增加了配載問題的解空間，如何進(jìn)行船舶的快速自動配載仍需要不斷研究.雙小車雙起升岸橋[25]、AGV伴侶、立體裝卸碼頭等新型集裝箱裝卸設(shè)備的出現(xiàn)，對碼頭方的船舶配載提出了新的挑戰(zhàn).新裝卸設(shè)備下的船舶自動配載方法也需要進(jìn)一步研究.

目前，僅有德國學(xué)者有關(guān)堆場跨運(yùn)車的實(shí)時(shí)調(diào)度策略研究.在裝船過程中，當(dāng)岸橋、場橋、AGV等裝卸設(shè)備故障時(shí)，或者集裝箱故障時(shí)，優(yōu)化的實(shí)時(shí)自動配載策略也需要進(jìn)一步研究.

[1]MONACO M F, SAMMARRA M, SORRENTINO G. The terminal-oriented ship stowage planning problem[J]. European Journal of Operational Research, 2014,239(1):256-265.

[2]楊杰敏,丁香乾,郭保琪,等.大型港口集裝箱船舶智能配載的集成算法研究[J].中國海洋大學(xué)學(xué)報(bào)：自然科學(xué)版,2011(10):121-127.

[3]沈繼平.集裝箱碼頭配載業(yè)務(wù)初探[J].集裝箱化,2007(1):9-13.

[4]衛(wèi)家駿.集裝箱船智能配載研究[D].大連:大連海事大學(xué),2012.

[5]張維英,林 焰,紀(jì)卓尚.集裝箱船全航線bay位排箱優(yōu)化模型[J].上海交通大學(xué)學(xué)報(bào),2007(2):199-204.

[6]STEENKEN D, VOB S, STAHLBOCK R. Container terminal operation and operations research-a classification and literature review[J]. OR Spectrum, 2004,26(1):3-49.

[7]楊杰敏.基于作業(yè)資源優(yōu)化調(diào)配的集裝箱碼頭智能配載關(guān)鍵技術(shù)研究[D].青島:中國海洋大學(xué),2011.

[8]WILSON I D, ROACH P A. Container stowage planning: a methodology for generating computerised solutions[J]. Journal of the Operational Research Society, 2000,51(11):1248-1255.

[9]張維英.集裝箱船全航線配載智能優(yōu)化研究[D].大連:大連理工大學(xué),2005.

[10]張維英,林 焰,紀(jì)卓尚,等.Review of containership stowage plans for full routes[J]. 船舶與海洋工程學(xué)報(bào)：英文版,2008(4):278-285.

[11]PACINO D, DELGADO A, JENSEN R M, et al. Fast generation of near-optimal plans for eco-efficient stowage of large container vessels[C]. In: Bose JW, Hu H, Jahn C, Shi X, Stahlbock R, Vob S, editors. Computational logistics: Springer Berlin Heidelberg, 2011：286-301.

[12]WILSON I D, ROACH P A. Principles of combinatorial optimization applied to container-ship stowage planning[J]. Journal of Heuristics, 1999,5(4):403-418.

[13]KANG J G, KIM Y D. Stowage planning in maritime container transportation[J]. Journal of the Operational Research Society, 2002,53(4):415-426.

[14]DELGADO A, JENSEN R M, Janstrup K, et al. A constraint programming model for fast optimal stowage of container vessel bays[J]. European Journal of Operational Research, 2012,220(1):251-261.

[15]張維英,林 焰,紀(jì)卓尚,等.基于指派問題的bay位排箱優(yōu)化模型與算法[J].大連理工大學(xué)學(xué)報(bào),2011(1):61-67.

[16]朱明華.多工況集裝箱船配載與堆場翻箱優(yōu)化研究[D].上海:上海交通大學(xué),2011.

[17]DUBROVSKY O, LEVITIN G, PENN M. A genetic algorithm with a compact solution encoding for the container ship stowage problem[J]. Journal of Heuristics, 2002,8(6):585-599.

[18]張維英,林 焰,紀(jì)卓尚,等.Model and algorithm for container ship stowage planning based on bin-packing problem[J].船舶與海洋工程學(xué)報(bào)：英文版,2005(3):30-36.

[19]STEENKEN D, WINTER T, ZIMMERMANN U. Stowage and transport optimization in ship planning[G]. Grotschel M, Krumke S O, Rambau J. Online Optimization of Large Scale Systems: Springer Berlin Heidelberg, 2001：731-745.

[20]AMBROSINO D, SCIOMACHEN A, TANFANI E. Stowing a containership: The master bay plan problem[J]. Transportation Research Part A: Policy and Practice, 2004,38(2):81-99.

[21]KIM K, KANG J, RYU K. A beam search algorithm for the load sequencing of outbound containers in port container terminals[J]. OR Spectrum, 2004,26(1):93-116.

[22]AMBROSINO D, SCIOMACHEN A, TANFANI E. A decomposition heuristics for the container ship stowage problem[J]. Journal of Heuristics, 2006,12(3):211-233.

[23]ALVAREZ J. A heuristic for vessel planning in a reach stacker terminal[J]. Journal of Maritime Research, 2006,3(1):3-16.

[24]IMAI A, SASAKI K, NISHIMURA E, et al. Multi-objective simultaneous stowage and load planning for a container ship with container rehandle in yard stacks[J]. European Journal of Operational Research, 2006,171(2):373-389.

[25]STAHLBOCK R, VOB S. Operations research at container terminals: a literature update[J]. OR Spectrum, 2008,30(1):1-52.

Review of Container Ship Automatic Stowage Based on Mathematical Programming Approaches

NIU Wangqiang1)CHU Jianxin1)ZHANG Yaozhou2)XU Tao2)

(KeyLaboratoryofMarineTechnologyandControlEngineering，MinistryofCommunications，ShanghaiMaritimeUniversity，Shanghai201306,China)1)(OnshoreHeavyIndustriesR&DInstitute,ShanghaiZhenhuaHeavyIndustryCo.,Ltd,Shanghai200125,China)2)

Mathematical programming approaches are the most important methods for container ship automatic stowage problem. First, the general idea is given to show how to deal with container stowage problem by a mathematical programming method; then works of automatic stowage problem in recent ten years are reviewed from the point of view of shipping lines and ports; finally, two future challenges of automatic stowage problem are pointed out, one is the emergence of super-sized container ship and novel loading and unloading equipments, and the other is real time stowage strategies.

container ship; ship stowage; mathematical programming; group-to-bay; container-to-slot

2015-01-28

*國家發(fā)改委發(fā)改辦高技術(shù)項(xiàng)目(批準(zhǔn)號：[2013]2519號)、2013年度上海市戰(zhàn)略性新興產(chǎn)業(yè)重點(diǎn)項(xiàng)目資助

U695.22

10.3963/j.issn.2095-3844.2015.03.015

牛王強(qiáng)(1977- )：男，博士，講師，主要研究領(lǐng)域?yàn)榇啊⒏劭谧詣踊c網(wǎng)絡(luò)控制