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

關(guān)鍵詞：智能倉(cāng)庫(kù)；混合存儲(chǔ)；訂單拆分；AGV-貨架任務(wù)分配；無(wú)沖突路徑規(guī)劃；改進(jìn)Q-Learning算法

中圖分類號(hào)：TP242 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

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

當(dāng)前，國(guó)內(nèi)外學(xué)者主要針對(duì)AGV調(diào)度和路徑規(guī)劃問(wèn)題展開(kāi)研究。在AGV調(diào)度方面，李林蔓等人^［6］在自動(dòng)化集裝箱碼頭的場(chǎng)景下，提出一種考慮有電量約束^{［7，8］}的AGV調(diào)度優(yōu)化方法。在電量約束的基礎(chǔ)上，陳仁勝等人^［9］構(gòu)建了可變速AGV與綠色集成調(diào)度模型，Li等人^［10］和Yuan等人^［11］針對(duì)柔性生產(chǎn)車間提出AGV動(dòng)態(tài)調(diào)度模型，可以為新任務(wù)和特殊情況重新分配AGV。

在AGV路徑規(guī)劃方面，A^*、D^*算法難以適應(yīng)復(fù)雜的動(dòng)態(tài)環(huán)境，標(biāo)準(zhǔn)啟發(fā)式算法存在收斂速度慢、易陷入局部最優(yōu)的缺陷。因此，張新艷等人^［12］和李昆鵬等人^［13］提出改進(jìn)的A^*算法用于AGV無(wú)碰撞路徑規(guī)劃，Lin等人^［14］和毛文平等人^［15］分別使用改進(jìn)的粒子群算法和改進(jìn)的蟻群算法探索AGV最佳路徑。一些學(xué)者將強(qiáng)化學(xué)習(xí)應(yīng)用到AGV路徑規(guī)劃中，Zhang等人^［16］將改進(jìn)的懲罰機(jī)制引入到Q-Learning算法的評(píng)價(jià)函數(shù)中，實(shí)現(xiàn)了AGV運(yùn)行距離與路載的均衡。Kawabe等人^［17］使用A^*算法搜尋最短路線，并使用Q-Learning算法避免碰撞。

綜合對(duì)智能倉(cāng)庫(kù)AGV訂單揀選優(yōu)化問(wèn)題的研究成果進(jìn)行回顧發(fā)現(xiàn)，現(xiàn)有文獻(xiàn)多針對(duì)路徑規(guī)劃、碰撞避免和AGV調(diào)度等某一環(huán)節(jié)進(jìn)行優(yōu)化研究，對(duì)于多環(huán)節(jié)的訂單揀選問(wèn)題研究較少。面對(duì)新興的智能倉(cāng)儲(chǔ)系統(tǒng)、貨架的靈活性以及多AGV的協(xié)調(diào)性等特征對(duì)訂單揀選提出了更高的要求。因此，如何在AGV與貨架的最佳匹配上實(shí)現(xiàn)AGV，完成所有訂單總時(shí)間最短且碰撞避免，是重點(diǎn)研究?jī)?nèi)容。

本文針對(duì)訂單小批量、多批次的特點(diǎn)，引入混合存儲(chǔ)策略和訂單拆分策略，在此基礎(chǔ)上設(shè)計(jì)了一種確定貨架優(yōu)先級(jí)的AGV-貨架任務(wù)分配算法;為了解決多AGV搬運(yùn)路徑?jīng)_突問(wèn)題，設(shè)計(jì)了一種帶有貪婪參數(shù)并嵌入沖突消解策略的改進(jìn)的Q-Learning算法。

1 問(wèn)題描述與模型建立

1.1 問(wèn)題描述

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

為了進(jìn)一步理解“貨到人”智能倉(cāng)庫(kù)系統(tǒng)訂單揀選流程，本研究給出相關(guān)要素的形式化定義。

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

