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

（1.同濟(jì)大學(xué) 機(jī)械與能源工程學(xué)院，上海 201804；2.浙江衢州聯(lián)州致冷劑有限公司，浙江 衢州 324004）

1 引言

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

國(guó)內(nèi)外學(xué)者針對(duì)四向穿梭式多深度倉(cāng)儲(chǔ)系統(tǒng)進(jìn)行了相應(yīng)研究。Manzini 等[4]提出了四向車單車存取貨物的行程時(shí)間數(shù)學(xué)模型，并進(jìn)行了倉(cāng)儲(chǔ)系統(tǒng)布局優(yōu)化。D’Antonio 等[5-6]提出了單次行程中包含多個(gè)存取貨物任務(wù)的行程時(shí)間數(shù)學(xué)模型，基于該模型進(jìn)行了四向車調(diào)度策略優(yōu)化。然而，文獻(xiàn)中提出的數(shù)學(xué)模型只針對(duì)單條主干道只運(yùn)行一輛四向車的情況，無(wú)法解決多車同時(shí)運(yùn)行的問(wèn)題。Tappia 等[7]使用排隊(duì)網(wǎng)絡(luò)建立分析模型，評(píng)估單層和多層多深度倉(cāng)儲(chǔ)系統(tǒng)的運(yùn)行情況，但模型并未考慮四向車的死鎖和堵塞問(wèn)題，使得結(jié)果和實(shí)際情況有較大偏差。付曉峰等[8]提出了針對(duì)四向車多深度倉(cāng)儲(chǔ)系統(tǒng)的貨物入庫(kù)上架過(guò)程和貨位分配方法，但文中使用的區(qū)域控制方法使得一條儲(chǔ)貨巷道中同時(shí)只允許一輛四向車工作，處于等待狀態(tài)的四向車會(huì)堵塞主干道，影響正常通行，導(dǎo)致系統(tǒng)效率較低。

本文針對(duì)倉(cāng)儲(chǔ)系統(tǒng)多深度儲(chǔ)貨區(qū)存在的問(wèn)題，基于道路定向法提出了四向車多車調(diào)度策略，避免車輛沖突與任務(wù)死鎖，保證了倉(cāng)儲(chǔ)系統(tǒng)高效運(yùn)行，并結(jié)合實(shí)際案例驗(yàn)證了所提策略的有效性。

2 問(wèn)題描述

多深度倉(cāng)儲(chǔ)系統(tǒng)由垂直提升機(jī)、四向穿梭車、多層貨架及管理控制系統(tǒng)組成。四向穿梭車實(shí)現(xiàn)貨架儲(chǔ)貨區(qū)托盤貨物的水平轉(zhuǎn)運(yùn)，垂直提升機(jī)實(shí)現(xiàn)托盤貨物的垂直轉(zhuǎn)運(yùn)和四向穿梭車的換層，控制信息系統(tǒng)負(fù)責(zé)整個(gè)倉(cāng)儲(chǔ)系統(tǒng)的設(shè)備監(jiān)控和調(diào)度。儲(chǔ)貨區(qū)域?yàn)槎鄬迂浖芙Y(jié)構(gòu)，每層布局相同，如圖1所示，儲(chǔ)貨區(qū)由多條平行的儲(chǔ)貨巷道構(gòu)成，每條儲(chǔ)貨巷道中有多個(gè)貨位。每條儲(chǔ)貨巷道中只能存放同一品類同一批次的貨物，即一個(gè)SKU（Stock Keep Unit），為保證倉(cāng)儲(chǔ)系統(tǒng)貨物先進(jìn)先出的原則，儲(chǔ)貨巷道內(nèi)的貨物同樣采用先進(jìn)先出的操作方式，即只從儲(chǔ)貨巷道一端入貨，從另一端出貨。

四向車采用電力驅(qū)動(dòng)，能夠與控制信息系統(tǒng)進(jìn)行無(wú)線通訊，接收出入庫(kù)任務(wù)。當(dāng)?shù)竭_(dá)目標(biāo)貨位時(shí)，通過(guò)托盤舉升裝置將托盤抬升或下降實(shí)現(xiàn)貨物的裝卸。四向車可沿巷道橫向和縱向四個(gè)方向行駛，可深入儲(chǔ)貨巷道內(nèi)部到達(dá)倉(cāng)儲(chǔ)系統(tǒng)中的任何一個(gè)儲(chǔ)位，當(dāng)四向穿梭車處于空車狀態(tài)時(shí)，可以在存有貨物的巷道中自由穿梭，當(dāng)四向穿梭車為載貨狀態(tài)時(shí)，可以在空閑的儲(chǔ)貨巷道中借路通行。

