考慮干涉情況的多臺龍門吊作業(yè)路徑優(yōu)化

林艷艷，樂美龍

(上海海事大學(xué)科學(xué)研究院，上海 201306)

0 引言

隨著世界經(jīng)濟的快速發(fā)展，集裝箱港口的競爭越來越激烈，如何在眾多競爭者中脫穎而出是現(xiàn)代集裝箱港口面臨的首要問題.現(xiàn)在的關(guān)鍵是通過提高集裝箱港口的裝卸效率實現(xiàn)降低成本、提高競爭力的目標.在集裝箱港口的后方堆場中，由于龍門吊尺寸過大且移動速度較為緩慢，其在不同箱區(qū)之間作業(yè)時，過道轉(zhuǎn)彎作業(yè)會占據(jù)大量道路空間，有可能因此導(dǎo)致堆場內(nèi)交通堵塞并耽擱集卡、甚至是其他船舶的作業(yè).顯然，場橋作業(yè)調(diào)度的優(yōu)劣不但會影響自身的作業(yè)效率，還會對碼頭整體作業(yè)水平產(chǎn)生影響.因此，如何提高龍門吊的工作效率，成為當前眾多研究者探討的熱點問題.

1 文獻綜述

到目前為止，針對龍門吊的作業(yè)優(yōu)化主要可以分為龍門吊調(diào)度優(yōu)化［1］、龍門吊配置優(yōu)化［2］以及龍門吊路徑優(yōu)化研究.龍門吊路徑優(yōu)化研究的主要貢獻如下:

KIM等［3］研究龍門吊處理出口集裝箱的路徑優(yōu)化問題.決策變量是龍門吊在堆場貝位上提取的集裝箱數(shù)量和龍門吊到達貝位的序列，并構(gòu)建混合整數(shù)規(guī)劃模型.目標函數(shù)為最小化龍門吊裝卸集裝箱的總時間，包括在貝位的處理時間和貝位間的運行時間.文中只考慮出港裝載操作.同時，作者設(shè)計出一個路徑優(yōu)化算法.

KIM等［4］在1997年研究的基礎(chǔ)上，將設(shè)計模型分解為幾個子問題，其中每個子問題都可以由動態(tài)規(guī)劃算法求解.算法能夠較好地求得最優(yōu)解，但是只適合于小型或中型船舶，大型船舶的問題則需要設(shè)計一個啟發(fā)式算法進行求解得到近似解.

NARASIMHAN等［5］首次證明龍門吊路徑優(yōu)化問題是一個NP完全問題，然后運用分支定界法計算該問題.在此基礎(chǔ)上，設(shè)計一個最壞案例的實現(xiàn)率(1.5)的列數(shù)啟發(fā)式算法.作者提出的模型以實現(xiàn)龍門吊完成給定裝載計劃所花費的時間最小為目的;但文中給出的模型過于簡單，且沒有考慮約束條件;主要設(shè)計4種算法，并通過算例進行比較與分析;最后得出，分支定界法適合小規(guī)模問題的求解，而啟發(fā)式算法則適合于較大規(guī)模的問題，且隨著港口不同，算法性能也會隨之改變.

KIM等［6］再次研究集裝箱港口后方堆場裝卸設(shè)備的路徑優(yōu)化問題.在之前研究的基礎(chǔ)上，運用遺傳算法(Genetic Algorithm，GA)和約束搜索方法求解該問題.在算例分析中將這兩種算法與精確算法進行比較;但文中對設(shè)計的兩種算法的描述不夠詳細;在算例分析中分別進行中小型問題的3種算法的比較，能夠較直觀地表現(xiàn)出3種算法的計算性能.

韓曉龍［7］研究一臺龍門吊的路徑優(yōu)化問題，建立以龍門吊總工作時間最短為目標的混合整數(shù)規(guī)劃模型.首先按照龍門吊就近服務(wù)的原則給出龍門吊的路徑及其啟動次數(shù)和工作時間;再對模型運用LINGO 8.0進行計算，得出優(yōu)化的龍門吊路徑;最后將兩者進行比較，得出設(shè)計模型的有效性.

