宓為建,張曉華,秦 曌,田 婷

(上海海事大學(xué)物流工程學(xué)院,上海201306)

?

集裝箱碼頭裝船貝內(nèi)發(fā)箱順序決策

宓為建,張曉華,秦 曌,田 婷

(上海海事大學(xué)物流工程學(xué)院,上海201306)

隨著世界集裝箱海運量的不斷增加及集裝箱船舶的日益大型化,集裝箱裝卸作業(yè)的穩(wěn)定高效已成為港口經(jīng)營者關(guān)注的重點,所以在裝船作業(yè)中如何通過優(yōu)化發(fā)箱順序決策提高裝船效率也變得尤為重要.針對集裝箱碼頭裝船貝內(nèi)發(fā)箱順序的決策問題,考慮船舶大型化對于防懸空約束、分艙蓋板約束,以翻箱次數(shù)最少、移機次數(shù)最少和轉(zhuǎn)場次數(shù)最少為目標(biāo),建立集裝箱裝船貝內(nèi)發(fā)箱順序的決策模型.然后設(shè)計模型算例,通過對于算例結(jié)果的分析驗證模型的有效性.相關(guān)思路及研究方法對于集裝箱碼頭裝船作業(yè)時的貝內(nèi)發(fā)箱順序決策具有借鑒意義,同時,模型的構(gòu)建方法對于研究同類基于空間布局的組合優(yōu)化問題具有一定借鑒意義.

集裝箱碼頭; 發(fā)箱順序; 分艙蓋板; 移機轉(zhuǎn)場

隨著世界集裝箱海運量的不斷增長及集裝箱船舶的日益大型化,集裝箱裝卸作業(yè)的穩(wěn)定高效已成為港口經(jīng)營者關(guān)注的重點.提高碼頭通過能力、降低碼頭能耗、提高船舶裝卸效率,是集裝箱碼頭未來集裝箱碼頭發(fā)展的必然趨勢.在集裝箱裝船作業(yè)中,如何提高裝船作業(yè)效率一直都是港口企業(yè)所追求的.合理的發(fā)箱順序,可以提高堆場場橋和碼頭前沿岸吊的作業(yè)效率,減少非工作時間,從而減少裝船作業(yè)時間和船舶在港停泊時間,避免造成船公司和港口時間上的浪費,所以通過優(yōu)化發(fā)箱順序達(dá)到提高裝船作業(yè)效率的目的是具有現(xiàn)實意義的.

對于裝船問題,有很多學(xué)者都進(jìn)行了較為詳細(xì)的研究,主要分為三個方面:場地堆存位置方面,裝船作業(yè)翻箱率方面和船舶配載方面.

場地堆存位置方面:合適的堆存位置會給之后的裝船作業(yè)中的配載和裝船作業(yè)指令提供便利,從而提高效率,所以它是提高碼頭裝卸效率的重要環(huán)節(jié).Kim等[1]運用動態(tài)規(guī)劃以及決策樹的方法對于集裝箱的場地堆存位置問題進(jìn)行了研究.郝聚民等[2]對于圖搜索理論和模式識別技術(shù)進(jìn)行了研究,以此為基礎(chǔ)建立了隨機條件下的混合順序作業(yè)堆場優(yōu)化模型,產(chǎn)生有利于之后做船舶配載的堆場.徐亞等[3]研究了集裝箱碼頭的堆場空間分配問題,建立了多目標(biāo)規(guī)劃模型,該模型考慮了“使得集卡總運輸距離最少”以及“使得各箱區(qū)工作量的差異最小”這兩個目標(biāo).

裝船作業(yè)翻箱率方面:對于碼頭來說,翻箱作業(yè)是做無用功的一種方式,浪費人力和物力,所以最大程度上地減少翻箱率是調(diào)高裝船效率的重要方式.靳志宏等[4]等考慮了海關(guān)是否放關(guān)的現(xiàn)實約束,建立了以最小翻箱數(shù)為目標(biāo)的集裝箱發(fā)箱順序決策模型.KIM等[5]利用分支定界和啟發(fā)式方法研究了提箱過程中翻箱落箱位置的確定問題,發(fā)現(xiàn)隨著問題規(guī)模的擴(kuò)大,使用分支定界法的求解時間呈指數(shù)形式上升,而啟發(fā)式方法解的質(zhì)量明顯下降.這對于問題的算法研究上具有重要意義.