定義2 AGV。 AGV定義為q={M_q［i， j］，w，C_q}，M_q［i， j］表示AGV在倉(cāng)庫(kù)M中的當(dāng)前位置，w表示AGV最大的承載重量。AGV的狀態(tài)C_q∈{0，1}，若C_q=1表示AGV正在執(zhí)行貨架的搬運(yùn)工作，處于忙碌狀態(tài)，C_q=0則表示AGV當(dāng)前沒(méi)有搬運(yùn)任務(wù)，處于空閑狀態(tài)。

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

定義4 揀選站。一個(gè)揀選站定義為v={M_v［i， j］，I_v，C_v}，M_v［i， j］表示揀選站的位置，揀選站的編號(hào)用I_v表示，揀選站的狀態(tài)C_v∈{0，1}，若C_v=1表示揀選站正在執(zhí)行貨物揀選任務(wù)，處于忙碌狀態(tài)，C_v=0表示揀選站無(wú)揀選任務(wù)，處于空閑狀態(tài)。

定義5 路徑。一條路徑定義為R={P_start，P_end，t_start，R^*}，其中P_start和P_end分別為路徑的起點(diǎn)和終點(diǎn)， t_start表示路徑出發(fā)時(shí)間。R^*={p₁，p₂，…，p_n}為路徑對(duì)應(yīng)的子段序列，由一系列子段p={t^q_start，t^q_end，M_q［i， j］_end，M_q［i， j］_dist}組成，子段中各項(xiàng)分別表示子段開(kāi)始時(shí)間和結(jié)束時(shí)間、子段起點(diǎn)坐標(biāo)、子段終點(diǎn)坐標(biāo)、起點(diǎn)到終點(diǎn)間的坐標(biāo)差。

1.2 混合存儲(chǔ)策略

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

如圖3（a）所示在倉(cāng)庫(kù)內(nèi)按照貨物周轉(zhuǎn)率從大到小排序，1區(qū)定義為周轉(zhuǎn)率占比60%～80%的貨物，距離揀選站較近，貨架使用率較高，2區(qū)定義為周轉(zhuǎn)率占比20%～30%的貨物，距離揀選站較遠(yuǎn)，貨架使用率一般，其余定義為3區(qū)貨物。對(duì)于每個(gè)貨架來(lái)說(shuō)，貨物存儲(chǔ)方式如圖3（b）中貨架3的混合存儲(chǔ)策略所示，A、B、C、D、E、F、G七種商品將關(guān)聯(lián)性強(qiáng)的商品分配在同一貨架，這種混合存儲(chǔ)策略在智能倉(cāng)庫(kù)中可將總檢索時(shí)間減少多達(dá)40%^［19］，而貨架1和2為傳統(tǒng)存儲(chǔ)策略，每層只能存放一種商品，可以存儲(chǔ)單個(gè)商品的多個(gè)計(jì)數(shù)，貨物之間的關(guān)聯(lián)性較弱，需要更多的時(shí)間完成訂單揀選。

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

1.3 訂單拆分策略

訂單拆分策略目前已應(yīng)用于倉(cāng)庫(kù)訂單揀選環(huán)節(jié)^［20］，并且在“貨到人”系統(tǒng)中引入訂單拆分策略可以減少AGV搬運(yùn)貨架次數(shù)和行駛距離，并且與不拆分相比可以實(shí)現(xiàn)每小時(shí)多47%的訂單揀選數(shù)量^［21］。

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

為了說(shuō)明在混合存儲(chǔ)策略和訂單拆分策略的加持下能減少AGV完成訂單的總時(shí)間和降低AGV之間發(fā)生碰撞的可能性，以示例1進(jìn)行說(shuō)明。

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

2 考慮訂單拆分的AGV揀選優(yōu)化模型

2.1 問(wèn)題假設(shè)和變量

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

為了建立AGV揀選優(yōu)化模型，定義以下變量符號(hào)：

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

參數(shù)：S為拆分后的新訂單；l為拆分后待揀選的訂單列表；t^q_k為AGV q從空載狀態(tài)的位置（過(guò)道或?？繀^(qū)）行駛到目標(biāo)貨架位置的所用時(shí)間；t^q_kv為AGV q從目標(biāo)貨架位置行駛到揀選站完成揀選的所用時(shí)間；t^q_vk為AGV q從揀選站行駛到目標(biāo)貨架位置所用時(shí)間。