LEE等［8］討論雙龍門吊系統(tǒng)的調(diào)度問題，主要描述在兩個不同箱區(qū)的兩臺龍門吊的集裝箱裝載操作.建立數(shù)學(xué)模型，并運用模擬退火(Simulated Annealing，SA)算法進行求解.模型中假設(shè)對兩臺龍門吊同時調(diào)度，裝載計劃和箱區(qū)計劃已知，兩臺龍門吊同時服務(wù)于一臺橋吊.但是模型中沒有考慮箱區(qū)上集裝箱的時間序列，也即未考慮集裝箱的需求時間，只考慮集裝箱的數(shù)量.在裝載過程中，龍門吊不會在兩個箱區(qū)間移動，那么就可以將問題分為兩個單一龍門吊的問題.作者又提出一個最低界評估的算法，用于與SA算法進行比較，雖然得出的結(jié)果是SA的方案比最低界評估的方案差10.3%，但是如果不需要精確解的話，SA算法的結(jié)果還是比較滿意的，且可以知道SA算法與集裝箱裝載的數(shù)量相互獨立，可以處理大規(guī)模的問題.

CAO等［9］主要研究用一個龍門吊調(diào)度系統(tǒng)服務(wù)裝船作業(yè)的問題，目標是最小化龍門吊總完成時間.設(shè)計一個貪婪算法、SA及龍門吊調(diào)度啟發(fā)式算法求解該問題.該系統(tǒng)由一大一小兩臺龍門吊構(gòu)成，在模型中除了有與普通兩臺龍門吊調(diào)度相同的約束外，還設(shè)計了避免干涉約束.但是，在技術(shù)上沒有考慮大的龍門吊和小的龍門吊的額定工作能力的不同限制.設(shè)計的貪婪算法，只有規(guī)則，沒有具體的算法步驟.GA也只是考慮兩臺龍門吊的情景，沒有考慮這個模型的特殊性，即沒有考慮一大一小龍門吊的優(yōu)越性.在算例分析中，較好的一點是對多個算法進行比較.

李麗麗［10］在研究集裝箱堆場布局的基礎(chǔ)上，將堆場中的各個功能區(qū)抽象為一個節(jié)點建立各個功能區(qū)之間的連通圖，提出利用最短路法和動態(tài)法的綜合路徑優(yōu)化求解法，建立龍門吊路徑優(yōu)化模型，并給出基于GA的求解過程，最后運用Flexsim進行仿真求解驗證上述問題的最優(yōu)結(jié)果.

從上面的文獻綜述中可以了解到，目前對龍門吊的路徑優(yōu)化研究較少，且大多只局限于對一臺龍門吊的路徑優(yōu)化.即使是研究兩臺龍門吊的路徑優(yōu)化，也只是兩臺龍門吊在兩個不同的箱區(qū)，而沒有考慮到多臺龍門吊在同一個箱區(qū)協(xié)同工作的情況.因此，研究者在研究龍門吊路徑優(yōu)化時，很少考慮龍門吊之間的干涉問題，即使有所考慮，也很少會將其納入計算中.目前，關(guān)于龍門吊之間干涉問題的研究主要有以下兩種假設(shè)約束:一是假設(shè)龍門吊之間發(fā)生干涉時，則一臺龍門吊停止等待另一臺龍門吊工作完成，見文獻［9］和［11］;一是假設(shè)避免龍門吊之間的干涉，并設(shè)定龍門吊之間的安全距離，見文獻［12］～［14］.本文在模型中考慮的干涉約束沿用第一種假設(shè)，而在計算中則假設(shè)龍門吊發(fā)生干涉時等待2 min，然后兩臺龍門吊的工作互換.

2 多臺龍門吊路徑優(yōu)化研究

龍門吊路徑優(yōu)化和VRP問題都是路徑優(yōu)化研究，但是兩者最大的不同之處是:VRP只需要確定最優(yōu)路徑，而龍門吊路徑優(yōu)化研究是在確定龍門吊最優(yōu)路徑的同時，還要確定龍門吊在路徑中每個貝位上提取的集裝箱數(shù)量.

本文主要是以KIM等［6］提出的單臺龍門吊的路徑優(yōu)化研究為基礎(chǔ)，提出多臺龍門吊的路徑優(yōu)化研究.龍門吊路徑優(yōu)化研究的重要前提是已知集裝箱堆場貝位上的集裝箱分布情況，即已知堆場分布圖，見圖1.出于安全因素考慮，每個貝位的集裝箱堆存不能超過7列、4層;且在第4層的左右兩端必須空出，以避免由于風、雨、雪等因素引起集裝箱傾倒的危險.這樣，每個貝位上最多堆存的集裝箱數(shù)為26個，且只能堆存同一種類型的集裝箱.

圖1 堆場分布