圖1 單層布局圖

對(duì)于單層儲(chǔ)貨區(qū)來(lái)說(shuō)，當(dāng)空閑四向車接到貨物入庫(kù)命令時(shí)，四向車從當(dāng)前位置尋路至每層的入庫(kù)口處，從入庫(kù)口的提升機(jī)處接取貨物后，將貨物運(yùn)送至指定貨位。執(zhí)行出庫(kù)命令時(shí)，四向穿梭車按照任務(wù)指示，尋路到待出庫(kù)貨物所在貨位，將貨物運(yùn)送至出庫(kù)口處的提升機(jī)。但在四向車運(yùn)行過(guò)程中，多車同時(shí)執(zhí)行任務(wù)會(huì)造成四向車之間、儲(chǔ)貨巷道內(nèi)任務(wù)之間出現(xiàn)死鎖與沖突，兩類沖突如圖2所示。

圖2 四向穿梭車沖突類型

當(dāng)多車同時(shí)運(yùn)行時(shí)，在道路交叉口處出現(xiàn)的四向車沖突與死鎖，會(huì)導(dǎo)致整個(gè)單層儲(chǔ)貨區(qū)癱瘓。如圖2所示，單層儲(chǔ)貨區(qū)中主要存在兩種形式的車輛沖突。圖2-a 為路口沖突，如果調(diào)度系統(tǒng)不加以控制，A、B 兩車將在路口發(fā)生碰撞，圖2-b 為相向沖突，該沖突類型會(huì)導(dǎo)致A、B兩車死鎖情況的發(fā)生。當(dāng)在主干道發(fā)生車輛沖突與死鎖時(shí)，會(huì)造成單層儲(chǔ)貨區(qū)的出入庫(kù)任務(wù)無(wú)法正常執(zhí)行，倉(cāng)儲(chǔ)系統(tǒng)吞吐量會(huì)受到大幅影響。

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

圖3 儲(chǔ)貨巷道內(nèi)任務(wù)死鎖類型

3 調(diào)度策略

3.1 道路定向策略

為避免圖2-a所示的路口沖突，采用路口使用權(quán)鎖定策略。當(dāng)A、B 兩車需要同時(shí)通過(guò)路口時(shí)，均需要申請(qǐng)路口節(jié)點(diǎn)的使用權(quán)，只有路口使用權(quán)被釋放時(shí)，下一輛四向車才能通過(guò)路口。同時(shí)在路口處維護(hù)一個(gè)四向車等待列表，路口按照通過(guò)等待列表中的次序依次放行每輛四向車。為避免如圖2-b 所示的相向沖突導(dǎo)致的車輛死鎖情況的發(fā)生，在滿足巷道內(nèi)貨物先進(jìn)先出特性的前提下，采用主干道定向策略解決四向車的死鎖問(wèn)題，保證了多輛四向車能夠在倉(cāng)儲(chǔ)區(qū)域的流暢運(yùn)行。主干道與儲(chǔ)貨巷道的定向結(jié)果如圖4所示。

圖4 主干道定向方向

3.2 任務(wù)交換策略

為解決儲(chǔ)貨巷道內(nèi)的任務(wù)死鎖問(wèn)題，采用巷道內(nèi)任務(wù)交換策略。利用巷道和貨位的多種狀態(tài)，靈活調(diào)整四向車最終執(zhí)行的任務(wù)，當(dāng)一條巷道內(nèi)同時(shí)出現(xiàn)多個(gè)出庫(kù)與入庫(kù)任務(wù)時(shí)，四向車先尋路到目標(biāo)貨位所在巷道的入口處，從緊鄰儲(chǔ)貨巷道出口的貨位開始，沿巷道出入貨反方向查詢貨位狀態(tài)，選擇第一個(gè)可以執(zhí)行的對(duì)應(yīng)任務(wù)，作為最終目標(biāo)任務(wù)，從而避免任務(wù)死鎖，保證一條巷道中的多個(gè)任務(wù)都能被順利執(zhí)行。貨位狀態(tài)S 和巷道狀態(tài)T 不同狀態(tài)對(duì)應(yīng)的不同含義均在狀態(tài)表中列出，見(jiàn)表1。

表1 狀態(tài)表

