堆場龍門吊調度問題研究

樂美龍，殷際龍

上海海事大學 物流研究中心，上海 201306

1 引言

近年來，隨著經濟的快速發展和航運業蓬勃發展，集裝箱運輸業已成為全球運輸行業的支柱，集裝箱碼頭間的競爭日趨激烈。集裝箱碼頭對于進出口船舶的操作大致可分為：卸載進口集裝箱和裝載出口集裝箱。對于大多數碼頭來說，裝卸集裝箱所涉及的設備主要有以下三種，即橋吊、集卡以及堆場龍門吊，因此要提高碼頭效率、降低費用消耗，就需要合理安排橋吊、集卡和堆場龍門吊的工作時間。本文主要研究堆場龍門吊的合理調度問題，堆場龍門吊的調度直接影響到碼頭的裝卸效率，對堆場龍門吊調度的研究有利于提高集裝箱碼頭的競爭力。

由于龍門吊調度問題的重要性，有關龍門吊調度問題研究已取得一些進展。堆場龍門吊調度的研究目標大多為使集卡等待時間最短，或在自定義的時間窗內未完成的工作量最少。

Lai等人[1]和Leung[2]提出多種龍門吊調度規則，并利用仿真模型進行驗證。Zhang[3]和Cheung[4]等人提出解決裝卸任務事前預知的靜態龍門吊調度模型。Zhang[5]等人提出了龍門吊調度問題的混合整數規劃模型，并利用拉格朗日松弛思想加以優化。

Kim[6]研究了單個堆場龍門吊的最優路徑問題，建立混合整數規劃模型，使龍門吊在箱區總移動時間最小。Ng等人[7]提出利用分支定界法來優化堆場龍門吊調度問題。Chen等人[8]提出了堆場龍門吊調度模型，并用禁忌搜索法加以求解。Javanshir和Seyedalizadeh Ganji[9]提出了避免多龍門吊相互干擾的龍門吊調度問題模型，利用啟發式算法求解并與Lingo求得的結果進行對比。

對于龍門吊調度問題，國內研究相對較少，本文通過考慮正在工作的龍門吊不能跨越等約束條件，提出龍門吊合理調度模型使集卡等待時間最小化。

圖1 堆場場區示意圖

2 問題描述

堆場龍門吊調度問題是集裝箱碼頭整體規劃中的重要部分，合理、高效地調度龍門吊可以節約資源，減少能耗和提高碼頭操作效率，從而提高碼頭的競爭力。本文通過考慮龍門吊間的干擾，合理調度龍門吊，減少集卡的等待時間。圖1為堆場場區示意圖。

模型基于以下假設：

（1）假設每項工作的服務時間是固定的，并且每臺龍門吊的工作效率相同。

（2）龍門吊從一個場區移動到另一個場區時，將浪費大量時間及能源，不考慮龍門吊在兩場區之間的移動。

（3）需考慮龍門吊之間的干擾，龍門吊之間不能相互跨越。

3 數學模型

給定參數：

ri表示集卡的到達時間；

li表示工作i的到達位置；

dij表示工作 j與工作i之間的移動時間；

h表示每個工作的服務時間；

Zil∈{0,1},當Zil=1時表示工作i的到達位置在箱位l處；

M為一個無窮大數。

決策變量：

Si表示工作i的開始時間；

Di表示工作i的完成時間；

Xijk∈{0,1},當 Xijk=1時表示同一臺龍門吊k對工作i的服務先于工作 j；

Ylk∈{0,1},Ylk=1時表示龍門吊k服務于箱位l。

龍門吊調度模型如下：

4 遺傳算法設計

由于模型比較復雜，利用求解器求解會使求解時間過長，故本文利用遺傳算法進行求解。遺傳算法是一種高效的、相對成熟的智能算法，其模擬自然進化，按照適者生存和優勝劣汰的原理，逐代演化產生出越來越好的近似解，最終得到近視最優解。遺傳算法的流程設計如圖2所示。

4.1 染色體編碼

本文中染色體編碼采用實值編碼，即工作序號表示染色體上的基因，用基因的先后順序來表示服務的先后順序。圖3為染色體示意圖，其表示有兩臺龍門吊，10個工作，第一臺龍門吊服務工作{4，5，3，6，8}，第二臺龍門吊服務工作{1，2，7，10，9}，其中的0將兩臺龍門吊的工作分隔開。

4.2 計算適應度和選擇父代染色體

（1）首先利用約束條件（7）對染色體進行篩選

篩選步驟如下：

圖2 遺傳算法設計流程圖

圖3 染色體示意圖

步驟1將需要服務的工作按到達時間從小到大排列。

步驟2檢查每條染色體中，不同龍門吊執行的任務是否存在時間上的重合，即Di>Sj。當此種情況存在時，檢查是否滿足約束（7），滿足則直接計算適應度進行初始父代的選擇；否則將該染色體的適應度標記0。

步驟3重復步驟2，直至不存在不滿足約束（7）的染色體。

（2）適應度計算

（3）選擇父代染色體

采用最佳保留選擇法對父代染色體進行選擇，即先按輪盤選擇規則（每個個體被選擇的概率為其適應度占整個種群適應度的比例，比例越大被選擇概率越大）執行選擇操作，然后將當前群體中適應度最高的個體結構完整的復制到下一代中。

