徐建峰 胡 靜

上海振華重工（集團(tuán)）股份有限公司 上海 200125

0 引言

對于整個碼頭而言，岸邊集裝箱起重機(jī)（以下簡稱岸橋）的效率并不是單臺的，而是所有作業(yè)岸橋的效率。本文所述方法是使各臺岸橋的自動導(dǎo)航小車（以下簡稱AGV）投放盡量均衡，即在一段時間內(nèi)，首先使各臺岸橋主小車的作業(yè)中斷時間盡量短，然后使各臺岸橋主小車不作業(yè)時間的最小值最大。這個方法就是調(diào)度派車，即將某1 臺無任務(wù)的AGV 分配給最合適的岸橋，執(zhí)行與該岸橋?qū)?yīng)的集裝箱水平運(yùn)輸任務(wù)。調(diào)度是按固定時間間隔執(zhí)行的線程，在每次調(diào)度線程執(zhí)行期間都要給當(dāng)前無任務(wù)的AGV 指定運(yùn)輸任務(wù)，AGV 收到任務(wù)后開始執(zhí)行，執(zhí)行完成后再由另一次調(diào)度線程指定下一個運(yùn)輸任務(wù)。

為了更高效地實(shí)現(xiàn)調(diào)度派車，本文引入了有限狀態(tài)機(jī)。有限狀態(tài)機(jī)（Finite-State Machine，F(xiàn)SM）又稱有限狀態(tài)自動機(jī)，是一種針對系統(tǒng)的數(shù)學(xué)模型，能描述系統(tǒng)在有限個狀態(tài)之間的轉(zhuǎn)移行為、系統(tǒng)在狀態(tài)變化時產(chǎn)生的動作行為。有限狀態(tài)機(jī)模型適用于描述一類狀態(tài)敏感的系統(tǒng)[1]，該類系統(tǒng)具有有限種可能的狀態(tài)，系統(tǒng)的狀態(tài)變化由輸入推動。輸出時間與輸入時間有關(guān)，輸出的內(nèi)容則取決于輸出時的系統(tǒng)狀態(tài)。根據(jù)系統(tǒng)的有限狀態(tài)機(jī)模型，能夠推算出有限狀態(tài)機(jī)模型的輸入-輸出對應(yīng)關(guān)系，且這種對應(yīng)關(guān)系與系統(tǒng)的輸入-輸出對應(yīng)關(guān)系一致。基于以上特性，有限狀態(tài)機(jī)模型可作為針對真實(shí)系統(tǒng)的模擬系統(tǒng)，用于要求真實(shí)系統(tǒng)的場合，如對真實(shí)系統(tǒng)自身測試[2，3]、基于真實(shí)系統(tǒng)的軟件開發(fā)和測試[4，5]等。

1 引入有限狀態(tài)機(jī)

集裝箱碼頭的岸橋主要分單小車岸橋和雙小車岸橋2 大類，其中自動化碼頭主要使用雙小車岸橋，本文著重研究的是雙小車岸橋的AGV 調(diào)度派車決策方法。雙小車岸橋主要由主小車、門架小車以及中轉(zhuǎn)平臺組成，負(fù)責(zé)船與AGV 之間的集裝箱運(yùn)輸，其卸船流程為：主小車負(fù)責(zé)從船上抓箱并放箱到中轉(zhuǎn)平臺，門架小車則負(fù)責(zé)從平臺上抓箱并放箱到AGV；裝船流程為：門架小車負(fù)責(zé)從AGV 上抓箱并放箱到平臺，主小車負(fù)責(zé)從中轉(zhuǎn)平臺上抓箱并放箱到船。

岸橋主小車的作業(yè)過程可以用有限狀態(tài)機(jī)進(jìn)行描述，該狀態(tài)機(jī)僅包含主小車、中轉(zhuǎn)平臺和鉤3 個對象。主小車包含作業(yè)狀態(tài)屬性，可能有裝卸和等待2 個屬性值。中轉(zhuǎn)平臺對象包含2 個屬性，即中轉(zhuǎn)平臺上存放的鉤數(shù)、中轉(zhuǎn)平臺可存放的鉤數(shù)上限。鉤是岸橋的作業(yè)單位，沒有屬性。當(dāng)岸橋單箱裝卸時，一鉤相當(dāng)于一個集裝箱；當(dāng)岸橋雙箱裝卸時，一鉤相當(dāng)于2 個20 ft 集裝箱。該狀態(tài)機(jī)相關(guān)的事件有：

