基于規(guī)則的環(huán)形穿梭車系統(tǒng)調度算法的應用研究

張可義，徐 健，田 博，向 旺，蔡 苗

（北自所（北京）科技發(fā)展有限公司，北京 100120）

0 引言

環(huán)形穿梭車作為運行在固定軌道上的智能物流設備，在物流倉儲行業(yè)中的應用越來越廣泛。環(huán)形穿梭車系統(tǒng)常用于連接自動化立體倉庫系統(tǒng)和出入庫站臺系統(tǒng)，具有方便快捷和靈活高效的特點，比數(shù)量繁多的直行穿梭車系統(tǒng)和布局復雜的輸送機方案具有更大的優(yōu)勢。而數(shù)量眾多的穿梭車在環(huán)形的固定軌道上運行時，如何盡量避免堵塞、合理地分配穿梭車的作業(yè)則是我們關注的重點。

傳統(tǒng)的調度算法往往通過上位機系統(tǒng)采集信息、依據(jù)算法分析信息、通過特殊軟件計算得出優(yōu)化結果后下發(fā)給穿梭車執(zhí)行作業(yè)任務。面對環(huán)形穿梭車系統(tǒng)的站臺變化快、高速運行時位置信息隨時變化等實際情況，傳統(tǒng)的調度算法模式用時較長，還可能會錯過最佳站臺位置。因為RGV在環(huán)形軌道上大部分時間是在高速運行中，當RGV收到作業(yè)任務時，RGV可能剛剛通過了需響應的作業(yè)站臺位置，可能會錯過一些最優(yōu)路徑的調度作業(yè)，這就要求我們努力尋找一種實時性更好、適應性更強的調度算法。于是，我們提出了基于規(guī)則的環(huán)形穿梭車作業(yè)調度算法，提出了三種作業(yè)調度區(qū)域規(guī)則的概念和一些輔助規(guī)則，通過在PLC控制系統(tǒng)融入這些規(guī)則，從而實現(xiàn)對環(huán)形穿梭車系統(tǒng)作業(yè)的優(yōu)化調度。

1 環(huán)形RGV系統(tǒng)調度算法優(yōu)化的理論分析

環(huán)形RGV一般是在固定的封閉式環(huán)形軌道上單方向運行，根據(jù)輸送系統(tǒng)的布局，設定順時針運行或逆時針運行。環(huán)形RGV系統(tǒng)也多采用單工位類型，能夠實時獲取自身和相鄰RGV的位置、狀態(tài)和作業(yè)情況，沿著軌道一圈可以完成一個或者多個作業(yè)。環(huán)形RGV系統(tǒng)如圖1所示。作為自動化立體倉庫和入出庫站臺的重要樞紐，進行貨物的傳遞和輸送，是自動化物流倉儲系統(tǒng)很重要的組成部分。

圖1 環(huán)形RGV系統(tǒng)

環(huán)形RGV的作業(yè)任務主要包含：取貨、行走和送貨三個過程，完成一個完整作業(yè)時間如下：

式中，t總為RGV一個完整作業(yè)時間，tw為RGV全程行走總時間，包括：加減速運行時間ta，勻速運行時間tc和停車等待時間tp。tl為RGV取貨或送貨輸送時間（二者通常相等且固定不變），t0為RGV的信息交互時間（通常是固定不變的）。

根據(jù)式(1)，一個完整的作業(yè)任務的快慢主要由tw來決定，而tw與行走過程中是否堵塞關系很大，堵塞的次數(shù)越多，停車和減速次數(shù)就越多，必然造成所用時間增多，故要提高環(huán)形RGV系統(tǒng)效率，就得需要合理調度RGV作業(yè)，使得RGV在環(huán)形軌道中運行時，盡可能多和盡可能早的形成作業(yè)，才可能提高環(huán)形RGV系統(tǒng)效率。所以，目標簡化為：作業(yè)次數(shù)多和堵塞次數(shù)少，建模如下：

式中，tc是第c臺RGV在固定時間內作業(yè)次數(shù)，Bc(q)為第c臺RGV在固定時間內因為堵塞而停車等待的次數(shù)，也即堵塞次數(shù)，n為整個軌道上RGV的數(shù)量。

