動態接力點模式下雙自動化軌道吊協調調度

邱亞　梁承姬　張悅

摘要：為提高自動化集裝箱碼頭堆場中自動化軌道吊（automated stacking crane，ASC）的作業效率，研究箱區動態接力點對雙ASC作業效率的影響。考慮雙ASC作業過程中的安全距離、相互沖突等因素，建立以最小化雙ASC最長完工時間為目標的混合整數規劃模型，利用遺傳算法對該模型進行求解。與固定貝位接力模式進行對比，結果表明，相較于固定貝位接力模式，動態接力點模式下雙ASC的作業效率更高。在不同規模算例背景下，將遺傳算法與CPLEX的計算結果進行對比，驗證了遺傳算法的有效性。

關鍵詞：自動化集裝箱碼頭; 自動化軌道吊; 動態接力點; 遺傳算法

中圖分類號：? U691.3

文獻標志碼：A

Coordination scheduling of twin automated stacking cranes under dynamic relay point mode

QIU Ya， LIANG Chengji， ZHANG Yue

（Institute of Logistics Science & Engineering， Shanghai Maritime University， Shanghai 201306， China）

Abstract：

In order to improve the operation efficiency of automated stacking cranes （ASCs） in the automated container terminal yards， the influence of dynamic relay points in the block on the operation efficiency of twin ASCs is studied. Considering the safety distance and conflicts in the operation process of twin ASCs， a mixed integer programming model aiming at minimizing the longest completion time of twin ASCs is established， which is solved by the genetic algorithm. Compared with the fixed shell relay mode， the results show that the twin ASCs are more efficient under the dynamic relay point mode. In the background of different scale examples， the calculation results from the genetic algorithm and CPLEX are compared to verify the effectiveness of the genetic algorithm.

Key words：

automated container terminal; automated stacking crane; dynamic relay point; genetic algorithm

0 引 言

集裝箱運輸的高速發展正在改變世界港口、船舶和裝卸工藝的傳統格局。與傳統集裝箱碼頭不同，自動化集裝箱碼頭的堆場采用垂岸式的布局，每個箱區有兩臺自動化軌道吊（automated stacking crane， ASC）分別負責海側和陸側作業。因此，ASC與自動導引小車 （automated guided vehicle， AGV）或外集卡的交接只能發生在箱區的兩端。隨著集裝箱碼頭的發展，碼頭作業效率的瓶頸已經從碼頭前沿轉移到了后方的堆場。ASC是堆場中主要的調度設備，其作業效率很大程度上影響了堆場的作業效率。考慮到本文所研究的并行式雙ASC之間不可相互穿越的特性，對雙ASC實行合理高效的調度是非常有必要的。

國內外學者對傳統碼頭場橋和自動化集裝箱碼頭ASC的調度做了很多的研究。初良勇等[1]考慮場橋作業的時間及成本，建立了集裝箱場橋的智能調度優化數學模型，并設計了基于遺傳算法（genetic algorithm，GA）的模型求解策略。劉志雄等[2]針對多場橋調度問題，提出一種混合演化策略算法，通過與其他算法的結果對比，證明了該算法在優化多場橋調度問題時的有效性。CHANG等[3]為實現場橋全局最優調度，提出一種新的動態滾動范圍決策策略，并用啟發式算法和仿真模型的計算結果驗證了所提方法的有效性和效率。裴磊磊等[4]在考慮ASC之間協調性、交接區容量限制的基礎上，采用GA與仿真相結合的方法對混合整數模型進行求解，得出最短的作業總時間和最小的ASC間行駛距離之差。盧毅勤[5]考慮了AGV的行駛速度和ASC作業時間的不確定性，建立了AGV與ASC的聯合調度優化模型，并采用改進的粒子群優化算法進行求解。HE等[6]考慮了船舶到達時間的不確定性，研究了任務組到達時間和處理量不確定情況下場橋的調度問題。CARLO等[7]針對并行式雙ASC在作業過程中發生沖突時的優先級問題提出了14條優先級規則，并量化所選優先級規則的影響，得出最優的優先級規則組合。NG等[8]研究了同一箱區多場橋作業相互干擾的問題，并開發了一種基于動態規劃的啟發式算法來解決場橋的調度問題。PARK等[9]為提高ASC的作業效率，在考慮翻箱的情況下，提出了基于啟發式算法和局部搜索的雙ASC實時調度方法，以實現AGV和外集卡的等待時間最短的目標。鄭紅星等[10]設計了混合和聲模擬退火算法，并采用實時預倒箱來降低倒箱對場橋作業的影響，以此減少船舶裝船作業時間。徐飛慶[11]將場橋調度問題轉化為一個基于軟時間窗的車輛路徑優化問題，在考慮節能減排的基礎上，實現場橋調度過程中能耗成本和延誤成本最低的目標。SHA等[12]從低碳角度探討場橋調度問題，提出了一種整數規劃模型，以最小化場橋的總能耗。

