徐建峰 胡 靜

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

2 需量控制方法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟1：當(dāng)過(guò)程開(kāi)始時(shí)，令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′過(guò)程結(jié)束。

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

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

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

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

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

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

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

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

4 應(yīng)用案例

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

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

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

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

5 總結(jié)

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