1）主小車作業(yè)開始事件 當(dāng)事件發(fā)生時，主小車的作業(yè)狀態(tài)為裝卸，并令岸橋主小車作業(yè)完成事件在T時間之后發(fā)生。

2）主小車作業(yè)完成事件 當(dāng)事件發(fā)生時，主小車的作業(yè)狀態(tài)為等待。若岸橋正在裝船，則令中轉(zhuǎn)平臺的鉤數(shù)為-1；若此時中轉(zhuǎn)平臺上的鉤數(shù)仍大于零，則立刻觸發(fā)作業(yè)開始事件。若岸橋正在卸船，則令中轉(zhuǎn)平臺的鉤數(shù)為+1；若此時中轉(zhuǎn)平臺上的鉤數(shù)仍小于最大值，則立刻觸發(fā)作業(yè)開始事件。

3）裝船鉤平臺到達(dá)事件 令中轉(zhuǎn)平臺的鉤數(shù)為+1，若此時岸橋主小車的作業(yè)狀態(tài)為等待，則觸發(fā)岸橋主小車的作業(yè)開始事件。

4）卸船鉤平臺離開事件 令中轉(zhuǎn)平臺的鉤數(shù)為-1，若此時岸橋主小車的作業(yè)狀態(tài)為等待，則觸發(fā)岸橋主小車的作業(yè)開始事件。

圖1 為岸橋卸船作業(yè)過程描述，圖中給出了以有限狀態(tài)機(jī)方法描述某岸橋主小車卸船作業(yè)過程的3 個例子，中轉(zhuǎn)平臺上能放的最大鉤數(shù)為2。圖中的箭頭表示時間，單橫線表示主小車的作業(yè)開始事件和作業(yè)完成事件（可能重疊），雙橫線表示卸船鉤平臺離開事件，箭頭左側(cè)的數(shù)字表示中轉(zhuǎn)平臺上的鉤數(shù)，右側(cè)灰色區(qū)域則表示岸橋主小車處于裝卸狀態(tài)的時間。

圖1 以有限狀態(tài)機(jī)描述的岸橋主小車卸船作業(yè)過程圖

圖1 中的3 個過程開始時，岸橋中轉(zhuǎn)平臺上都有1鉤。在過程（1）中，由于未派出AGV，導(dǎo)致無鉤離開平臺，主小車做完1 鉤后就進(jìn)入等待狀態(tài)不再作業(yè)。在過程（2）中，由于AGV 到達(dá)及時，岸橋主小車能連做2 鉤，之后才進(jìn)入等待狀態(tài)不再作業(yè)。在過程（3）中，由于AGV 未及時到達(dá)，主小車做完第1 鉤后作業(yè)發(fā)生中斷，直到卸船鉤離開事件發(fā)生后才能繼續(xù)做1 鉤，之后才進(jìn)入等待狀態(tài)不再作業(yè)。由圖1 推斷，由于主小車作業(yè)可能中斷，影響岸橋作業(yè)情況的因素不僅包括派出AGV 的數(shù)量，還有AGV 的派出時間。

2 需量控制方法

需量方法是按照岸橋作業(yè)路上的鉤數(shù)判斷岸橋?qū)GV 需求迫切程度的方法。作業(yè)路包括岸橋、對岸橋服務(wù)的AGV、對岸橋服務(wù)的堆場起重機(jī)（ASC）等。對于卸船作業(yè)路，可以對主小車、中轉(zhuǎn)平臺、門架小車以及作業(yè)路內(nèi)AGV 上的鉤數(shù)進(jìn)行加權(quán)求和作為指標(biāo)，并以指標(biāo)值作為衡量岸橋?qū)GV 需求程度的依據(jù)，該方法的缺陷是這種指標(biāo)忽略了岸橋主小車的作業(yè)中斷。在岸橋主小車短期將發(fā)生中斷的情況下，按照需量方法判斷得到的岸橋?qū)GV 的需求程度可能與實(shí)際情況不符。對于裝船作業(yè)路，雖然按照需量方法也能在形式上將岸橋?qū)GV 的需求程度計算成數(shù)值，但若正值岸橋裝船或卸船工況，要按照需量方法判斷各臺岸橋?qū)GV 的需求程度，則還需要合理的方法將裝船需量和卸船需量進(jìn)行統(tǒng)一。