四向車執(zhí)行入庫(kù)任務(wù)流程如下：

步驟1：空車狀態(tài)的四向車接收到入庫(kù)任務(wù)后，將對(duì)應(yīng)貨位狀態(tài)代碼S設(shè)置為3，表示該貨位已被分配入貨，防止被選為下個(gè)入庫(kù)任務(wù)。

步驟2：將四向車當(dāng)前目的地設(shè)置為入庫(kù)口，使用Dijkstra 算法規(guī)劃路徑，并尋路至入庫(kù)口完成取貨操作。此時(shí)四向車為載貨狀態(tài)。

步驟3：將四向車當(dāng)前目的地設(shè)置為目標(biāo)貨位巷道的入口處，使用Dijkstra 算法規(guī)劃路徑，如果規(guī)劃路徑中需借路通行，則將對(duì)應(yīng)巷道的借路狀態(tài)T+1。

步驟4：四向車按照規(guī)劃路徑到達(dá)巷道入口。如果途中出現(xiàn)借路通行，及時(shí)更新借路巷道對(duì)應(yīng)的巷道狀態(tài)T。

步驟5：從緊鄰巷道出口的貨位開始，沿巷道出入貨反方向查詢貨位狀態(tài)，選擇第一個(gè)貨位狀態(tài)為3的貨位，作為最終入庫(kù)目標(biāo)貨位。將該最終目標(biāo)貨位狀態(tài)S更改為5，表示有四向車向該貨位入貨，并且已經(jīng)進(jìn)入巷道，防止在巷道入口路段的下個(gè)執(zhí)行入庫(kù)任務(wù)的四向車選擇這個(gè)貨位為最終目標(biāo)貨位。

步驟6：進(jìn)入巷道，到達(dá)目標(biāo)貨位后卸貨，將該貨位狀態(tài)S設(shè)置為1，表示該貨位已經(jīng)有貨存在，完成入庫(kù)任務(wù)。此時(shí)四向車為空車狀態(tài)，可以繼續(xù)執(zhí)行下個(gè)任務(wù)。

例如，當(dāng)出現(xiàn)圖3-a 情況時(shí)，B 車在巷道入口路段處將任務(wù)執(zhí)行貨位更改為a貨位，解決出貨巷道內(nèi)入庫(kù)任務(wù)間的死鎖。

四向車執(zhí)行出庫(kù)任務(wù)流程如下：

步驟1：空車狀態(tài)的四向車接到出庫(kù)任務(wù)，如果四向車恰巧位于目標(biāo)巷道內(nèi)，并且目標(biāo)貨位位于小車當(dāng)前位置到出貨巷道出口之間，此時(shí)四向車可以直接出貨。如果四向車可以直接出貨，將出貨貨位狀態(tài)S更改為4，表示該貨位上的貨物已被分配出貨，并執(zhí)行步驟3。否則，執(zhí)行步驟2。

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

步驟3：從緊鄰巷道出口的貨位開始，沿巷道出入貨反方向查詢貨位狀態(tài)，選擇第一個(gè)貨位狀態(tài)為4的貨位，作為最終入庫(kù)目標(biāo)貨位。并將該貨位狀態(tài)S更改為6，表示有四向車從該貨位出貨，并且已經(jīng)進(jìn)入巷道，防止在巷道入口路段的下個(gè)執(zhí)行出庫(kù)任務(wù)的四向車選擇這個(gè)貨位為最終目標(biāo)貨位。

步驟4：四向車啟動(dòng)，到達(dá)最終出庫(kù)目標(biāo)貨位完成取貨操作，將該貨位狀態(tài)S 更改為2，表示貨位為空。此時(shí)四向車變?yōu)檩d貨狀態(tài)。

步驟5：將四向車目的地設(shè)置為出庫(kù)口，并使用Dijkstra 算法規(guī)劃路徑，如果規(guī)劃路徑中需要借路通行，則將對(duì)應(yīng)巷道的借路狀態(tài)T+1。

步驟6：四向車按照規(guī)劃路徑到達(dá)出庫(kù)口，執(zhí)行卸貨操作，完成出庫(kù)任務(wù)。如果途中出現(xiàn)借路通行，及時(shí)更新對(duì)應(yīng)巷道狀態(tài)T。此時(shí)四向車為空車狀態(tài)，可以繼續(xù)執(zhí)行下個(gè)任務(wù)。

