王曉軍，楊春霞*，陳航慧，范 英，白新利

(1.太原科技大學(xué)交通與物流學(xué)院，太原 030024;2.山西海德拉太礦國際采礦刀具設(shè)備有限公司，太原 030024)

AutoStore系統(tǒng)是一種新興的緊致輕載倉儲系統(tǒng)[1-2]，它取消巷道，將標準化貨格直接組合在一起，形成魔方型結(jié)構(gòu)；用于存儲貨物的料箱規(guī)格統(tǒng)一，垂直堆存在每個貨格中。自動引導(dǎo)車(automated guided vehicle，AGV)在貨架頂層沿軌道移動，小車4個側(cè)面各設(shè)有一組輪子，能實現(xiàn)前后左右4個方向的移動和轉(zhuǎn)向，小車底部裝有伸縮抓取裝置。工作臺設(shè)置在貨架邊緣，當存儲或揀選任務(wù)產(chǎn)生時，由工作人員確定要存入或揀選的料箱，將指令發(fā)送至AGV管理系統(tǒng)。AGV接受到指令后，移動到目標箱位所在貨格頂部，伸縮臂伸入貨格將料箱抓取收入自己“腹”中，隨后帶著料箱移動到工作臺頂部，并通過抓取裝置將料箱放入工作臺通道。待工作人員存入或揀選完貨物后，調(diào)用AGV將料箱運回，至此，完成一次存儲或揀選工作。

從上述工作流程看，AGV為該“貨到人”系統(tǒng)的核心環(huán)節(jié)，對其進行研究能提高系統(tǒng)運行效率。AGV路徑規(guī)劃是生產(chǎn)調(diào)度領(lǐng)域的熱點問題，中外已有較多研究成果：從問題研究范疇上，可分為靜態(tài)調(diào)度、動態(tài)調(diào)度和聯(lián)合調(diào)度[3-4]；從研究方法上，可分為數(shù)學(xué)建模方法、仿真優(yōu)化、智能優(yōu)化和混合優(yōu)化等[5-6]。然而，AutoStore獨特的倉儲結(jié)構(gòu)使得AGV路徑規(guī)劃問題與傳統(tǒng)研究有較大區(qū)別，主要體現(xiàn)在兩個方面：一方面，AutoStore系統(tǒng)中AGV在頂層軌道實現(xiàn)水平方向移動，底部伸縮裝置實現(xiàn)垂直方向移動，路徑規(guī)劃問題轉(zhuǎn)變?yōu)槿S空間路徑尋優(yōu)問題，傳統(tǒng)平面路徑尋優(yōu)方法已不適用；另一方面，AutoStore系統(tǒng)中存在大量的倒箱操作，當目標箱不在貨格頂層時，AGV需要將其上部的阻礙箱依次搬開直至目標箱處于頂層。這使得AGV除了要完成搬運目標箱的工作外，還需完成相應(yīng)的倒箱工作。而倒箱的次數(shù)和具體位置是可變的，即任務(wù)數(shù)不確定，增加了路徑規(guī)劃的復(fù)雜程度。

現(xiàn)階段針對AutoStore系統(tǒng)的研究大多關(guān)注生產(chǎn)線設(shè)計[7-8]、存儲策略[9-10]及貨位優(yōu)化[11]。王曉軍等[12]認為存儲越深的目標箱需要倒箱的可能性越高，因此在AGV路徑規(guī)劃建模時將目標箱垂直提升時間乘以了一個系數(shù)，但該研究未考慮倒箱實際操作，本質(zhì)上還是二維平面路徑尋優(yōu)問題。

考慮到AutoStore系統(tǒng)的倒箱和集裝箱堆場倒箱(翻箱)操作有一定的相似處，文獻[13-15]進行了分析。堆場倒箱主要發(fā)生在提箱環(huán)節(jié)，需要根據(jù)目標箱位置及當前堆場的實時狀態(tài)來制定倒箱堆放策略。在倒箱限制及落箱位的選擇上，所研究的內(nèi)容與堆場倒箱的不同之處如下。

