楊春霞 陳航慧 師浩森

摘 ?要：為探究針對魔方型倉儲系統(tǒng)的多AGV調(diào)度問題，建立考慮倒箱因素的多AGV調(diào)度優(yōu)化數(shù)學(xué)模型，設(shè)計改進的多層編碼的遺傳算法，有助于算法跳出局部最優(yōu)并改善其局部搜索能力。通過設(shè)計不同算例，對比優(yōu)化前后的AGV調(diào)度方案，驗證改進算法的有效性和可行性，同時，對不同任務(wù)規(guī)模、AGV規(guī)模、倉儲填充率、倉儲立體規(guī)模和倉儲平面規(guī)模五方面的工況進行探究分析，為魔方型倉儲系統(tǒng)運行狀況研究提供理論基礎(chǔ)。

關(guān)鍵詞：魔方型倉儲；AGV任務(wù)分配；改進遺傳算法

中圖分類號：F406.5文獻標志碼：ADOI：10.13714/j.cnki.1002-3100.2024.11.045

Abstract： In order to explore the multi-AGV scheduling problem for the Rubik's cube storage system， establish a multi-AGV scheduling optimization mathematical model considering the factor of the box， and design an improved multi-layer coding genetic algorithm， which is helpful for the algorithm to jump out of the local optimum and improve its local search capability， through designing standard examples， comparing the AGV scheduling scheme before and after optimization， and verifying the effectiveness and feasibility of the improved algorithm. The working conditions are explored and analyzed， which provides a theoretical basis for the research on the operation status of the Rubik's cube storage system.

Key words： Rubik's cube storage; AGV task assignment; improved genetic algorithm

魔方型倉儲系統(tǒng)是一種新型密集倉儲系統(tǒng)，與傳統(tǒng)倉儲系統(tǒng)相比，有較大的區(qū)別。如圖1仿真模型所示，貨架整體呈現(xiàn)魔方型結(jié)構(gòu)，每一縱列稱之為一個貨格，存儲單元（白色貨箱）依次放置其中；其次，揀選AGV在貨架頂部水平移動，通過伸縮裝置深入貨格抓取貨箱。這種模塊化結(jié)構(gòu)使得該系統(tǒng)具有存儲能力強、拓展性強、自動化程度高等特點，適用于輕載倉儲領(lǐng)域。

現(xiàn)階段魔方型倉儲系統(tǒng)主要以Auto Store系統(tǒng)為代表，與AGV調(diào)度相關(guān)研究主要體現(xiàn)在以下幾個方面：王博[1]對Auto Store系統(tǒng)多AGV路徑規(guī)劃策略進行研究與仿真。王曉軍等[2]通過雙層路徑規(guī)劃將倒箱路徑尋優(yōu)嵌入多AGV多任務(wù)路徑分配中。李沁[3]重點研究了翻箱策略方面，但該文沒有進一步研究翻箱和目標箱調(diào)度問題。Xiang T R Kong等[4]提出蜂窩倉儲模型，分析蜂窩倉儲的形成、操作流程和應(yīng)用場景，創(chuàng)建其物理仿模型作為進一步評估的試驗臺。H？覽v？覽s A K[5]對Auto Store的錯誤數(shù)據(jù)庫進行分析，根據(jù)分析結(jié)果提出正確的維護措施。Tjeerdsma S[6]利用布局規(guī)劃、產(chǎn)能規(guī)劃和生產(chǎn)管理提高Auto Store生產(chǎn)線的性能，提出五種干預(yù)措施并通過模擬模型進行評估驗證。

現(xiàn)有相關(guān)研究中，一部分完全不考慮倒箱因素對所研究問題的影響，另一部分雖然考慮倒箱因素，卻只在宏觀上提出倒箱策略，倒箱對其所研究問題產(chǎn)生了何種影響以及如何產(chǎn)生影響并沒有明確的研究，更沒有在考慮倒箱操作下的系統(tǒng)優(yōu)化問題。

1 ?問題描述

在對Auto Store密集倉儲系統(tǒng)任務(wù)調(diào)度優(yōu)化中，揀選AGV每次只能搬運一個料箱。Auto Store系統(tǒng)的任務(wù)調(diào)度過程包含兩個環(huán)節(jié)：一是把阻礙箱搬走，二是提取目標箱。

倒箱操作是為取出目標箱而將目標箱上方的阻礙箱依次搬走的操作。在探究倒箱作業(yè)的具體流程中，主要解決兩個問題：一是誰來搬運阻礙箱，二是將阻礙箱放置在何處。本文選擇AGV合用的方法來搬運阻礙箱，AGV合用即用同一個AGV進行阻礙箱的搬運和目標箱的提取。