針對接力區的研究如下：黃繼偉等[13]為解決雙ASC存取箱作業沖突問題，在箱區內設置接力區，最小化雙ASC最長完工時間，并用GA進行求解。KRESS等[14]研究了在ASC不可相互穿越的條件下，在箱區內設置接力區，并提出一種動態規劃算法和相關的波束搜索啟發式算法進行求解。GHAREHGOZLI等[15]為研究堆場內接力區的設置對ASC作業的影響，以最小化ASC的完工時間或等待時間為目標，對接力區集裝箱堆放位置以及接力區的有無、大小、數量等展開研究。

已有的研究多數針對固定貝位接力模式，而很少考慮不同接力模式對ASC作業效率的影響。本文采用動態接力點的雙ASC接力模式對進出口集裝箱進行作業調度。在對雙ASC的調度研究中，以最小化雙ASC的最長完工時間為目標，建立混合整數規劃模型，用GA和CPLEX對不同規模算例進行求解，并與固定貝位接力模式的調度結果進行對比。

1 問題描述

在自動化集裝箱碼頭，ASC只能在箱區的兩端與AGV或外集卡進行交接作業。為提高ASC的利用率，避免雙ASC出現忙閑不一的情況，對雙ASC實行有效的調度就顯得尤為重要。由于本文所研究的雙ASC不可相互穿越，在已有的固定貝位接力模式下，接力點固定在箱區的中間，雙ASC的作業范圍受到限制，只能在接力區的某一側進行作業。然而，在動態接力點模式下，接力點不固定，陸側ASC可到海側作業，海側ASC也可到陸側作業。

雙ASC的動態接力點模式可分解為兩個階段：第一階段，一側ASC將需要接力的任務箱放至動態接力點，這個階段為主作業;第二階段，另一側ASC從動態接力點提走任務箱并放至目標位置，這個階段為接力作業。在雙ASC的動態接力過程中，如果任務箱的起點和終點在箱區的同一側（即都在圖1虛線的左側或右側），那么這個任務箱由該側的ASC獨立完成;如果任務箱的起點和終點不在箱區的同一側，那么就需要ASC接力完成，即海側（陸側）ASC將任務箱放至動態接力點，陸側（海側）ASC結束正在進行的任務后去完成接力任務。

相較于已有的固定貝位接力，本文研究的雙ASC動態接力體現在接力點的不固定上。如果某側ASC有任務箱a需要接力，找到該ASC的下一個任務箱b所在位置，將a箱放至靠近箱區中間位置且與b箱所在位置相隔一個貝位處，這樣就確定了接力點。如圖1所示，以任務箱起點在海側為例，1號箱的起始位置在海側，終點位置在陸側，由于起點與終點不在同側，所以海側ASC將1號箱放至距其下一個任務2號箱一個貝位處，等待陸側ASC過來完成接力，此時海側ASC離開并進行下一個任務作業。起點在陸側的任務箱作業原理相同。在雙ASC作業過程中可能會出現ASC互相干擾的情況，如圖2所示：由于2臺ASC不能相互跨越，且海側作業優先級高于陸側作業優先級，一旦2臺ASC發生作業沖突，海側ASC就優先于陸側ASC進行作業，在此過程中，陸側ASC要與海側ASC保持一定的安全距離。

2 模型建立

本文考慮雙ASC不可跨越以及作業過程中保持安全距離等因素，建立混合整數規劃模型。為得到雙ASC最長完工時間的最小值，假設：（1）接力區存儲空間足夠大;（2）ASC在移動時始終保持勻速，不考慮加速或減速;（3）不考慮ASC小車的移動;（4）ASC提箱與放箱所用的時間一致，并且為固定值;（5）在ASC作業過程中不考慮翻箱;（6）ASC在交接點作業時無須等待。

2.1 符號說明

