文/張?jiān)瞥?/p>

隨著自動(dòng)化物流發(fā)展，密集存儲(chǔ)得到越來(lái)越廣泛地應(yīng)用，成為未來(lái)發(fā)展方向之一。作為密集存儲(chǔ)系統(tǒng)中關(guān)鍵設(shè)備之一，穿梭車的調(diào)度是一個(gè)技術(shù)難點(diǎn)，目前相關(guān)技術(shù)應(yīng)用的研究還比較少，尚未形成一套有針對(duì)性的成熟理論和實(shí)現(xiàn)方案。本文借鑒行業(yè)內(nèi)應(yīng)用廣泛、技術(shù)成熟的AGV調(diào)度相關(guān)技術(shù)，結(jié)合多層穿梭車系統(tǒng)的特點(diǎn)和項(xiàng)目實(shí)踐經(jīng)驗(yàn)，詳細(xì)闡述了其中的理論原理和關(guān)鍵技術(shù)。

一、密集存儲(chǔ)系統(tǒng)簡(jiǎn)介

多層密集存儲(chǔ)系統(tǒng)是一種利用穿梭車進(jìn)行存取貨物的特殊貨架系統(tǒng)，由穿梭車、升降機(jī)、充電站、貨架導(dǎo)軌以及上位調(diào)度管理軟件組成，可實(shí)現(xiàn)貨架深度上貨物的連續(xù)存儲(chǔ)，達(dá)到存儲(chǔ)密度最大化。

密集存儲(chǔ)系統(tǒng)的工作流程是，在貨架深度方向設(shè)置穿梭車導(dǎo)軌，入庫(kù)時(shí)只需將貨物輸送到升降機(jī)入口站臺(tái)，系統(tǒng)根據(jù)貨物存儲(chǔ)位置控制升降機(jī)，將貨物輸送到相應(yīng)的層；同時(shí)，調(diào)度穿梭車到升級(jí)機(jī)站臺(tái)取貨，然后將貨物搬運(yùn)到貨架內(nèi)指定的位置，出庫(kù)過程與之相反。密集式多層穿梭車系統(tǒng)適用于“先進(jìn)先出”或“先進(jìn)后出”的自動(dòng)化倉(cāng)儲(chǔ)場(chǎng)景。

穿梭車是一種在軌道上作業(yè)的智能機(jī)器人，可以在系統(tǒng)控制下實(shí)現(xiàn)出入庫(kù)、盤點(diǎn)、放置等任務(wù)，并可與上位WMS系統(tǒng)進(jìn)行通訊或者通過手持終端控制，結(jié)合應(yīng)用RFID、條碼等技術(shù)，實(shí)現(xiàn)自動(dòng)識(shí)別、自動(dòng)存取等功能。

穿梭車調(diào)度系統(tǒng)是自動(dòng)化立體倉(cāng)庫(kù)中的監(jiān)控和調(diào)度中心，主要負(fù)責(zé)對(duì)穿梭車、升降機(jī)、充電站等相關(guān)設(shè)備的參數(shù)進(jìn)行配置以及狀態(tài)監(jiān)控，接收來(lái)自業(yè)務(wù)系統(tǒng)的入庫(kù)、出庫(kù)、移庫(kù)等業(yè)務(wù)工單，能根據(jù)業(yè)務(wù)工單和在軌穿梭車狀態(tài)對(duì)任務(wù)進(jìn)行分解，依據(jù)調(diào)度策略及路徑規(guī)劃方法，形成穿梭車調(diào)度工單并下達(dá)給穿梭車，還需具備對(duì)穿梭車充電管理及異常情況處理的能力，實(shí)時(shí)向業(yè)務(wù)系統(tǒng)反饋任務(wù)完成情況。并且，能將系統(tǒng)操作內(nèi)容、操作時(shí)間及設(shè)備狀態(tài)記錄到數(shù)據(jù)庫(kù)，作為系統(tǒng)日志管理，具備斷電恢復(fù)能力。

二、問題描述