4.3 染色體交叉

染色體交叉是遺傳算法的重要操作，其示意圖如圖4，本文采用的交叉步驟如下：

圖4 染色體交叉示意圖

步驟1在一個父代中隨即產生一個子串。

步驟2將這個子串復制到第二個父代的相同位置，刪除第二個父代中相同的基因。

步驟3將第二個父代剩余的基因從左向右順序放入子代空位中。

4.4 變異

本文采用的是實數編碼，因此在變異操作中需隨機選擇兩個基因位置，并將其位置互換。基因的變異概率比較小，根據以往的研究數據，文中的變異概率取值為0.09。圖5為基因變異示意圖。

圖5 基因變異示意圖

5 算例

用遺傳算法來計算下面這個算例。龍門吊數K=2，工作數m=10，設時段開始時間為0，每個工作都是卸載一個相同規格的集裝箱并將其堆放到指定位置（或將一個集裝箱裝載到集卡上）。各個工作的到達時間分別為r1=60 s，r2=240 s，r3=360 s，r4=540 s，r5=660 s，r6=720 s，r7=960 s，r8=1 080 s，r9=1 260 s，r10=1 440 s；集裝箱到達的箱位為l1=l4=1，l2=l6=5，l3=l5=7，l7=l10=13，l8=15，l9=19；龍門吊的操作一個集裝箱用時為240 s，移動時間dij=3×|li-lj|。

利用遺傳算法對算例進行求解，得到運算結果如表1所示。龍門吊1的工作順序為1-4-6-7-10，對應的箱位為1-1-5-13-13；龍門吊2的工作順序為2-3-5-8-9，對應的箱位為5-7-7-15-19。集卡最小等待總時長為312 s，最早完成時間為1 680 s。

表1 算例運算結果

圖6為龍門吊在這10個工作時段的運動軌跡（如龍門吊1的軌跡，第一個拐點表示龍門吊1離開箱位3，第二個拐點表示龍門吊1到達箱位5），可以更為直觀地看出龍門吊所處的位置以及最早結束時間。

下面與文獻[9]的調度模式進行對比。文獻[9]的模型為了避免龍門吊間的相互干擾，在約束中規定不同的龍門吊不能在同一箱位處工作，這樣很好地避免了龍門吊間產生干擾，但同時也限制了龍門吊的可工作位置范圍。下面利用文獻[9]中的模型（在其基礎上加入移動時間便于對比）來計算本文中的算例，圖7為文獻[9]的模型針對本文算例進行求解所得到的龍門吊移動軌跡圖。

圖6 龍門吊移動軌跡圖

圖7 基于文獻[9]模型的龍門吊軌跡圖

最終求得其最早完成時間為1 680 s，與本文模型計算的結果相同；最小等待時間是324 s，大于本文模型的結果312 s?？梢钥闯?，本文的模型比單純考慮龍門吊空間位置干擾的模型更能提高龍門吊工作效率。

6 結論

在集裝箱碼頭的物流作業中，堆場龍門吊調度問題是一個非常重要的環節。本文整體考慮龍門吊在時間和空間上的相互影響，其結果更加接近現實情況，有助于提高碼頭效率。

本文的創新點在于利用龍門吊工作時間上的重合以及空間位置約束來確定龍門吊的工作位置。一方面避免了人為規定工作時間段對龍門吊調度的影響，另一方面避免了單純考慮空間位置的干擾而給龍門吊工作位置的選擇帶來更大的限制。最后，由于模型的復雜性，引入遺傳算法進行求解，縮短了求解時間并得到了滿意結果。

[1]Lai K，Lam K.A study of container yard equipment allocation strategy in Hong Kong[J].International Journal of Modeling and Simulation，1994，14（3）：134-138.

[2]Lai Leung J W.Analysis of yard crane deployment strategies in a container terminal[C]//Proceedings of ICC and IE Conference，1996：1187-1190.

[3]Zhang C，Liu J，Wan Y W，et al.Storage space allocation in container terminals[J].Transportation Research：Part B MethodoLogy，2003，37（10）：883-903.

[4]Cheung R K，Li C L，Lin W.Inter block crane deployment in container terminals[J].Transportation Science，2002，36（1）：79-93.

[5]Zhang C，Wan Y W，Liu J，et al.Dynamic crane deployment in container storage yards[J].Transportation Research：Part B MethodoLogy，2002，36（6）：537-555.

[6]Kim K H.An optimalrouting algorithm fora transfer crane in port container terminals[J].Transportation Science，2003，33（1）：17-33.

[7]Ng W C，Mak K L.Yard crane scheduling in port container terminals[J].AppliedMathematicalModeling，2005，29（3）：263-276.

[8]Chen L，Bostel N，Dejax P，et al.TaBu search algorithm for the integrated scheduling problem of container handling systems in a maritime terminal[J].European Journal of Operational Research，2009，181：40-58.

[9]Javanshir H，Seyedalizadeh Ganji S R.Yard crane scheduling in port container terminals using genetic algorithm[J].Journal of Industrial and Systems Engineering，2010，6（11）：39-50.