n為總任務數量;K為ASC的集合，K={1，2}，k∈K;Jk為第k臺ASC的任務集;J為所有ASC的任務集，J=J1∪J2;A為同一任務拆分后的子任務對{i，j}的集合，A={（i，j）|i∈Jk，j∈Jk′，k≠k′};P1為目標箱在初始位置提箱任務的集合;D1為主作業中在接力點放箱任務的集合;P2為接力作業中目標箱在接力點提箱任務的集合;D2為接力作業中目標箱在目的地放箱任務的集合;P=P1∪P2;D=D1∪D2;v為ASC的移動速度;l為單位貝位的長度;si為任務i的開始時刻;ti為任務i的操作完成時刻;B為單箱區總的貝位數，b=1，2，…，B;Tij為ASC從任務i的結束位置移動到任務j的初始位置所需時間，當i=j時，表示ASC從一個任務的起點移動到終點的時間;oi為操作提箱任務i或放箱任務i所需的時間;σ為雙ASC作業的安全距離;bik為ASC k作業任務i時所在的貝位;h（1）i∈{0，1}，若bi1為海側交接點則h（1）i=1，否則h（1）i=0;h（2）i∈{0，1}，若bi2為陸側交接點則h（2）i=1，否則h（2）i=0;M為足夠大的數。

決策變量：x（k）ij∈{0，1}，若ASC k以（i，j）的順序進行作業則x（k）ij=1，否則x（k）ij=0;u（k）i∈{0，1}，若ASC k從任務i開始作業則u（k）i=1，否則u（k）i=0;w（k）i∈{0，1}，若ASC k在任務i結束作業則w（k）i=1，否則w（k）i=0;y（k）tb∈{0，1}，若ASC k在時刻t處于貝位b則y（k）tb=1，否則y（k）tb=0。

2.2 目標函數及約束條件

式（1）是目標函數，表示最小化雙ASC的最長完工時間;式（2）表示每個接力任務的主作業只進行一次操作;式（3）表示每個接力任務的接力作業最多進行一次操作;式（4）和（5）確保ASC 1和ASC 2的移動路徑從箱區的兩端開始，在最后一個任務處結束;式（6）表示ASC從一個任務移動到下一個任務所需要的時間;式（7）表示同一任務的操作完成時刻約束;式（8）保證任務間作業的連續性;式（9）表示任意兩個任務之間的起止時間關系;式（10）表示接力點的提箱操作應當在這個接力點放箱操作完成之后再進行;式（11）和（12）確保一臺ASC每次只能作業一個任務箱;式（13）保證一個任務總的作業時間由ASC的移動時間與操作時間組成;式（14）確保交接點處的任務靠近哪一側就只能由那一側對應的ASC完成;式（15）表示對于由同一任務拆分而來的兩個任務，先完成主作業，后完成接力作業;式（16）保證雙ASC在作業過程中保持安全距離。

3 算法設計

GA是一種常用的元啟發式算法，雙ASC的動態接力問題是NP難問題，而GA對該類問題具有良好的適應性，因此本文采用GA進行求解。

3.1 染色體編碼與解碼

染色體采用實數編碼的形式，整數部分表示集裝箱的任務編號，小數部分表示接力作業的不同階段。染色體長度為任務箱量，即ASC作業任務數。編碼時，首先對ASC和集裝箱任務進行編號，海側ASC編號為1，陸側ASC編號為2。為滿足式（4）和式（5）約束，ASC 1和ASC 2的第一個任務的初始貝位必須是貝位1和貝位42（見第4.1節）。將染色體的前半段設置為需要ASC 1完成的任務，后半段設置為需要ASC 2完成的任務，以滿足式（13）約束。對于不需要接力的任務，一個任務對應一臺ASC，對于需要接力的任務，其作業的2個階段需要2臺ASC共同完成。如圖3所示：7.1表示任務7的第一個階段，由ASC 1完成;7.2表示任務7的第二個階段，由ASC 2完成。

解碼過程分為2個階段，首先根據對應基因位將任務分配至2臺ASC，然后按照任務段中的任務順序依次解碼，得到ASC 1和ASC 2對應的集裝箱作業序列。在圖3所示的染色體中，解碼得到ASC 1的作業序列為{2，7.1，6，10.2，9，8，5}，ASC 2的作業序列為{3，7.2，10.1，1，4}。

3.2 適應度函數

適應度函數為f（u）=1/Cmax，其中Cmax為ASC最長完工時間的最小值。

3.3 遺傳操作

3.3.1 選擇操作

