□ 欒 晨 □ 韓笑樂

同濟(jì)大學(xué)機(jī)械與能源工程學(xué)院 上海 201804

1 研究背景

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

2 問題描述

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

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

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

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

3 建模

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

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

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

Tj為AGV從任務(wù)j接貨點(diǎn)行駛至送貨點(diǎn)所需的時間。

Sij為AGV從任務(wù)i送貨點(diǎn)行駛至任務(wù)j接貨點(diǎn)所需的時間。

HP為接貨的任務(wù)交接時間。

HD為送貨的任務(wù)交接時間。

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

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

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

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

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

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

模型中的決策變量如下：

sj為任務(wù)j的接貨時間。

cj為任務(wù)j的送貨時間。

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

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

模型中的約束如下：

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

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

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

4.1 自適應(yīng)遺傳算法流程

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

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

（4）若φ＞δ，表明當(dāng)前全局最優(yōu)解未改進(jìn)，調(diào)用重啟機(jī)制。

（5）計(jì)算每個個體的適應(yīng)度值，輪盤賭方式選擇新的個體。

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

（7）計(jì)算每個個體新的目標(biāo)值。

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

▲圖1 算法整體框架

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

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

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

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

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

（4）計(jì)算cj。若Crane l2的前序任務(wù)為接貨，則cj=max若 Crane l2的前序任務(wù)為送貨，則

（5）計(jì)算所有可用AGV對應(yīng)的sj和cj，找出cj最小且編號靠前的AGV，作為該任務(wù)的運(yùn)輸車輛。

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

（7） 更新 MV、MC、任務(wù)開始時間矩陣 Ms、任務(wù)結(jié)束時間矩陣Me。

（8）判斷是否完成全部任務(wù)，是則停止，返回最后任務(wù)的結(jié)束時間；否則，轉(zhuǎn)第（1）步。

4.3 任務(wù)生成子算法

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

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

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

（3） 令 s+1，轉(zhuǎn)第（2）步。

（4）若a=n，則任務(wù)順序確定，任務(wù)選擇結(jié)束；否則，令 s=1，轉(zhuǎn)第（2）步。

4.4 任務(wù)并行子算法

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

（1） 若 b＞0，轉(zhuǎn)第（2）步；否則，轉(zhuǎn)第（6）步。

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

（4） 若 i≤b-2，轉(zhuǎn)第（2）步；否則，結(jié)束。

（5）消除當(dāng)前任務(wù)已經(jīng)選定的AGV信息，依據(jù)更新的sj和cj重新選擇AGV。

5 試驗(yàn)與結(jié)果分析

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

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

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

表1 試驗(yàn)結(jié)果

6 結(jié)論

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