圖2 為需量方法判斷結(jié)果與實(shí)際情況不符的缺陷示意圖。在圖2 中，橫向虛線表示與本次派出AGV 有關(guān)的卸船鉤的平臺離開事件的發(fā)生時間，其他符號的含義與圖1 相同。圖中有2 臺岸橋正在進(jìn)行卸船作業(yè)，且在調(diào)度發(fā)生時，2 臺岸橋的中轉(zhuǎn)平臺均已經(jīng)放滿，岸橋正處于等待狀態(tài)。在之前的調(diào)度中，已向岸橋1 派出了1臺AGV，向岸橋2 派出了2 臺AGV。然而，由于岸橋1 的卸船鉤平臺離開事件發(fā)生較晚，反而是岸橋2 首先進(jìn)入等待狀態(tài)不再作業(yè)。如果僅按照需量判斷，很容易得到岸橋1 更需要AGV 的結(jié)果；然而，由于岸橋1 的中斷時間較長，將AGV 派給岸橋2 反而更合理。

圖2 需量方法的缺陷示意圖

3 基于有限狀態(tài)機(jī)的調(diào)度派車決策支持方法設(shè)計

本文在有限狀態(tài)機(jī)基礎(chǔ)上引入事件和狀態(tài)這2 個與時間有關(guān)的因素，形成調(diào)度派車的決策支持方法。該方法假設(shè)：1）同一岸橋的主小車對每個裝船鉤的作業(yè)時間為定值，對每個卸船鉤的作業(yè)時間為定值；2）與已派出AGV 對應(yīng)的裝船鉤中轉(zhuǎn)平臺到達(dá)事件和卸船鉤中轉(zhuǎn)平臺離開事件的發(fā)生時間均可準(zhǔn)確預(yù)計。

在調(diào)度派車決策支持方法設(shè)計中，B為調(diào)度考慮的時間長度；I為可派車的岸橋總數(shù)，各岸橋的編號為i或i′，1 ≤i，i′≤I；Ei為不考慮裝船鉤的中轉(zhuǎn)平臺到達(dá)事件和卸船鉤的中轉(zhuǎn)平臺到達(dá)事件時岸橋i主小車的最后一次作業(yè)完成事件發(fā)生的時間點(diǎn)。

當(dāng)調(diào)度開始時，在考慮主小車吊具和中轉(zhuǎn)平臺上的鉤數(shù)、不考慮卸船箱中轉(zhuǎn)平臺離開事件和裝船箱中轉(zhuǎn)平臺到達(dá)事件的條件下，計算得到岸橋主小車作業(yè)的停止時間。對于裝船岸橋，該時間為中轉(zhuǎn)平臺為空，且岸橋主小車空車回到平臺外等待位的時間；對于卸船岸橋，該時間為中轉(zhuǎn)平臺放滿，且岸橋主小車帶箱回到平臺外等待位的時間。Mi為岸橋i每一鉤作業(yè)的時間；Oi為調(diào)度不考慮的時間長度。

從調(diào)度時刻起，裝船岸橋的裝船箱中轉(zhuǎn)平臺到達(dá)事件的時間一般明顯晚于卸船岸橋的卸船箱平臺離開事件的時間。為了避免出現(xiàn)調(diào)度結(jié)果中AGV 向卸船岸橋過分集中的情況（尤其是裝船岸橋與卸船岸橋同時剛開始做新的WorkQueue 時），本方法對每臺岸橋定義一個時間Oi，并在計算giji′時從計算結(jié)果中扣除。該時間的實(shí)際意義是本次調(diào)度無法對中轉(zhuǎn)平臺造成影響的時間。

對于裝船岸橋，Oi是ASC 出箱時間、ASC 將集裝箱放到AGV 上的交接時間、AGV 從海側(cè)交互車道（WSTP）到岸橋后的緩存停車道（QCPB）的時間的最小值、AGV 從QCPB 到岸橋作業(yè)車道（QCTP）的時間的最小值、門架小車從作業(yè)車道上方空車下降起始到將AGV 上一鉤集裝箱抓起并放至中轉(zhuǎn)平臺為止的時間等的總和。

