堆場(chǎng)龍門吊調(diào)度問(wèn)題研究

樂(lè)美龍，殷際龍

上海海事大學(xué) 物流研究中心，上海 201306

1 引言

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

由于龍門吊調(diào)度問(wèn)題的重要性，有關(guān)龍門吊調(diào)度問(wèn)題研究已取得一些進(jìn)展。堆場(chǎng)龍門吊調(diào)度的研究目標(biāo)大多為使集卡等待時(shí)間最短，或在自定義的時(shí)間窗內(nèi)未完成的工作量最少。

Lai等人[1]和Leung[2]提出多種龍門吊調(diào)度規(guī)則，并利用仿真模型進(jìn)行驗(yàn)證。Zhang[3]和Cheung[4]等人提出解決裝卸任務(wù)事前預(yù)知的靜態(tài)龍門吊調(diào)度模型。Zhang[5]等人提出了龍門吊調(diào)度問(wèn)題的混合整數(shù)規(guī)劃模型，并利用拉格朗日松弛思想加以優(yōu)化。

Kim[6]研究了單個(gè)堆場(chǎng)龍門吊的最優(yōu)路徑問(wèn)題，建立混合整數(shù)規(guī)劃模型，使龍門吊在箱區(qū)總移動(dòng)時(shí)間最小。Ng等人[7]提出利用分支定界法來(lái)優(yōu)化堆場(chǎng)龍門吊調(diào)度問(wèn)題。Chen等人[8]提出了堆場(chǎng)龍門吊調(diào)度模型，并用禁忌搜索法加以求解。Javanshir和Seyedalizadeh Ganji[9]提出了避免多龍門吊相互干擾的龍門吊調(diào)度問(wèn)題模型，利用啟發(fā)式算法求解并與Lingo求得的結(jié)果進(jìn)行對(duì)比。

對(duì)于龍門吊調(diào)度問(wèn)題，國(guó)內(nèi)研究相對(duì)較少，本文通過(guò)考慮正在工作的龍門吊不能跨越等約束條件，提出龍門吊合理調(diào)度模型使集卡等待時(shí)間最小化。

圖1 堆場(chǎng)場(chǎng)區(qū)示意圖

2 問(wèn)題描述

堆場(chǎng)龍門吊調(diào)度問(wèn)題是集裝箱碼頭整體規(guī)劃中的重要部分，合理、高效地調(diào)度龍門吊可以節(jié)約資源，減少能耗和提高碼頭操作效率，從而提高碼頭的競(jìng)爭(zhēng)力。本文通過(guò)考慮龍門吊間的干擾，合理調(diào)度龍門吊，減少集卡的等待時(shí)間。圖1為堆場(chǎng)場(chǎng)區(qū)示意圖。

模型基于以下假設(shè)：

（1）假設(shè)每項(xiàng)工作的服務(wù)時(shí)間是固定的，并且每臺(tái)龍門吊的工作效率相同。

（2）龍門吊從一個(gè)場(chǎng)區(qū)移動(dòng)到另一個(gè)場(chǎng)區(qū)時(shí)，將浪費(fèi)大量時(shí)間及能源，不考慮龍門吊在兩場(chǎng)區(qū)之間的移動(dòng)。

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

3 數(shù)學(xué)模型

給定參數(shù)：

ri表示集卡的到達(dá)時(shí)間；

li表示工作i的到達(dá)位置；

dij表示工作 j與工作i之間的移動(dòng)時(shí)間；

h表示每個(gè)工作的服務(wù)時(shí)間；

Zil∈{0,1},當(dāng)Zil=1時(shí)表示工作i的到達(dá)位置在箱位l處；

M為一個(gè)無(wú)窮大數(shù)。

決策變量：

Si表示工作i的開(kāi)始時(shí)間；

Di表示工作i的完成時(shí)間；

Xijk∈{0,1},當(dāng) Xijk=1時(shí)表示同一臺(tái)龍門吊k對(duì)工作i的服務(wù)先于工作 j；

Ylk∈{0,1},Ylk=1時(shí)表示龍門吊k服務(wù)于箱位l。

龍門吊調(diào)度模型如下：

4 遺傳算法設(shè)計(jì)

由于模型比較復(fù)雜，利用求解器求解會(huì)使求解時(shí)間過(guò)長(zhǎng)，故本文利用遺傳算法進(jìn)行求解。遺傳算法是一種高效的、相對(duì)成熟的智能算法，其模擬自然進(jìn)化，按照適者生存和優(yōu)勝劣汰的原理，逐代演化產(chǎn)生出越來(lái)越好的近似解，最終得到近視最優(yōu)解。遺傳算法的流程設(shè)計(jì)如圖2所示。

4.1 染色體編碼