例如，當(dāng)出現(xiàn)圖3-b 情況時(shí)，B 車在巷道入口路段處將任務(wù)執(zhí)行貨位更改為a貨位，解決儲(chǔ)貨巷道內(nèi)出庫(kù)任務(wù)間的死鎖。

當(dāng)載貨四向車規(guī)劃路徑時(shí)，會(huì)選擇沒(méi)有存放貨物并且沒(méi)有生成入庫(kù)任務(wù)的空閑儲(chǔ)貨巷道借路，出現(xiàn)借路情況時(shí)，將借路儲(chǔ)貨巷道狀態(tài)T+1，表示會(huì)有一輛四向車借路，在四向車通過(guò)該儲(chǔ)貨巷道時(shí)及時(shí)將巷道狀態(tài)T-1，表示借路四向車已經(jīng)通過(guò)。并且不生成儲(chǔ)貨巷道狀態(tài)T大于0巷道的入庫(kù)任務(wù)，解決借路載貨車造成的任務(wù)死鎖問(wèn)題。

4 案例分析

某企業(yè)冷庫(kù)的多深度倉(cāng)儲(chǔ)系統(tǒng)的儲(chǔ)貨區(qū)初步規(guī)劃如圖1所示，并給出三種不同的出入庫(kù)口布局方案，如圖5所示。倉(cāng)儲(chǔ)系統(tǒng)設(shè)計(jì)要求及設(shè)備參數(shù)見(jiàn)表2。

圖5 三種布局

表2 倉(cāng)儲(chǔ)系統(tǒng)設(shè)計(jì)要求及設(shè)備參數(shù)

4.1 建模仿真

采用Plant Simulation 軟件對(duì)倉(cāng)儲(chǔ)系統(tǒng)單層進(jìn)行仿真建模，如圖6所示。以下為針對(duì)仿真模型做出的假設(shè)：

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

（2）系統(tǒng)隨機(jī)產(chǎn)生的出入庫(kù)任務(wù)均滿足儲(chǔ)貨巷道先進(jìn)先出的出入貨條件；

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

（4）四向穿梭車連續(xù)執(zhí)行出入庫(kù)任務(wù)以期獲得最大吞吐量；

（5）忽略提升機(jī)對(duì)出入庫(kù)的影響。

為選擇最佳布局和四向車數(shù)量，對(duì)于每種布局，四向車的數(shù)量從1變化至25 輛，仿真時(shí)間設(shè)置為24h，每個(gè)實(shí)驗(yàn)重復(fù)進(jìn)行10次，對(duì)吞吐量取平均值。

4.2 結(jié)果分析

實(shí)驗(yàn)結(jié)果如圖7所示，布局1能夠在12輛車時(shí)滿足企業(yè)所提出的最大吞吐量為300托/h的要求，布局2和布局3均無(wú)法滿足該要求。

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

布局1能夠獲得更多的吞吐量，該布局出入庫(kù)口不在同一位置，能夠減少多車堵塞對(duì)吞吐量的影響。而在四向車少于8 輛時(shí)，多車堵塞現(xiàn)象較少，布局1相較布局2 更加有優(yōu)勢(shì)，出入庫(kù)口位于同一位置，四向車出貨時(shí)無(wú)需繞路，完成單個(gè)任務(wù)效率較高。布局3 相較于其他兩個(gè)布局沒(méi)有優(yōu)勢(shì)。企業(yè)可以靈活調(diào)整四向車數(shù)量以滿足不同的吞吐量需求。

圖6 仿真建模結(jié)果

圖7 出入庫(kù)口位置對(duì)吞吐量的影響

圖8 四向車等待時(shí)間占比變化趨勢(shì)

5 結(jié)語(yǔ)

本文對(duì)四向穿梭車多深度倉(cāng)儲(chǔ)系統(tǒng)的調(diào)度策略進(jìn)行了研究。采用道路定向的方式解決四向車沖突問(wèn)題，提出任務(wù)調(diào)度策略解決儲(chǔ)貨巷道中的任務(wù)死鎖問(wèn)題，保證單條巷道中執(zhí)行不同任務(wù)四向車可同時(shí)工作，提高整個(gè)倉(cāng)儲(chǔ)系統(tǒng)的工作效率。針對(duì)實(shí)際案例，通過(guò)仿真分析和優(yōu)化，解決了倉(cāng)儲(chǔ)布局選擇和四向車數(shù)量配置的問(wèn)題，在工程應(yīng)用中具有指導(dǎo)意義。