□ 欒 晨 □ 韓笑樂

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

1 研究背景

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

2 問題描述

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

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

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

（3）資源配置。AGV的數(shù)量和位置已知，假定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上連續(xù)任務i和j的時間差，存在以下四種情況：

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

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

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

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

建模時，設M為足夠大的數(shù)。

模型中的決策變量如下：

sj為任務j的接貨時間。

cj為任務j的送貨時間。

模型中的目標函數(shù)為：

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

模型中的約束如下：

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

4 算法設計

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

4.1 自適應遺傳算法流程

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

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

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

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

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

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

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

▲圖1 算法整體框架

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

4.2 啟發(fā)式算法流程

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

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

（3）計算sj。 根據(jù) 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）執(zhí)行任務并行子算法，得到修正的sj和cj，以及更新的AGV信息。

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

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

4.3 任務生成子算法

任務執(zhí)行順序編碼為｛x1，x2，...，xn｝，已經(jīng)安排任務數(shù)為a，預定義任務間順序約束為Pij，記錄已經(jīng)安排任務的數(shù)組為P。

（1） 在｛x1，x2，．．．，xn｝中從 xs任務開始，若令，則執(zhí)行任務 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 任務并行子算法

在啟發(fā)式算法第（1）～第（5）步中，安排相應的AGV完成分配的任務，但是依據(jù)Crane前序任務完成后再安排后續(xù)任務，不符合實際運作過程出現(xiàn)的并行操作，為此需要修正對應Crane上的任務執(zhí)行順序。當前任務j接貨點處Crane上已有任務數(shù)為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）消除當前任務已經(jīng)選定的AGV信息，依據(jù)更新的sj和cj重新選擇AGV。

5 試驗與結果分析

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

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

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

表1 試驗結果

6 結論

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