一種面向多深度儲貨區的四向車調度策略

徐立云，陳 晨，占翔南，宓 宏

（1.同濟大學 機械與能源工程學院，上海 201804；2.浙江衢州聯州致冷劑有限公司，浙江 衢州 324004）

1 引言

由于倉儲用地資源緊張，人力成本不斷升高，社會對倉儲的需求越來越大，要求倉儲系統往密集化和智能化方向發展[1]。目前應用最為廣泛的是堆垛式自動化立體倉儲系統（Automated Storage and Retrieval System），但該倉儲系統存在兩方面的問題，一是當巷道中堆垛機發生故障時，其所服務的整條巷道隨即處于癱瘓狀態，無法進行相應的出入庫作業；二是當堆垛式自動化立體倉儲系統設計建造完成后，其出入庫能力也隨之固定。為解決這一問題，出現了多層穿梭車倉儲系統（Multi-tier Shuttle Warehousing System），該倉儲系統能夠在一定程度上解決堆垛式自動化立體倉儲系統的不足，但是由于該倉儲系統的存儲巷道深度大部分為單個貨位，同時每條主干道只有一輛穿梭車執行存取任務，產生了存儲空間利用率較低、貨物存取不靈活等問題[2-3]。為滿足市場需要，出現了一種新型的基于四向穿梭車的多深度倉儲系統，該系統兼具上述兩種系統的優勢，同時在同一層貨架中可以放置多輛四向車，能夠根據出入庫效率需求的不同，動態調整四向車數量，使得該類型的倉儲系統具有較強的靈活性，并且多深度的存儲巷道能夠保證較高的倉儲空間利用率。

國內外學者針對四向穿梭式多深度倉儲系統進行了相應研究。Manzini 等[4]提出了四向車單車存取貨物的行程時間數學模型，并進行了倉儲系統布局優化。D’Antonio 等[5-6]提出了單次行程中包含多個存取貨物任務的行程時間數學模型，基于該模型進行了四向車調度策略優化。然而，文獻中提出的數學模型只針對單條主干道只運行一輛四向車的情況，無法解決多車同時運行的問題。Tappia 等[7]使用排隊網絡建立分析模型，評估單層和多層多深度倉儲系統的運行情況，但模型并未考慮四向車的死鎖和堵塞問題，使得結果和實際情況有較大偏差。付曉峰等[8]提出了針對四向車多深度倉儲系統的貨物入庫上架過程和貨位分配方法，但文中使用的區域控制方法使得一條儲貨巷道中同時只允許一輛四向車工作，處于等待狀態的四向車會堵塞主干道，影響正常通行，導致系統效率較低。

本文針對倉儲系統多深度儲貨區存在的問題，基于道路定向法提出了四向車多車調度策略，避免車輛沖突與任務死鎖，保證了倉儲系統高效運行，并結合實際案例驗證了所提策略的有效性。

2 問題描述

多深度倉儲系統由垂直提升機、四向穿梭車、多層貨架及管理控制系統組成。四向穿梭車實現貨架儲貨區托盤貨物的水平轉運，垂直提升機實現托盤貨物的垂直轉運和四向穿梭車的換層，控制信息系統負責整個倉儲系統的設備監控和調度。儲貨區域為多層貨架結構，每層布局相同，如圖1所示，儲貨區由多條平行的儲貨巷道構成，每條儲貨巷道中有多個貨位。每條儲貨巷道中只能存放同一品類同一批次的貨物，即一個SKU（Stock Keep Unit），為保證倉儲系統貨物先進先出的原則，儲貨巷道內的貨物同樣采用先進先出的操作方式，即只從儲貨巷道一端入貨，從另一端出貨。

四向車采用電力驅動，能夠與控制信息系統進行無線通訊，接收出入庫任務。當到達目標貨位時，通過托盤舉升裝置將托盤抬升或下降實現貨物的裝卸。四向車可沿巷道橫向和縱向四個方向行駛，可深入儲貨巷道內部到達倉儲系統中的任何一個儲位，當四向穿梭車處于空車狀態時，可以在存有貨物的巷道中自由穿梭，當四向穿梭車為載貨狀態時，可以在空閑的儲貨巷道中借路通行。

圖1 單層布局圖

對于單層儲貨區來說，當空閑四向車接到貨物入庫命令時，四向車從當前位置尋路至每層的入庫口處，從入庫口的提升機處接取貨物后，將貨物運送至指定貨位。執行出庫命令時，四向穿梭車按照任務指示，尋路到待出庫貨物所在貨位，將貨物運送至出庫口處的提升機。但在四向車運行過程中，多車同時執行任務會造成四向車之間、儲貨巷道內任務之間出現死鎖與沖突，兩類沖突如圖2所示。

圖2 四向穿梭車沖突類型

