基于規則的環形穿梭車系統調度算法的應用研究

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

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

0 引言

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

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

1 環形RGV系統調度算法優化的理論分析

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

圖1 環形RGV系統

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

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

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

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

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

2 基于規則的調度算法的實現

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

圖2 設備網絡圖

基于規則的調度算法中，各個RGV會根據環形軌道的布局、軌道上RGV數量和站臺布局等因素進行智能判斷，得出不同區域RGV與相鄰RGV的最佳距離，也就是說每一臺RGV每次作業完成后，都會根據后面相鄰RGV的相關信息，很快停靠在一個最佳位置，以此類推，整個系統各個RGV很快會處于動態平衡狀態，整個系統就能夠隨時選擇RGV以最快的速度和最小的距離及時響應任意站臺的作業請求，同時也能夠避免環形軌道上的堵塞。

3 作業調度區域規則

基于各個RGV在軌道上的合理動態分布，選擇了環形RGV的不同作業調度區域作為調度算法的主要規則，再依據一些特定的規則，通過PLC控制系統實現環形RGV的最優調度方案，調度方案是通過各個RGV在特定作業調度區域內進行作業調度，作業調度區域主要包括：標準調度區域、擴展調度區域和全局調度區域。

3.1 RGV標準調度區域

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

圖3 RGV標準調度區域

3.2 RGV擴展調度區域

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

圖4 RGV擴展調度區域

3.3 RGV全局調度區域

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

圖5 RGV全局調度區域

4 輔助的規則

除了基于三種調度區域的規則外，我們還提出了一些輔助的規則，通過這些規則的應用，環形穿梭車系統各個RGV能夠有條不紊的作業，有效的避免堵塞和不必要的等待，這些規則主要包括：調整站臺優先級規則、合理停靠區域規則和空閑不停車區域規則。

4.1 調整站臺優先級規則

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

圖6 調整站臺優先級規則

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

4.2 合理停靠區域規則

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

圖7 合理停靠區域規則圖示

4.3 空閑不停車區域規則

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

圖8 空閑不停車區域規則圖示

5 工程應用

綜合以上的三種調度區域和輔助規則，我們形成了一套基于規則的調度算法，環形RGV系統各個RGV能夠根據站臺布局、前后RGV作業狀態及站臺作業情況等因素，合理調度作業、合理停靠在環形軌道的最佳位置，更早更快的響應站臺的作業請求，大大的提高了環形RGV的系統效率。

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

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

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

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

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