船舶配載方面:裝船作業(yè)指令發(fā)送是在配載已知的情況下進(jìn)行的,好的配載結(jié)果可以得到更好的裝傳作業(yè)效率.SHIELDS等[6]首先對船舶的配載問題進(jìn)行了研究建模,并和實際的裝船情況進(jìn)行了比較,獲得了一定的效果.但是由于當(dāng)時船舶比較小,裝箱量也較少,其研究結(jié)果已不適合當(dāng)前超大型的集裝箱船舶.BOSE等[7]對影響船舶配載的所有因素都進(jìn)行了分析,并用模擬仿真技術(shù)做了一個決策支持系統(tǒng).但是該系統(tǒng)中所有因素相對比較孤立,沒有從系統(tǒng)的角度來解,也沒有進(jìn)行系統(tǒng)優(yōu)化.VIS等[8]對于近年來涉及的該類文章中的模型和算法做了較為綜合全面的綜述.STEENKEN等[9]針對集裝箱碼頭管理運營的生產(chǎn)調(diào)度數(shù)學(xué)模型做了概括和總結(jié),并且對其涉及的優(yōu)化模型和方法進(jìn)行了研究.BISH等[10]證明了用一個單獨的模型來解決所有與集裝箱碼頭相關(guān)的決策優(yōu)化問題遠(yuǎn)遠(yuǎn)超出了現(xiàn)今的計算能力.

然而以上文獻(xiàn)多數(shù)只考慮發(fā)箱順序?qū)τ诜渎驶虼胺€(wěn)性的影響,隨著船舶的大型化發(fā)展,船舶穩(wěn)性的可控范圍增大,所以如何在船舶穩(wěn)性允許的條件下通過更好的發(fā)箱順序提高裝船效率變得更加重要.本文考慮當(dāng)集裝箱分布在多貝位或多箱區(qū)時所引起的場橋移機次數(shù)和轉(zhuǎn)場次數(shù),以及船舶對于裝卸艙蓋板的作業(yè)因素,提出基于多箱區(qū)發(fā)箱的多目標(biāo)混合整數(shù)規(guī)劃模型，對發(fā)箱順序進(jìn)行決策.

1 問題描述

集裝箱碼頭的主要業(yè)務(wù)有四種:卸船業(yè)務(wù)、提箱業(yè)務(wù)、集港業(yè)務(wù)和裝船業(yè)務(wù).其中,裝船業(yè)務(wù)主要是將已經(jīng)集港的出口箱進(jìn)行復(fù)核、放行確認(rèn)、配載和最終的實際裝船.而裝船作業(yè)中,配載的主要任務(wù)是把場地上需要裝船的集裝箱與相應(yīng)船上的指定船箱位進(jìn)行一一對應(yīng),即要計劃每個集裝箱將來要裝到船上什么位置.配載結(jié)束之后才可以得出完整的箱量分布圖,在制定好配載計劃后,船控調(diào)度人員需要根據(jù)堆場內(nèi)的集裝箱的堆存位置和該集裝箱在船上的配載位置,制定發(fā)箱順序.在作業(yè)過程中,通常岸橋都是以一個船貝為單位進(jìn)行裝船作業(yè),因此針對每一個船貝的發(fā)箱順序的確認(rèn)對整個出口箱裝船作業(yè)的有效、順利進(jìn)行起著十分重要的作用,是整個裝船作業(yè)流程中的關(guān)鍵環(huán)節(jié)之一.

在發(fā)箱順序決策時,需要考慮一些限制條件,本文考慮首先要避免集裝箱懸空,發(fā)箱順序很大程度上決定了貝內(nèi)的裝船順序,且裝船過程中集裝箱的船箱位不可隨意改動,因而要避免裝船時出現(xiàn)懸空問題.其次是隨著船舶大型化的發(fā)展,對于中型或者大型集裝箱船舶來說,艙內(nèi)的同一個船貝可能會有2～3塊艙蓋板,在裝卸作業(yè)過程中應(yīng)碼頭的要求和為提高裝卸效率,需要先裝卸一塊艙蓋板下面的集裝箱,再進(jìn)行下一塊艙蓋板下面的集裝箱裝卸,不允許在兩塊艙蓋板之間交替作業(yè).