對(duì)于多層密集式貨架的其中一層來(lái)說(shuō)，存貨巷道X向是連通的，Y向只有行走巷道是連通的，所有巷道均是雙向可行，即穿梭車可往復(fù)行駛。根據(jù)貨架特點(diǎn)，為便于計(jì)算機(jī)處理，很自然地將貨架區(qū)域進(jìn)行柵格化處理。要想規(guī)劃出穿梭車行駛的最優(yōu)路徑，就需要建立一個(gè)數(shù)字地圖（如圖1所示），該地圖以貨格大小，將倉(cāng)庫(kù)劃分為大小相同的柵格，每個(gè)貨位、每個(gè)行走巷道、出入庫(kù)口、升降機(jī)都是一個(gè)柵格節(jié)點(diǎn)。每個(gè)柵格節(jié)點(diǎn)都有一個(gè)坐標(biāo)，由層數(shù)、巷道數(shù)、貨位排數(shù)、節(jié)點(diǎn)間距和是否換向等屬性來(lái)描述。

圖1 二維平面柵格地圖

多層穿梭車調(diào)度，需要解決以下主要問題：

1.三維動(dòng)態(tài)路徑規(guī)劃問題：穿梭車調(diào)度系統(tǒng)屬于實(shí)時(shí)性要求較高的控制系統(tǒng)，需要在三維立體貨架空間、多車動(dòng)態(tài)環(huán)境下進(jìn)行最優(yōu)路徑規(guī)劃，并且保證算法的高效率。

2.路徑?jīng)_突和鎖死問題：由于穿梭車對(duì)路徑資源具有獨(dú)占性，穿梭車運(yùn)行過程中不可避免會(huì)存在路徑?jīng)_突，在某些情況下甚至?xí)霈F(xiàn)系統(tǒng)鎖死現(xiàn)象。

3.穿梭車運(yùn)行過程中遇到故障報(bào)警，或外界干擾等突發(fā)事件，如何進(jìn)行處理的問題。

為解決上述問題，對(duì)系統(tǒng)設(shè)定如下規(guī)則：

● 每個(gè)柵格可雙向通行，每個(gè)柵格只能通過一輛車；

● 小車具備障礙探測(cè)能力，可減速或緊急停車；

●每個(gè)任務(wù)在下達(dá)時(shí)指定優(yōu)先級(jí)，出庫(kù)優(yōu)先級(jí)大于入庫(kù)優(yōu)先級(jí)、載貨優(yōu)先級(jí)大于空載優(yōu)先級(jí)、充電優(yōu)先級(jí)大于空閑，排隊(duì)靠前的任務(wù)優(yōu)先級(jí)高于靠后的任務(wù)；

●任務(wù)根據(jù)緩急之分有不同優(yōu)先級(jí)；

●穿梭車一次只能執(zhí)行一個(gè)任務(wù)，當(dāng)且僅當(dāng)完成當(dāng)前任務(wù)才能響應(yīng)下一任務(wù)。

在密集式貨架某一層中，穿梭車之間是否存在沖突，可根據(jù)兩車之間同一坐標(biāo)方向的距離判斷。若兩輛穿梭車的坐標(biāo)分別為，那么它們之間的距離為中較大的。

根據(jù)穿梭車上傳的信息可以知道小車的行駛方向，而沖突類型可通過兩車行駛方向的夾角進(jìn)行確定。若兩車之間的夾角為180°內(nèi)，則判斷兩車的沖突類型為相向沖突；若兩車之間的夾角為0°內(nèi)，則判斷兩車的沖突類型為追趕沖突；若兩車之間的夾角為90°內(nèi)，則判斷兩車的沖突類型為路口沖突。

多個(gè)穿梭車在執(zhí)行任務(wù)的過程中，需要占用貨位、行走通道、出入庫(kù)口（升降機(jī)可視為出入庫(kù)口）等資源，可能出現(xiàn)三種交通沖突：相向沖突，追趕沖突和路口沖突，如圖2所示。

圖2 小車沖突的三種情況