本文集裝箱組的設(shè)計沿用KIM等［6］制定的集裝箱組分類方法，即按照集裝箱的目的港及集裝箱尺寸進行分類，另外還新加入集裝箱重量這一參數(shù)，即在設(shè)計時協(xié)同考慮這三要素，這主要是滿足出口箱裝船時船舶對集裝箱重量的要求.圖1中，不同顏色代表不同的集裝箱組，如貝位1和貝位7堆存不同數(shù)量的同種類型的集裝箱，其集裝箱組的目的港為BANGKOK，20英尺箱，且重量相同.

掌握堆場分布圖后，根據(jù)研究需要細化出每個箱區(qū)的集裝箱組分布情況，得到堆場計劃表，見表1(表中給出貝位數(shù)P=15情況下的堆場計劃表).從表中可以了解到在貝位1中有A組集裝箱9 TEU，在貝位2中有B組集裝箱19 TEU，依此類推.

表1 堆場計劃表說明(P=15)

多臺龍門吊路徑優(yōu)化研究的另一個重要前提是了解集裝箱的裝船計劃，即裝載計劃表，見表2(表中給出P=15情況下的裝載計劃表)，其中子任務(wù)表示龍門吊需要完成的裝載任務(wù)的子任務(wù).

表2 裝載計劃表說明(P=15)

已知這些數(shù)據(jù)后，通過建立多臺龍門吊的路徑優(yōu)化模型，并運用C#_2008編程，再用Gurobi_4.5求解，計算得到每臺龍門吊的最優(yōu)路徑及在每個貝位上提取的集裝箱數(shù)量.

3 模型

3.1 問題描述

研究針對的是在集裝箱港口中多臺龍門吊同時服務(wù)一條船裝載出口箱的情景.由于龍門吊本身形狀的特殊性，堆場上每個箱區(qū)中最多只能有兩臺龍門吊.根據(jù)所研究的龍門吊服務(wù)的具體情形，可知兩臺龍門吊同時完成一個任務(wù).根據(jù)裝載計劃獲知一個任務(wù)可以劃分為幾個子任務(wù).如表2所示，一個任務(wù)劃分為8個子任務(wù)，在子任務(wù)中要提取A集裝箱組中的18 TEU，在子任務(wù)2中要提取B集裝箱組中的15 TEU，依次類推.

為了切合實際，模型遵循以下假設(shè)條件:

(1)只考慮出口集裝箱，因此集裝箱的貝位圖一般已知，即堆場上的集裝箱分布情況已知;

(2)研究龍門吊處理出口集裝箱的裝載優(yōu)化，因此其研究前提即裝載計劃已知;

(3)由于龍門吊的尺寸較為龐大，一個箱區(qū)最多只能有兩臺龍門吊同時工作;

(4)只考慮一個運行方向上的集裝箱箱區(qū)，即龍門吊行走無須轉(zhuǎn)彎，不必考慮龍門吊轉(zhuǎn)過場的時間(一般出口集裝箱會集中堆放，這既符合實際情況，又降低研究難度);

(5)進行分組裝載優(yōu)化，因此只考慮一種標準箱型(20英尺箱)有利于優(yōu)化研究;

(6)只考慮出口集裝箱組，且每個貝位上只有一種集裝箱組，此為研究前提.

3.2 模型描述

設(shè)計多臺龍門吊的綜合優(yōu)化混合整數(shù)規(guī)劃模型，模型中考慮龍門吊之間的干涉問題.首先解釋說明模型中相關(guān)字母的涵義.

m為組成一臺龍門吊的一個任務(wù)的子任務(wù)數(shù)量;n為龍門吊數(shù)量;P為堆場貝位數(shù)量;Q為集裝箱組數(shù)量;K={1 ，2，…，n}為龍門吊的索引集;B={1，2，3，…，p}為堆場貝位的索引集;G={1，2，3，…，q}為集裝箱組的索引集(即對堆場貝位和集裝箱組都進行編號);S(h)為與集裝箱組h相對應(yīng)的子任務(wù)編號集;B(h)為堆場貝位集，其中該貝位上的集裝箱組為h;ch，j為堆存在貝位j上的集裝箱組h的初始數(shù)量;rt為子任務(wù)t中提取的集裝箱數(shù)量;gt為在子任務(wù)t中必須提取的集裝箱組數(shù);B(gt)為在子任務(wù)t中必須提取的集裝箱組所在的堆場貝位集.

可以將龍門吊路徑優(yōu)化問題描述為一個網(wǎng)絡(luò)圖問題.一個網(wǎng)絡(luò)圖由點集V和弧集A構(gòu)成(見圖2).