在裝船作業(yè)中,為達(dá)到高效的裝船效率,就應(yīng)當(dāng)避免一些不必要的作業(yè),本文主要考慮的是在決策發(fā)箱順序時的一些因素,以此作為優(yōu)化目標(biāo),包括避免不必要的翻箱、降低場吊的移機次數(shù)和降低場吊的轉(zhuǎn)場次數(shù).發(fā)箱順序可以控制場地內(nèi)集裝箱操作的序列,對于在同一位串(某一排)內(nèi)的集裝箱,應(yīng)盡量保證上面的集裝箱先發(fā),否則就會產(chǎn)生翻箱作業(yè).移機指的是場橋在同一箱區(qū)要從一個貝移動到另一個貝,在作業(yè)過程中還應(yīng)該使場吊需要移機的總次數(shù)盡量少,以避免因指派不當(dāng)造成場吊在同一箱區(qū)不同貝內(nèi)頻繁移動,降低作業(yè)效率,導(dǎo)致船期的延誤.轉(zhuǎn)場指的是場橋要從一個箱區(qū)移動到另一個箱區(qū),在作業(yè)過程中還應(yīng)該使場吊需要轉(zhuǎn)場的總次數(shù)盡量少,轉(zhuǎn)場所消耗的時間相比于翻箱操作和移機操作更費時間,所以更應(yīng)該避免.

2 模型建立

2.1 模型假設(shè)

不考慮碼頭不截關(guān)的情況;假設(shè)裝船箱位是已知的且不會再做調(diào)整;假設(shè)先從堆場中取走的集裝箱都先被裝上船;本文只考慮12.192 m(40ft)集裝箱的貝內(nèi)發(fā)箱順序問題;本文假設(shè)只針對單路發(fā)箱進(jìn)行決策;假設(shè)裝船業(yè)務(wù)時分艙蓋板,必須當(dāng)一塊艙蓋板的裝船任務(wù)全部完成后,才能繼續(xù)裝下一塊艙蓋板,而不允許多塊艙蓋板底下的集裝箱交替進(jìn)行裝船.

2.2 模型建立

2.2.1 約束限制

(1) 防止裝船懸空

(1)

如式(1)所示,不等式左側(cè)表示每個船箱位v將來的順序號,不等式右側(cè)表示每個船箱位v上面一層船箱位的順序號,所以要求左邊<右邊,從而保證不懸空.

(2) 分艙蓋板限制

(2)

(3)

(4)

(5)

(3) 集裝箱序號與發(fā)箱順序一一對應(yīng)

(6)

(7)

式(6)表示一個集裝箱序號只能對應(yīng)一個發(fā)箱順序號,而式(7)表示一個發(fā)箱順序只能對應(yīng)一個集裝箱序號.

2.2.2 目標(biāo)函數(shù)

(1) 場內(nèi)翻箱次數(shù)最少

(8)

(9)

式(8)表示目標(biāo)函數(shù)一:發(fā)箱作業(yè)過程中發(fā)生翻箱的總次數(shù)最少.式(9)中不等式左邊表示第y個場箱位上面一層的場箱位的發(fā)箱順序號,而不等式右邊表示第y個場箱位的發(fā)箱順序號,若不等式左邊大于右邊,表示第y個場箱位先發(fā),第y個場箱位的上一層的場箱位后發(fā),否則會造成翻箱.

(2) 場吊移機次數(shù)最少

(10)

(11)

(12)

(13)

式10表示目標(biāo)函數(shù)二:發(fā)箱作業(yè)過程中場橋移機的總次數(shù)最少.式(11)—(13)用于計算移機次數(shù),思路與式(3)—(5)類似,這里不再贅述.

(3) 場吊轉(zhuǎn)場次數(shù)最少

(14)

(15)

(16)

(17)