密集存儲(chǔ)穿梭車調(diào)度系統(tǒng)需要解決以上穿梭車運(yùn)行過程中的交通管理基本問題，這三種沖突本質(zhì)上就是對(duì)資源使用的時(shí)空重疊問題，只有解決沖突才能保證穿梭車無(wú)碰撞運(yùn)行，避免系統(tǒng)死鎖等問題。

三、關(guān)鍵技術(shù)應(yīng)用

1.路徑規(guī)劃

多層密集式存儲(chǔ)貨架垂直方向穿梭車換層都需要通過升降機(jī)進(jìn)行，穿梭車跨層作業(yè)路徑規(guī)劃可視為三維立體空間柵格化的路徑求解問題，需要在二維柵格平面的基礎(chǔ)上增加垂直方向的Z坐標(biāo)。根據(jù)已知貨架的三維柵格地圖信息，為滿足穿梭車調(diào)度控制實(shí)時(shí)性要求，穿梭數(shù)量車路徑規(guī)劃采用A＊算法求解，能得到穿梭車行駛的最優(yōu)路徑。

A＊算法是一種典型的啟發(fā)式最優(yōu)路徑求解搜索算法，把評(píng)價(jià)函數(shù)定義為，從初始柵格經(jīng)過第f柵格到達(dá)目標(biāo)柵格的最小代價(jià)路徑的代價(jià)估計(jì)值，其一般形式是，式中是從初始柵格到第n柵格的實(shí)際代價(jià)，是從第柵格到目標(biāo)柵格的路徑估計(jì)代價(jià)，被稱為啟發(fā)性函數(shù)。

穿梭車在分配到任務(wù)后，將需經(jīng)過的地址對(duì)（包含起點(diǎn)、終點(diǎn)）順序輸入調(diào)用的A＊算法規(guī)劃出最優(yōu)路徑，再將最優(yōu)路徑中每一段路徑轉(zhuǎn)化為穿梭車可執(zhí)行指令（包含柵格內(nèi)的轉(zhuǎn)向操作），依據(jù)穿梭車運(yùn)行狀態(tài)下達(dá)指令。

當(dāng)穿梭車裝載貨物后，A＊算法調(diào)用的地圖信息主要包含貨位上是否有貨的障礙物信息以及其它車輛狀態(tài)；當(dāng)穿梭車空載并被分配一個(gè)任務(wù)時(shí)，A＊算法調(diào)用的地圖信息包含其它車輛當(dāng)前的位置信息，并將其作為障礙物而不考慮貨位上是否有貨的障礙物信息，采用這種方式可有效減少或避免載貨和空載穿梭車之間的沖突。

在二維平面柵格地圖下，采用A＊算法規(guī)劃出的穿梭車出入庫(kù)最優(yōu)路徑，如圖3所示。

圖3 出入庫(kù)路徑規(guī)劃

2.交通管控

本文采用基于任務(wù)優(yōu)先級(jí)時(shí)間窗控制方法進(jìn)行穿梭車交通管控，這種路徑規(guī)劃方法屬于預(yù)測(cè)式防沖突控制方法。系統(tǒng)有兩種解決交通沖突的策略：基于時(shí)間窗的幾何路徑解決策略和基于優(yōu)先級(jí)排隊(duì)調(diào)節(jié)解決策略，兩種策略優(yōu)先級(jí)不同，當(dāng)采用幾何路徑無(wú)法找到路徑或耗時(shí)較長(zhǎng)時(shí)，可以選擇基于優(yōu)先級(jí)排隊(duì)調(diào)節(jié)解決策略。首先為各穿梭車規(guī)劃好最優(yōu)路徑，然后根據(jù)每臺(tái)穿梭車的路徑預(yù)測(cè)穿梭車之間是否會(huì)發(fā)生沖突，如果存在沖突則調(diào)整穿梭車的路徑來(lái)避免碰撞。

