考慮訂單拆分策略的AGV揀選效率優化方法

摘 要：為提高智能倉庫系統中AGV的揀選效率，針對AGV訂單揀選優化問題分為AGV-貨架任務分配、多AGV無沖突路徑規劃兩個子問題進行研究，根據訂單特點引入訂單拆分策略，并以最小化AGV完成所有訂單的總時間為目標構建數學模型。首先，設計了確定貨架優先級的AGV-貨架任務分配算法（AGV-shelf task allocation algorithm，ASTA）求解匹配問題。然后，提出一種帶有貪婪參數并嵌入沖突消解策略的改進Q-Learning算法，得到拆分策略下最優無沖突揀選路徑方案。最后，通過在40 m×40 m倉庫布局中的訂單集數值實驗對比分析，所提算法與現有的兩種算法對比結果顯示，AGV完成所有訂單的總時間分別平均減少11.63%和26.74%，驗證了拆分策略的有效性，并且通過AGV使用數量、完成訂單時間和路徑沖突等待時間占比三個指標的對比驗證了拆分策略和所提算法能有效緩解擁堵情況，減少行駛路徑長度，提高揀選效率。此外，針對AGV數量靈敏度分析，在不同數量的AGV對行駛時間和路徑沖突等待時間的影響方面，發現19臺AGV數量是最佳配置，驗證了模型的可行性和算法的有效性。

關鍵詞：智能倉庫；混合存儲；訂單拆分；AGV-貨架任務分配；無沖突路徑規劃；改進Q-Learning算法

中圖分類號：TP242 文獻標志碼：A 文章編號：1001-3695（2024）11-008-3258-07

doi：10.19734/j.issn.1001-3695.2024.04.0081

Optimization method of AGV picking efficiency considering order splitting strategy

Zhang Yanju^{a， b， c?}， Yang Qinggang^a， Wu Jun^a， Wu Yixuan^a， Li Yuyang^a

（a.School of Business Administration， b.Institute of Management Science amp; Engineering， c.Modern Enterprise System Innovation Research Center， Liaoning Technical University， Huludao Liaoning 125105， China）

Abstract：To improve the picking efficiency of AGVs in intelligent warehouse systems， aiming at two sub-problems of AGV-shelf task allocation and multi-AGV conflict-free path planning， this paper introduced order splitting strategy according to the order characteristics and built a mathematical model with the objective of minimizing the total time for AGVs to complete all orders. Firstly， it designed the ASTA to solve the matching problem by determining the shelf priority. Secondly， it proposed an improved Q-Learning algorithm with a greedy parameter and embedded conflict elimination strategy to obtain the optimal conflict-free picking path scheme under the splitting strategy. Finally， through experimental comparative analysis of order set values in the 40 m×40 m warehouse layout， the proposed algorithm was compared with the two existing algorithms. The results indicate that the proposed algorithm reduced the total time for AGVs to complete the all orders by an average of 11.63% and 26.74% respectively， which verified the effectiveness of the splitting strategy. And it was verified that the splitting strategy and the proposed algorithm can effectively alleviate the congestion， reduce the length of traveling paths and improve the picking efficiency， through the comparison of three indexes of the number of AGVs used， the time of complete orders and the percentage of waiting time for path conflict. Furthermore， for the sensitivity on the number of AGVs， it tested the influence of different numbers of AGVs on the travel time and path conflict waiting time. It was found that the number of 19 AGVs is the optimal configuration. These results verify the feasibility of the model and the effectiveness of the proposed algorithm.

Key words：intelligent warehouse; hybrid storage; order splitting; AGV-shelf matching; conflict-free path planning; improved Q-Learning algorithm

0 引言

隨著電商行業的快速發展以及互聯網移動支付的普及，網絡購物已成為主要的消費方式，《中國電子商務報告》發布：2023年全國電子商務交易額達45.5萬億元，同比增長8.5%，導致電商企業每日要處理海量的訂單，而且消費者的需求更趨向于個性化和多樣化，訂單具有多品種、小批量、多批次的特點^［1］。面對揀選效率和物流成本的雙重挑戰，亞馬遜首次將Kiva系統引入倉庫中，使用自動導引車（automated guided vehicle， AGV）代替傳統的人工揀選方式，這種“貨到人”智能揀選系統與人工揀選優化問題^［2～5］相比可大大縮減工作量和人工成本，提高揀選效率。

當前，國內外學者主要針對AGV調度和路徑規劃問題展開研究。在AGV調度方面，李林蔓等人^［6］在自動化集裝箱碼頭的場景下，提出一種考慮有電量約束^［7，8］的AGV調度優化方法。在電量約束的基礎上，陳仁勝等人^［9］構建了可變速AGV與綠色集成調度模型，Li等人^［10］和Yuan等人^［11］針對柔性生產車間提出AGV動態調度模型，可以為新任務和特殊情況重新分配AGV。