基于以上的理論分析，本文提出的基于規(guī)則的調度算法，也是主要考慮盡量多形成復合作業(yè)和盡量避免堵塞兩個主要方面，當然也考慮了對站臺的預判斷，系統(tǒng)提前響應站臺取貨請求和提前啟動作業(yè)等措施。基于一些特殊的規(guī)則，通過PLC程序對這些規(guī)則進行實現(xiàn)，從而達到提前、快速和及時響應站臺作業(yè)請求，形成調度作業(yè)，執(zhí)行作業(yè)任務。

2 基于規(guī)則的調度算法的實現(xiàn)

在環(huán)形穿梭車系統(tǒng)中，基于規(guī)則的調度算法，是把環(huán)形RGV系統(tǒng)和上位機調度系統(tǒng)的功能融為一體，作為一套獨立的系統(tǒng)，基于一定的規(guī)則，通過PLC控制系統(tǒng)實現(xiàn)調度算法，各個RGV作為智能從站，實時對各個站臺的作業(yè)請求進行智能判斷，根據(jù)算法規(guī)則的優(yōu)先級進行篩選，在具備條件的情況下以最短的時間形成作業(yè)任務，迅速去執(zhí)行，并及時把相關信息傳送給地面主控制器，地面主控制器作為樞紐，進行相鄰RGV或者作業(yè)相關的RGV之間的信息傳遞。各RGV根據(jù)地面主控制器傳遞的相鄰RGV的信息進行避讓和對作業(yè)調度區(qū)域進行調整，PLC控制系統(tǒng)的網(wǎng)絡圖，如圖2所示。

圖2 設備網(wǎng)絡圖

基于規(guī)則的調度算法中，各個RGV會根據(jù)環(huán)形軌道的布局、軌道上RGV數(shù)量和站臺布局等因素進行智能判斷，得出不同區(qū)域RGV與相鄰RGV的最佳距離，也就是說每一臺RGV每次作業(yè)完成后，都會根據(jù)后面相鄰RGV的相關信息，很快?？吭谝粋€最佳位置，以此類推，整個系統(tǒng)各個RGV很快會處于動態(tài)平衡狀態(tài)，整個系統(tǒng)就能夠隨時選擇RGV以最快的速度和最小的距離及時響應任意站臺的作業(yè)請求，同時也能夠避免環(huán)形軌道上的堵塞。

3 作業(yè)調度區(qū)域規(guī)則

基于各個RGV在軌道上的合理動態(tài)分布，選擇了環(huán)形RGV的不同作業(yè)調度區(qū)域作為調度算法的主要規(guī)則，再依據(jù)一些特定的規(guī)則，通過PLC控制系統(tǒng)實現(xiàn)環(huán)形RGV的最優(yōu)調度方案，調度方案是通過各個RGV在特定作業(yè)調度區(qū)域內進行作業(yè)調度，作業(yè)調度區(qū)域主要包括：標準調度區(qū)域、擴展調度區(qū)域和全局調度區(qū)域。

3.1 RGV標準調度區(qū)域

RGV標準調度區(qū)域為前RGV所在位置到本RGV所在位置所覆蓋的區(qū)域，如圖3所示,RGV沿著逆時針單方向運行，RGV1的標準調度區(qū)域為站臺L01-L04之間，RGV2的標準調度區(qū)域為站臺L05-L06之間,RGV3的標準調度區(qū)域為站臺L07-L11之間。標準調度區(qū)域主要體現(xiàn)了調度作業(yè)分配的優(yōu)先近處規(guī)則。環(huán)形RGV根據(jù)一定規(guī)則分布在整個軌道上，所有RGV的標準調度區(qū)域囊括了整個軌道區(qū)域的所有站臺，為每個有作業(yè)請求的站臺都提供了相對均等的機會，也避免了傳統(tǒng)調度算法可能形成同一區(qū)域多個作業(yè)容易導致堵塞的情況。

圖3 RGV標準調度區(qū)域

3.2 RGV擴展調度區(qū)域