在整個(gè)調(diào)度系統(tǒng)中，穿梭車是資源使用者，行走巷道、貨位巷道、升降機(jī)和充電站均是資源，每一個(gè)資源在一定時(shí)間內(nèi)只能由一輛穿梭車使用，穿梭車使用資源的過程通過基于優(yōu)先級(jí)的交通規(guī)則法進(jìn)行調(diào)度，根據(jù)資源使用時(shí)間及建立的優(yōu)先級(jí)來(lái)決定避讓規(guī)則，對(duì)穿梭車進(jìn)行路徑規(guī)劃，或者排隊(duì)等待，避免路徑?jīng)_突和死鎖情況的出現(xiàn)。

基于任務(wù)優(yōu)先級(jí)的交通管控策略如下描述：

為了優(yōu)化管理多個(gè)穿梭車在巷道中的通行問題，對(duì)車輛經(jīng)過的柵格地圖路徑以調(diào)度系統(tǒng)的時(shí)鐘為基準(zhǔn)建立一個(gè)時(shí)間窗表，該時(shí)間表的作用就是判斷穿梭車對(duì)沖突柵格資源的占用時(shí)間。每一個(gè)在執(zhí)行任務(wù)的穿梭車均有一個(gè)時(shí)間窗表，該時(shí)間表描述了每個(gè)資源的占用情況，即經(jīng)過每個(gè)柵格的到達(dá)時(shí)間和離開時(shí)間。以執(zhí)行第一個(gè)任務(wù)的穿梭車規(guī)劃的路徑和建立的時(shí)間窗表為基礎(chǔ)，為后續(xù)穿梭車逐個(gè)規(guī)劃路徑并建立時(shí)間窗表。若新規(guī)劃的路徑與前面已規(guī)劃好的路徑?jīng)]有沖突，或路徑?jīng)_突但時(shí)間沒有重疊，則表示路徑規(guī)劃是可行的；若新規(guī)劃的路徑有沖突并且時(shí)間有重疊，需要重新規(guī)劃路徑，重復(fù)上述過程，直到不存在沖突或時(shí)間重疊。如果不能規(guī)劃出最短路徑，或重新規(guī)劃的路徑用時(shí)比排隊(duì)等待用時(shí)還長(zhǎng)，則暫停對(duì)該任務(wù)的執(zhí)行，排隊(duì)等待。

針對(duì)穿梭車交通管控沖突類型，對(duì)應(yīng)的具體調(diào)度控制方法如下：

（1）相向沖突有三種情況，即在貨位巷道上的沖突、在行走巷道上的沖突和在出入庫(kù)口、升降機(jī)位（包括進(jìn)出升降機(jī)前的一個(gè)柵格）的沖突。貨位巷道或行走巷道上的沖突發(fā)生時(shí)，根據(jù)設(shè)定的優(yōu)先級(jí)決定低優(yōu)先級(jí)的穿梭車采取規(guī)避沖突路徑規(guī)劃策略，也就是低優(yōu)先級(jí)的穿梭車視高優(yōu)先級(jí)穿梭車所規(guī)劃的路徑均為占用，低優(yōu)先級(jí)的穿梭車路徑規(guī)劃避開所有占用路徑。如果在入庫(kù)口或升降機(jī)位的沖突發(fā)生時(shí)，低優(yōu)先級(jí)穿梭車需等待其它穿梭車釋放入庫(kù)口或升降機(jī)位置資源，再進(jìn)行路徑規(guī)劃（任務(wù)排隊(duì)等待執(zhí)行）；如果在出庫(kù)口或升降機(jī)位的沖突發(fā)生時(shí)，因空載穿梭車（此時(shí)可視為高優(yōu)先級(jí)）物理上已占據(jù)資源，所以載貨穿梭車（此時(shí)可視為低優(yōu)先級(jí)）需等待其它穿梭車釋放出庫(kù)口或升降機(jī)位置資源，再進(jìn)行路徑規(guī)劃（任務(wù)排隊(duì)等待執(zhí)行）。相向沖突三種情況下的路徑規(guī)劃，如圖4所示。

圖4 相向沖突的調(diào)度