在AGV路徑規劃方面，A^*、D^*算法難以適應復雜的動態環境，標準啟發式算法存在收斂速度慢、易陷入局部最優的缺陷。因此，張新艷等人^［12］和李昆鵬等人^［13］提出改進的A^*算法用于AGV無碰撞路徑規劃，Lin等人^［14］和毛文平等人^［15］分別使用改進的粒子群算法和改進的蟻群算法探索AGV最佳路徑。一些學者將強化學習應用到AGV路徑規劃中，Zhang等人^［16］將改進的懲罰機制引入到Q-Learning算法的評價函數中，實現了AGV運行距離與路載的均衡。Kawabe等人^［17］使用A^*算法搜尋最短路線，并使用Q-Learning算法避免碰撞。

綜合對智能倉庫AGV訂單揀選優化問題的研究成果進行回顧發現，現有文獻多針對路徑規劃、碰撞避免和AGV調度等某一環節進行優化研究，對于多環節的訂單揀選問題研究較少。面對新興的智能倉儲系統、貨架的靈活性以及多AGV的協調性等特征對訂單揀選提出了更高的要求。因此，如何在AGV與貨架的最佳匹配上實現AGV，完成所有訂單總時間最短且碰撞避免，是重點研究內容。

本文針對訂單小批量、多批次的特點，引入混合存儲策略和訂單拆分策略，在此基礎上設計了一種確定貨架優先級的AGV-貨架任務分配算法;為了解決多AGV搬運路徑沖突問題，設計了一種帶有貪婪參數并嵌入沖突消解策略的改進的Q-Learning算法。

1 問題描述與模型建立

1.1 問題描述

“貨到人”智能倉庫系統訂單揀選流程如圖1所示。首先，履行倉庫對在線零售平臺的訂單需求信息生成訂單列表進行拆分形成揀選列表。在確定完目標貨架后，按照任務分配方式將倉庫內的k個貨架分配給q臺AGV搬運；其次，AGV接收到指令后，按照規劃的路徑先從初始位置移動至目標貨架處，再將貨架搬運至相應的揀選站；然后，揀選員按照訂單要求重新合并打包各項商品，放置于出庫區等待出庫；最后，AGV將其搬運至原儲位。圖2為基于柵格法的倉庫布局簡圖，黑色網格表示貨架，白色網格表示揀選通道。其包括AGV停靠區、存儲區、人工作業區三大區域，AGV執行搬運任務為M1、M2、M3三個階段。M1：從空閑狀態的位置（揀選通道或停靠區）行駛到目標貨架位置的過程；M2：從目標貨架位置搬運到揀選站完成揀選的過程；M3：從揀選站位置返回到原儲位的過程。

為了進一步理解“貨到人”智能倉庫系統訂單揀選流程，本研究給出相關要素的形式化定義。

定義1 倉庫。離散成網格化的倉庫M，其中M［i， j］表示第i行和第j列的網格。網格的值可以是0或1，表示此位置是否有貨架。

定義2 AGV。 AGV定義為q={M_q［i， j］，w，C_q}，M_q［i， j］表示AGV在倉庫M中的當前位置，w表示AGV最大的承載重量。AGV的狀態C_q∈{0，1}，若C_q=1表示AGV正在執行貨架的搬運工作，處于忙碌狀態，C_q=0則表示AGV當前沒有搬運任務，處于空閑狀態。

定義3 貨架。一個貨架定義為k={M_k［i， j］，C_k}， M_k［i， j］表示貨架的位置。貨架的狀態C_k∈{0，1}，若C_k=1表示貨架正被AGV搬運，處于忙碌狀態，C_k=0表示貨架未被AGV搬運，處于空閑狀態。

定義4 揀選站。一個揀選站定義為v={M_v［i， j］，I_v，C_v}，M_v［i， j］表示揀選站的位置，揀選站的編號用I_v表示，揀選站的狀態C_v∈{0，1}，若C_v=1表示揀選站正在執行貨物揀選任務，處于忙碌狀態，C_v=0表示揀選站無揀選任務，處于空閑狀態。

定義5 路徑。一條路徑定義為R={P_start，P_end，t_start，R^*}，其中P_start和P_end分別為路徑的起點和終點， t_start表示路徑出發時間。R^*={p₁，p₂，…，p_n}為路徑對應的子段序列，由一系列子段p={t^q_start，t^q_end，M_q［i， j］_end，M_q［i， j］_dist}組成，子段中各項分別表示子段開始時間和結束時間、子段起點坐標、子段終點坐標、起點到終點間的坐標差。

1.2 混合存儲策略

