自動化集裝箱碼頭裝卸系統的協同調度優化*

□ 欒 晨 □ 韓笑樂

同濟大學機械與能源工程學院 上海 201804

1 研究背景

自動化集裝箱碼頭因安全性、可靠性、作業效率和場地利用效率高，環境友好，以及人力成本低等顯著優點，已在世界很多港口實現應用。自動導引車（AGV）、岸邊吊橋（QC）、場地吊橋（YC）作為核心裝卸運輸設備，三者間的協同作業效率對自動化集裝箱碼頭的整體效率有至關重要的影響，因此關于碼頭裝卸系統調度的研究和應用，也一直受到業界關注。在現有的文獻［1-6］中，大部分研究僅針對單類或兩類設備進行調度，并假設其它設備不構成瓶頸，這一假設與實際情況存在差異。另有部分研究［7-14］考慮了三類設備的集成調度，但僅設定單裝單卸作業模式，不能有效提升雙循環操作下的設備利用率。針對這一現狀，筆者研究了三類設備的裝卸混合作業模式，考慮裝卸任務的并行操作、任務間順序約束和雙循環作業，通過建立數學規劃模型和設計啟發式算法，對三類設備的集成調度進行優化，以提高自動化集裝箱碼頭裝卸系統整體的協同作業效率。

2 問題描述

在自動化集裝箱碼頭裝卸作業過程中，將集裝箱任務經過QC、AGV和YC，并運送至堆場的過程稱為一個卸載過程。反之，將集裝箱任務經過YC、AGV和QC，并運送至船舶的過程稱為一個裝載過程。由于在裝卸系統中沒有設置緩沖區，設備間在任務交接時可能存在互相等待。考慮到在裝卸系統調度問題中QC和YC的對稱性，將此兩類設備統一稱為Crane，以簡化模型表述。對其它問題設置進行描述。

（1）作業任務。已知信息包括裝卸箱的運輸起始點、裝載量，集裝箱任務之間存在預定義順序約束。

（2）時間參數。所有固定時間設定為常量，可變時間設置為起始點與目的點之間距離的正比，不考慮不同轉運設備之間的運行速率差異。

（3）資源配置。AGV的數量和位置已知，假定QC裝卸任務時間恒定，任意車道及任意QC之間通行時間已知，同一堆場或岸橋既有卸載任務的集裝箱，也有裝載任務的集裝箱。

3 建模

N=｛0，1，...，i，j，...，n，n+1｝，為任務集合,包括了虛擬的初始和終止變量：0，n+1。

V=｛1，...，k，|V|｝，為 AGV 集合。

C=｛1，...，l，...，|C|｝，為 Crane 集合，包括 QC、YC。

Tj為AGV從任務j接貨點行駛至送貨點所需的時間。

Sij為AGV從任務i送貨點行駛至任務j接貨點所需的時間。

HP為接貨的任務交接時間。

HD為送貨的任務交接時間。

Dijl為Crane l上連續任務i和j的時間差，存在以下四種情況：

（1）i為接貨，j為接貨，為一次取箱的往返時間；

（2）i為接貨，j為送貨，為取箱完成后繼續送箱時間，可視為0；

（3）i為送貨，j為接貨，為送箱并取箱往返的時間，屬雙循環；

（4）i為送貨，j為送貨，為一次送箱的往返時間。

建模時，設M為足夠大的數。

模型中的決策變量如下：

sj為任務j的接貨時間。

cj為任務j的送貨時間。

模型中的目標函數為：

筆者所研究問題的目標是總運輸時間最少化。由于任務具有連續性，因此最后一個虛擬終止任務的結束時間即為總運輸時間。

模型中的約束如下：

式（2）表示每個任務只能由一臺AGV完成。式（3）～式（5）表示 x、y、z、u 的關系。 式（6）～式（9）保證每臺AGV先完成任務0，最后完成任務n+1。式（10）、式（11）限制每個任務前后有且只有一個任務。式（12）表示每臺AGV依次連續完成各個任務。式（13）和式（14）表示任務的接貨時間選取接貨點處Crane和AGV可用時間中的大值。式（15）和式（16）表示任務的送貨時間選取送貨點處Crane和AGV可用時間中的大值。式（17）～式（23）表示 Crane的調度約束，類似于 AGV的調度約束。

4 算法設計

基于遺傳算法搜索框架進行定制化算法設計。染色體編碼為任務的初始執行順序，遺傳操作、適應度函數及自適應算法采用文獻［15］中的方法。解碼采用基于任務順序約束與染色體編碼任務序列的啟發式算法：結合任務順序約束和染色體編碼任務序列運用啟發式算法確定任務執行順序，順序確定后對QC、YC和AGV進行協同調度，逐步安排所有任務。算法整體框架如圖1所示。

4.1 自適應遺傳算法流程

給定初始參數，包括最大迭代步數λmax、當前迭代步數λ、群體規模n、交叉概率Pc、變異概率Pm、當前全局最優解未發生變化的代數φ、判斷是否發生早熟的閾值δ。遺傳迭代中第λ代群體中第k個染色體用表示，第λ代群體中的最優解稱為當代最優解，算法截至第λ代得到的最優解為當前全局最優解xbest。