(1)堆場倒箱操作大部分在單貝位內(nèi)進行，少部分能在相鄰貝位進行，但在AutoStore系統(tǒng)中，AGV可帶著料箱在整個貨格頂層行走，落箱位置選擇范圍更大，造成倒箱規(guī)模復(fù)雜。

(2)AutoStore系統(tǒng)是具有自我調(diào)節(jié)能力的智能系統(tǒng)，產(chǎn)生倒箱操作的料箱不需再運回原處，慢慢地提取率高的料箱會處于貨架上層，而提取率低的料箱會沉入下層。

(3)AutoStore大多采用訂單批處理的策略，即一次需要提取多個目標箱，使得阻礙箱數(shù)量增多，且阻礙箱的落箱位置會相互影響，使得問題研究更為復(fù)雜。

考慮倒箱操作的AutoStore系統(tǒng)AGV路徑規(guī)劃需解決以下核心問題：一是建立適合該魔方型倉儲揀選系統(tǒng)的倒箱策略；二是如何對能在三維空間活動的AGV路徑問題進行建模和求解；三是倒箱和搬運都需要由AGV完成，如何將兩者結(jié)合起來。

基于上述分析，首先在工作流程基礎(chǔ)上對問題進行了界定，給出了建模方法及倒箱、提箱的作業(yè)規(guī)則；其次建立了AGV路徑規(guī)劃雙層模型，內(nèi)層模型用于求解阻礙箱的倒箱路徑，以此為基礎(chǔ)，外層模型對多AGV路徑規(guī)劃問題進行了分析；然后基于模型特點提出了嵌套啟發(fā)式算法，最后通過算例對模型和算法進行了驗證和比較分析。

1 問題描述

AGV的指令均由工作臺發(fā)出，根據(jù)目標箱與工作臺的相對位置，可分為“目標箱出庫”和“目標箱入庫”兩類指令。其中“目標箱出庫”指將目標箱搬運至工作臺，可分解成如下步驟。

步驟1AGV接收任務(wù)，獲取目標箱及其上方阻礙箱的位置信息。

步驟2從當前位置空駛至目標箱貨格頂層。

步驟3依次搬運阻礙箱至相應(yīng)落箱位，直到目標箱位于頂層。

步驟4將目標箱搬運至工作臺。

步驟5出庫指令完成，釋放AGV。

工作人員在工作臺對目標箱完成揀選或存儲操作后，發(fā)出“目標箱入庫”指令，調(diào)用最近的空閑AGV，將目標料箱搬運回貨架，為了保持貨架整體存儲平衡，存入最深可用的貨格。與“目標箱出庫”相比，目標箱入庫較為簡單，屬于起始位置確定且不涉及倒箱操作的AGV調(diào)用問題，用最短路徑尋優(yōu)即可解決，因此，主要討論“目標箱出庫”這一階段。

在貨到人工作模式下，存儲和揀選的區(qū)別體現(xiàn)在工作人員對目標箱的操作及服務(wù)時間上，對AGV路徑規(guī)劃求解無本質(zhì)影響，因此，將二者統(tǒng)一考慮。同時為與實際情況相符，設(shè)工作人員一次處理一批訂單，訂單內(nèi)包含數(shù)個任務(wù)，但順序無先后約束。綜上，本問題可以簡述為：有一系列待提取目標箱，初始位置和終點位置(工作臺)確定，目標箱上面的阻礙箱數(shù)量及位置確定，有多個AGV，需要將阻礙箱倒箱及目標箱運輸任務(wù)分配給各AGV，并指定執(zhí)行先后順序，選擇最優(yōu)運行路徑。

1.1 AutoStore系統(tǒng)建模

AutoStore貨架呈魔方型結(jié)構(gòu)，在傳統(tǒng)柵格法建模[16]基礎(chǔ)上，采用柵格法進行三維建模。以貨架左下角為坐標原點O，對行、列、層分別建立X、Y和Z軸。以料箱尺寸為基本單位，將貨架劃分成立體柵格，一個柵格代表一個箱位，用確定坐標(x，y，z)表示。

圖1給出了4×4×4規(guī)模貨架示意圖。設(shè)貨架所有箱位集合為M，根據(jù)箱位是否存放料箱又可分為兩個子集合：被料箱占用的實箱位集合M1，如箱位a(1,1,4)∈M1；沒被占用的空箱位集合M2，如箱位e(2,1,4)∈M2。