混合儲存策略主要適用于目前主流的B2C在線零售商的履行倉庫。基于消費者的個性化需求以及小批量、多批次等訂單特性，訂單通常包括少量訂單行，亞馬遜設施的平均訂單只有1.6個訂單行^［18］，履行倉庫需要快速處理訂單，減少訂單揀選期間的非生產性行走時間，為混合存儲策略提供了有利條件。

如圖3（a）所示在倉庫內按照貨物周轉率從大到小排序，1區定義為周轉率占比60%～80%的貨物，距離揀選站較近，貨架使用率較高，2區定義為周轉率占比20%～30%的貨物，距離揀選站較遠，貨架使用率一般，其余定義為3區貨物。對于每個貨架來說，貨物存儲方式如圖3（b）中貨架3的混合存儲策略所示，A、B、C、D、E、F、G七種商品將關聯性強的商品分配在同一貨架，這種混合存儲策略在智能倉庫中可將總檢索時間減少多達40%^［19］，而貨架1和2為傳統存儲策略，每層只能存放一種商品，可以存儲單個商品的多個計數，貨物之間的關聯性較弱，需要更多的時間完成訂單揀選。

如果混合存儲策略（貨架3）中七種商品的存放數量能同時滿足多個訂單需求，那么將充分發揮混合存儲策略能減少AGV搬運時間和路徑發生沖突可能性的優化效果。為了盡可能達到這種優化效果，引入訂單拆分策略。

1.3 訂單拆分策略

訂單拆分策略目前已應用于倉庫訂單揀選環節^［20］，并且在“貨到人”系統中引入訂單拆分策略可以減少AGV搬運貨架次數和行駛距離，并且與不拆分相比可以實現每小時多47%的訂單揀選數量^［21］。

圖4為訂單拆分策略過程圖，分為三個階段：a）原始訂單商品信息獲取階段；b）原始訂單含有相同商品歸類階段；c）訂單拆分及新訂單合并階段。假設在階段a）有6個訂單且訂單信息已知，共需要A、B、C、D、E、F、G七種商品，在階段b）分別對這七種商品進行歸類，對于A商品來說，訂單1、3、4、5都需要1個A商品，共需要4個A商品，同理可以歸類出B、C、D、E、F、G商品總需求數量；在階段c）對階段b）歸類的訂單和商品進行合并，并重新命名為新的訂單名稱，比如在6個訂單中，訂單1、3、4、5都需要A商品，把這4個訂單重新命名為訂單S1，同理可以得出其余的訂單S2～S7。

為了說明在混合存儲策略和訂單拆分策略的加持下能減少AGV完成訂單的總時間和降低AGV之間發生碰撞的可能性，以示例1進行說明。

示例1：假設履行倉庫在某個時間段接收到同時需要A、B、C、D、E、F、G七種商品的訂單，圖5為兩種策略下的AGV搬運路徑對比示意圖，在圖5（a）中由于未拆分及傳統存儲策略，為了減少AGV搬運時間，需要同時安排兩輛AGV 把貨架1和2搬運到揀選站（M2階段），其搬運路徑可能與M3階段的AGV行駛路徑發生沖突，增加碰撞的可能性，而在圖5（b）中貨架3就能滿足訂單需求，AGV只需把貨架3搬至揀選站，這與M3階段的AGV行駛路徑未發生沖突，降低了碰撞的可能性，減少AGV完成訂單的總時間。

2 考慮訂單拆分的AGV揀選優化模型

2.1 問題假設和變量

為了簡化問題，對“貨到人”智能倉庫系統中的AGV訂單揀選問題作出如下假設：a）在揀選前訂單和商品信息已知；b）履行倉庫能滿足所有訂單的需求，不存在缺貨的情況；c）不考慮商品體積對訂單拆分和合并的影響；d）移動貨架重量在AGV承受范圍內；e）AGV每次最多只能搬運一個貨架；f）所有AGV規格相同且每秒以單位速度行駛1個單元格。

為了建立AGV揀選優化模型，定義以下變量符號：

集合：Q為AGV集合，Q={1，2，…，q}；O為訂單集合，O={1，2，…，o}；K為貨架集合，K={1，2，…，k}；V為揀選站集合，V={1，2，…，v}。

參數：S為拆分后的新訂單；l為拆分后待揀選的訂單列表；t^q_k為AGV q從空載狀態的位置（過道或停靠區）行駛到目標貨架位置的所用時間；t^q_kv為AGV q從目標貨架位置行駛到揀選站完成揀選的所用時間；t^q_vk為AGV q從揀選站行駛到目標貨架位置所用時間。

2.2 模型建立

1）決策變量

x^q_kv：0-1變量，等于1表示AGV q將貨架k搬運至揀選站v處分揀，否則為0。