2.2 模型建立

1）決策變量

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

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

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

2）目標(biāo)函數(shù)

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）

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

3 AGV訂單揀選求解算法

在“貨到人”智能倉(cāng)庫(kù)系統(tǒng)中可將AGV訂單揀選問(wèn)題分為AGV-貨架任務(wù)分配、多AGV無(wú)沖突路徑規(guī)劃兩個(gè)子問(wèn)題來(lái)求解。

3.1 AGV-貨架任務(wù)分配算法

由于商品采用混合存儲(chǔ)策略，一個(gè)商品可能存放在多個(gè)貨架上，而且訂單拆分使新訂單中只含有一種商品的多個(gè)計(jì)數(shù)，為了最大化減少搬運(yùn)時(shí)間，每個(gè)揀選列表l={s₁，s₂，…，s_n}中會(huì)含有多個(gè)拆分后的訂單，那么就有必要確定貨架的優(yōu)先級(jí)，貨架中存放的商品滿足揀選列表中的商品種類和數(shù)量越多，貨架的優(yōu)先級(jí)就越高，成為其目標(biāo)貨架的可能性就越大。為了便于比較貨架的優(yōu)先級(jí)，下面引入0-1決策變量定義訂單填充性，令Y_sk標(biāo)識(shí)拆分后的每個(gè)訂單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-貨架任務(wù)分配算法步驟如下：

a）獲得當(dāng)前揀選列表l的信息以及無(wú)搬運(yùn)任務(wù)空閑狀態(tài)的AGV進(jìn)入任務(wù)匹配池；

b）根據(jù)式（8）（9）計(jì)算每個(gè)貨架k的C_sk值，最大值MaxC_sk所對(duì)應(yīng)的貨架k為目標(biāo)貨架；

c）根據(jù)式（10）計(jì)算空閑狀態(tài)AGV與目標(biāo)貨架k的曼哈頓距離，最小值MinΔdist₁為最佳AGV-貨架任務(wù)匹配對(duì)；

d）算法結(jié)束，從任務(wù)匹配池中移除當(dāng)前揀選列表l和AGV-貨架匹配對(duì)。

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

3.2.1 沖突消解策略

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

a）相向沖突消解策略：兩輛AGV行駛在同一條路徑上，方向相向行駛，將會(huì)在圖6（a）中圓點(diǎn)處產(chǎn)生碰撞，從而造成死鎖。其策略為根據(jù)路徑規(guī)劃算法形成的二維時(shí)間預(yù)約表，路徑長(zhǎng)度較短的AGV獲得優(yōu)先通過(guò)權(quán)，則另一輛AGV重新進(jìn)行路徑規(guī)劃，獲得次優(yōu)路徑，如果兩輛AGV路徑長(zhǎng)度相同，則隨機(jī)選擇優(yōu)先通過(guò)權(quán)。

b）十字路口沖突消解策略：當(dāng)兩輛AGV在同一時(shí)刻到達(dá)同一節(jié)點(diǎn)時(shí)，將會(huì)在圖6（b）中圓點(diǎn)處產(chǎn)生碰撞，從而產(chǎn)生死鎖，其策略為路徑長(zhǎng)度較短的AGV獲得優(yōu)先通過(guò)權(quán)，則另一輛AGV在路徑上進(jìn)行等待，如果兩輛AGV路徑長(zhǎng)度相同，則隨機(jī)選擇通過(guò)。

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

3.2.2 改進(jìn)的Q-Learning路徑規(guī)劃算法

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

在Q-Learning算法中，一般只有在AGV到達(dá)目標(biāo)時(shí)才給予相應(yīng)的瞬時(shí)獎(jiǎng)勵(lì)Re₁，為了讓AGV在最短時(shí)間內(nèi)到達(dá)目標(biāo)位置，增設(shè)向目標(biāo)點(diǎn)靠近動(dòng)作的獎(jiǎng)勵(lì)Re₂，其計(jì)算公式為

Re₂=10 Δdist₂lt;0

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