圖1 三維柵格建模示意圖Fig.1 Schematic diagram of 3D grid modeling

貨架建模完成后，在頂層坐標(Zmax+1)處建立虛擬柵格區(qū)作為AGV移動區(qū)，如AGV1當前坐標為(3,1,5)，則移動路徑可以用一連串柵格坐標表示。AGV充電區(qū)設(shè)置貨格頂層外側(cè)，不影響貨格正常存儲，同時該區(qū)域也是路徑規(guī)劃的起始點和終點，如AGV2的坐標為(0,2,5)。工作臺設(shè)置在貨架外側(cè)，規(guī)模尺寸為兩個標準化貨格，上部為運輸通道，分為入庫通道和出庫通道，下部為人工操作臺。AGV將入庫目標箱放入入庫通道即可離去，目標箱在通道內(nèi)排隊，按先到先服務(wù)原則接受服務(wù)。工作人員完成操作后，將目標箱推入出庫通道底部，依次調(diào)用AGV。

1.2 目標箱及阻礙箱確定

同一波次訂單達到后，首先對其進行匯總，將同類貨品歸類，獲得待揀貨品列表及其所需求數(shù)量?？紤]到料箱尺寸較小，設(shè)定每個料箱只存放一類貨品且不能超過料箱容積，同類貨品可存儲在多個料箱中。對待揀選列表中的任一貨品，搜索所有存儲該貨品的料箱并確認庫存，當需求量小于某個料箱現(xiàn)有庫存量時，調(diào)用該目標箱；當需求量大于料箱最大庫存量時，需將該貨品訂單拆分成兩個訂單甚至更多，直到每個子訂單的需求能被單個料箱滿足。對訂單進行拆分能將訂單任務(wù)與需要提取的料箱一一對應(yīng)，確定目標箱集合N={1，2，…，n}，n≥初始訂單數(shù)。

目標箱確定后，其所在三維坐標系的位置也可以確定，則對應(yīng)阻礙箱也可以確定。對于目標箱i∈N，存在阻礙箱集合Ei={1，2，…，ni}，ni為目標料箱i上面阻礙箱的數(shù)目。同批次訂單內(nèi)，所有阻礙箱集合為E={E1，E2，…，En}，共有m個阻礙箱，m=n1+n2+…+ni,i∈N。

倒箱操作需將目標箱上的阻礙箱依次轉(zhuǎn)移到其他貨格的空余箱位。如圖1所示，若c(1,1,2)為目標箱，則b(1,1,3)和a(1,1,4)為阻礙箱，需依次搬運至其他空位。確定每個阻礙箱的落箱位是倒箱操作的核心環(huán)節(jié)，落箱位需滿足當前時刻為空箱且下方為實箱位的條件，如圖1中，g被占用，e下方為空，均不滿足條件，f、i可作為落箱位。對于阻礙箱j∈E，設(shè)落箱位置集合為Dj={1,2,…，mj}，其中mj為阻礙箱j的可落箱位置數(shù)目。對于所有阻礙箱，落箱位置集合為D={D1，D2，…，Dm}。

通過以上分析，AGV路徑規(guī)劃問題可轉(zhuǎn)化為：將訂單分解形成目標箱集合N，調(diào)用多個AGV，將阻礙箱集合E中的料箱搬運至集合D，將目標箱集合N中的料箱搬運至工作臺W接受服務(wù)并返回，在滿足相關(guān)約束的前提下，獲得AGV行駛路徑，以提高系統(tǒng)運行效率。

2 AGV路徑規(guī)劃雙層優(yōu)化模型

2.1 模型假設(shè)