圖2 龍門吊作業(yè)路徑網(wǎng)絡(luò)

在本模型中，假設(shè)一個點由t(i)表示，其中t表示子任務(wù)數(shù)，i表示堆場貝位數(shù)，則該問題就變成在網(wǎng)絡(luò)中從初始貝位S點到終點貝位T點找到每臺龍門吊的一條路徑，并決定它們在每個點上提取的集裝箱數(shù).A(V)為弧集，A(V)={(i，j)|i，j∈V}，且點集V是給定的;S={S1，S2，…，Sn}為龍門吊的出發(fā)點集，且 S?B;T={T1，T2，…，Tn}為龍門吊的結(jié)束點集，且 T?B;t=0，1，…，m，m+1，其中 t=0 表示龍門吊在初始位置，而t=m+1則表示龍門吊在終點位置;Ts為龍門吊在每個堆場貝位的調(diào)整時間;Td為每個堆場貝位的長度;Tv為龍門吊的運行速度;Th為龍門吊裝卸一個集裝箱的時間.

決策變量:

經(jīng)過我們與盲人的深入交流，結(jié)合上網(wǎng)分析查閱，我們發(fā)現(xiàn)盲人在病患方面有較多顧慮，并且醫(yī)療器械方面的溫度計沒有針對盲人研發(fā)專門的盲人用便捷溫度計。于是我們小組希望針對盲人設(shè)計其專門使用的溫度計，以改善盲人的生活質(zhì)量。

綜上，考慮干涉的多臺龍門吊路徑優(yōu)化模型可表述如下:

其中:式(1)為目標函數(shù)，表示最小化總時間，包括龍門吊的運行時間、準備時間及處理集裝箱的時間;式(2)為約束條件，表示每個箱區(qū)的龍門吊數(shù)量不能超過2臺;式(3)～(5)共同控制龍門吊路徑網(wǎng)絡(luò)的流量，其中式(3)和(4)表示每個任務(wù)的出發(fā)點的出度和結(jié)束點的入度均為1，式(5)表示中間節(jié)點的出度等于入度;式(6)和(7)共同保證龍門吊的運行路徑不會出現(xiàn)內(nèi)循環(huán);式(8)表示龍門吊只有到達貝位才可以開始作業(yè);式(9)和(10)保證避免龍門吊之間的干涉;式(11)表示龍門吊要滿足每個任務(wù)要求提取的集裝箱數(shù)量;式(12)表示龍門吊提取的集裝箱數(shù)量不能超過貝位上原有的集裝箱數(shù)量;式(13)和(14)為(0，1)決策變量的約束;式(15)表示該決策變量為非負數(shù).

4 算例設(shè)計及分析

首先，對第3節(jié)中構(gòu)建的模型，結(jié)合某港口的實際數(shù)據(jù)對其進行算例設(shè)計.本算例主要是針對一個箱區(qū)上的裝船任務(wù)，即在龍門吊的數(shù)量n=2的情況下，分別進行3組試驗(P，Q，m)=(15，3，8)，(25，4，10)，(35，4，11).其中，由該港口的實際情況得到每個貝位的長為Td=6.096 m，龍門吊的運行速度為Tv=30 m/min，龍門吊處理一個集裝箱的時間Th=2 min，而龍門吊的調(diào)整時間Ts=1 min.關(guān)于P=15的案例的具體實驗數(shù)據(jù)見表1和2，而P=25和35的案例的具體數(shù)據(jù)見表3和4(為了簡化，將裝載計劃表與堆場計劃表合并組成集裝箱裝載計劃).

表3 集裝箱裝載計劃(P=25)

運用C#_2008進行編程，并調(diào)用Gurobi_4.5進行計算.對上述設(shè)計的每個算例均進行10次重復(fù)計算，得到較為穩(wěn)定的計算結(jié)果，且計算時間均在理想范圍內(nèi).

圖3表示3種案例的龍門吊行走路徑，橫軸表示子任務(wù)，縱軸表示貝位.圖中，兩條路徑交點處表示兩臺龍門吊在一個子任務(wù)內(nèi)均到達過的貝位，由于計算中加入避免干涉的條件，可以由圖中看出，每個子任務(wù)中兩臺龍門吊到達同一貝位的時間是錯開 的，因此沒有發(fā)生干涉.

表4 集裝箱裝載計劃(P=35)

圖3 龍門吊最優(yōu)路徑

表5 龍門吊在不同貝位和子任務(wù)中提取的集裝箱數(shù)量(P=15)TEU