式(14)表示目標(biāo)函數(shù)三:發(fā)箱作業(yè)過程中場橋轉(zhuǎn)場的總次數(shù)最少.式(15)—(17)用于計算移機次數(shù),思路與式(3)—(5)類似,這里不再贅述.

針對以上3個目標(biāo),由于量綱統(tǒng)一且都是求最小值,本文使用線性加權(quán)法將模型從多目標(biāo)轉(zhuǎn)化為單目標(biāo),如式(18)所示.

(18)

式中:w1,w2,w3表示3個子目標(biāo)的權(quán)重.O表示總目標(biāo)函數(shù).

3 算例驗證

為驗證模型的有效性,本文應(yīng)用LINGO軟件進(jìn)行編程,在IntelCore i7-4710HQ 2.50GHz計算機上進(jìn)行求解,采用確定性分支定界整數(shù)規(guī)劃方法.

3.1 算例描述

本文設(shè)計算例,場地堆存位置及船上配載位置如圖1，2所示.共裝船14個集裝箱,編號從C1～C14.待裝集裝箱分布在堆場A132,A136,A212共3個貝,其中A132與A136為A1箱區(qū)不同貝,而A212為A2箱區(qū)的12貝.

圖1 場地堆存位置示意圖Fig.1 Diagrammatic sketch of storage location

(1) 場地堆存位置

(2) 船上配載位置

(3) 子目標(biāo)權(quán)重

根據(jù)上海外高橋二期碼頭實際作業(yè)時翻箱、轉(zhuǎn)場、移機所消耗的時間長短平均值,本文分別取w1,w2,w3為4,1,12.

3.2 算例結(jié)果及分析

(1) 算例結(jié)果

最優(yōu)目標(biāo)函數(shù)值如表1所示,最優(yōu)解如表2所示.

圖2 船上配載位置示意圖Fig.2 Diagrammatic sketch of stowage location表1 最優(yōu)目標(biāo)函數(shù)值Tab.1 Best Objective Value

總最優(yōu)目標(biāo)值子目標(biāo)一/次(翻箱數(shù))子目標(biāo)二/次(移機數(shù))子目標(biāo)三/次(數(shù))22221

(2) 算例結(jié)果分析

① 如圖3所示,根據(jù)上述求解結(jié)果,耗時10,27 min,可以看出由該模型得到的發(fā)箱順序結(jié)果較為合理,在整個過程中共發(fā)生翻箱2次,移機2次,轉(zhuǎn)場1次,實現(xiàn)了全局最優(yōu)解.而其中移機2次和轉(zhuǎn)場次數(shù)1是不可避免的,從而可以看出整體的求解結(jié)果較為理想,使用該模型對于發(fā)箱順序進(jìn)行決策較為理想.

表2 最優(yōu)解

圖3 算例結(jié)果示意圖Fig.3 Diagrammatic Sketch of Case Results

② 若在做配載時將船上配載位置的C7箱與C8箱交換,C9箱與C11箱交換,如圖3所示,則可以避免兩次翻箱,得到更好的目標(biāo)函數(shù)值.經(jīng)過求解,耗時1.1 min,可得翻箱數(shù)為0,轉(zhuǎn)場數(shù)為2,移機數(shù)為1.從而說明在條件允許的情況下對于船舶配載結(jié)果進(jìn)行適當(dāng)優(yōu)化調(diào)整可以提高發(fā)箱順序的效果,從而提高裝船效率.所以在做船舶裝船配載時就應(yīng)當(dāng)考慮到發(fā)箱順序?qū)τ谘b船作業(yè)的影響,在滿足其他約束(如重壓輕限制,單槽高度限制等)的條件下,適當(dāng)調(diào)整配載結(jié)果可以直接提高裝船效率,避免不必要的翻箱、移機或轉(zhuǎn)場.

(3) 雖然本模型為純整數(shù)線性規(guī)劃模型,但由于模型的很多約束較為復(fù)雜,給LINGO運用分支定界法帶來了難處,求解時間隨著求解規(guī)模的增加呈指數(shù)級增長,與KIM等[5]得出的結(jié)論類似;另外,修改配載位置前后的算例求解時間相差10倍,說明同樣的問題規(guī)模,數(shù)據(jù)不同可能會導(dǎo)致求解效率差異比較大,說明運用分支定界法對于該模型進(jìn)行求解穩(wěn)定性不高,具有一定局限,故在以后的研究中可以考慮使用啟發(fā)式算法進(jìn)行求解.