分析可知，AGV任務(wù)可分解成兩類子任務(wù)：搬運阻礙箱和搬運目標箱。對搬運阻礙箱子任務(wù)，落箱位不確定，且當某一目標箱上面存在多個阻礙箱時，AGV需要多次返回倒箱；當多個AGV同時進行倒箱操作時，落箱位很容易出現(xiàn)沖突，因此，該任務(wù)求解的核心在于建立一個動態(tài)箱位狀態(tài)數(shù)據(jù)庫。對搬運目標箱子任務(wù)，需要AGV通過最短路徑將目標箱搬運至工作臺，問題的核心為多AGV任務(wù)指派。這兩個任務(wù)既有一定獨立性又有一定的順序約束，根據(jù)AGV調(diào)用情況，有兩種策略可以選擇：一是將目標箱和其對應(yīng)阻礙箱安排給同一AGV，即AGV接收到任務(wù)后，行走到目標箱頂層，先進行倒箱，再搬運目標箱；二是將AGV分成兩部分，一部分只負責(zé)倒箱，一部分只負責(zé)搬運?？紤]到目標箱和相應(yīng)阻礙箱都在同一貨格，采用第二種方法容易產(chǎn)生沖突，因此，使用第一種策略。

為此，將AGV路徑規(guī)劃抽象成一個車輛路徑問題(vehicle routing problem,VRP)：給多個任務(wù)(包含倒箱和搬運目標箱)安排AGV，每個任務(wù)必須且只能被完成一次。AGV完成任務(wù)的時間分解成4部分：①從當前位置移動到目標箱頂層的空駛時間，由AGV路徑規(guī)劃確定；②倒箱時間，由阻礙箱數(shù)目及各自落箱位確定；③目標箱直提時間，由目標箱縱向坐標確定；④水平搬運至工作臺時間，由AGV路徑規(guī)劃確定。

基于以上假設(shè)，可建立AGV路徑規(guī)劃雙層優(yōu)化模型，內(nèi)層模型求解指定任務(wù)的倒箱時間，以此為基礎(chǔ)，利用外層模型對多AGV路徑規(guī)劃問題進行分析。

2.2 內(nèi)層倒箱路徑模型

倒箱路徑優(yōu)化問題可以轉(zhuǎn)化成單AGV路徑規(guī)劃問題：調(diào)用AGV依次搬運阻礙箱，需確定落箱位，優(yōu)化目標為完成時間最短。且為了與外層路徑規(guī)劃模型相匹配，在內(nèi)層模型中，AGV初始位置和終點位置均為目標箱貨格頂層。

2.2.1 倒箱規(guī)則

對于任一阻礙箱i∈E，其落箱位包含兩方面的信息：一是水平坐標，表示AGV要搬運至何處；二是縱向坐標，表示放入位置的深度。在求解落箱位前，先確定倒箱規(guī)則。

規(guī)則1落箱位選擇范圍確定。為避免阻礙箱落在訂單內(nèi)其他目標箱上造成重復(fù)倒箱，需先行確定落箱位水平坐標范圍。

規(guī)則2落箱位滿足堆放約束。阻礙箱的落箱位必須為空，且當落箱位置不在第一層時，其下方相鄰箱位不為空。對箱位集合M中的箱位si，坐標為si(xi,yi,zi)。用θ(si)表示位置si的當前狀態(tài)，若有箱，則θ(si)=1，否則=0。

2.2.2 倒箱時間

|Zk-zi|tv}, ?k∈Dj

(1)

式(1)中：th、tv分別為AGV水平行駛單位距離時間和垂直提升單位距離時間。

(2)

2.3 多AGV路徑規(guī)劃優(yōu)化模型

2.3.1 模型假設(shè)

外層模型以內(nèi)層模型為基礎(chǔ)，并滿足以下假設(shè)：①考慮單一工作臺；②初始倉庫堆存狀態(tài)已知，不考慮缺貨無法滿足訂單需求的情況；③所有AGV勻速行駛，且不考慮重量影響；④對某一目標箱，阻礙箱倒箱和目標箱提取由同一個AGV完成，每AGV每次最多搬運一個料箱。

2.3.2 參數(shù)及決策變量

設(shè)N={1,2,…，n}為所有目標箱集合；設(shè)虛擬任務(wù)點集合A={0,1,2，…，n}，0表示AGV初始化位置；K={1,2,…，m}為所有AGV集合；工作臺坐標為(Work_X0,Work_Y0,Work_Z0)。

2.3.3 優(yōu)化目標及約束條件