當多車同時運行時，在道路交叉口處出現的四向車沖突與死鎖，會導致整個單層儲貨區癱瘓。如圖2所示，單層儲貨區中主要存在兩種形式的車輛沖突。圖2-a 為路口沖突，如果調度系統不加以控制，A、B 兩車將在路口發生碰撞，圖2-b 為相向沖突，該沖突類型會導致A、B兩車死鎖情況的發生。當在主干道發生車輛沖突與死鎖時，會造成單層儲貨區的出入庫任務無法正常執行，倉儲系統吞吐量會受到大幅影響。

由于四向車的運行特性，四向車到達某個指定位置的路徑可以有多條，本文中采用Dijkstra 算法為四向車選擇最短路徑，但是由于多車同時運行，四向車到達目的地的過程中存在等待路口使用權和停車轉向造成的延遲時間，當兩臺四向車分別接收到同一巷道的出貨命令時，先接到任務的小車并不一定先到達目標巷道，出貨任務死鎖如圖3-a 所示，A 車需要出庫a位置貨物，B車需要出庫b位置貨物，而B車先進入巷道內部，這時B車取得貨物之后無法離開巷道，a 位置貨物會擋住B 車造成死鎖。同理，入貨任務死鎖如圖3-b所示，在兩個同一巷道的入庫任務同時執行時，也會出現類似死鎖情況。另外，載貨狀態的四向車可以通過沒有放置貨物的儲貨巷道借路通行，由于四向車的路徑規劃是在接到任務后立即執行，有可能在路徑規劃時借路的儲貨巷道是空閑的，但當載貨車經過一段時間到達借路儲貨巷道時，有可能已經存在新的貨物，會造成借路死鎖。

圖3 儲貨巷道內任務死鎖類型

3 調度策略

3.1 道路定向策略

為避免圖2-a所示的路口沖突，采用路口使用權鎖定策略。當A、B 兩車需要同時通過路口時，均需要申請路口節點的使用權，只有路口使用權被釋放時，下一輛四向車才能通過路口。同時在路口處維護一個四向車等待列表，路口按照通過等待列表中的次序依次放行每輛四向車。為避免如圖2-b 所示的相向沖突導致的車輛死鎖情況的發生，在滿足巷道內貨物先進先出特性的前提下，采用主干道定向策略解決四向車的死鎖問題，保證了多輛四向車能夠在倉儲區域的流暢運行。主干道與儲貨巷道的定向結果如圖4所示。

圖4 主干道定向方向

3.2 任務交換策略

為解決儲貨巷道內的任務死鎖問題，采用巷道內任務交換策略。利用巷道和貨位的多種狀態，靈活調整四向車最終執行的任務，當一條巷道內同時出現多個出庫與入庫任務時，四向車先尋路到目標貨位所在巷道的入口處，從緊鄰儲貨巷道出口的貨位開始，沿巷道出入貨反方向查詢貨位狀態，選擇第一個可以執行的對應任務，作為最終目標任務，從而避免任務死鎖，保證一條巷道中的多個任務都能被順利執行。貨位狀態S 和巷道狀態T 不同狀態對應的不同含義均在狀態表中列出，見表1。

表1 狀態表

四向車執行入庫任務流程如下：

步驟1：空車狀態的四向車接收到入庫任務后，將對應貨位狀態代碼S設置為3，表示該貨位已被分配入貨，防止被選為下個入庫任務。

步驟2：將四向車當前目的地設置為入庫口，使用Dijkstra 算法規劃路徑，并尋路至入庫口完成取貨操作。此時四向車為載貨狀態。

步驟3：將四向車當前目的地設置為目標貨位巷道的入口處，使用Dijkstra 算法規劃路徑，如果規劃路徑中需借路通行，則將對應巷道的借路狀態T+1。

步驟4：四向車按照規劃路徑到達巷道入口。如果途中出現借路通行，及時更新借路巷道對應的巷道狀態T。

步驟5：從緊鄰巷道出口的貨位開始，沿巷道出入貨反方向查詢貨位狀態，選擇第一個貨位狀態為3的貨位，作為最終入庫目標貨位。將該最終目標貨位狀態S更改為5，表示有四向車向該貨位入貨，并且已經進入巷道，防止在巷道入口路段的下個執行入庫任務的四向車選擇這個貨位為最終目標貨位。

步驟6：進入巷道，到達目標貨位后卸貨，將該貨位狀態S設置為1，表示該貨位已經有貨存在，完成入庫任務。此時四向車為空車狀態，可以繼續執行下個任務。

例如，當出現圖3-a 情況時，B 車在巷道入口路段處將任務執行貨位更改為a貨位，解決出貨巷道內入庫任務間的死鎖。

四向車執行出庫任務流程如下：

步驟1：空車狀態的四向車接到出庫任務，如果四向車恰巧位于目標巷道內，并且目標貨位位于小車當前位置到出貨巷道出口之間，此時四向車可以直接出貨。如果四向車可以直接出貨，將出貨貨位狀態S更改為4，表示該貨位上的貨物已被分配出貨，并執行步驟3。否則，執行步驟2。

