本文主要對密集存儲系統中多層穿梭車調度系統的設計及關鍵技術進行分析，對如何實現穿梭車路徑規劃、交通管控、自動充電等智能調度問題，提出了一套完整可行的方案，詳細論述了其技術原理和方法，可為類似密集存儲系統中穿梭車的調度系統開發提供參考。

隨著自動化物流發展，密集存儲得到越來越廣泛地應用，成為未來發展方向之一。作為密集存儲系統中關鍵設備之一，穿梭車的調度是一個技術難點，目前相關技術應用的研究還比較少，尚未形成一套有針對性的成熟理論和實現方案。本文借鑒行業內應用廣泛、技術成熟的AGV調度相關技術，結合多層穿梭車系統的特點和項目實踐經驗，詳細闡述了其中的理論原理和關鍵技術。

一、密集存儲系統簡介

多層密集存儲系統是一種利用穿梭車進行存取貨物的特殊貨架系統，由穿梭車、升降機、充電站、貨架導軌以及上位調度管理軟件組成，可實現貨架深度上貨物的連續存儲，達到存儲密度最大化。

密集存儲系統的工作流程是，在貨架深度方向設置穿梭車導軌，入庫時只需將貨物輸送到升降機入口站臺，系統根據貨物存儲位置控制升降機，將貨物輸送到相應的層；同時，調度穿梭車到升級機站臺取貨，然后將貨物搬運到貨架內指定的位置，出庫過程與之相反。密集式多層穿梭車系統適用于“先進先出”或“先進后出”的自動化倉儲場景。

穿梭車是一種在軌道上作業的智能機器人，可以在系統控制下實現出入庫、盤點、放置等任務，并可與上位WMS系統進行通訊或者通過手持終端控制，結合應用RFID、條碼等技術，實現自動識別、自動存取等功能。

穿梭車調度系統是自動化立體倉庫中的監控和調度中心，主要負責對穿梭車、升降機、充電站等相關設備的參數進行配置以及狀態監控，接收來自業務系統的入庫、出庫、移庫等業務工單，能根據業務工單和在軌穿梭車狀態對任務進行分解，依據調度策略及路徑規劃方法，形成穿梭車調度工單并下達給穿梭車，還需具備對穿梭車充電管理及異常情況處理的能力，實時向業務系統反饋任務完成情況。并且，能將系統操作內容、操作時間及設備狀態記錄到數據庫，作為系統日志管理，具備斷電恢復能力。

二、問題描述

對于多層密集式貨架的其中一層來說，存貨巷道X向是連通的，Y向只有行走巷道是連通的，所有巷道均是雙向可行，即穿梭車可往復行駛。根據貨架特點，為便于計算機處理，很自然地將貨架區域進行柵格化處理。要想規劃出穿梭車行駛的最優路徑，就需要建立一個數字地圖（如圖1所示），該地圖以貨格大小，將倉庫劃分為大小相同的柵格，每個貨位、每個行走巷道、出入庫口、升降機都是一個柵格節點。每個柵格節點都有一個坐標，由層數、巷道數、貨位排數、節點間距和是否換向等屬性來描述。

圖1 二維平面柵格地圖

多層穿梭車調度，需要解決以下主要問題：

1.三維動態路徑規劃問題：穿梭車調度系統屬于實時性要求較高的控制系統，需要在三維立體貨架空間、多車動態環境下進行最優路徑規劃，并且保證算法的高效率。

2.路徑沖突和鎖死問題：由于穿梭車對路徑資源具有獨占性，穿梭車運行過程中不可避免會存在路徑沖突，在某些情況下甚至會出現系統鎖死現象。

3.穿梭車運行過程中遇到故障報警，或外界干擾等突發事件，如何進行處理的問題。

為解決上述問題，對系統設定如下規則：

• 每個柵格可雙向通行，每個柵格只能通過一輛車；

• 小車具備障礙探測能力，可減速或緊急停車；

• 每個任務在下達時指定優先級，出庫優先級大于入庫優先級、載貨優先級大于空載優先級、充電優先級大于空閑，排隊靠前的任務優先級高于靠后的任務；

• 任務根據緩急之分有不同優先級；

• 穿梭車一次只能執行一個任務，當且僅當完成當前任務才能響應下一任務。

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

設定一個運行安全距離，為兩個柵格大小。

如果則存在沖突可能性，然后對兩個車輛的路徑進行對比，如果路徑中存在重疊的柵格且通過時間差不大于1個柵格的通行時間，就認為沖突存在，需要進行交通管控。當確定了兩輛穿梭車之間存在沖突后，則需對沖突類型加以判斷。

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

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

圖2 小車沖突的三種情況

密集存儲穿梭車調度系統需要解決以上穿梭車運行過程中的交通管理基本問題，這三種沖突本質上就是對資源使用的時空重疊問題，只有解決沖突才能保證穿梭車無碰撞運行，避免系統死鎖等問題。

三、關鍵技術應用

1.路徑規劃

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

A*算法是一種典型的啟發式最優路徑求解搜索算法，把評價函數定義為，從初始柵格經過第柵格到達目標柵格的最小代價路徑的代價估計值，其一般形式是，式中是從初始柵格到第柵格的實際代價，是從第柵格到目標柵格的路徑估計代價，被稱為啟發性函數。

基于密集式存儲貨架柵格地圖的特點，在本設計中采用作為啟發函數，這個估算路徑距離在大多數情況下與穿梭車實際行走的距離非常接近或相等（穿梭車在貨架中只能前后、左右和上下六個方向移動），所以規劃出的路徑一定是最優路徑，并且搜索效率非常高。