本文的選擇操作采取精英保留的策略，將種群中適應度值大的前10%的個體保留下來，與隨機產生的90%的新個體形成新種群。

3.3.2 交叉操作

由于本文染色體的集裝箱任務部分由海側ASC和陸側ASC完成，所以交叉時也將其分為海側ASC作業序列和陸側ASC作業序列2部分進行交叉，且每個部分都采用雙切點交叉法。根據交叉概率，每次從上一代個體中選擇2個個體作為父代，如圖4a所示：在每個父代個體的海側ASC作業序列部分隨機生成2個交叉點①和②，將這兩個交叉點之間的基因值進行交換;在每個父代個體的陸側ASC作業序列部分隨機生成2個交叉點③和④，也將這兩個交叉點之間的基因值進行交換。得到的新個體見圖4b。

3.3.3 變異操作

本文采用逆轉變異法，即在每臺ASC的作業序列中隨機選2個點，將其基因值進行交換。同樣地，由于染色體的集裝箱任務部分由海側ASC和陸側ASC完成，所以變異時也將其分為海側ASC作業序列和陸側ASC作業序列2部分進行變異。圖5為變異操作示意圖。

3.3.4 修復操作

經過交叉和變異操作后，可能會產生一些不可行的染色體，因此需要進行基因修復。本文設計的基因修復規則如下：

規則1：如果新種群中產生了不滿足式（14）約束的個體，即染色體中出現了接力任務的接力作業開始時間早于主作業的完成時間的情況，則此條染色體需要修復，將相關基因值的位置進行調整。

規則2：對于不需要接力的任務以及由需要接力的任務拆分而來的2個子任務，ASC只能對該任務作業一次，即2臺ASC對應的作業序列中的基因值都各不相同。如果ASC 1或ASC 2對應的染色體作業序列中有2個基因值相同（如圖4b所示），則需要基因修復。修復結果如圖4c所示。

4 算例分析

4.1 參數設置

某自動化集裝箱碼頭的堆場采用兩端式雙ASC的布置，一個箱區有40個貝位，設海側交接點為貝位1，陸側交接點為貝位42，從海側至陸側貝位號依次遞增。海側ASC的起始位置為貝位1，陸側ASC的起始位置為貝位42。2臺同型號的ASC協同作業，在移動過程中保持勻速，并且速度相同，安全距離為1個貝位，放箱操作和提箱操作的時間為70 s。以20個集裝箱任務為例，輸入的數據見表1。

交叉和變異算子對 GA性能有重要影響，問題類型的不同導致算法參數值的選取存在差異。為找到適當的交叉和變異算子的參數值，本文對動態接力點模式下雙ASC的調度問題進行多次實驗。設置種群數量為100，最大迭代次數為100，實驗在Intel（R） Core（TM）i5的處理器、內存4 GB的PC上進行，在MATLAB 2018a平臺上編程實現。實驗結果如表 2 所示：在所有備選參數中，當交叉概率Pc=0.9，變異概率Pm= 0.2時算法性能最佳。在后面的數值實驗中本文將采用此組交叉和變異參數值進行計算。

4.2 兩種模式下的結果分析

4.2.1 動態接力點模式下雙ASC調度結果

圖6為動態接力點模式下ASC的移動路線圖，當雙ASC發生作業沖突時，陸側ASC等待海側ASC完成作業后再進行作業。動態接力點模式下雙ASC的最長完工時間為3 078 s，雙ASC的具體調度結果見表3。圖7為動態接力點模式下調度結果的甘特圖，其中每個矩形兩側的部分是ASC提放箱的時間，中間部分是ASC移動的時間（或移動加等待的時間），任務7～14為接力任務，由2臺ASC共同完成。

4.2.2 固定貝位接力模式下雙ASC調度結果

圖8為固定貝位接力模式下ASC移動路線圖，從圖8可以看出雙ASC在作業過程中未發生沖突，海（陸）側ASC只能在海（陸）側移動，不能到另一側進行作業。固定貝位接力模式下雙ASC的最長完工時間為3 251 s，雙ASC的具體調度結果見表4。圖9為固定貝位接力模式下調度結果的甘特圖。