表6 龍門吊在不同貝位和子任務(wù)中提取的集裝箱數(shù)量(P=25)TEU

表7 龍門吊在不同貝位和子任務(wù)中提取的集裝箱數(shù)量(P=35)TEU

從上述各表中可以清楚地看出每個案例中龍門吊的啟動頻率(即訪問貝位的次數(shù))和龍門吊在每個子任務(wù)及每個貝位上提取的集裝箱數(shù).為了進一步研究龍門吊的路徑優(yōu)化問題，同時計算一臺龍門吊處理上述任務(wù)的總時間以及啟動頻率，然后將一臺龍門吊與兩臺龍門吊的優(yōu)化結(jié)果進行比較，結(jié)果見表8.

表8 單臺龍門吊和多臺龍門吊工作效率的比較

從表8中可以發(fā)現(xiàn)，兩臺龍門吊處理任務(wù)的時間明顯少于一臺龍門吊，幾乎能夠節(jié)省一半時間.雖然一臺龍門吊的啟動頻率少于兩臺龍門吊的總啟動頻率，但平均下來，一臺龍門吊的啟動頻率大于兩臺龍門吊的單臺啟動頻率.因此，在處理同一任務(wù)時，兩臺龍門吊的工作效率高于一臺龍門吊的工作效率，從而驗證模型是可行有效的.

5 總結(jié)與展望

以KIM等［6］提出的單臺龍門吊路徑優(yōu)化問題的模型為基礎(chǔ)設(shè)計多臺龍門吊的路徑優(yōu)化研究.模型中考慮多臺龍門吊的干涉問題，并對集裝箱組的分類方法進行更新.在未來研究中，需要對更大規(guī)模的實例作進一步設(shè)計分析，更需要設(shè)計新的啟發(fā)式算法進行計算，以加快計算速度.

［1］何軍良，宓為建，嚴偉.基于爬山算法的集裝箱堆場場橋調(diào)度［J］.上海海事大學(xué)學(xué)報，2007，28(4):11－15.

［2］金鑫，丁以中.新工藝下集裝箱碼頭裝卸資源分配模擬［J］.上海海事大學(xué)學(xué)報，2010，31(1):28－32.

［3］KIM Ki Young，KIM Kap Hwan.A routeing algorithm for a single transfer crane to load export containers onto a container ship［J］.Computers ＆Ind Eng，1997，33(3/4):673－676.

［4］KIM Ki Young，KIM Kap Hwan.An optimal routeing algorithm for a transfer crane in port container terminals［J］.Transportation Sci，1999，33(1):17－33.

［5］NARASIMHAN A，PALEKAR U S.Analysis and algorithms for the transtainer routeing problem in container port operations［J］.Transportation Sci，2002，36(1):63－78.

［6］KIM Ki Young，KIM Kap Hwan.Heuristic algorithm for routeing yard－side equipment for minimizing loading times in container terminals［J］.Naval Res Logistics，2003，(50):498－514.

［7］韓曉龍.集裝箱港口龍門吊的最優(yōu)路徑問題［J］.上海海事大學(xué)學(xué)報，2005，26(2):39－41.

［8］LEE Der－Horng，CAO Zhi，MENG Qiang.Scheduling of two－transtainer systems for loading outbound containers in port container terminals with simulated annealing algorithm［J］.Sci Direct，Int J Production Econ，2007，107(1):115－124.

［9］CAO Zhi，LEE Der－Horng，MENG Qiang.Deployment strategies of double－rail－mounted gantry crane systems for loading outbound containers in container terminals［J］.Int J Production Econ，2008，115(1):221－228.

［10］李麗麗.集裝箱堆場布局與場橋調(diào)度優(yōu)化研究［D］.大連:大連海事大學(xué)，2011.

［11］NG W C.Crane scheduling in container yards with inter－crane interference［J］.Eur J Operational Res，2005，164:64－78.

［12］JAVANSHIR H，GANJI S R S.Yard crane scheduling in port container terminals using genetic algorithm［J］.J Ind Eng Int，2010，6(11):39－50.

［13］MAK Kai Ling，SUN Di.A scheduling method for cranes in a container yard with inter－crane interference［J］.Electronic Eng ＆ Computing Technol，2010，60:715－725.

［14］HU Zhihua.Improved discrete time model for container yard crane scheduling［C］//2010 Third Int Joint Conf Computational Sci＆ Optimization－Volume 02 IEEE Computer Society Washington，DC，USA.2010:34－37.