穿梭車在分配到任務后，將需經過的地址對（包含起點、終點）順序輸入調用的A*算法規劃出最優路徑，再將最優路徑中每一段路徑轉化為穿梭車可執行指令（包含柵格內的轉向操作），依據穿梭車運行狀態下達指令。

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

在二維平面柵格地圖下，采用A*算法規劃出的穿梭車出入庫最優路徑，如圖3所示。

圖3 出入庫路徑規劃

2.交通管控

本文采用基于任務優先級時間窗控制方法進行穿梭車交通管控，這種路徑規劃方法屬于預測式防沖突控制方法。系統有兩種解決交通沖突的策略：基于時間窗的幾何路徑解決策略和基于優先級排隊調節解決策略，兩種策略優先級不同，當采用幾何路徑無法找到路徑或耗時較長時，可以選擇基于優先級排隊調節解決策略。首先為各穿梭車規劃好最優路徑，然后根據每臺穿梭車的路徑預測穿梭車之間是否會發生沖突，如果存在沖突則調整穿梭車的路徑來避免碰撞。

在整個調度系統中，穿梭車是資源使用者，行走巷道、貨位巷道、升降機和充電站均是資源，每一個資源在一定時間內只能由一輛穿梭車使用，穿梭車使用資源的過程通過基于優先級的交通規則法進行調度，根據資源使用時間及建立的優先級來決定避讓規則，對穿梭車進行路徑規劃，或者排隊等待，避免路徑沖突和死鎖情況的出現。

基于任務優先級的交通管控策略如下描述：

為了優化管理多個穿梭車在巷道中的通行問題，對車輛經過的柵格地圖路徑以調度系統的時鐘為基準建立一個時間窗表，該時間表的作用就是判斷穿梭車對沖突柵格資源的占用時間。每一個在執行任務的穿梭車均有一個時間窗表，該時間表描述了每個資源的占用情況，即經過每個柵格的到達時間和離開時間。以執行第一個任務的穿梭車規劃的路徑和建立的時間窗表為基礎，為后續穿梭車逐個規劃路徑并建立時間窗表。若新規劃的路徑與前面已規劃好的路徑沒有沖突，或路徑沖突但時間沒有重疊，則表示路徑規劃是可行的；若新規劃的路徑有沖突并且時間有重疊，需要重新規劃路徑，重復上述過程，直到不存在沖突或時間重疊。如果不能規劃出最短路徑，或重新規劃的路徑用時比排隊等待用時還長，則暫停對該任務的執行，排隊等待。

針對穿梭車交通管控沖突類型，對應的具體調度控制方法如下：

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

圖4 相向沖突的調度

（2）追趕沖突有兩種情況（假定空載車輛速度大于載貨車輛），前車減速（包括靜止）追趕和空載車輛追趕載貨車輛。因為在路徑規劃時，即根據時間窗控制進行無沖突或根據優先級排隊等待原則規避，追趕沖突只有在前車故障時發生，后車采取停車等待或重新進行路徑規劃繼續執行任務。

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

圖5 路口沖突的調度

（4）對于上述（3）中方法無法解決的第四種問題（鎖死沖突），需要根據任務優先級給低優先級車輛附加一個臨時任務，行駛到起始位置附近進行避讓（附加任務不能與其它穿梭車路徑產生新的沖突），并釋放之前占用的資源，到達新位置后再重新規劃路。

（5）對于穿梭車運行過程中發生故障或受到外界干擾而中斷任務執行的情況，其它與任務中斷穿梭車路徑有交叉的穿梭車在行駛到故障點附近后，保持安全距離暫停等待。如果能夠短時間內恢復，則由當前穿梭車按原路徑繼續執行任務；否則應取消當前穿梭車的任務，由系統調度其它空閑小車接管任務，并更新受影響的穿梭車時間窗信息。

綜合上述多種情況來看，采用基于優先級的排隊等待和重新規劃路徑兩種策略，均能解決路徑沖突和穿梭車運行過程中發生故障的問題。一是低優先級的穿梭車在沖突時排隊等待高優先級的穿梭車通過并釋放資源，再繼續執行；二是重新規劃穿梭車路徑繼續執行當前任務，或由其它穿梭車接管任務。

3.軟件系統設計

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

穿梭車調度系統軟件主要由信息通訊、狀態監控、設備管理、故障處理、任務管理及調度規劃、系統日志管理等模塊組成。

圖6 軟件結構示意圖

信息通訊模塊，按照擬定的通訊協議通過以太網或無線網絡實現與業務系統、穿梭車、升降機、充電站的實時通訊。狀態監控模塊，主要實現對穿梭車、升降機、充電站等相關設備運行狀態、接受的任務工單狀態、下達的調度工單狀態和選擇的調度策略狀態的實時顯示。設備管理模塊，主要實現對接入調度系統的穿梭車、升降機、充電站等設備的參數設定以及貨架中貨位信息的設定。故障處理模塊，主要實現對穿梭車、升降機和充電站上報的故障信息進行故障類型判斷，依據故障處理應急方案下達任務中止、重新調度及上報故障等命令。任務管理及調度規劃模塊，主要實現將業務系統下達的任務分解為調度系統可解算的子任務，規劃穿梭車行走路徑，動態調度穿梭車及升降機執行任務，具備多穿梭車交通管理及避碰的能力，還有穿梭車充電管理。系統日志管理模塊，主要實現對調度系統的操作內容、操作時間及設備狀態記錄到數據庫，具備斷電恢復能力。

4.虛擬仿真

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

四、結束語

本文針對密集式存儲穿梭車調度問題，通過將多層三維空間貨架進行柵格化處理，利用A*算法和時間窗原理進行穿梭車路徑求解，能很好地解決穿梭車執行任務過程中的路徑規劃和無沖突交通管控問題，為系統的實際應用提供基礎技術支撐，對類似系統的應用具有較高參考價值。