y^q_k：0-1變量，等于1表示AGV q被安排前往貨架k的位置，否則為0。

z^q_vk：0-1變量，等于1表示AGV q將貨架k從揀選站v搬運至原儲位，否則為0。

2）目標函數

min∑q∈Q（t^q_k+t^q_kv+t^q_vk）（1）

3） 約束條件

t^q_k－∑q∈Qy^q_k=0

?k∈K（2）

t^q_kv－∑v∈Vx^q_kv=0

?k∈K，v∈V（3）

∑v∈Vx^q_kv=1

?q∈Q，k∈K（4）

∑k∈Kx^q_kv－∑k∈Kz^q_vk=0

?q∈Q，v∈V，k∈K（5）

x^q_kv－∑k∈Kz^q_vk=0

?q∈Q，v∈V（6）

x^q_kv，y^q_k，z^q_vk∈{0，1}

?q∈Q，k∈K，v∈V（7）

目標函數式（1）表示最小化所有AGV的總完工時間，包括AGV從空載狀態的位置（過道或停靠區）行駛到目標貨架位置的所用時間、AGV從目標貨架位置行駛到揀選站完成揀選的所用時間和AGV從揀選站行駛到目標貨架位置所用時間總和；約束條件式（2）表示AGV q未從初始位置移至貨架k處，則AGV q的行駛時間為0，即如果處于M1階段的AGV q未執行搬運貨架k的任務，那么AGV q從空載狀態行駛到貨架k處所需時間為0；約束條件式（3）表示AGV q未將貨架k搬運至揀選站v，則AGV q的搬運時間為0，即如果處于M2階段的AGV q未執行將貨架k搬運至揀選站v的任務，那么AGV q從貨架k位置行駛到揀選站v完成揀選的所用時間為0；約束條件式（4）表示AGV q只能將貨架k搬至一個揀選站進行揀選；約束條件式（5）表示AGV q搬運貨架k的連續性，即AGV q將貨架k搬至揀選站v后，需要把貨架k搬至原儲位；約束條件式（6）表示AGV q未將貨架k搬至揀選站，則無須將其搬至原儲位；約束條件式（7）表示決策變量x^q_kv、y^q_k和z^q_vk在不同情況下的取值。

3 AGV訂單揀選求解算法

在“貨到人”智能倉庫系統中可將AGV訂單揀選問題分為AGV-貨架任務分配、多AGV無沖突路徑規劃兩個子問題來求解。

3.1 AGV-貨架任務分配算法

由于商品采用混合存儲策略，一個商品可能存放在多個貨架上，而且訂單拆分使新訂單中只含有一種商品的多個計數，為了最大化減少搬運時間，每個揀選列表l={s₁，s₂，…，s_n}中會含有多個拆分后的訂單，那么就有必要確定貨架的優先級，貨架中存放的商品滿足揀選列表中的商品種類和數量越多，貨架的優先級就越高，成為其目標貨架的可能性就越大。為了便于比較貨架的優先級，下面引入0-1決策變量定義訂單填充性，令Y_sk標識拆分后的每個訂單S是否可以從貨架中填充，則

Y_sk=1

如果貨架k存放有拆分后訂單S中的商品0

否則 （8）

C_sk=∑s∑kY_sk

?k∈K，s∈l（9）

Δdist₁=|M^free_q［i］－M_k［i］|+|M^free_q［j］－M_k［j］|（10）

AGV-貨架任務分配算法步驟如下：

a）獲得當前揀選列表l的信息以及無搬運任務空閑狀態的AGV進入任務匹配池；

b）根據式（8）（9）計算每個貨架k的C_sk值，最大值MaxC_sk所對應的貨架k為目標貨架；

c）根據式（10）計算空閑狀態AGV與目標貨架k的曼哈頓距離，最小值MinΔdist₁為最佳AGV-貨架任務匹配對；

d）算法結束，從任務匹配池中移除當前揀選列表l和AGV-貨架匹配對。

3.2 基于沖突消解策略的路徑規劃算法

3.2.1 沖突消解策略

AGV在行駛過程中主要會產生十字路口沖突、相向沖突和追尾沖突三種類型沖突^［22］，如圖6所示。由于假設AGV每秒以單位速度行駛1個單元格，所以不考慮趕超類追尾沖突類型。

a）相向沖突消解策略：兩輛AGV行駛在同一條路徑上，方向相向行駛，將會在圖6（a）中圓點處產生碰撞，從而造成死鎖。其策略為根據路徑規劃算法形成的二維時間預約表，路徑長度較短的AGV獲得優先通過權，則另一輛AGV重新進行路徑規劃，獲得次優路徑，如果兩輛AGV路徑長度相同，則隨機選擇優先通過權。