步驟2：將目標貨位狀態S設置為4，表示該貨位上的貨物已被分配出貨，設置四向車目的地為該貨位所在巷道入口處，使用Dijkstra 算法規劃路徑并尋路至巷道入口。

步驟3：從緊鄰巷道出口的貨位開始，沿巷道出入貨反方向查詢貨位狀態，選擇第一個貨位狀態為4的貨位，作為最終入庫目標貨位。并將該貨位狀態S更改為6，表示有四向車從該貨位出貨，并且已經進入巷道，防止在巷道入口路段的下個執行出庫任務的四向車選擇這個貨位為最終目標貨位。

步驟4：四向車啟動，到達最終出庫目標貨位完成取貨操作，將該貨位狀態S 更改為2，表示貨位為空。此時四向車變為載貨狀態。

步驟5：將四向車目的地設置為出庫口，并使用Dijkstra 算法規劃路徑，如果規劃路徑中需要借路通行，則將對應巷道的借路狀態T+1。

步驟6：四向車按照規劃路徑到達出庫口，執行卸貨操作，完成出庫任務。如果途中出現借路通行，及時更新對應巷道狀態T。此時四向車為空車狀態，可以繼續執行下個任務。

例如，當出現圖3-b 情況時，B 車在巷道入口路段處將任務執行貨位更改為a貨位，解決儲貨巷道內出庫任務間的死鎖。

當載貨四向車規劃路徑時，會選擇沒有存放貨物并且沒有生成入庫任務的空閑儲貨巷道借路，出現借路情況時，將借路儲貨巷道狀態T+1，表示會有一輛四向車借路，在四向車通過該儲貨巷道時及時將巷道狀態T-1，表示借路四向車已經通過。并且不生成儲貨巷道狀態T大于0巷道的入庫任務，解決借路載貨車造成的任務死鎖問題。

4 案例分析

某企業冷庫的多深度倉儲系統的儲貨區初步規劃如圖1所示，并給出三種不同的出入庫口布局方案，如圖5所示。倉儲系統設計要求及設備參數見表2。

圖5 三種布局

表2 倉儲系統設計要求及設備參數

4.1 建模仿真

采用Plant Simulation 軟件對倉儲系統單層進行仿真建模，如圖6所示。以下為針對仿真模型做出的假設：

（1）初始貨物容量為總庫位的80%；

（2）系統隨機產生的出入庫任務均滿足儲貨巷道先進先出的出入貨條件；

（3）四向車充電一次能夠連續工作8h；

（4）四向穿梭車連續執行出入庫任務以期獲得最大吞吐量；

（5）忽略提升機對出入庫的影響。

為選擇最佳布局和四向車數量，對于每種布局，四向車的數量從1變化至25 輛，仿真時間設置為24h，每個實驗重復進行10次，對吞吐量取平均值。

4.2 結果分析

實驗結果如圖7所示，布局1能夠在12輛車時滿足企業所提出的最大吞吐量為300托/h的要求，布局2和布局3均無法滿足該要求。

三種布局的吞吐量變化趨勢曲線類似，在四向車數量較少時，四向車數量與吞吐量呈線性相關，而當四向車數量達到10-16輛時，三種布局的吞吐量分別達到飽和狀態，之后增加四向車數量并不能使吞吐量增長，這是由于多車之間的堵塞抵消了車輛增多帶來的吞吐量增長。四向車整個工作過程中的等待時間（包括裝卸貨時間、轉向時間和多車堵塞時間）占比更加印證了這一點。如圖8所示，當四向車數量較少時，多車堵塞現象較少，等待時間占比相對穩定，而當四向車數量達到10-16 輛時，多車堵塞導致等待時間占比迅速增加，隨著四向車數量的不斷增加，四向車的使用效率不斷下降。

布局1能夠獲得更多的吞吐量，該布局出入庫口不在同一位置，能夠減少多車堵塞對吞吐量的影響。而在四向車少于8 輛時，多車堵塞現象較少，布局1相較布局2 更加有優勢，出入庫口位于同一位置，四向車出貨時無需繞路，完成單個任務效率較高。布局3 相較于其他兩個布局沒有優勢。企業可以靈活調整四向車數量以滿足不同的吞吐量需求。

圖6 仿真建模結果

圖7 出入庫口位置對吞吐量的影響

圖8 四向車等待時間占比變化趨勢

5 結語

本文對四向穿梭車多深度倉儲系統的調度策略進行了研究。采用道路定向的方式解決四向車沖突問題，提出任務調度策略解決儲貨巷道中的任務死鎖問題，保證單條巷道中執行不同任務四向車可同時工作，提高整個倉儲系統的工作效率。針對實際案例，通過仿真分析和優化，解決了倉儲布局選擇和四向車數量配置的問題，在工程應用中具有指導意義。