基于有限狀態(tài)機的調度派車決策支持方法

徐建峰 胡 靜

上海振華重工（集團）股份有限公司 上海 200125

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

2 需量控制方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟1：當過程開始時，令k＝0，G0＝Ei，H0＝0。若K＞0，則轉入步驟2，否則轉入步驟5。

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

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

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

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

式（1）、式（2）相關附加限定條件為

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

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

1）第j臺AGV 已經分配給第i′臺岸橋

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

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

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

式（7）表示1 次調度只派出1 臺AGV 給岸橋。

4 應用案例

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

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

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

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

5 總結

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