（2）追趕沖突有兩種情況（假定空載車輛速度大于載貨車輛），前車減速（包括靜止）追趕和空載車輛追趕載貨車輛。因?yàn)樵诼窂揭?guī)劃時(shí)，即根據(jù)時(shí)間窗控制進(jìn)行無(wú)沖突或根據(jù)優(yōu)先級(jí)排隊(duì)等待原則規(guī)避，追趕沖突只有在前車故障時(shí)發(fā)生，后車采取停車等待或重新進(jìn)行路徑規(guī)劃繼續(xù)執(zhí)行任務(wù)。

（3）路口沖突有四種情況，兩輛車在路口沖突后的路徑不重疊、兩輛車在路口沖突后的路徑重疊、兩輛車在路口沖突后有一方行駛到對(duì)方之前的位置，以及兩輛車在路口沖突后相互行駛到對(duì)方之前的位置（鎖死沖突），如圖5所示。前三種情況在路徑規(guī)劃時(shí)，均可根據(jù)時(shí)間窗控制或根據(jù)優(yōu)先級(jí)排隊(duì)等待進(jìn)行規(guī)避。

圖5 路口沖突的調(diào)度

（4）對(duì)于上述（3）中方法無(wú)法解決的第四種問題（鎖死沖突），需要根據(jù)任務(wù)優(yōu)先級(jí)給低優(yōu)先級(jí)車輛附加一個(gè)臨時(shí)任務(wù)，行駛到起始位置附近進(jìn)行避讓（附加任務(wù)不能與其它穿梭車路徑產(chǎn)生新的沖突），并釋放之前占用的資源，到達(dá)新位置后再重新規(guī)劃路。

（5）對(duì)于穿梭車運(yùn)行過程中發(fā)生故障或受到外界干擾而中斷任務(wù)執(zhí)行的情況，其它與任務(wù)中斷穿梭車路徑有交叉的穿梭車在行駛到故障點(diǎn)附近后，保持安全距離暫停等待。如果能夠短時(shí)間內(nèi)恢復(fù)，則由當(dāng)前穿梭車按原路徑繼續(xù)執(zhí)行任務(wù)；否則應(yīng)取消當(dāng)前穿梭車的任務(wù)，由系統(tǒng)調(diào)度其它空閑小車接管任務(wù)，并更新受影響的穿梭車時(shí)間窗信息。

圖6 軟件結(jié)構(gòu)示意圖

綜合上述多種情況來(lái)看，采用基于優(yōu)先級(jí)的排隊(duì)等待和重新規(guī)劃路徑兩種策略，均能解決路徑?jīng)_突和穿梭車運(yùn)行過程中發(fā)生故障的問題。一是低優(yōu)先級(jí)的穿梭車在沖突時(shí)排隊(duì)等待高優(yōu)先級(jí)的穿梭車通過并釋放資源，再繼續(xù)執(zhí)行；二是重新規(guī)劃穿梭車路徑繼續(xù)執(zhí)行當(dāng)前任務(wù)，或由其它穿梭車接管任務(wù)。

3.軟件系統(tǒng)設(shè)計(jì)

穿梭車調(diào)度管理系統(tǒng)的總體設(shè)計(jì)以“軟件平臺(tái)思想”為指導(dǎo)，將系統(tǒng)設(shè)計(jì)為一套支持穿梭車調(diào)度從路徑規(guī)劃、流程設(shè)計(jì)、系統(tǒng)仿真到系統(tǒng)實(shí)施全過程的整體解決方案。上位控制系統(tǒng)根據(jù)從其它系統(tǒng)接收到的出入庫(kù)指令，統(tǒng)籌調(diào)度穿梭車車輛，將任務(wù)分配給合適的小車。小車在智能交通管理控制下，沿規(guī)定的路線自動(dòng)高效地完成搬運(yùn)任務(wù)，并可及時(shí)調(diào)度小車進(jìn)行充電、維護(hù)保養(yǎng)等。

穿梭車調(diào)度系統(tǒng)軟件主要由信息通訊、狀態(tài)監(jiān)控、設(shè)備管理、故障處理、任務(wù)管理及調(diào)度規(guī)劃、系統(tǒng)日志管理等模塊組成。