對于卸船岸橋，Oi是AGV 從當(dāng)前位置到QCTP 的時間的最小值、門架小車從作業(yè)車道上方帶箱下降起始到將一鉤集裝箱放至AGV 上并空車回到中轉(zhuǎn)平臺抓起下一鉤集裝箱為止的時間等的總和。

J為碼頭的AGV 總數(shù)，各個AGV 的編號為j，1 ≤j≤J；Fj為表示本次調(diào)度中第j臺AGV 是否可被派給岸橋的0 ～1 變量。Aij表示本次調(diào)度開始前第j臺AGV 對應(yīng)的鉤是否正在向第i臺岸橋中轉(zhuǎn)平臺移動的0 ～1 變量，若已將第j臺AGV 派給裝船岸橋i，且對應(yīng)的裝船鉤平臺到達(dá)事件尚未發(fā)生，則令A(yù)ij＝1，否則Aij＝0。若已將第j臺AGV 派給卸船岸橋i，且對應(yīng)的卸船鉤平臺到達(dá)事件尚未發(fā)生，則令A(yù)ij＝1，否則Aij＝0。Tij為第i臺岸橋與第j臺AGV 對應(yīng)的卸船鉤平臺到達(dá)事件或裝船鉤平臺離開事件的發(fā)生時間。

在調(diào)度時，每臺已分配給岸橋的AGV 總是處在某種狀態(tài)，且在卸船箱中轉(zhuǎn)平臺離開事件或裝船箱中轉(zhuǎn)平臺到達(dá)事件發(fā)生前還會依次經(jīng)歷若干種狀態(tài)。假設(shè)AGV處于某一種狀態(tài)的時間長度總是可以估計的，已知AGV進(jìn)入當(dāng)前狀態(tài)的時間，即可由此推斷出卸船箱中轉(zhuǎn)平臺離開事件或裝船箱中轉(zhuǎn)平臺到達(dá)事件的發(fā)生時間。

事件的發(fā)生時間可以按照如下方式計算：首先對AGV 所有未經(jīng)歷的狀態(tài)的時間求和（S1）；然后若當(dāng)前時刻到AGV開始當(dāng)前狀態(tài)的時間小于當(dāng)前狀態(tài)的時間，則將二者的差值（S2）加到上一步的求和結(jié)果上（形成S3），再從調(diào)度時間往后推相應(yīng)的時間（S3）即可。hiji′為將第j臺AGV 派給第i臺岸橋后，岸橋i′主小車作業(yè)中斷的總時間；giji′為將第j臺AGV 派給第i臺岸橋后，岸橋i′主小車不再作業(yè)的時間點(diǎn)；fij為將第j臺AGV 派給第i臺岸橋后，對應(yīng)決策方案的評價值；決策變量xij為若本次調(diào)度將第j臺AGV 派給岸橋i，則有xij＝1，否則xij＝0；因變量Liji′為本次調(diào)度將第j臺AGV 派給第i臺岸橋之后，岸橋i′的所有卸船鉤平臺到達(dá)事件或裝船鉤平臺離開事件發(fā)生時間的集合。

調(diào)度派車決策的目標(biāo)是找到令評價值最小的派車方法，主要考慮的因素是岸橋的作業(yè)中斷時間最小，次要的目標(biāo)是岸橋的最早作業(yè)停止時間到調(diào)度時間范圍終點(diǎn)的時間最小。目標(biāo)函數(shù)設(shè)計公式為

式中：ω為常數(shù)，且有ω＞＞1。

最晚岸橋主小車作業(yè)完成事件發(fā)生時間的計算方法為

式（2）中的hiji′和giji′可以用參數(shù)B、Ei、Mi、Oi和Liji′進(jìn)行計算，計算過程中的K為集合Liji′中的元素個數(shù)；pk為集合Liji′的第k個元素，此處1 ≤k≤K；Gk為第k步迭代后的不再作業(yè)時間，0 ≤k≤K；Hk為第k步迭代后的中斷時間，0 ≤k≤K。