為保證出庫作業(yè)快速完成，以最小化AGV最長作業(yè)時間為目標，包括前往目標箱的空駛時間與服務(wù)于目標箱的工作時間，目標函數(shù)的表達式為

?k∈K

(3)

與目標箱服務(wù)時間相關(guān)約束為

(4)

(5)

?i∈N

(6)

與AGV任務(wù)指派相關(guān)約束為

(7)

(8)

(9)

式(7)、式(8)表示每個目標箱都會被訪問唯一一次，式(9)表示若小車k從目標箱j到目標箱i，則目標箱i被小車k服務(wù)。

與AGV空駛相關(guān)約束為

?i∈N,?j∈N

(10)

?k∈K,?j∈N

(11)

?k∈K,?i∈N

(12)

(13)

(14)

3 嵌套式路徑生成啟發(fā)式算法

3.1 算法原理

根據(jù)魔方型倉儲結(jié)構(gòu)及優(yōu)化模型的特點，算法需解決以下5個核心問題。

3.1.1 倉儲狀態(tài)隨機生成子系統(tǒng)

通過三維柵格法建成貨架結(jié)構(gòu)后，可根據(jù)實際情況依次設(shè)定存有料箱的箱位。但為了提高算法適用性，能多次重復(fù)進行不同規(guī)模的試驗，建立倉儲狀態(tài)隨機生成子系統(tǒng)，主要步驟為：①確定需生成的存儲比例；②在所有空余箱位中，隨機生成一個料箱；③判斷該料箱是否滿足堆存規(guī)則，即除了在第一層，下層不能為空，滿足則留下該料箱，否則刪除；④重復(fù)②，直到料箱數(shù)量/總箱位數(shù)達到要求的存儲比例。

3.1.2 箱位狀態(tài)數(shù)據(jù)庫系統(tǒng)

倒箱和移箱不僅會使得相應(yīng)箱位狀態(tài)發(fā)生變化，更會影響隨后的決策。建立一個箱位狀態(tài)數(shù)據(jù)庫，在提取和存入等關(guān)鍵節(jié)點及時更新。路徑尋優(yōu)過程中，均在當前箱位狀態(tài)下進行。

3.1.3 多AGV實時并行系統(tǒng)

多AGV同時作業(yè)屬于多線程并行問題。在已有多AGV路徑規(guī)劃研究中，該問題的求解一般分為兩步：首先不考慮時間線，將多AGV依次分配給多個任務(wù)，得到數(shù)條初始規(guī)劃路徑；其次，考慮每段路徑的起止時間約束，將所有路徑安排在同一時間軸上，得到可執(zhí)行路徑。在所研究的AGV路徑規(guī)劃問題，除了將目標箱搬運至工作臺外，還需要接受入庫指令，入庫指令的時間取決于工作臺的服務(wù)狀態(tài)，無法通過計算式直接求解。因此，采用仿真模擬的思想，在路徑規(guī)劃時就引入時間線，建立AGV實時并行系統(tǒng)，一步生成路徑方案。

3.1.4 任務(wù)安排及AGV調(diào)用系統(tǒng)

多AGV多任務(wù)指派的核心在于確定目標箱提取順序和AGV調(diào)用策略。考慮到同波次訂單已經(jīng)在目標箱生成中被打亂順序，按到達時間順序提取意義不大。在魔方型倉儲中，壓箱會造成過多的倒箱，因此，設(shè)定提取原則為：目標箱提取順序與其阻礙箱數(shù)目成反比，當阻礙箱數(shù)目一致時，越靠近貨架底層的越先提取，以減少后期被壓箱的可能性。

確定目標箱提取順序后，依次將任務(wù)安排給AGV。AGV安排策略有兩種，先完成先分配和輪流分配。先完成先分配能減少在貨格頂層移動的AGV數(shù)目，減少沖突，因此采用此策略。

3.1.5 分階段路徑生成系統(tǒng)

將某個目標箱任務(wù)指派給某AGV后，該AGV的路徑生成可以分解成3個階段：①從接收到指令時的當前位置移動到目標箱頂層，用最短折線路線法生成行駛路徑；②倒箱路徑生成，首先根據(jù)倒箱路徑優(yōu)化模型求得最優(yōu)落箱位，其次采用最短折線路線法生成倒箱路徑；③將目標箱提升到頂層后，通過最短折線路線法生成到工作臺的路徑。