信息通訊模塊，按照擬定的通訊協(xié)議通過以太網(wǎng)或無(wú)線網(wǎng)絡(luò)實(shí)現(xiàn)與業(yè)務(wù)系統(tǒng)、穿梭車、升降機(jī)、充電站的實(shí)時(shí)通訊。狀態(tài)監(jiān)控模塊，主要實(shí)現(xiàn)對(duì)穿梭車、升降機(jī)、充電站等相關(guān)設(shè)備運(yùn)行狀態(tài)、接受的任務(wù)工單狀態(tài)、下達(dá)的調(diào)度工單狀態(tài)和選擇的調(diào)度策略狀態(tài)的實(shí)時(shí)顯示。設(shè)備管理模塊，主要實(shí)現(xiàn)對(duì)接入調(diào)度系統(tǒng)的穿梭車、升降機(jī)、充電站等設(shè)備的參數(shù)設(shè)定以及貨架中貨位信息的設(shè)定。故障處理模塊，主要實(shí)現(xiàn)對(duì)穿梭車、升降機(jī)和充電站上報(bào)的故障信息進(jìn)行故障類型判斷，依據(jù)故障處理應(yīng)急方案下達(dá)任務(wù)中止、重新調(diào)度及上報(bào)故障等命令。任務(wù)管理及調(diào)度規(guī)劃模塊，主要實(shí)現(xiàn)將業(yè)務(wù)系統(tǒng)下達(dá)的任務(wù)分解為調(diào)度系統(tǒng)可解算的子任務(wù)，規(guī)劃穿梭車行走路徑，動(dòng)態(tài)調(diào)度穿梭車及升降機(jī)執(zhí)行任務(wù)，具備多穿梭車交通管理及避碰的能力，還有穿梭車充電管理。系統(tǒng)日志管理模塊，主要實(shí)現(xiàn)對(duì)調(diào)度系統(tǒng)的操作內(nèi)容、操作時(shí)間及設(shè)備狀態(tài)記錄到數(shù)據(jù)庫(kù)，具備斷電恢復(fù)能力。

4.虛擬仿真

多層穿梭車存儲(chǔ)系統(tǒng)地圖模型和調(diào)度模型建立后，還需要建立離線虛擬仿真系統(tǒng)。根據(jù)穿梭車運(yùn)行參數(shù)、出入庫(kù)任務(wù)和系統(tǒng)能力需求，模擬真實(shí)系統(tǒng)運(yùn)行情況，通過對(duì)系統(tǒng)出入庫(kù)能力、設(shè)備使用效率等仿真結(jié)果對(duì)比分析，發(fā)現(xiàn)系統(tǒng)運(yùn)行過程中可能存在的瓶頸問題，并找出在系統(tǒng)能力需求下的最佳穿梭車配置數(shù)量。為了保證數(shù)據(jù)接口的一致性，便于程序模擬調(diào)試，系統(tǒng)采用PLC仿真器的方式模擬穿梭車運(yùn)行狀態(tài)，PLC仿真器可手動(dòng)或自動(dòng)模擬更改穿梭車的數(shù)據(jù)。穿梭車調(diào)度系統(tǒng)可以手動(dòng)或自動(dòng)模擬添加任務(wù)，同時(shí)通過數(shù)據(jù)接口讀寫PLC仿真器的實(shí)時(shí)數(shù)據(jù)，結(jié)合地圖數(shù)據(jù)對(duì)系統(tǒng)進(jìn)行模擬仿真。

四、結(jié)束語(yǔ)

本文針對(duì)密集式存儲(chǔ)穿梭車調(diào)度問題，通過將多層三維空間貨架進(jìn)行柵格化處理，利用A＊算法和時(shí)間窗原理進(jìn)行穿梭車路徑求解，能很好地解決穿梭車執(zhí)行任務(wù)過程中的路徑規(guī)劃和無(wú)沖突交通管控問題，為系統(tǒng)的實(shí)際應(yīng)用提供基礎(chǔ)技術(shù)支撐，對(duì)類似系統(tǒng)的應(yīng)用具有較高參考價(jià)值。