b）十字路口沖突消解策略：當兩輛AGV在同一時刻到達同一節點時，將會在圖6（b）中圓點處產生碰撞，從而產生死鎖，其策略為路徑長度較短的AGV獲得優先通過權，則另一輛AGV在路徑上進行等待，如果兩輛AGV路徑長度相同，則隨機選擇通過。

c）追尾沖突消解策略：兩輛AGV在同一路徑上，AGV2靜止在某個位置，AGV1向AGV2方向行駛，如圖6（c）所示在同一時刻，AGV1將會追尾AGV2產生碰撞，其策略為采取先來后到的原則進行避讓，后占用柵格的AGV必須先等到占用柵格的AGV離開后，才能占有該柵格。

3.2.2 改進的Q-Learning路徑規劃算法

面向多品種、高頻次的AGV智能揀選系統，要求AGV系統能夠智能地規劃路徑、避免碰撞、快速響應任務變更，并降低錯誤率。Q-Learning算法^［23］與目前主流的AGV路徑規劃算法，如A^*、D^*算法^［24］相比算法原理簡單、適應性強，并且在未知的環境下擁有強大的自主學習能力，在智能控制、AGV等領域受到廣泛的運用，但可能會陷入局部最優。當多個AGV在同一時間使用相同的路徑時會導致路徑沖突，影響揀選效率和AGV的安全性，所以為了提高揀選效率和保證AGV的安全，提高算法的尋優能力，采用嵌入有沖突消解策略的改進的Q-Learning算法進行AGV無沖突路徑規劃。其改進措施為在AGV動作選擇策略上增設貪婪參數α（0≤α≤100%），表示有α概率的AGV會按照AGV-貨架任務分配的路徑選擇行為，1－α的概率使用隨機行為，幫助AGV在已知的最優路徑和嘗試新路徑之間取得平衡，以增加找到更好的無沖突路徑的可能性。

在Q-Learning算法中，一般只有在AGV到達目標時才給予相應的瞬時獎勵Re₁，為了讓AGV在最短時間內到達目標位置，增設向目標點靠近動作的獎勵Re₂，其計算公式為

Re₂=10 Δdist₂lt;0

－10 Δdist₂gt;00 otherwise （11）

其中：Δdist₂為AGV q當前狀態柵格位置M_q［i， j］和前一狀態柵格位置M_q［i， j］′與終點柵格位置M_end［i， j］的曼哈頓距離之差；終點位置M_end［i， j］可以是揀選站M_v［i， j］，也可以是M_k［i， j］，其公式為

Δdist₂=（|M_q［i］－M_end［j］|+|M_q［j］－M_end［j］|）－

（|M_q［i］′－M_end［i］|+|M_q［j］′－M_end［j］|）（12）

除了給予瞬時獎勵Re₁和向目標點靠近動作的獎勵Re₂外，AGV每走一步都將得到-1的獎勵值，其目的在于讓AGV盡快走向終點。綜上，本研究的獎懲函數計算公式為

Re=Re₁+Re₂-1（13）

算法步驟如下：

a）初始化獎勵矩陣Re和Q^*值表；

b）判斷是否達到最大學習次數，沒有達到則繼續，否則執行步驟h）；

c）初始化相關參數；

d）判斷是否找到最終目標，如果沒有則繼續，否則執行步驟h）；

e）動作選擇狀態；

f）根據式（11）～（13）給出瞬時獎勵Re；

g）Q^*值更新，相關參數衰減；

h）判斷Q^*值表是否收斂，未收斂返回步驟c），否則繼續；

i）根據式（8）～（10）分配的AGV-貨架方案，輸出規劃的路線并保存路線的起點、終點和開始時間；

j）根據沖突消解策略調整路徑；

k）算法結束，輸出最優無沖突路徑R。

4 實驗與分析

4.1 數據描述與參數設計

在智能倉庫中構建40 m×40 m的雙面貨架布局（圖7），共有728個貨架，每個貨架6層，可以存儲60個商品，每個商品不固定存儲在某個貨架上，采用混合存儲策略^［19］，AGV每秒勻速行駛一個單元格（m）。數據以某在線零售平臺在三個月內訂單量為例，由于該零售平臺主要銷售日常生活用品類商品，所以具有小批量、多批次的特點，經過對三個月訂單量的統計和計算，每個訂單大約為2個商品（一單多品）。為了能測試出本文所提出的訂單揀選優化方法的有效性和適用性，使用表1的訂單集數量進行實驗。實驗在搭載Intel Core AMD（3.2 GHz）和16 GB RAM并運行Windows 11系統的筆記本電腦上，通過MATLAB 2022a對算法統一求解。

由于AGV每次只能搬運一個貨架，在AGV承載重量w范圍內，目標貨架存放的商品與揀選列表l中商品的匹配度越高，則需搬運任務的AGV數量就越少，所以每個揀選列表l中的訂單數量直接影響著揀選效率。