其中：Δdist₂為AGV q當(dāng)前狀態(tài)柵格位置M_q［i， j］和前一狀態(tài)柵格位置M_q［i， j］′與終點(diǎn)柵格位置M_end［i， j］的曼哈頓距離之差；終點(diǎn)位置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）

除了給予瞬時(shí)獎(jiǎng)勵(lì)Re₁和向目標(biāo)點(diǎn)靠近動(dòng)作的獎(jiǎng)勵(lì)Re₂外，AGV每走一步都將得到-1的獎(jiǎng)勵(lì)值，其目的在于讓AGV盡快走向終點(diǎn)。綜上，本研究的獎(jiǎng)懲函數(shù)計(jì)算公式為

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

算法步驟如下：

a）初始化獎(jiǎng)勵(lì)矩陣Re和Q^*值表；

b）判斷是否達(dá)到最大學(xué)習(xí)次數(shù)，沒(méi)有達(dá)到則繼續(xù)，否則執(zhí)行步驟h）；

c）初始化相關(guān)參數(shù)；

d）判斷是否找到最終目標(biāo)，如果沒(méi)有則繼續(xù)，否則執(zhí)行步驟h）；

e）動(dòng)作選擇狀態(tài)；

f）根據(jù)式（11）～（13）給出瞬時(shí)獎(jiǎng)勵(lì)Re；

g）Q^*值更新，相關(guān)參數(shù)衰減；

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

i）根據(jù)式（8）～（10）分配的AGV-貨架方案，輸出規(guī)劃的路線并保存路線的起點(diǎn)、終點(diǎn)和開(kāi)始時(shí)間；

j）根據(jù)沖突消解策略調(diào)整路徑；

k）算法結(jié)束，輸出最優(yōu)無(wú)沖突路徑R。

4 實(shí)驗(yàn)與分析

4.1 數(shù)據(jù)描述與參數(shù)設(shè)計(jì)

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

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

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

4.2 實(shí)驗(yàn)結(jié)果

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

首先驗(yàn)證ASTA算法的有效性，在智能倉(cāng)儲(chǔ)系統(tǒng)中基于表1的訂單集進(jìn)行了三組不同實(shí)驗(yàn)，并在路徑規(guī)劃算法固定為改進(jìn)Q-Learning算法的前提下，對(duì)比了不同的任務(wù)分配算法，包括ASTA、Auction^［25］和Random算法^［26］，從總路程、完成時(shí)間、任務(wù)效用（總路程/完成時(shí)間）和AGV使用數(shù)量四個(gè)方面來(lái)衡量ASTA算法的有效性。結(jié)合表2的實(shí)驗(yàn)結(jié)果來(lái)看，隨著訂單數(shù)量的增加，ASTA算法在總路程、完成時(shí)間和任務(wù)效用方面表現(xiàn)最好，用ASTA算法完成搬運(yùn)任務(wù)的時(shí)間與其他算法相比平均減少11.63%和26.74%。

圖10所示為ASTA、Auction和Random算法完成所有訂單所需AGV數(shù)量，在5個(gè)訂單集中，ASTA算法與兩種分配算法相比，所需AGV數(shù)量最少，這是因?yàn)锳STA算法考慮了訂單拆分和混合存儲(chǔ)策略，在這兩種策略的加持下，可以減少AGV使用數(shù)量，緩解AGV搬運(yùn)路徑?jīng)_突的情況，節(jié)約完成訂單的時(shí)間，這也說(shuō)明了訂單拆分的必要性。

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

4.2.2 AGV數(shù)量靈敏度分析

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

5 結(jié)束語(yǔ)