步驟1：當(dāng)過程開始時，令k＝0，G0＝Ei，H0＝0。若K＞0，則轉(zhuǎn)入步驟2，否則轉(zhuǎn)入步驟5。

步驟2：將Liji′中的元素按由小到大的順序排列，形成元素序列p1～pK。令k＝1，轉(zhuǎn)入步驟3。

步驟3：若pk≤Gk-1，則令Gk＝Gk-1+Mi，令Hk＝Hk-1；否則，令Gk＝pk+Mi，令Hk＝Hk-1+pk～Gk-1。轉(zhuǎn)入步驟4。

步驟4：若k＜K，則令k＝k+1，轉(zhuǎn)入步驟3；否則，轉(zhuǎn)入步驟5。

步驟5：另giji′＝max(0，GK-Oi)，令hiji′＝HK，輸出giji′和hiji′過程結(jié)束。

式（1）、式（2）相關(guān)附加限定條件為

式（3）表示所有的AGV 均不可能同時處于“可以派給岸橋”和“鉤事件尚未到達(dá)中轉(zhuǎn)平臺”這2 種狀態(tài)，且可能不屬于這2 種狀態(tài)中的任意一種。

式（4）表示任意1 臺AGV 在判斷Ti′j是否屬于Liji′時，只要滿足以下2 個條件之一即可：

1）第j臺AGV 已經(jīng)分配給第i′臺岸橋

2）第j臺AGV 在本次調(diào)度中被分配給第i′臺岸橋

式（5）表示第j臺AGV 不可以被調(diào)度時，不能將其派給岸橋。

式（6）表示無論如何分配，都不應(yīng)使岸橋的不再作業(yè)時間超出調(diào)度考慮的范圍。

式（7）表示1 次調(diào)度只派出1 臺AGV 給岸橋。

4 應(yīng)用案例

到目前為止，該調(diào)度派車決策方法已實(shí)施于自動化碼頭項(xiàng)目中，其中碼頭A 和碼頭B 已投入商業(yè)運(yùn)營，其調(diào)度優(yōu)化效率如表1 所示。

表1 調(diào)度優(yōu)化效率表

在表1 中，優(yōu)化前時間點(diǎn)是指項(xiàng)目開始調(diào)度優(yōu)化前的時間點(diǎn)；優(yōu)化前效率是指調(diào)度優(yōu)化前碼頭岸橋設(shè)備作業(yè)的平均效率；優(yōu)化后時間點(diǎn)是指調(diào)度派車決策方法應(yīng)用并調(diào)優(yōu)后的時間點(diǎn)；優(yōu)化后效率是指調(diào)度派車決策方法應(yīng)用并調(diào)優(yōu)后岸橋設(shè)備作業(yè)的平均效率；效率提升百分比是指調(diào)度派車決策方法應(yīng)用并調(diào)優(yōu)后岸橋作業(yè)效率的提升百分比。引入調(diào)度派車決策方法后，調(diào)度系統(tǒng)在分配AGV 和岸橋作業(yè)時序控制上始終保障了岸橋的作業(yè)中斷時間最小以及岸橋的最早作業(yè)停止時間到調(diào)度時間范圍終點(diǎn)的時間最小，因而作業(yè)效率能得到較大的提升。效率提升百分比的計算方式為

根據(jù)表1 所示，由于調(diào)度派車決策方法的引入，為碼頭A 的作業(yè)效率提高了7 個Move/h，效率提升百分比約為31.8%；為碼頭B 的作業(yè)效率提高了6 個Move/h，效率提升百分比約為28.6%。以上案例說明，調(diào)度派車決策方法的投入使用，能夠極大提升自動化碼頭的生產(chǎn)作業(yè)效率，也幫助公司大大縮短了項(xiàng)目交付時長。

5 總結(jié)

本文在有限狀態(tài)機(jī)的基礎(chǔ)上設(shè)計了1 套調(diào)度派車決策的方法，大大縮減了岸橋的中斷時間及其最早作業(yè)停止時間至調(diào)度時間范圍終點(diǎn)的時間，使岸橋和AGV 等設(shè)備更加有節(jié)奏地均勻分布作業(yè)，極大地提升了碼頭岸橋作業(yè)的整體效率。