在標準調度區(qū)域的基礎上，為了預先更快形成調度作業(yè)，我們提出了RGV擴展調度區(qū)域的概念，如果某個RGV前面的RGV正在執(zhí)行取貨作業(yè)時，后面RGV可以把調度區(qū)域擴展到前RGV取貨作業(yè)站臺位置后面的站臺位置，如圖4所示，比如RGV4正在執(zhí)行從L14站臺的取貨作業(yè)，則RGV3的調度區(qū)域可擴展到如圖4所示的站臺L13的位置，這樣當前面RGV4還在站臺L11-L12位置處，RGV3就可以把調度區(qū)域擴展到站臺L13處，從而提前進行調度作業(yè)，當此時站臺L12或L13處有作業(yè)需求時，能夠預先形成調度作業(yè)，在RGV4前進時，RGV3就同時前進去站臺L12或L13處進行取貨作業(yè)，對站臺請求進行預先判斷，提前形成作業(yè)任務以便提前啟動RGV運行，從而提高系統(tǒng)的整體運行效率。

圖4 RGV擴展調度區(qū)域

3.3 RGV全局調度區(qū)域

在擴展調度區(qū)域的基礎上，我們進一步優(yōu)化提出了RGV全局調度區(qū)域的概念。當RGV相鄰的前面RGV正在作業(yè)時，且已經(jīng)完成了從起始站臺取貨，正在往目的站臺運行時，本RGV調度區(qū)域可以再次擴展到前RGV的優(yōu)化調度臺列（此優(yōu)化調度站臺列與運行的目的地址以及自身前車RGV的位置信息等有關），前車的優(yōu)化調度站臺列可能再次擴展到前車的前車優(yōu)化調度站臺列，以此類推，若前面幾輛車都處于已經(jīng)取完貨正往目的站臺運行的情況，本RGV的調度區(qū)域就可能進一步擴展到環(huán)形軌道很大區(qū)域甚至是擴展到全部區(qū)域，這樣RGV就能更早的捕捉到更大區(qū)域的站臺作業(yè)請求，顯著地提升了環(huán)形RGV系統(tǒng)的作業(yè)效率和響應速度。全局調度區(qū)域體現(xiàn)任務調度的全區(qū)域覆蓋性，也體現(xiàn)了調度任務的更早的預判性。如圖5所示，假如RGV2正在執(zhí)行從站臺L06的取貨作業(yè)，準備送往站臺L19,RGV3正在執(zhí)行從站臺L10取貨，準備送往站臺L18，則RGV1的調度區(qū)域可以擴展到從站臺L01到站臺L11的更大區(qū)域，以此類推，每個RGV均有可能出現(xiàn)調度區(qū)域擴展到全區(qū)域的可能性，從而更早更快的響應站臺的作業(yè)請求。

圖5 RGV全局調度區(qū)域

4 輔助的規(guī)則

除了基于三種調度區(qū)域的規(guī)則外，我們還提出了一些輔助的規(guī)則，通過這些規(guī)則的應用，環(huán)形穿梭車系統(tǒng)各個RGV能夠有條不紊的作業(yè)，有效的避免堵塞和不必要的等待，這些規(guī)則主要包括：調整站臺優(yōu)先級規(guī)則、合理?？繀^(qū)域規(guī)則和空閑不停車區(qū)域規(guī)則。

4.1 調整站臺優(yōu)先級規(guī)則

在調度區(qū)域內，調度站臺的優(yōu)先級是根據(jù)站臺請求的等待時間長短來判斷的，這體現(xiàn)了先進先出的規(guī)則。如圖6所示，假如RGV2的調度區(qū)域為站臺L05-L06，則根據(jù)L05-L06站臺的等待時間最長的站臺優(yōu)先形成調度作業(yè)，假如站臺L05和站臺L06均有作業(yè)請求，而L05等待時間更長，按照本文上面介紹的標準調度區(qū)域的規(guī)則，RGV2應該形成從站臺L05的取貨作業(yè)，若后面RGV1處于空閑狀態(tài)，根據(jù)本文上面介紹的擴展調度區(qū)域規(guī)則，RGV1可能會形成從L06取貨的作業(yè)，若完全按照以上分析的調度規(guī)則執(zhí)行，可能會形成RGV1準備往L06處運行時，RGV2還在站臺L05處取貨，堵塞了RGV1，只能等待RGV2從站臺L05取貨完畢，離開站臺L05，RGV1才能繼續(xù)前進到站臺L06處進行取貨作業(yè)，針對此種情況，我們提出了調整站臺優(yōu)先級的規(guī)則。

圖6 調整站臺優(yōu)先級規(guī)則