3.2 算法流程

采用Python語言編寫算法程序。算法從結(jié)構(gòu)上可以分為內(nèi)外兩層，兩層互相嵌套互相影響。外層求解多AGV指派多個任務(wù)問題，需要建立兩個列表，待執(zhí)行任務(wù)列表和空閑AGV列表，從任務(wù)列表中依次提取目標箱，將其分配給AGV列表中的小車，過程中需滿足上節(jié)所述任務(wù)安排及AGV調(diào)用策略。外層主要結(jié)構(gòu)如圖2所示。

Free AGV List為空閑AGV列表；Task List為任務(wù)列表；All Task List為待執(zhí)行任務(wù)列表圖2 算法外層結(jié)構(gòu)主要流程圖Fig.2 Main flow chart of the outer structure of the algorithm

外層結(jié)構(gòu)中的單AGV路徑規(guī)劃方案需調(diào)用內(nèi)層算法求解。內(nèi)層算法的已知條件為將小車I配置給了目標箱i，目標箱位置為(x，y，z)，包括4個步驟：①確定阻礙箱列表；②確定有效空位列表；③依次將所有阻礙箱搬運至最優(yōu)空位；④搬運小車至工作臺。內(nèi)層算法結(jié)構(gòu)圖如圖3所示。

圖3 算法內(nèi)層法結(jié)構(gòu)圖Fig.3 Calculating the structure diagram of the inner layer method

4 算例分析與比較

AutoStore系統(tǒng)中，倉儲規(guī)模、存儲率、AGV數(shù)目、目標箱數(shù)目4個參數(shù)會直接影響AGV路徑尋優(yōu)的結(jié)果。先通過一典型工況對算法的有效性進行分析；再對不同參數(shù)取值進行對比，以分析算法的效率及適應(yīng)性。

4.1 有效性分析

設(shè)典型工況基本參數(shù)為：倉庫規(guī)模為10×10×10；倉儲率為75%；AGV數(shù)目為5臺；隨機生成20個目標箱位；同時AGV水平行駛速度為3格/s，垂直提升速度為2格/s。算法隨機生成的倉儲系統(tǒng)如圖4所示。

通過嵌套式啟發(fā)式算法進行求解，可得到每個AGV的任務(wù)分配方案及行走路徑。首先以2號AGV為例，進行路徑分析。圖5中，目標箱位置為(10,2,8)，上面有一個障礙箱(10,2,9)，小車的當前位置在(4,1,11)。小車的路徑一共分為以下5步：①從當前位置水平移至目標箱貨格頂層(10,2,11)；②伸縮臂伸入貨格提取障礙箱至頂層；③通過倒箱路徑尋優(yōu)模型，找到最近的倒箱位置(8，2，10)，將障礙箱放入；④返回至目標箱頂層；⑤將目標箱搬運至工作臺(10，10，11)。

圖5 AGV搬運一個目標箱路徑Fig.5 The path diagram of the AGV carrying a target box

所有AGV路徑方案統(tǒng)計如表1所示。AGV遵循輪流分配策略，每臺車服務(wù)的目標箱數(shù)目均為4臺，總服務(wù)時間差別不大。倒箱服務(wù)存在大量的往返操作，因此，各AGV空載和負載時間也相差不大。對此工況，算法求解效率較高，僅為0.12 s。

表1 典型工況下AGV路徑規(guī)劃統(tǒng)計Table 1 AGV path planning statistics under typical working conditions

4.2 不同參數(shù)規(guī)模下的問題求解及分析

4.2.1 倉儲規(guī)模變化工況

AutoStore系統(tǒng)一般布置在室內(nèi)，考慮到空間高度，一般層數(shù)為10～20層。為使研究更為普遍性，倉儲規(guī)模為10×10×10、15×15×15、20×20×20，倉儲率為75%，5臺AGV，20個目標箱工況下，統(tǒng)計AGV作業(yè)時間和運算效率，如表2所示。倉儲規(guī)模增大后，目標箱分散度增加，單AGV和所有AGV作業(yè)時間大幅度增加。運算時間也大幅度增加，但絕對值不高。