AGV提取目標箱為傳統(tǒng)意義上的任務(wù)調(diào)度，但AGV合用則將倒箱作業(yè)也由該AGV完成，即在傳統(tǒng)任務(wù)調(diào)度中加入倒箱操作，需將倒箱作業(yè)視為任務(wù)調(diào)度中的一個環(huán)節(jié)，將其嵌入任務(wù)調(diào)度中。

因此，該問題可轉(zhuǎn)為三個子問題：一是選擇合適的倒箱策略以確定阻礙箱的落箱位置；二是探究多AGV任務(wù)調(diào)度數(shù)學(xué)模型及求解算法；三是探究倒箱作業(yè)與任務(wù)調(diào)度之間的聯(lián)系，將倒箱作業(yè)模型嵌入任務(wù)調(diào)度模型，對Auto Store系統(tǒng)的運行狀況進行分析。

2 ?多AGV建模

2.1 ?模型假設(shè)

在Auto Store系統(tǒng)揀選作業(yè)中，本文規(guī)定一個任務(wù)的起始時刻為揀選AGV移動到該任務(wù)所在存儲柱的上方，結(jié)束時刻為揀選AGV移動到下一個任務(wù)所在存儲柱的上方，因此每個任務(wù)包含三個階段，第一階段為倒箱作業(yè)，由揀選AGV在該任務(wù)所在存儲柱的上方將阻礙箱放置到通過倒箱規(guī)則確定的相應(yīng)落箱位上；第二階段為出庫作業(yè)，由揀選AGV將目標箱提取并搬運到工作臺；第三階段為任務(wù)間作業(yè)，揀選AGV從工作臺到下一個任務(wù)所在存儲柱的上方。

（1）只考慮揀貨作業(yè)環(huán)節(jié)；（2）揀選AGV移動速度為勻速，即不考慮重量對AGV速度的影響；（3）每個存儲貨格均同形且為正方形；（4）設(shè)倉庫底層左上方的貨格為原點坐標1，1，1；（5）倉庫堆存狀態(tài)和貨物位置已知；（6）作業(yè)臺根據(jù)就近原則選擇，即不考慮作業(yè)臺的選擇；（7）暫不考慮料箱在工作臺的揀貨時間，即其設(shè)為常量。

參數(shù)設(shè)置：

Z表示Auto Store系統(tǒng)的最大堆存高度；t表示揀選車水平方向移動單位距離所用時間；t表示揀選車垂直方向移動單位距離所用時間；o=X，Y表示第k輛AGV，o所在的初始位置；e=X，Y，Z表示Auto Store系統(tǒng)的作業(yè)臺所在位置；g=X，Y，Z表示目標箱g即任務(wù)i所在的位置，I=1，2，…，i，…，a；a表示AGV任務(wù)列表內(nèi)的商品個數(shù)；P表示第k輛AGV完成所有任務(wù)并返回初始位置的時間，K=1，2，…，k，…，n；P表示所有AGV完成所有任務(wù)并返回初始位置的時間的最大值；T表示第k輛AGV完成任務(wù)i所需的時間；T表示第k輛AGV從任務(wù)i到任務(wù)j走最短折線路徑所需時間；T表示第k輛AGV從初始位置到任務(wù)i走最短折線路徑所需時間；T表示第k輛AGV從任務(wù)j到初始位置走最短折線路徑所需時間；T表示第k輛AGV任務(wù)i中目標箱g上存在b個阻礙箱時的倒箱作業(yè)時間；T表示第k輛AGV從任務(wù)i到作業(yè)臺e走最短折線路徑所需時間；T表示第k輛AGV從作業(yè)臺e到達任務(wù)j走最短折線路徑所需時間；u表示第k輛AGV執(zhí)行任務(wù)i的次序，用于消除子回路。

決策變量：

2.2 ?目標函數(shù)與約束條件

式（1）為任務(wù)調(diào)度模型的目標函數(shù)，表示最小化n輛AGV的最長運行時間；式（2）表示選擇運行時間最長的AGV的運行時間；式（3）表示第k輛AGV的總運行時間，分別包含完成任務(wù)的時間，任務(wù)間轉(zhuǎn)移的時間，以及從初始位置到達第一個任務(wù)的時間和從最后一個任務(wù)完成到初始位置的時間四部分；式（4）表示第k輛AGV的任務(wù)i與任務(wù)j之間的運行時間；式（5）表示第k輛AGV從初始位置到達任務(wù)j的運行時間；式（6）表示第k輛AGV從任務(wù)i回到初始位置的運行時間；式（7）表示第k輛AGV對任務(wù)i的完成時間，包含倒箱作業(yè)時間，從目標箱到工作臺時間，以及從工作臺到下一個任務(wù)的時間三部分；式（8）表示第k輛AGV從任務(wù)i到作業(yè)臺的運行時間；式（9）表示第k輛AGV從作業(yè)臺到任務(wù)j的運行時間；式（10）、式（11）表示第k輛AGV的起止點約束；式（12）、式（13）、式（14）表示每個任務(wù)都被執(zhí)行且只執(zhí)行一次；式（15）表示第k輛AGV的線路流量平衡；式（16）表示第k輛AGV的消除子回路約束；式（17）、式（18）均表示決策變量約束。