4 結(jié)語

本文通過對集裝箱碼頭裝船作業(yè)流程的調(diào)研以及研究,針對船舶大型化所帶來的問題及影響裝船效率的主要因素,建立集裝箱裝船貝內(nèi)發(fā)箱順序決策模型,模型考慮防懸空和分艙蓋板的約束,并且以翻箱次數(shù)最少、移機次數(shù)最少和轉(zhuǎn)場次數(shù)最少作為目標(biāo)進(jìn)行優(yōu)化.之后,通過設(shè)計算例和求解結(jié)果分析證明本文提出的模型能夠較好地解決集裝箱裝船貝內(nèi)發(fā)箱順序決策問題,并且好的配載結(jié)果可以指導(dǎo)發(fā)箱順序進(jìn)行決策.綜上所述,該模型對于裝船發(fā)箱順序決策具有較高的應(yīng)用價值.同時,模型的構(gòu)建方法對于研究同類基于空間布局的組合優(yōu)化問題具有一定的借鑒意義.

[1] KIM K H,PARK Y M,RYU K R.Deriving decision rules to locate export containers in container yards [J ].European Journal of Operational Research,2000,124(1):89-101.

[2] HAO Jumin,JI Zhuoshang.Study of optimization of a bay of stacking[J].Journal of Dalian University of Technology,2000,40(1):102-105.

[3] XU Ya,CHEN Qiushuang.Yard space allocation based on multi-objective programming[J].Journal of Systems Engineering,2009,03:365-369.

[4] JIN Zhihong,LAN Hui.Optimization on containership loading scheduling based on actual constraints [J].Journal of Dalian University of Technology,2011(1):71-74.

[5] KIM K H,Hong G P.A heuristic rule for relocating blocks [J].Computers and Operations Research(S0305-0548),2006,33(4):940-954.

[6] SHIELDS J J.Container-ship stowage:a computer-aided preplanning system[J].Martime.Technol,1984,21(4):370-383.

[7] BOSE J,REINERS T,STEENKEN D.2000 Vehicle dispatching at seaport container terminals using evolutionary algorithms[C]//Proceedings of the 33rd Hawaii International Conferenceon System Science,Piscataway:IEEE,2000:1-10.

[8] VIS I F A,RENE D K.Transshipment of containers at a container terminal:An overview[J].European Journal of Operational Research 2003,147:1-16.

[9] STEENKEND,VOLL S,STAHLBOCK R.Container terminal operation and operations research—a classification and literature review[J].OR Spectrum,2004,26:3-49.

[10] BISH E K.A multiple-crane-constrained scheduling problem in a container terminal[J].European Journalof Operational Research,2003,144:83-107.

Decisions on container retrieving orders forcontainer terminals

MI Wei-jian,ZHANG Xiao-hua,QIN Zhao,TIAN Ting

(Logistics Engineering College,Shanghai Maritime University, Shanghai 201306,China)

Owing to the increase of world container shipping and enlargement of container ships, the port operators have focused on the stability and efficiency of container handling operation. In this regard, the container retrieving order decision during loading operation secures a crucial position for loading efficiency. By considering the hatch cover and anti-vacant limitations as constraints, and the minimum marshalling times, times of moving in the same block and times of moving in different blocks as objectives, a decision-making model for container retrieving orders is established. Afterwards, a computational example is designed to verify model efficiency. Therefore, this approach provides instructions for similar combined optimization problems based on spatial distribution.

container terminal, ship loading, hatch cover, movement in same block, movement in different blocks.

上海市科學(xué)技術(shù)委員會部分地方院校能力建設(shè)專項計劃(13510501800);上海青年科技英才揚帆計劃(15YF1404900);上海市教育委員會科研創(chuàng)新項目(14ZZ140);上海海事大學(xué)博士創(chuàng)新項目(2014ycx040)

宓為建(1956-),男,教授,工學(xué)博士.E-mail:nearzxh@163.com

U 691.3

A

1672-5581(2016)04-0369-06