表2 倉儲規(guī)模變化下AGV方案及求解效率對比Table 2 Comparison of AGV schemes and solution efficiency under changing conditions of storage scale

綠色為目標箱；紅色為阻礙箱；其余為白色圖4 75%存儲率的倉儲系統(tǒng)Fig.4 75% storage rate warehousing system

4.2.2 AGV數(shù)量變化工況

對4.1節(jié)工況增加AGV數(shù)，即倉儲規(guī)模10×10×10，存儲率75%，20個目標箱對應(yīng)計算結(jié)果如表3所示。AGV數(shù)量翻倍后，單個AGV分配的目標箱只有原來的1/2，因此作業(yè)時間也相應(yīng)減少。相應(yīng)的，等待AGV的時間也有所減少，使得總作業(yè)時間減少。求解效率影響不大。

表3 AGV數(shù)目變化下AGV方案及求解效率對比Table 3 Comparison of AGV schemes and solution efficiency under changing conditions of the number of AGVs

4.2.3 倉儲率變化工況

倉儲率會影響倒箱位置和垂直提升距離，在倉儲規(guī)模為15×15×15,5臺AGV，20個目標箱，倉儲率分別為50%，75%，90%工況下計算結(jié)果如表4所示。當倉儲率發(fā)生變化時，受目標箱位置隨機分布的影響，最長AGV作業(yè)時間變化不明顯。總作業(yè)時間隨著倉儲率增加而增加，通過分析具體路徑發(fā)現(xiàn)，當倉儲率高時，阻礙箱數(shù)目增加，倒箱次數(shù)增多。運算效率隨倉儲率提高而提高，主要是因為當倉儲率較高時，落箱位的選擇性變少，更容易找到倒箱位置。

表4 倉儲率變化下AGV方案及求解效率對比Table 4 Comparison of AGV schemes and solution efficiency under changing storage rates

4.2.4 目標箱數(shù)目變化工況

在倉儲規(guī)模為20×20×20，倉儲率為75%，5臺AGV的工況下，計算對比結(jié)果如表5所示。隨著目標箱增多，單個AGV服務(wù)時間增加，總時間增加，呈較明顯的正相關(guān)關(guān)系。考慮到目標箱生成的隨機性，運算效率變化規(guī)律在此不明顯，但絕對值都不高。

表5 目標箱變化下AGV方案及求解效率對比Table 5 Comparison of AGV schemes and solution efficiency under changing conditions of target box

5 結(jié)論

(1)AGV雙層路徑規(guī)劃模型能將倒箱路徑尋優(yōu)與多AGV任務(wù)分配及尋優(yōu)進行結(jié)合，符合AutoStore系統(tǒng)的工作特性，算例中的AGV路徑方案也證明了在三維空間探索的有效性。

(2)根據(jù)模型特點給出了嵌套式啟發(fā)式算法，通過Python編寫算法程序，重點解決了倉儲狀態(tài)隨機生成子系統(tǒng)、箱位狀態(tài)數(shù)據(jù)庫系統(tǒng)、多AGV并行系統(tǒng)、AGV任務(wù)分配系統(tǒng)及路徑生成系統(tǒng)等核心問題。

(3)不同工況的算例結(jié)果表明：倉儲規(guī)模增大后，目標箱分散度增加，AGV作業(yè)時間大幅度增加；AGV數(shù)量和作業(yè)時間負相關(guān)；倉儲率提高會增加倒箱幾率，增加作業(yè)時間；目標箱數(shù)目變化與AGV作業(yè)時間正相關(guān)。在求解效率方面，主要受目標箱隨機生成位置和倉儲率影響，但絕對值也僅在10秒左右。

(4)需說明的是，僅研究了將目標箱移動至工作臺這一階段，在下一步工作中，會與目標箱返回相結(jié)合。同時因貨格頂層行走路徑較多，未特意設(shè)置沖突解決策略。在實際求解中，當兩車需同時占用一個節(jié)點時，隨機選取其一為優(yōu)先級高的車，讓其先行，另外一輛車等待即可。