為了確定每個揀選列表中的訂單數量，分別設置了揀選列表訂單數量|l|為：10、15、20、25、30時，在5個訂單集中訂單填充能力平均值C_sk和AGV完成訂單總時間的情況。圖8為訂單填充能力平均值C_sk與揀選列表訂單數量|l|變化圖。當|l|為10、15和20時，C_sk值相對較低，目標貨架存放的商品與揀選列表l中商品的匹配度較低；當|l|為30時，C_sk值基本達到最大值60，說明部分訂單中商品數量超出貨架存放容量和AGV承載重量，而圖9中當|l|為25時，AGV在5個訂單集中完成訂單總時間最短。所以從揀選時間和倉庫安全兩方面綜合考慮將揀選列表中的訂單數量統一設為25。

4.2 實驗結果

4.2.1 拆分策略和算法有效性分析

首先驗證ASTA算法的有效性，在智能倉儲系統中基于表1的訂單集進行了三組不同實驗，并在路徑規劃算法固定為改進Q-Learning算法的前提下，對比了不同的任務分配算法，包括ASTA、Auction^［25］和Random算法^［26］，從總路程、完成時間、任務效用（總路程/完成時間）和AGV使用數量四個方面來衡量ASTA算法的有效性。結合表2的實驗結果來看，隨著訂單數量的增加，ASTA算法在總路程、完成時間和任務效用方面表現最好，用ASTA算法完成搬運任務的時間與其他算法相比平均減少11.63%和26.74%。

圖10所示為ASTA、Auction和Random算法完成所有訂單所需AGV數量，在5個訂單集中，ASTA算法與兩種分配算法相比，所需AGV數量最少，這是因為ASTA算法考慮了訂單拆分和混合存儲策略，在這兩種策略的加持下，可以減少AGV使用數量，緩解AGV搬運路徑沖突的情況，節約完成訂單的時間，這也說明了訂單拆分的必要性。

為了驗證路徑規劃算法的有效性，在智能倉儲系統中基于表1的訂單集進行了4組不同實驗，并在分配算法固定為ASTA算法的前提下，對比了不同的路徑規劃算法，包括改進Q-Learning、Q-Learning、IGA^［27］和改進的A^*算法^［12］，從AGV使用數量、總時間和路徑沖突等待時間占比三個方面來衡量改進Q-Learning算法的有效性。圖11和12分別顯示了不同的路徑規劃算法下，AGV完成訂單所需的數量和總時間。訂單集o₁和o₂中由于訂單基數較少，改進Q-Learning算法與其他算法相比相差不大，但隨著訂單基數的增加，逐漸表現出優勢，這是因為改進Q-Learning算法在AGV動作選擇策略上增設了貪婪參數，在已知的最優路徑和嘗試新路徑之間取得平衡，提高了AGV走向終點的能力，而路徑沖突等待時間占比（圖13）更能說明改進Q-Learning算法嵌入沖突消解策略后，有效緩解了路徑沖突的情況，實現了安全和高效的目標。通過對上述ASTA和改進Q-Learning算法多指標的對比，驗證了ASTA+改進Q-Learning算法組合在訂單拆分策略下的有效性。

4.2.2 AGV數量靈敏度分析

AGV數量的合理配置是確保整個智能揀選系統性能的關鍵。當AGV數量不足時，即使訂單拆分和路徑規劃再優化，也難以滿足系統的揀選效率要求，而當AGV數量過多時，雖然可以減少AGV行駛時間，但也會增加路徑沖突的可能性。鑒于本文在40 m×40 m的倉庫布局中展開實驗，所以以訂單集o₄的訂單規模為例，在有限的AGV資源情況下，選取AGV行駛時間和路徑沖突等待時間兩個指標，利用所提算法探究最佳的AGV數量，使得行駛時間和路徑沖突時間之和最小。圖14 中，在其他變量因素不變的情況下，行駛時間和路徑沖突等待時間呈現悖反關系，行駛時間隨著AGV數量增加逐漸降低，相反，路徑沖突等待時間隨著AGV數量增加逐漸增大。當AGV數量為19臺時，行駛時間和和路徑沖突等待時間均優于其他AGV數量條件，此時無論AGV數量增加或減少，行駛時間和路徑沖突等待時間之和都會增大，因此在16～24臺內，AGV的最佳數量為19臺。通過對AGV數量合理的配置，可以實現高效和安全的揀選任務。ASTA、Auction及Random算法在不同訂單集下的性能對比數據如表2所示。

5 結束語