本文研究了“貨到人”系統(tǒng)中AGV訂單揀選問(wèn)題，考慮訂單需求多樣性、商品在倉(cāng)庫(kù)中多貨架存儲(chǔ)、訂單與貨架匹配關(guān)系未知，及AGV路徑可能產(chǎn)生沖突等實(shí)際因素，在混合存儲(chǔ)基礎(chǔ)上引入訂單拆分策略，基于訂單拆分策略構(gòu)建以總訂單完工時(shí)間最小為目標(biāo)的數(shù)學(xué)模型，并根據(jù)問(wèn)題特點(diǎn)設(shè)計(jì)AGV-貨架任務(wù)匹配算法、路徑?jīng)_突消解策略與改進(jìn)的Q-Learning算法。數(shù)值實(shí)驗(yàn)結(jié)果表明，所提算法能在40 m×40 m的倉(cāng)庫(kù)布局中處理800個(gè)訂單任務(wù)。此外，通過(guò)對(duì)AGV數(shù)量的靈敏度分析，發(fā)現(xiàn)19臺(tái)AGV數(shù)量配置是最為適宜的。

此外，本文為“貨到人”智能倉(cāng)庫(kù)系統(tǒng)的運(yùn)營(yíng)提供如下管理啟示：

a）運(yùn)用本文模型和ASTA算法求解的AGV-貨架任務(wù)分配問(wèn)題為AGV揀選環(huán)節(jié)提供一個(gè)良好的調(diào)度基礎(chǔ)。

b）針對(duì)“一單多品”的智能揀選系統(tǒng)，如食品和日用品倉(cāng)庫(kù)、促銷活動(dòng)與捆綁銷售策略倉(cāng)庫(kù)等，商品之間的關(guān)聯(lián)度較高，管理者可充分利用混合存儲(chǔ)和訂單拆分策略以減少貨架移動(dòng)次數(shù)，提高揀選效率，緩解AGV之間的路徑?jīng)_突問(wèn)題。

c）針對(duì)季節(jié)性、熱銷品類等出庫(kù)率較高的商品，管理者可適當(dāng)調(diào)整移動(dòng)貨架位置，減少AGV搬運(yùn)時(shí)間。

在本文的研究中，訂單拆分時(shí)進(jìn)行了理想化處理，并沒(méi)有考慮商品體積、類型對(duì)拆分和合并的影響，后續(xù)將考慮按照商品性質(zhì)進(jìn)行拆分，其次是基于離線訂單的揀選優(yōu)化問(wèn)題，并沒(méi)有考慮在線訂單、緊急訂單插入、訂單取消等問(wèn)題，未來(lái)的研究中將盡可能還原真實(shí)揀選場(chǎng)景，實(shí)現(xiàn)在線的優(yōu)化。

參考文獻(xiàn)：

［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］李建斌， 蒙銘友， 戴賓. 電子商務(wù)環(huán)境下的存儲(chǔ)策略優(yōu)化研究： 固定存儲(chǔ)還是分類隨機(jī)存儲(chǔ) ［J］. 中國(guó)管理科學(xué)， 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］謝勇， 任建偉， 王紅衛(wèi). 考慮通道阻塞的雙揀貨員訂單揀選優(yōu)化研究 ［J］. 系統(tǒng)工程理論與實(shí)踐， 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］李林蔓， 李雨青， 王孟雅， 等. 基于啟發(fā)式規(guī)則的自動(dòng)化碼頭換電式AGV調(diào)度優(yōu)化方法 ［J］. 運(yùn)籌與管理， 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］陳仁勝， 吳斌， 閆飛一. 基于混合學(xué)習(xí)策略的可變速AGV與機(jī)器綠色集成調(diào)度 ［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］張新艷， 鄒亞圣. 基于改進(jìn)A^*算法的自動(dòng)導(dǎo)引車無(wú)碰撞路徑規(guī)劃 ［J］. 系統(tǒng)工程理論與實(shí)踐， 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］李昆鵬， 韓雪芳. 智能倉(cāng)庫(kù)中多AGV在線任務(wù)指派與全局路徑規(guī)劃問(wèn)題研究 ［J/OL］. 中國(guó)管理科學(xué)（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］毛文平， 李帥永， 謝現(xiàn)樂(lè). 基于自適應(yīng)機(jī)制改進(jìn)蟻群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃 ［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］牛雅倩， 余芳， 劉靜雯， 等. 基于動(dòng)態(tài)平衡策略的自動(dòng)化碼頭多AGV路徑優(yōu)化算法研究 ［J］. 計(jì)算機(jī)應(yīng)用研究， 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.