當后車空閑時，若本車調度區(qū)域內有兩個或兩個以上的站臺均有取貨作業(yè)請求時，若后面站臺優(yōu)先級高的時候，需要調整前后站臺的優(yōu)先級，先執(zhí)行前面站臺的取貨作業(yè)，以便后車及時過來執(zhí)行后面站臺的取貨作業(yè)，也就是說提前給后車留機會，這樣前車和后車均可以迅速到達這兩個站臺處，同步進行取貨作業(yè)，之后同步向前運行，避免了堵塞，提高了系統(tǒng)整體的作業(yè)效率。

4.2 合理?？繀^(qū)域規(guī)則

為進一步合理布局RGV無作業(yè)時在環(huán)形軌道上的動態(tài)分布，我們還提出了合理停靠區(qū)域規(guī)則。如圖7所示，此環(huán)形RGV沿著軌道逆時針單向運行，根據(jù)合理停靠區(qū)域規(guī)則，我們會調度RGV在出庫作業(yè)區(qū)L19站臺和入庫作業(yè)區(qū)L20站臺之間近距離?？慷噍vRGV，以便入庫站臺L20-L22有取貨請求時，多輛RGV系統(tǒng)能夠及時迅速的形成調度作業(yè)，把入庫站臺L20-L22上的貨物及時快速的取走，從而提高環(huán)形RGV系統(tǒng)效率。

圖7 合理?？繀^(qū)域規(guī)則圖示

4.3 空閑不停車區(qū)域規(guī)則

針對環(huán)形軌道區(qū)域中一些無站臺的區(qū)域和出庫作業(yè)區(qū)域，我們提出了空閑不停車區(qū)域的概念，此區(qū)域范圍有空閑RGV時，繼續(xù)前進以便?？吭诟线m的區(qū)域，避免在個別特殊區(qū)域不該停車時停車，同時能避免需要停車的區(qū)域RGV數(shù)量不足，從而整體及時快速響應站臺取貨請求。如圖8所示，L16和L19的區(qū)域之間就不適合停放空閑的RGV，同樣在L22到L01的區(qū)間也是不適合停放RGV的，此類區(qū)域若有空閑RGV，需及時運行到入出庫站臺之間或者立庫站臺區(qū)域的合適位置。

圖8 空閑不停車區(qū)域規(guī)則圖示

5 工程應用

綜合以上的三種調度區(qū)域和輔助規(guī)則，我們形成了一套基于規(guī)則的調度算法，環(huán)形RGV系統(tǒng)各個RGV能夠根據(jù)站臺布局、前后RGV作業(yè)狀態(tài)及站臺作業(yè)情況等因素，合理調度作業(yè)、合理?？吭诃h(huán)形軌道的最佳位置，更早更快的響應站臺的作業(yè)請求，大大的提高了環(huán)形RGV的系統(tǒng)效率。

在某化纖企業(yè)成品立體倉庫中的應用中，環(huán)形軌道長度248米，其中直道230米，彎道18米，站臺33個，環(huán)形RGV共設置8臺RGV，環(huán)形軌道直道速度120米/分鐘，彎道24米/分鐘，輸送機速度16米/分鐘，托盤交接輸送距離1.6米，托盤輸送方向為1.2米，RGV與站臺交接響應時間0.5秒。

根據(jù)式(5)，得出t總=tw+12.5

tw=0.5秒，tl=1.6/16×60秒=6秒，2tl+t0=12.5秒，一個完整作業(yè)時間主要取決于tw的值。

根據(jù)式(6)計算能得到行走時間。經(jīng)現(xiàn)場實際測試，采用了基于規(guī)則的調度算法后，實測的12小時的均值為320托/小時，原有系統(tǒng)的實測12小時均值為238托/小時，效率提高了34.5%。

這種基于規(guī)則的環(huán)形穿梭車調度算法，后經(jīng)在多個項目的運行測試，具有一定的實用性和穩(wěn)定性。作為一個獨立的系統(tǒng)，通過PLC控制系統(tǒng)來實現(xiàn)調度作業(yè)，基于特定的規(guī)則，脫離了上位機調度系統(tǒng)，避免了復雜的智能算法和實效性差的弊端，既為企業(yè)節(jié)約了成本，又滿足了系統(tǒng)對高實時性的要求，使得效率得到了很大的提升，合理的滿足了項目的需求。