由表3和4可知，動態接力點模式下雙ASC的完工時間為3 078 s，相較于固定貝位接力模式，雙ASC的作業效率提高了5.3%。從ASC的作業效率看，在相同任務量的情況下，動態接力點模式優于固定貝位接力模式。從圖6和8可以看出，在固定貝位接力模式下，ASC的移動范圍有一定的局限性，而動態接力點模式下ASC的移動范圍沒有局限，這更有利于ASC間的相互協作。在圖7和9中可以更直觀地看出每個任務的作業時間以及ASC間的沖突情況，雖然動態接力點模式中有干擾發生，但ASC整體的完工時間是優于固定貝位接力模式的。

為進一步驗證動態接力點模式的有效性，本文設置不同規模的算例，并用GA和CPLEX對不同作業模式、不同規模的算例進行求解，結果見表5。

從表5可以看出：在不同任務量下，GA和CPLEX求出的ASC完工時間相差不大;由于CPLEX對大規模算例求解較慢，所以當任務量大于等于50時，本文設置CPLEX的求解時間的上限為14 000 s，即運行時間到達14 000 s后，算法停止運行;對于任務量為200的算例，由于CPLEX的內存不足，所以無法在可接受的范圍內求出最優解。通過對比GA和CPLEX的計算結果能夠得出，GA計算出的結果是有效并且能被接受的，可以作為最優解。

5 結 論

本文針對自動化集裝箱碼頭堆場單箱區雙自動化軌道吊（ASC）的接力問題進行了研究。考慮了雙ASC不可跨越以及作業過程中保持安全距離等因素，以最小化雙ASC的最長完工時間為目標，建立混合整數規劃模型，并設計遺傳算法（GA）進行求解。在算例分析部分，本文設計了不同規模的算例，計算結果表明，與固定貝位接力模式相比，在動態接力點模式下雙ASC的最長完工時間更短，作業效率更高。然而，在實際操作中，ASC作業過程中的翻箱以及ASC與自動導引小車（AGV）和外集卡的協調等問題都會影響ASC的作業效率，在后續研究中可以考慮雙ASC與AGV和外集卡的聯合調度，使研究更加具有現實意義。

參考文獻：

[1]初良勇， 阮志毅， 李淑娟. 基于遺傳算法的港口集裝箱堆場場橋智能調度優化[J]. 中國航海， 2018， 41（1）： 48-52.

[2]劉志雄， 李俊， 張煜， 等. 基于混合演化策略算法的多場橋調度優化[J]. 計算機應用與軟件， 2016， 33（5）： 242-247.

[3]CHANG Daofang， JIANG Zuhua， YAN Wei， et al. Developing a dynamic rolling-horizon decision strategy for yard crane scheduling[J]. Advanced Engineering Informatics， 2011， 25： 485-494. DOI： 10.1016/j.aei.2011.02.003.

[4]裴磊磊， 萇道方. 基于仿真優化的自動化集裝箱碼頭雙ARMG調度研究[J]. 廣西大學學報（自然科學版）， 2017， 42（2）： 500-510. DOI： 10.13624/j.cnki.issn.1001-7445.2017.0500.

[5]盧毅勤. 自動化碼頭堆場設備聯合調度不確定優化[J]. 計算機仿真， 2019， 36（8）： 325-328.

[6]HE Junliang， TAN Caimao， ZHANG Yuting， et al. Yard crane scheduling problem in a container terminal considering risk caused by uncertainty[J]. Advanced Engineering Informatics， 2019， 39： 14-24. DOI： 10.1016/j.aei.2018.11.004.

[7]CARLO H J， MARTNEZ-ACEVEDO F L. Priority rules for twin automated stacking cranes that collaborate[J]. Computers & Industrial Engineering， 2015， 89： 23-33. DOI： 10.1016/j.cie.2015.04.026.

[8]NG W C， MAK K L. Yard crane scheduling in port container terminals[J]. Applied Mathematical Modelling， 2005， 29： 263-276. DOI： 10.1016/j.apm.2004.09.009.

[9]PARK T， CHOE R， OK S M， et al. Real-time scheduling for twin RMGs in an automated container yard[J]. OR Spectrum， 2010， 32： 593-615. DOI： 10.1007/s00291-010-0209-0.

[10]鄭紅星， 劉保利， 匡海波， 等. 考慮實時預倒箱的出口箱堆場多場橋調度優化[J]. 中國管理科學， 2018， 26（9）： 85-96. DOI： 10.16381/j.cnki.issn1003-207x.2018.09.009.

[11]徐飛慶. 基于軟時間窗的集裝箱碼頭場橋調度研究[J]. 物流工程與管理， 2016， 38（3）： 23-26. DOI： 10.3969/j.issn.1674-4993.2016.03.008.