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

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

0 引言

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

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

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

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

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

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

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

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

式中，tc是第c臺RGV在固定時間內(nèi)作業(yè)次數(shù)，Bc(q)為第c臺RGV在固定時間內(nèi)因?yàn)槎氯＼嚨却拇螖?shù)，也即堵塞次數(shù)，n為整個軌道上RGV的數(shù)量。

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

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

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

圖2 設(shè)備網(wǎng)絡(luò)圖

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

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

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

3.1 RGV標(biāo)準(zhǔn)調(diào)度區(qū)域

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

圖3 RGV標(biāo)準(zhǔn)調(diào)度區(qū)域

3.2 RGV擴(kuò)展調(diào)度區(qū)域

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

圖4 RGV擴(kuò)展調(diào)度區(qū)域

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

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

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

4 輔助的規(guī)則

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

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

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

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

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

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

為進(jìn)一步合理布局RGV無作業(yè)時在環(huán)形軌道上的動態(tài)分布，我們還提出了合理?？繀^(qū)域規(guī)則。如圖7所示，此環(huán)形RGV沿著軌道逆時針單向運(yùn)行，根據(jù)合理?？繀^(qū)域規(guī)則，我們會調(diào)度RGV在出庫作業(yè)區(qū)L19站臺和入庫作業(yè)區(qū)L20站臺之間近距離停靠多輛RGV，以便入庫站臺L20-L22有取貨請求時，多輛RGV系統(tǒng)能夠及時迅速的形成調(diào)度作業(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ù)前進(jìn)以便停靠在更合適的區(qū)域，避免在個別特殊區(qū)域不該停車時停車，同時能避免需要停車的區(qū)域RGV數(shù)量不足，從而整體及時快速響應(yīng)站臺取貨請求。如圖8所示，L16和L19的區(qū)域之間就不適合停放空閑的RGV，同樣在L22到L01的區(qū)間也是不適合停放RGV的，此類區(qū)域若有空閑RGV，需及時運(yùn)行到入出庫站臺之間或者立庫站臺區(qū)域的合適位置。

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

5 工程應(yīng)用

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

在某化纖企業(yè)成品立體倉庫中的應(yīng)用中，環(huán)形軌道長度248米，其中直道230米，彎道18米，站臺33個，環(huán)形RGV共設(shè)置8臺RGV，環(huán)形軌道直道速度120米/分鐘，彎道24米/分鐘，輸送機(jī)速度16米/分鐘，托盤交接輸送距離1.6米，托盤輸送方向?yàn)?.2米，RGV與站臺交接響應(yīng)時間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)場實(shí)際測試，采用了基于規(guī)則的調(diào)度算法后，實(shí)測的12小時的均值為320托/小時，原有系統(tǒng)的實(shí)測12小時均值為238托/小時，效率提高了34.5%。

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