（2） 判斷 λ 是否≤λmax，若是，轉第（3）步；否則，轉第（9）步。

（4）若φ＞δ，表明當前全局最優解未改進，調用重啟機制。

（5）計算每個個體的適應度值，輪盤賭方式選擇新的個體。

（6）計算Pc和Pm，對種群中的個體進行交叉和變異。

（7）計算每個個體新的目標值。

（8） 得到新一代種群，令 λ+1，轉第（2）步。

▲圖1 算法整體框架

（9） 滿足終止條件，輸出 xbest。

4.2 啟發式算法流程

（1）執行任務生成子算法，得到當前需要執行的任務 j。

（2）計算sij。由AGV前序任務矩陣MV確定該AGV前序任務的Crane l2，計算與本任務的Crane l1的距離，由距離計算出時間。

（3）計算sj。 根據 MV、Crane前序任務矩陣 MC得出 cj，若 Crane l1前序任務為接貨，則若 Crane l1前序任務為送貨，則 sj=max（ci1+

（4）計算cj。若Crane l2的前序任務為接貨，則cj=max若 Crane l2的前序任務為送貨，則

（5）計算所有可用AGV對應的sj和cj，找出cj最小且編號靠前的AGV，作為該任務的運輸車輛。

（6）執行任務并行子算法，得到修正的sj和cj，以及更新的AGV信息。

（7） 更新 MV、MC、任務開始時間矩陣 Ms、任務結束時間矩陣Me。

（8）判斷是否完成全部任務，是則停止，返回最后任務的結束時間；否則，轉第（1）步。

4.3 任務生成子算法

任務執行順序編碼為｛x1，x2，...，xn｝，已經安排任務數為a，預定義任務間順序約束為Pij，記錄已經安排任務的數組為P。

（1） 在｛x1，x2，．．．，xn｝中從 xs任務開始，若令，則執行任務 xs，在 P 中記錄 xs，令 a+1，轉第（4）步；否則，令 s+1，轉第（2）步。

（2） 檢測 xs是否在 P 中，如果不在，轉第（1）步，否則，轉第（3）步。

（3） 令 s+1，轉第（2）步。

（4）若a=n，則任務順序確定，任務選擇結束；否則，令 s=1，轉第（2）步。

4.4 任務并行子算法

在啟發式算法第（1）～第（5）步中，安排相應的AGV完成分配的任務，但是依據Crane前序任務完成后再安排后續任務，不符合實際運作過程出現的并行操作，為此需要修正對應Crane上的任務執行順序。當前任務j接貨點處Crane上已有任務數為b，接貨點處Crane 上已安排任務序列為｛w1，wi，．．．，ws｝。

（1） 若 b＞0，轉第（2）步；否則，轉第（6）步。

（2）從虛擬任務wi開始作為任務j=ws的前序任務，修正sj，判斷任務在當前Crane l1上操作，若是接貨且當前 sj＜swi+1，轉第（3）步；若是送貨且當前 sj＜swi+1，轉第（3）步；否則，令 i+1，重復第（2）步。

（4） 若 i≤b-2，轉第（2）步；否則，結束。

（5）消除當前任務已經選定的AGV信息，依據更新的sj和cj重新選擇AGV。

5 試驗與結果分析

基于典型碼頭配置，筆者設計了9組算例，每組算例計算10個實例，考慮不同的QC、YC、AGV和任務數量，具體規模分別對應為 “1-2-2-10”“1-2-4-10”“1-2-3-6-10”“1-2-2-15”“1-2-4-15”“1-2-6-15”“2-4-6-20”“2-4-8-20”“2-4-10-20”。 參數設置時，QC的新任務取送時間為180 s，YC任務的取送時間滿足［180，540］均勻分布，AGV 滿載和空載的速度都設為10 m/s，在接貨和送貨時都有任務交接時間30 s，裝卸箱任務比例各為50%概率。對于預定義任務順序約束，主要采用約束密度控制的方法［16］來生成，令優先級密度參數ρ=0.4，任務i、j間存在順序約束的概率φij為：

上界采用第一代染色體的最優值作為對比對象，下界采用Cplex優化軟件求出的調度問題精確解作為對比對象，由此能反映算法的實際效果。運行數值試驗的電腦配置為中央處理器頻率3.5 GHz，內存16 GB，編程語言為C#。表1中數據是9組算例的平均結果，并以TGA和TCplex分別表示遺傳算法運算時間和Cplex軟件運算時間。

由表1可知，在不同任務規模下，應用筆者所提出算法得到的結果相比上界有較大提升，平均改善幅度為8.4%。同時對比應用Cplex求解軟件所得出的精確解，最優差距在4%之內。由此可見，筆者提出的算法能很好地安排調度任務。對于實際運作中的實時性要求，TGA相比TCplex有明顯優勢。

表1 試驗結果

6 結論

針對自動化集裝箱碼頭裝卸系統三類設備在裝卸混合模式下的協同調度問題，建立了相應的數學優化模型，并設計基于啟發式的自適應遺傳算法，經試驗驗證，筆者所提出的協同調度方法能為碼頭運作提供有效的調度決策支持。