本文研究了“貨到人”系統中AGV訂單揀選問題，考慮訂單需求多樣性、商品在倉庫中多貨架存儲、訂單與貨架匹配關系未知，及AGV路徑可能產生沖突等實際因素，在混合存儲基礎上引入訂單拆分策略，基于訂單拆分策略構建以總訂單完工時間最小為目標的數學模型，并根據問題特點設計AGV-貨架任務匹配算法、路徑沖突消解策略與改進的Q-Learning算法。數值實驗結果表明，所提算法能在40 m×40 m的倉庫布局中處理800個訂單任務。此外，通過對AGV數量的靈敏度分析，發現19臺AGV數量配置是最為適宜的。

此外，本文為“貨到人”智能倉庫系統的運營提供如下管理啟示：

a）運用本文模型和ASTA算法求解的AGV-貨架任務分配問題為AGV揀選環節提供一個良好的調度基礎。

b）針對“一單多品”的智能揀選系統，如食品和日用品倉庫、促銷活動與捆綁銷售策略倉庫等，商品之間的關聯度較高，管理者可充分利用混合存儲和訂單拆分策略以減少貨架移動次數，提高揀選效率，緩解AGV之間的路徑沖突問題。

c）針對季節性、熱銷品類等出庫率較高的商品，管理者可適當調整移動貨架位置，減少AGV搬運時間。

在本文的研究中，訂單拆分時進行了理想化處理，并沒有考慮商品體積、類型對拆分和合并的影響，后續將考慮按照商品性質進行拆分，其次是基于離線訂單的揀選優化問題，并沒有考慮在線訂單、緊急訂單插入、訂單取消等問題，未來的研究中將盡可能還原真實揀選場景，實現在線的優化。

參考文獻：

［1］Winkelhaus S， Grosse E H. Logistics 4.0： a systematic review towards a new logistics system ［J］. International Journal of Production Research， 2020， 58（1）： 18-43.

［2］Onal S， Zhu Wen， Das S. Order picking heuristics for online order fulfillment warehouses with explosive storage ［J］. International Journal of Production Economics， 2023， 256： 108747-108754.

［3］李建斌， 蒙銘友， 戴賓. 電子商務環境下的存儲策略優化研究： 固定存儲還是分類隨機存儲 ［J］. 中國管理科學， 2021， 29（8）： 67-80. （Li Jianbin， Meng Mingyou， Dai Bin. Optimization of storage strategy in e-commerce environment： fixed storage or classified random storage ［J］. Chinese Journal of Management Science， 2021， 29（8）： 67-80.）

［4］謝勇， 任建偉， 王紅衛. 考慮通道阻塞的雙揀貨員訂單揀選優化研究 ［J］. 系統工程理論與實踐， 2023， 43（4）： 1203-1219. （Xie Yong， Ren Jianwei， Wang Hongwei. Optimization study of order picking by dual pickers considering channel blocking ［J］. Systems Engineering Theory and Practice， 2023， 43（4）： 1203-1219.）

［5］Masae M， Glock C H， Vichitkunakorn P. A method for efficiently routing order pickers in the leaf warehouse ［J］. International Journal of Production Economics， 2021， 234： 108069-108092.

［6］李林蔓， 李雨青， 王孟雅， 等. 基于啟發式規則的自動化碼頭換電式AGV調度優化方法 ［J］. 運籌與管理， 2023， 32（10）： 9-15. （Li Linman， Li Yuqing， Wang Mengya， et al. A heuristic rule-based scheduling optimization method for power-switching AGVs in automated terminals ［J］. Operations Research and Management Science， 2023， 32（10）： 9-15.）

［7］Boccia M， Masone A， Sterle C， et al. The parallel AGV scheduling problem with battery constraints： a new formulation and a matheuristic approach ［J］. European Journal of Operational Research， 2023， 307（2）： 590-603.

［8］Li Linman， Li Yuqing， Liu Ran， et al. A two-stage stochastic programming for AGV scheduling with random tasks and battery swapping in automated container terminals ［J］. Transportation Research Part E： Logistics and Transportation Review， 2023， 174： 103110-103138.

［9］陳仁勝， 吳斌， 閆飛一. 基于混合學習策略的可變速AGV與機器綠色集成調度 ［J/OL］. 控制與決策.（2024-03-30）. https：//doi. org/10. 13195/j. kzyjc. 2023. 1708. （Chen Rensheng， Wu Bin， Yan Feiyi. Integrated scheduling of variable-speed AGV with machine green based on hybrid learning strategy ［J/OL］. Control and Decision.（2024-03-30）. https：//doi. org/10. 13195/j. kzyjc. 2023. 1708.）

［10］Li Zhongkai， Sang Hongyan， Pan Quanke， et al. Dynamic AGV scheduling model with special cases in matrix production workshop ［J］. IEEE Trans on Industrial Informatics， 2022， 19： 7762-7770.