2.3 ?倒箱策略

在上式中，T由倒箱策略求出。在本文中，倒箱策略主要有三點：

一是落箱位不能在訂單內(nèi)其他目標箱。

二是落箱位滿足堆放約束，阻礙箱的落箱位必須為空，且當落箱位置不在第一層時，其下方相鄰箱位不為空。

三是倒箱距離盡量短。倒箱距離為AGV水平行駛單位距離時間和垂直提升單位距離時間之和。

因此，倒箱位搜尋為一個簡單的搜索，首先根據(jù)規(guī)則一、二確定可以選擇的落箱位，其次選擇行駛距離最短的位置。落箱位確定，既可得到單個阻礙箱倒箱時間。當目標箱上的阻礙箱不止一個時，將所有阻礙箱加起來即可。

3 ?改進遺傳算法

本文提出基于多層編碼改進的遺傳調(diào)度優(yōu)化算法，在隨機生成初始解的基礎(chǔ)上加入初始解差異評價因子，提高初始解在解空間分布的均勻性，提高算法收斂速度，加入進化逆轉(zhuǎn)操作以改善其局部搜索能力。

3.1 ?個體編碼生成設(shè)計

本文采用的染色體編碼方式為整數(shù)編碼，每個染色體代表每個AGV的任務(wù)執(zhí)行順序，當任務(wù)總數(shù)為n時，染色體長度為2*n。其中，染色體前半部分表示任務(wù)順序，隨機排列n個任務(wù)的順序；后半部分表示AGV序號，因一個AGV只完成一個任務(wù)屬于極劣解，所以每個AGV對應(yīng)的任務(wù)個數(shù)至少為2個。當n=10時，如圖2所示。

圖2表示的解為AGV1的任務(wù)執(zhí)行順序17→16→12→15，AGV2的任務(wù)執(zhí)行順序4→9→13→19→2，AGV3的任務(wù)執(zhí)行順序7→5→3→1→20，AGV4的任務(wù)執(zhí)行順序10→8→18→11→14→6；1～10位為任務(wù)順序，11～20位為AGV序號，且與前10位一一對應(yīng)。

3.2 ?遺傳操作設(shè)計

任務(wù)調(diào)度模型的目標函數(shù)是使任務(wù)全部完成的總時間最小，屬于最小化問題。本文采取的是多層編碼，所以交叉操作和變異操作均需將染色體分層之后再操作。

交叉操作采用整數(shù)交叉法，本文僅第一層編碼為任務(wù)順序編碼，因此，只對第一層進行交叉操作，將染色體前半段的隨機生成的兩個位置進行交叉操作。如圖3所示，交叉位置為7，只對染色體1和染色體2的前半部分即任務(wù)部分進行交叉；交叉后的結(jié)果可以看出，存在某些任務(wù)缺失，如染色體1中缺少的任務(wù)7和10，也存在某些任務(wù)多余，染色體1中多余的任務(wù)6和9，因此，需要將多余的任務(wù)改為缺失的任務(wù)。

變異操作采取隨機選擇兩個點對換其位置的策略。本文采取多層編碼的編碼設(shè)計，因此需要分層進行變異操作，第一層，隨機生成1，10范圍內(nèi)的隨機整數(shù)R和R，將其所對應(yīng)位置的任務(wù)號對換，如R=4，R=8；第二層的范圍則是11，20，操作與第一層相同，如圖4所示。

3.3 ?進化逆轉(zhuǎn)操作設(shè)計

為改善遺傳算法的局部搜索能力，本文在選擇、交叉、變異之后，加入連續(xù)多次的進化逆轉(zhuǎn)操作，“逆轉(zhuǎn)”是指將種群中的每一個個體的每一層編碼都進行逆轉(zhuǎn)操作，“進化”是指只有逆轉(zhuǎn)之后所得新個體的適應(yīng)度值提高的會被保留，反之保持原先編碼，即逆轉(zhuǎn)無效。