本文中染色體編碼采用實(shí)值編碼，即工作序號(hào)表示染色體上的基因，用基因的先后順序來(lái)表示服務(wù)的先后順序。圖3為染色體示意圖，其表示有兩臺(tái)龍門吊，10個(gè)工作，第一臺(tái)龍門吊服務(wù)工作{4，5，3，6，8}，第二臺(tái)龍門吊服務(wù)工作{1，2，7，10，9}，其中的0將兩臺(tái)龍門吊的工作分隔開(kāi)。

4.2 計(jì)算適應(yīng)度和選擇父代染色體

（1）首先利用約束條件（7）對(duì)染色體進(jìn)行篩選

篩選步驟如下：

圖2 遺傳算法設(shè)計(jì)流程圖

圖3 染色體示意圖

步驟1將需要服務(wù)的工作按到達(dá)時(shí)間從小到大排列。

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

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

（2）適應(yīng)度計(jì)算

（3）選擇父代染色體

采用最佳保留選擇法對(duì)父代染色體進(jìn)行選擇，即先按輪盤選擇規(guī)則（每個(gè)個(gè)體被選擇的概率為其適應(yīng)度占整個(gè)種群適應(yīng)度的比例，比例越大被選擇概率越大）執(zhí)行選擇操作，然后將當(dāng)前群體中適應(yīng)度最高的個(gè)體結(jié)構(gòu)完整的復(fù)制到下一代中。

4.3 染色體交叉

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

圖4 染色體交叉示意圖

步驟1在一個(gè)父代中隨即產(chǎn)生一個(gè)子串。

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

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

4.4 變異

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

圖5 基因變異示意圖

5 算例

用遺傳算法來(lái)計(jì)算下面這個(gè)算例。龍門吊數(shù)K=2，工作數(shù)m=10，設(shè)時(shí)段開(kāi)始時(shí)間為0，每個(gè)工作都是卸載一個(gè)相同規(guī)格的集裝箱并將其堆放到指定位置（或?qū)⒁粋€(gè)集裝箱裝載到集卡上）。各個(gè)工作的到達(dá)時(shí)間分別為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；集裝箱到達(dá)的箱位為l1=l4=1，l2=l6=5，l3=l5=7，l7=l10=13，l8=15，l9=19；龍門吊的操作一個(gè)集裝箱用時(shí)為240 s，移動(dòng)時(shí)間dij=3×|li-lj|。

利用遺傳算法對(duì)算例進(jìn)行求解，得到運(yùn)算結(jié)果如表1所示。龍門吊1的工作順序?yàn)?-4-6-7-10，對(duì)應(yīng)的箱位為1-1-5-13-13；龍門吊2的工作順序?yàn)?-3-5-8-9，對(duì)應(yīng)的箱位為5-7-7-15-19。集卡最小等待總時(shí)長(zhǎng)為312 s，最早完成時(shí)間為1 680 s。

表1 算例運(yùn)算結(jié)果

圖6為龍門吊在這10個(gè)工作時(shí)段的運(yùn)動(dòng)軌跡（如龍門吊1的軌跡，第一個(gè)拐點(diǎn)表示龍門吊1離開(kāi)箱位3，第二個(gè)拐點(diǎn)表示龍門吊1到達(dá)箱位5），可以更為直觀地看出龍門吊所處的位置以及最早結(jié)束時(shí)間。

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

圖6 龍門吊移動(dòng)軌跡圖

圖7 基于文獻(xiàn)[9]模型的龍門吊軌跡圖

最終求得其最早完成時(shí)間為1 680 s，與本文模型計(jì)算的結(jié)果相同；最小等待時(shí)間是324 s，大于本文模型的結(jié)果312 s。可以看出，本文的模型比單純考慮龍門吊空間位置干擾的模型更能提高龍門吊工作效率。

6 結(jié)論

在集裝箱碼頭的物流作業(yè)中，堆場(chǎng)龍門吊調(diào)度問(wèn)題是一個(gè)非常重要的環(huán)節(jié)。本文整體考慮龍門吊在時(shí)間和空間上的相互影響，其結(jié)果更加接近現(xiàn)實(shí)情況，有助于提高碼頭效率。

本文的創(chuàng)新點(diǎn)在于利用龍門吊工作時(shí)間上的重合以及空間位置約束來(lái)確定龍門吊的工作位置。一方面避免了人為規(guī)定工作時(shí)間段對(duì)龍門吊調(diào)度的影響，另一方面避免了單純考慮空間位置的干擾而給龍門吊工作位置的選擇帶來(lái)更大的限制。最后，由于模型的復(fù)雜性，引入遺傳算法進(jìn)行求解，縮短了求解時(shí)間并得到了滿意結(jié)果。

[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.