［11］Yuan Minghai， Zheng Liang， Huang Hanyu， et al. Research on flexible job shop scheduling problem with AGV using double DQN ［J/OL］. Journal of Intelligent Manufacturing， 2023. https：//doi.org/10.1007/s10845-023-02252-8.

［12］張新艷， 鄒亞圣. 基于改進A^*算法的自動導引車無碰撞路徑規劃 ［J］. 系統工程理論與實踐， 2021， 41（1）： 240-246. （Zhang Xinyan， Zou Yasheng. Collision-free path planning for automated guided vehicles based on improved A^* algorithm ［J］. System Engineering Theory and Practice， 2021， 41（1）： 240-246.）

［13］李昆鵬， 韓雪芳. 智能倉庫中多AGV在線任務指派與全局路徑規劃問題研究 ［J/OL］. 中國管理科學（2023-06-27）. https：//doi.org/10.16381/j.cnki.issn1003-207x.2023.0429. （Li Kunpeng， Han Xuefang. Research on multi-AGV online task assignment and global path planning problem in intelligent warehouse ［J/OL］. Chinese Journal of Management Science.（2023-06-27）. https：//doi.org/10.16381/j.cnki.issn1003-207x.2023.0429.）

［14］Lin Shiwei， Liu Ang， Wang Jianguo， et al. An improved fault-tole-rant cultural-PSO with probability for multi-AGV path planning ［J］. Expert Systems with Applications， 2024， 237： 121510-121521.

［15］毛文平， 李帥永， 謝現樂. 基于自適應機制改進蟻群算法的移動機器人全局路徑規劃 ［J］. 控制與決策， 2023， 38（9）： 2520-2528. （Mao Wenping， Li Shuaiyong， Xie Xianle. Global path planning for mobile robots based on improved ant colony algorithm with adaptive mechanism ［J］. Control and Decision， 2023， 38（9）： 2520-2528.）

［16］Zhang Xiumei， Li Wensong， Li Hui， et al. Load balancing of multi-AGV road network based on improved Q-Learning algorithm and ma-croscopic fundamental diagram ［J］. Complex amp; Intelligent Systems， 2024， 10： 3025-3039.

［17］Kawabe T， Nishi T， Liu Z. Flexible route planning for multiple mobile robots by combining Q-Learning and graph search algorithm ［J］. Applied Sciences， 2023， 13（3）： 1879-1899.

［18］Boysen N， De Koster R， Weidinger F. Warehousing in the e-commerce ERA： a survey ［J］. European Journal of Operational Research， 2019， 277（2）： 396-411.

［19］Mirzaei M， Zaerpour N， De Koster R. The impact of integrated cluster-based storage allocation on parts-to-picker warehouse performance ［J］. Transportation Research Part E： Logistics and Transportation Review， 2021， 146： 102207-102222.

［20］Haouassi M， Kergosien Y， Mendoza J E， et al. The integrated orderline batching， batch scheduling， and picker routing problem with multiple pickers： the benefits of splitting customer orders ［J］. Flexible Services and Manufacturing Journal， 2022， 34（3）： 614-645.

［21］Xie Lin， Thieme N， Krenzler R， et al. Introducing split orders and optimizing operational policies in robotic mobile fulfillment systems ［J］. European Journal of Operational Research， 2021， 288（1）： 80-97.

［22］牛雅倩， 余芳， 劉靜雯， 等. 基于動態平衡策略的自動化碼頭多AGV路徑優化算法研究 ［J］. 計算機應用研究， 2022， 39（2）： 385-390. （Niu Yaqian， Yu Fang， Liu Jingwen， et al. Research on multi-AGV path optimization algorithm for automated terminal based on dynamic balancing strategy ［J］. Application Research of Computers， 2022， 39（2）： 385-390.）

［23］Tan Tao， Xie Hong， Feng Liang. Q-learning with heterogeneous update strategy ［J］. Information Sciences， 2024， 656： 119902-119918.

［24］Xie Kaili， Qiang Jie， Yang Haitao. Research and optimization of D-start lite algorithm in track planning ［J］. IEEE Access， 2020， 8： 161920-161928.

［25］Clinch K， Wood TA， Manzie C. Auction algorithm sensitivity for multi-robot task allocation ［J］. Automatica， 2023， 158： 111239-111248.

［26］Sun Yifei， Wu Jigang， Liu Tonglai. Joint task allocation and path planning for space robot ［J］. IEEE Access， 2023， 11： 42314-42323.

［27］Liu Qihao， Wang Cuiyun， Li Xinyu， et al. An improved genetic algorithm with modified critical path-based searching for integrated process planning and scheduling problem considering automated guided vehicle transportation task ［J］. Journal of Manufacturing Systems， 2023， 70： 127-136.