多搬運任務(wù)下考慮碰撞避免的AGV路徑規(guī)劃

張艷菊 吳俊 程錦倩 陳澤榮

摘 要：為提升自動導(dǎo)引小車在“貨到人”倉庫中的運行效率，針對AGV-托盤任務(wù)分配、單AGV路徑規(guī)劃及多AGV碰撞避免三個子問題的研究，以最小化AGV行駛距離為目標(biāo)構(gòu)建數(shù)學(xué)模型。首先，根據(jù)AGV與托盤的雙邊匹配問題特點設(shè)計改進(jìn)的匈牙利算法求解匹配結(jié)果。其次，提出一種二維編碼機制的改進(jìn)遺傳算法（improved genetic algorithm，IGA），采用一種局部搜索算子代替原變異操作，在提高算法搜索性能的基礎(chǔ)上使其成功應(yīng)用于單AGV路徑規(guī)劃問題。然后，利用時空數(shù)據(jù)設(shè)計一種三維網(wǎng)格沖突檢測方法，并根據(jù)商品SKU數(shù)量設(shè)定AGV的優(yōu)先級以降低多AGV執(zhí)行任務(wù)時的碰撞概率。最后，在32 m×22 m的倉庫中針對不考慮碰撞與考慮碰撞兩種情形進(jìn)行AGV路徑優(yōu)化分析，給出合理的行駛距離和碰撞次數(shù)。IGA與標(biāo)準(zhǔn)遺傳算法的對比結(jié)果顯示，IGA能夠在合理的時間內(nèi)獲得更高質(zhì)量的解，行駛距離減少約1.74%，算法求解時間縮短約37.07%。此外，針對AGV數(shù)量靈敏度分析，在不同目標(biāo)托盤規(guī)模下測試不同數(shù)量的AGV對行駛距離和碰撞次數(shù)的影響，發(fā)現(xiàn)14～16臺AGV數(shù)量是最佳配置，驗證了模型的可行性和算法的有效性。

關(guān)鍵詞：智能倉庫；AGV路徑規(guī)劃；碰撞避免；雙邊匹配；改進(jìn)的遺傳算法

中圖分類號：TP242?? 文獻(xiàn)標(biāo)志碼：A??? 文章編號：1001-3695（2024）05-026-1462-08

doi： 10.19734/j.issn.1001-3695.2023.09.0426

AGV path planning considering collision avoidance of multiple handling tasks

Abstract：To improve the operation efficiency of automated guided vehicle in the “parts-to-picker” warehouse， aiming at the three sub-problems of AGVs-pallets task assignment， single AGV path planning and multi-AGVs collision avoidance， this paper built a mathematical model with the objective of minimizing the driving distance of AGVs. Firstly， it designed the improved Hungarian algorithm to solve the matching results according to the characteristics of bipartite matching problem between AGVs and pallets. Secondly， it proposed an improved genetic algorithm （IGA） with two-dimensional encoding mechanism， for which it designed a local search operator replace the original mutation operation. It successfully applied the algorithm to the single AGV path planning problem on the premise of improving the search performance of this algorithm. Then， it utilized spatiotemporal data to design a three-dimensional mesh conflict detection method， and set the priority of AGVs according to the number of commodity SKUs to reduce the collision probability when multiple AGVs execute tasks. Finally， it studied the AGV path optimization for the two scenarios of no collision and considering collision at the warehouse of 32 m×22 m， which gave reasonable driving distance and collision times. IGA was compared with standard genetic algorithm. The results indicate that the IGA can obtain the higher quality solutions in a reasonable time， which reduced the driving distance by about 1.74% and the solution time of the algorithm by about 37.07%. Furthermore， for the sensitivity analysis on the number of AGVs， it tested the influence of different numbers of AGVs on the driving distance and the number of collisions under different target pallets sizes. It was found that the number of 14～16 AGVs is the optimal configuration. These results verify the feasibility of the model and the effectiveness of the proposed algorithm.

Key words：intelligent warehouse; AGV path planning; collision avoidance; bipartite matching; improved genetic algorithm

0 引言

近年來，我國電子商務(wù)行業(yè)發(fā)展迅猛。數(shù)據(jù)顯示，2022年的網(wǎng)上零售額達(dá)到13.79萬億元，與2012年的1.304萬億元相比，增長了近十倍。隨著電商訂單向小批量、多品種、高頻次轉(zhuǎn)變［1］，傳統(tǒng)的“人到貨”揀選系統(tǒng)弊端日益凸顯，主要體現(xiàn)在揀選員僅花費在貨架間行走的時間就占據(jù)了總作業(yè)時間的60%左右，揀貨的準(zhǔn)確性也受到揀貨員工作強度等因素的影響而大打折扣。為提升揀選作業(yè)效率，亞馬遜首次將具有智能倉儲機器人的Kiva系統(tǒng)應(yīng)用到倉庫中。隨后，眾多電商巨頭也紛紛采用“貨到人”揀選系統(tǒng)，將自動導(dǎo)引小車（automated guided vehicle，AGV）投入到倉庫中使用［2］。在該系統(tǒng)中，AGV將托盤搬至揀選站、存儲區(qū)或空托盤回收站，揀選員只需待在揀選站執(zhí)行商品揀選作業(yè)，不僅大大縮減了揀貨員的工作量和人工成本，訂單揀選效率也有了質(zhì)的飛躍［3］。

當(dāng)前，眾多學(xué)者針對“貨到人”揀選系統(tǒng)的研究主要集中在AGV調(diào)度、路徑規(guī)劃和碰撞避免［4］方面。關(guān)于AGV調(diào)度的研究，付建林等人［5］將AGV調(diào)度總結(jié)為靜態(tài)調(diào)度、動態(tài)調(diào)度與AGV聯(lián)合其他資源調(diào)度三種類型。胡曉陽等人［6］針對多AGV柔性作業(yè)車間調(diào)度問題，設(shè)計了一種融合貪心啟發(fā)式規(guī)則的改進(jìn)迭代局部搜索算法。Boccia等人［7］研究了一種具有電池約束的AGV調(diào)度（ASP-BC）問題。近年來，多負(fù)載AGV任務(wù)調(diào)度［8，9］吸引了部分學(xué)者的研究興趣。Maoudj等人［10］針對AGV容量和沖突產(chǎn)品約束的多AGV調(diào)度問題，提出了一種離散方法。

關(guān)于AGV路徑規(guī)劃問題的研究，傳統(tǒng)A*算法和標(biāo)準(zhǔn)智能優(yōu)化算法存在收斂速度慢且易陷入局部最優(yōu)的缺陷，改進(jìn)的A*算法［11］、改進(jìn)的自適應(yīng)遺傳算法［12］和改進(jìn)的自適應(yīng)蟻群算法［13，14］被相繼提出。與此同時，一些學(xué)者也開始將強化學(xué)習(xí)應(yīng)用到AGV路徑規(guī)劃中。黃巖松等人［15］提出一種結(jié)合Q-learning與深度學(xué)習(xí)的DQN算法，用于求解AGV多起點多終點的路徑規(guī)劃問題。Hu等人［16］針對AGV反向沖突和相同點占用沖突，設(shè)計了一種多智能體深度確定性梯度策略（MADDPG）方法。賀雪梅等人［17］基于深度強化學(xué)習(xí)設(shè)計了一種改進(jìn)的DL-DDPG算法，實現(xiàn)了AGV在大規(guī)模未知復(fù)雜環(huán)境中的自主導(dǎo)航和避障。然而，利用強化學(xué)習(xí)解決AGV路徑規(guī)劃問題大多是在仿真實驗環(huán)境下進(jìn)行的，與真實倉庫環(huán)境有一定差距。此外，強化學(xué)習(xí)過程在探索階段具有隨機性，即使在相同的條件下，每次訓(xùn)練的結(jié)果也有一定的差異。

關(guān)于AGV碰撞避免的研究，Zhang等人［18］提出四種AGV碰撞類型，并設(shè)計了三種解決方案。Xiao等人［19］針對AGV單向?qū)б窂骄W(wǎng)絡(luò)，提出了一種基于流量順序優(yōu)化策略的碰撞和死鎖預(yù)防方法。武星等人［20］基于多載量AGV變長特性和交叉路口沖突，分別設(shè)計了變長度AGV路徑空間沖突避免方法和帶防死鎖策略的交叉路口通行順序優(yōu)化方法。李昆鵬等人［21］針對可能發(fā)生沖突的路徑交叉點，設(shè)計的碰撞避免及檢測算法實現(xiàn)了AGV的主動避撞。

綜合對AGV調(diào)度、路徑規(guī)劃和碰撞避免問題的研究成果進(jìn)行回顧發(fā)現(xiàn)，現(xiàn)有文獻(xiàn)多針對某一環(huán)節(jié)進(jìn)行研究，對于多環(huán)節(jié)問題的研究較少。此外，關(guān)于AGV與托盤的一對多雙邊匹配關(guān)系還未得到充分研究。同時考慮托盤任務(wù)分配與AGV路徑規(guī)劃兩個環(huán)節(jié)，更具實際應(yīng)用價值。此外，在“貨到人”倉庫的高峰運行期間，往往會安排多臺AGV同時執(zhí)行搬運作業(yè)，一旦發(fā)生碰撞事件就會影響倉庫的整體運作效率。因此，如何在AGV與托盤的最佳匹配上實現(xiàn)AGV總行駛距離最短且碰撞避免，是重點研究內(nèi)容。

本文的貢獻(xiàn)包括：a）為更好實現(xiàn)AGV與托盤的匹配，引入雙邊匹配模型，并利用最大貪心思想對匈牙利算法進(jìn)行改進(jìn)；b）考慮到不同托盤由不同AGV搬運的問題特點，設(shè)計一種二維編碼方式的改進(jìn)遺傳算法（improved genetic algorithm，IGA）解決單AGV路徑規(guī)劃問題，并用局部搜索算子替換變異算子，增強了算法尋優(yōu)能力并跳出局部最優(yōu)；c）在AGV的時空數(shù)據(jù)的基礎(chǔ)上，設(shè)計碰撞檢測算法檢測可能發(fā)生的路徑?jīng)_突，并劃分AGV的優(yōu)先級作為避讓規(guī)則。

1 問題描述及模型建立

1.1 問題描述

“貨到人”倉庫訂單揀選流程如圖1所示。首先，倉庫接收包含商品SKU編號和數(shù)量等信息的o個訂單，在確定儲位后，按照既定的任務(wù)分配方式將倉庫內(nèi)的p個托盤分配給a臺AGV搬運。其次，AGV接到任務(wù)指令后，按照既定的優(yōu)化路線與交通規(guī)則先從初始位置移至目標(biāo)托盤處，確認(rèn)托盤信息無誤后將托盤搬至相應(yīng)的揀選站。然后，揀貨員按照訂單要求執(zhí)行各項商品的揀選任務(wù)。最后，對于已完成揀選作業(yè)的托盤，AGV有兩種選擇：若托盤上的商品仍有剩余，則將其搬至原儲位；否則，將其搬至空托盤回收站。

為進(jìn)一步理解“貨到人”倉庫的訂單揀選流程，下面給出相關(guān)要素的形式化定義。

定義1 訂單。一個訂單定義為o={Io，Uo，No}。Io為訂單編號，Uo表示訂單所需商品的SKU編號，訂單所需商品數(shù)量為正整數(shù)No。

定義2 托盤。一個托盤定義為p={Xp，Yp，Jp，Sp}。以Xp為橫坐標(biāo)、Yp為縱坐標(biāo)表示托盤的位置，Jp為托盤編號，拖盤的狀態(tài)Sp∈{0，1}。若Sp=1表示托盤正被AGV搬運，處于忙碌狀態(tài)；若Sp=0表示托盤未被AGV搬運，處于空閑狀態(tài)。

定義3 AGV。一個AGV定義為a={Xa，Ya，Sa}。Xa、Ya分別為AGV的橫坐標(biāo)與縱坐標(biāo)，AGV的狀態(tài)Sa∈{0，1}。若Sa=1表示AGV正執(zhí)行托盤搬運工作，處于忙碌狀態(tài)；若Sa=0表示AGV當(dāng)前無搬運任務(wù)，處于空閑狀態(tài)。

定義4 揀選站。一個揀選站定義為w={Iw，Xw，Yw，Sw}。Iw為揀選站編號，揀選站以Xw為橫坐標(biāo)、以Yw為縱坐標(biāo)，揀選站的狀態(tài)Sw∈{0，1}。若Sw=1表示揀選站正在執(zhí)行商品揀選任務(wù)，處于忙碌狀態(tài)；若Sw=0表示揀選站無揀選任務(wù)，處于空閑狀態(tài)。

基于實際情況，考慮了如下假設(shè)：a）所有訂單信息均已知，不存在訂單拆分；b）每個托盤上有多個貨位可供存放商品，商品也可以存放在多個托盤上；c）一臺AGV一次只能搬運一個托盤；d）托盤上的商品SKU種類和數(shù)量能夠滿足工作期間所有訂單的需求；e）出于安全考慮，每臺AGV每秒勻速行駛1個單元格，且所有AGV在工作期間無須進(jìn)行充電操作。

1.2 模型建立

基于上述問題描述、定義及相關(guān)假設(shè)，模型中涉及的集合、參數(shù)與決策變量如下：

a）集合：O為訂單集合，O={1，2，…，o}；P為托盤（儲位）集合，P={1，2，…，p}；A為AGV集合，A={1，2，…，a}；W為揀選站集合，W={1，2，…，w}；S為商品SKU集合，S={1，2，…，s}；K為空托盤回收站集合，K={1，2，…，k}。

b）參數(shù)：Tos為訂單o對商品s的需求量；T為訂單的總商品需求量；Qps為托盤p存放商品s的數(shù)量；Q為托盤存放的總商品數(shù)量；gpsw為托盤p上的商品s在揀選站w被揀選的數(shù)量；dap為AGV a從初始位置移至托盤p處的行駛距離；dapw為AGV a將托盤p從原儲位搬至揀選站w的行駛距離；dawp為AGV a將揀選站w的托盤p搬至原儲位的行駛距離；dawpk為AGV a將揀選站w的托盤p搬至空托盤回收站k的行駛距離。

c）決策變量：

xapw為0-1變量，等于1表示AGV a將托盤p搬至揀選站w處分揀，否則為0；

ypw為0-1變量，等于1表示托盤p上的商品在揀選站w被全部揀選；否則為0；

hap為0-1變量，等于1表示AGV a被安排前往托盤p處的位置，否則為0；

zawp為0-1變量，等于1表示AGV a將揀選站w處的托盤p搬至原儲位，否則為0；

δawpk為0-1變量，等于1表示AGV a將托盤p從揀選站w搬至空托盤回收站k，否則為0。

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

e）約束條件

目標(biāo)函數(shù)式（1）表示最小化所有AGV的總行駛距離。約束條件式（2）表示AGV a未從初始位置移至托盤p處，則AGV a的行駛距離為0；約束條件式（3）表示AGV a未將托盤p搬至揀選站w，則AGV a的行駛距離為0；約束條件式（4）表示AGV a將托盤p搬至揀選站w，并且托盤p上的商品在揀選站w被全部揀選，則AGV a將揀選站w處的托盤p搬至其原儲位的行駛距離為0；約束條件式（5）表示AGV a將托盤p搬至揀選站w，并且托盤p上的商品在揀選站w完成揀選后仍有剩余，則AGV a將揀選站w處的托盤p搬至空托盤回收站k的行駛距離為0；約束條件式（6）表示AGV a只能將托盤p搬至一個揀選站；約束條件式（7）表示AGV a只能將完成揀選的托盤p從揀選站w搬至一個原儲位或一個空托盤回收站；約束條件式（8）表示AGV a未將托盤p搬至揀選站w，托盤p上一定有剩余商品；約束條件式（9）表示托盤p上的商品在揀選站w完成揀選后仍有剩余，則AGV a需將其搬至原儲位；約束條件式（10）表示AGV a未將托盤p搬至揀選站，則無須將其搬至原儲位；約束條件式（11）表示AGV a未將托盤p搬至揀選站w，或者AGV a將托盤p搬至揀選站w，托盤p上的商品在完成揀選后仍有剩余，則AGV a無須將托盤p搬至空托盤回收站k；約束條件式（12）表示托盤p上的商品在揀選站w處被全部揀選，則AGV a需將其搬至空托盤回收站k；約束條件式（13）表示決策變量約束。

2 AGV-托盤匹配思路設(shè)計

2.1 倉庫柵格化地圖建立

柵格化是一種將對象的空間數(shù)據(jù)以二維矩陣的形式進(jìn)行表示的方法。利用柵格化可以將倉庫地圖劃分為大小均等的小柵格，每個小柵格對應(yīng)倉庫內(nèi)的一種要素，如圖2所示。

規(guī)定每個小柵格的長度為1，將中心點位置作為每個小柵格的位置［22］。假設(shè)第i個小柵格的坐標(biāo)為（bi，ci），當(dāng)mod（bi，ci）≠0，計算公式如下：

其中：mod為求余運算；ceil（j）為不小于j的最小整數(shù)；ε為每一行的小柵格數(shù)。當(dāng)mod（bi，ci）=0時，小柵格位置的計算公式依據(jù)式（15）進(jìn)行更新：

利用收集到的數(shù)據(jù)集，選取曼哈頓距離度量AGV與托盤間的遠(yuǎn)近程度，如表1所示。規(guī)定AGV編號為1～19，托盤編號為20～167。

2.2 AGV-托盤的一對多雙邊匹配

在“貨到人”倉庫中，出于成本考慮，AGV數(shù)量要遠(yuǎn)少于托盤的數(shù)量。因此，研究的AGV-托盤任務(wù)分配問題（AGVs-pallets task allocation problem， APTAP）是典型的一對多雙邊匹配問題。APTAP問題可以描述為：一個托盤主體集合P={p1，p2，…，pm}，一個AGV主體集合A={a1，a2，…，an}，m個托盤需要n臺AGV搬運。一個托盤最多與一臺AGV匹配，而一臺AGV可以與多個托盤匹配。如圖3所示，有3臺AGV（a1、a2、a3）可用，6個托盤需要搬運（p1、p2、p3、p4、p5、p6）。a1能夠搬運托盤p2、p3、p4；a2能夠搬運托盤p1、p2、p3、p5、p6；a3能夠搬運托盤p4、p5、p6。最終，a1與p2和p4匹配，a2與p1和p3匹配，a3與p5和p6匹配。

2.3 改進(jìn)的匈牙利算法

匈牙利算法（Hungarian algorithm，HA）是Kuhn在引用康尼格一個關(guān)于矩陣中0元素定理的基礎(chǔ)上提出來的，被認(rèn)為是解決分配指派問題的標(biāo)準(zhǔn)解法［23］。分配指派問題可細(xì)分為平衡指派問題和非平衡指派問題［24］，研究的APTAP問題屬于非平衡指派問題。為降低求解難度，需要將APTAP問題轉(zhuǎn)換為平衡指派問題。具體做法為：將數(shù)據(jù)集中的148個托盤進(jìn)行拆解，前七組屬于19×19的平衡指派，第八組為19×15的不平衡指派，需增設(shè)4個虛擬托盤（托盤與AGV間的曼哈頓距離設(shè)為M，一個極大的值）。傳統(tǒng)匈牙利算法首先會對初始效率矩陣進(jìn)行變換，直至各行各列均出現(xiàn)0元素，然后才進(jìn)行試指派。需要注意的是，如果需要進(jìn)行多次矩陣變換，計算時間就會增加?；诖?，為保證AGV-托盤的匹配結(jié)果更優(yōu)，利用一種最大貪心策略對匈牙利算法進(jìn)行改進(jìn)，即每次選擇能夠最大程度地減少目標(biāo)函數(shù)值的要素，具體的計算步驟為：

a）依據(jù)對148個托盤的拆解結(jié)果，計算出每組中每臺AGV與托盤間的曼哈頓距離，并將曼哈頓距離作為匹配值矩陣。其中，行代表AGV，列代表托盤。

b）依次計算出匹配值矩陣中各行和各列的最小距離值和次小距離值的差額。

c）從行或列差額中選出最大的元素，選擇它所在行或列中的最小距離值，并劃掉最小距離值所在的行和列。

d）將未劃去的距離值再分別計算出各行、各列的最小距離值和次小距離值的差額。

e）重復(fù)步驟b）和c），直至所有托盤均已指派給AGV，輸出最終指派結(jié)果。

利用改進(jìn)的匈牙利算法求解托盤和AGV數(shù)量皆為4的平衡指派問題，如圖4所示，最終的指派結(jié)果為（a3，p32）、（a7，p28）、（a10，p21）、（a12，p25）。雖與傳統(tǒng)匈牙利算法計算出的結(jié)果一致，但改進(jìn)的匈牙利算法大大提高了計算效率。

在AGV與托盤進(jìn)行匹配前，通過驗證訂單數(shù)據(jù)和托盤數(shù)據(jù)發(fā)現(xiàn)，大部分托盤上存儲的商品正好滿足用戶的實際需求，只有少量托盤上的商品有些許存量。例如，p160剩有2類商品SKU的數(shù)量分別為24和15；p161剩有2類商品SKU的數(shù)量分別為14和25；p162剩有2類商品SKU的數(shù)量分別為30和11；p163剩有1類商品SKU的數(shù)量為20；p164剩有2類商品SKU的數(shù)量分別為33和54；p165剩有2類商品SKU的數(shù)量分別為2和34；p166剩有2類商品SKU的數(shù)量分別為31和24；p167剩有2類商品SKU的數(shù)量分別為52和4。有趣的是，p160、p161、p162、p164、p165、p166和p167剩余的商品SKU種類與數(shù)量等于其初始的商品SKU種類與數(shù)量。因此，編號為p160、p161、p162、p164、p165、p166和p167的托盤無須進(jìn)行搬運。利用改進(jìn)的匈牙利算法求出的AGV與托盤匹配結(jié)果如表2所示。可以看出，a3、a4、a5、a7、a8、a9、a14、a15、a17、a18和a19搬運的托盤數(shù)量為7個，其他AGV搬運的托盤數(shù)量均為8個。匹配結(jié)果總體上比較均衡，倉庫資源的利用較為合理。

3 AGV路徑規(guī)劃與避碰算法設(shè)計

3.1 AGV任務(wù)劃分

一般來說，AGV在倉庫內(nèi)有三項任務(wù)：一是將目標(biāo)托盤搬至揀選站；二是在揀選任務(wù)完成后將托盤從揀選站搬至原儲位；三是在揀選任務(wù)完成后將托盤從揀選站搬至空托盤回收站。其中，任務(wù)二和任務(wù)三只選擇其中一個執(zhí)行，圖5為一臺AGV在倉庫內(nèi)執(zhí)行三種任務(wù)的示例。

3.2 基于改進(jìn)遺傳算法的單AGV路徑規(guī)劃

求解AGV路徑規(guī)劃這類組合優(yōu)化問題時，利用遺傳算法（genetic algorithm，GA）雖能在合理時間內(nèi)獲取較優(yōu)方案，但也存在收斂速度慢、易陷入局部最優(yōu)等不足?！柏浀饺恕眰}庫中的AGV路徑規(guī)劃問題，就是為AGV規(guī)劃出一條能安全且快速地從起點到達(dá)目標(biāo)點的路徑。在不考慮AGV碰撞的前提下，為實現(xiàn)所有AGV在倉庫內(nèi)的總行駛距離最短，設(shè)計改進(jìn)的遺傳算法（improved genetic algorithm，IGA），算法的流程如圖6所示。

3.2.1 編碼機制

結(jié)合不同托盤由不同AGV搬運的問題特點，本文設(shè)計一種二維編碼方式。如圖7所示，AGV1搬運托盤35、52、71和94，AGV2搬運托盤29、41、70和88。

3.2.2 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是遺傳算法中評價個體優(yōu)劣的有效工具。本文將目標(biāo)函數(shù)值映射成適應(yīng)度值，適應(yīng)度值越大，代表個體越優(yōu)。

3.2.3 種群初始化

初始種群大小反映種群中的個體數(shù)量。種群過大，算法計算復(fù)雜，導(dǎo)致運行效率低；而種群過小，則容易陷入局部最優(yōu)。種群初始化的示例如圖8所示，具體步驟如下：

a）將托盤集合P中的托盤進(jìn)行隨機排列，得到排列集合Pr，形成染色體的第一維編碼；

b）針對Pr中的每一個托盤，依據(jù)表2的結(jié)果從AGV集合A中選擇出相應(yīng)的AGV進(jìn)行搬運，形成染色體的第二維編碼；

c）按照托盤與AGV間的曼哈頓距離進(jìn)行降序排列，從而得到每臺AGV的托盤搬運任務(wù)序列Bx；

d）重復(fù)步驟a）～c），直至達(dá)到預(yù)設(shè)的種群規(guī)模Yz，輸出初始種群。

3.2.4 遺傳操作

1）交叉算子。

種群初始化后的每條染色體代表一個搬運方案。交叉操作將種群中的兩個個體按照一定的交叉概率交換部分染色體，從而得到新的個體。具體步驟為：首先，利用輪盤賭機制從種群中選擇2條染色體作為父代染色體；其次，隨機選擇1個托盤作為交叉點位置；最后，根據(jù)交叉概率對2條父代染色體執(zhí)行交叉操作，如圖9所示。

2）局部搜索算子。

在完成交叉操作后，標(biāo)準(zhǔn)遺傳算法通常會進(jìn)行變異操作。然而，有時由于變異概率設(shè)置過低，可能會導(dǎo)致算法的搜索能力較差［25］?；诖耍疚脑O(shè)計一種局部搜索算子（single-segment operator，SSO）以提升算法的搜索能力。具體步驟為：首先，隨機從子代種群中挑選出1個子代染色體，并從染色體中選擇一個片段；其次，從選擇的染色體片段中選擇一個托盤p（p∈P），將其插入到片段中除起始位置的一個可行位置。最后，將插入新位置產(chǎn)生的新解與初始解進(jìn)行比較。若優(yōu)于初始解，則用新解替換初始解，如圖10所示。

3.3 多AGV碰撞檢測與避免算法

3.3.1 多AGV網(wǎng)格化碰撞檢測

在“貨到人”倉庫中，托盤占據(jù)了倉庫的大部分面積，這使得AGV通行的通道寬度受到限制。當(dāng)多臺AGV同時在倉庫內(nèi)執(zhí)行任務(wù)時，路徑?jīng)_突是不可避免的。這會導(dǎo)致碰撞與擁堵情況的出現(xiàn)，進(jìn)而影響正常的揀選工作。常見的四種AGV沖突類型如圖11所示。其中，圖11（a）為兩臺AGV在垂直方向同時經(jīng)過十字小柵格引發(fā)的垂直沖突；圖11（b）為兩臺AGV在水平方向同時朝著同一條直線行駛，最終會在某個小柵格引發(fā)相向沖突；圖11（c）為兩臺AGV在同一窄通道內(nèi)行駛，由于無法調(diào)整行駛方向進(jìn)行避讓引發(fā)的相向死鎖；圖11（d）為前往1處的AGV和前往2處的AGV在窄通道引發(fā)死鎖導(dǎo)致雙方都無法到達(dá)各自的目的地。

為提高AGV的沖突檢測效率，利用AGV的時空數(shù)據(jù)設(shè)計一種基于三維網(wǎng)格的AGV沖突檢測方法，如圖12所示。三維網(wǎng)格是在二維網(wǎng)格的基礎(chǔ)上考慮了時間因素。對于路徑routei中的第a臺AGV，可以根據(jù)其行駛過程中的三維坐標(biāo)（ti， j，xi， j，yi， j），確定它所在的網(wǎng)格單元nete，f，g。

假定一個網(wǎng)格單元以自身為中心，能夠檢測自身及空間維度內(nèi)的（32-1）+1=9個網(wǎng)格，并組成該網(wǎng)格單元的鄰域，如式（16）所示。如果在該鄰域內(nèi)檢測到其他AGV，表明該路徑可能會發(fā)生沖突。針對這種情況，本文需要確定這種可能性沖突的類別，并采取相應(yīng)的碰撞避免策略。如果在鄰域內(nèi)未檢測到其他AGV，則表明該路徑不會發(fā)生沖突。

3.3.2 基于優(yōu)先級規(guī)劃法的多AGV碰撞避免

為避免多臺AGV發(fā)生碰撞，傳統(tǒng)做法是讓AGV在原地等待。盡管這種做法確保了AGV的安全性，但對訂單的準(zhǔn)時交付率影響較大。當(dāng)AGV搬運托盤時，若托盤上的商品SKU數(shù)量為13以上（包括13）的用戶訂單，則設(shè)定AGV等級為1。若托盤上的商品SKU數(shù)量為13以下的用戶訂單，則設(shè)定AGV等級為2。具體的AGV等級劃分如表3所示。規(guī)定避讓原則為：當(dāng)?shù)蛢?yōu)先級的AGV與高優(yōu)先級的AGV在經(jīng)過沖突檢測后可能會發(fā)生碰撞時，低優(yōu)先級的AGV要主動避讓并調(diào)整路徑。例如，如果發(fā)生類似圖11（a）中的碰撞，低優(yōu)先級的AGV需向下移動1個單元格。當(dāng)AGV的優(yōu)先級一致時，則以托盤上的具體商品SKU數(shù)量為判定依據(jù)。此外，為防止發(fā)生如圖11（d）所示的死鎖現(xiàn)象，高優(yōu)先級的AGV在規(guī)劃路徑時，要避免占用未進(jìn)行路徑規(guī)劃的低優(yōu)先級AGV的連通節(jié)點。

4 數(shù)值實驗與結(jié)果分析

4.1 數(shù)據(jù)描述與實驗參數(shù)設(shè)置

本文實驗數(shù)據(jù)來自公開數(shù)據(jù)集，倉庫是一個大小為32 m×22 m的矩形區(qū)域，如圖13所示。

倉庫內(nèi)共有18個揀選站。當(dāng)AGV將托盤搬至揀選站時，揀選員開始執(zhí)行商品揀選工作。倉庫需處理675個用戶訂單，每個訂單皆為一單一品，共計有185種商品SKU種類。倉庫內(nèi)托盤呈兩列一組排列，共計有148個托盤。托盤上可存放1～5種不同的商品SKU。托盤間的白色小柵格為AGV的單行通道。倉庫內(nèi)?？恐?9臺可用AGV，它們分布在倉庫內(nèi)的不同位置。假定每臺AGV每秒勻速行駛一個單元格（1 m），將四方向（上、下、左、右）搜索節(jié)點法作為AGV的行駛方向依據(jù)。此外，倉庫內(nèi)還有2個空托盤回收站、6個固定障礙物和6個保留節(jié)點。托盤與揀選站間的曼哈頓距離、揀選站與空托盤回收站間的曼哈頓距離如表4和5所示。

圖14和15為數(shù)據(jù)集中關(guān)于用戶訂單商品SKU數(shù)量分布情況和托盤存儲SKU種類分布情況?？梢钥闯?，商品SKU數(shù)量為［1，5］的用戶訂單有381個，占比超過了一半以上。商品SKU數(shù)量為［6，10］、［11，15］、［16，20］和［21，219］的用戶訂單分別有92、50、34和118個，占比分別為13.63%、7.41%、5.04%和17.48%。這表明用戶訂單多以小批量為主。存儲的商品SKU種類為［1，3］的托盤有142個，占比高達(dá)95.95%。而存儲的商品SKU種類為［4，5］的托盤只有6個，僅占4.05%。

實驗通過Python 3.7 編程實現(xiàn)，在搭載Intel Core i7（2.80 GHz）CPU和16 GB RAM并運行Windows 11系統(tǒng)的筆記本電腦上進(jìn)行求解計算。經(jīng)過大量測試，最終確定算法的最佳參數(shù)設(shè)置為：種群大小為50，最大迭代次數(shù)為200次，交叉概率為0.9。

4.2 實驗結(jié)果

4.2.1 算法有效性分析

兩臺AGV（AGV3和AGV17）的具體無沖突搬運路線如圖16所示。其中，除目標(biāo)托盤（②）外，其他托盤都設(shè)置為障礙物（黑色小柵格），③為揀選站，①為AGV，④為空托盤回收站。AGV3的任務(wù)是將（24，16）處的托盤②搬至（31，16）處的揀選站③，并在揀選任務(wù)結(jié)束后將托盤②搬至（31，20）處的空托盤回收站④。AGV17的任務(wù)是將（12，5）處的托盤②搬至（9，0）處的揀選站③，并在揀選任務(wù)結(jié)束后將托盤②搬至（1，0）處的空托盤回收站④。圖17為兩臺AGV的無沖突路徑時間窗?？梢园l(fā)現(xiàn)，利用所提算法規(guī)劃出的路徑不存在交叉節(jié)點和重合節(jié)點。因此，這兩臺AGV在倉庫內(nèi)同時執(zhí)行托盤搬運任務(wù)時不會發(fā)生路徑?jīng)_突。

結(jié)合表2的AGV-托盤匹配結(jié)果，將AGV執(zhí)行任務(wù)分成兩種情況：不考慮碰撞的情況和考慮碰撞的情況。每臺AGV行駛的距離如表6所示。具體來看，在考慮碰撞的情況下，AGV出于避讓或改向等因素，19臺AGV的總行駛距離為6 754 m，比不考慮碰撞情況下多行駛179 m。所有AGV從各自的初始位置出發(fā)，在任務(wù)結(jié)束后返回到各自的初始位置。

為評估所提IGA的有效性，將其與標(biāo)準(zhǔn)遺傳算法在不同訂單數(shù)量下的AGV行駛距離和求解時間進(jìn)行對比，結(jié)果如表7所示。其中，order表示訂單數(shù)，pallet表示目標(biāo)托盤數(shù)，distance表示AGV行駛距離（m），time表示算法求解耗時（s），gap1表示兩種算法在不同訂單數(shù)量下的AGV行駛距離差異度（%），gap2表示兩種算法在不同訂單數(shù)量下的求解耗時差異度（%）。

由表7可知，IGA求解出的AGV行駛距離較GA更短，并且隨著訂單規(guī)模的增大，這種差距也呈現(xiàn)出逐漸擴大的趨勢。其次，在算法求解耗時方面，當(dāng)訂單數(shù)量從50增加到300時，GA消耗的時間從12.1 s增加到90.5 s。GA和IGA的平均運行時間分別為52.05 s和31.05 s。這表明IGA使用局部搜索算子替換了傳統(tǒng)的變異算子，在一定程度上提高了求解效率。此外，兩種算法的gap值存在一定差異。其中，gap1相差約1.74%，gap2相差約37.07%，這兩項指標(biāo)可作為評估IGA性能的重要參考。

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

在32 m×22 m的倉庫中，選取AGV行駛距離和碰撞次數(shù)兩個指標(biāo)，利用本文算法探究不同目標(biāo)托盤規(guī)模下最優(yōu)AGV數(shù)量的調(diào)度問題，以更有效地利用倉庫內(nèi)有限的AGV資源。結(jié)果如表8和圖18、19所示。其中，P為目標(biāo)托盤數(shù)。

從表8中可以看出：a）在不同托盤數(shù)量下，隨著AGV數(shù)量的增加，AGV行駛距離整體呈現(xiàn)出遞減的趨勢。例如，在托盤數(shù)量為20個和40個的情況下，當(dāng)AGV數(shù)量為10臺時，AGV的行駛距離分別為703 m和1 485 m。但當(dāng)AGV數(shù)量增加至14臺時，AGV的行駛距離分別為688 m和1 370 m，各減少了15 m和115 m。這可能是因為當(dāng)AGV數(shù)量較少時，部分托盤與AGV間的距離太長，導(dǎo)致路徑距離的增加。b）當(dāng)托盤數(shù)量一致時，AGV數(shù)量越多，AGV發(fā)生碰撞的可能性就越高，碰撞次數(shù)也就越多?；诖?，綜合考慮AGV的行駛距離和碰撞次數(shù)，在32 m×22 m的倉庫中，合理的AGV數(shù)量應(yīng)為14～16臺。這種配置既能夠高效地完成托盤的搬運任務(wù)，對于提升倉庫資源的利用率和企業(yè)的經(jīng)濟(jì)效益也有一定的幫助。

5 結(jié)束語

在電商訂單需求激增的背景下，僅依靠人力揀選的“人到貨”倉庫費時又費力。相比之下，加入AGV的“貨到人”倉庫具有揀選效率高、人工成本低等優(yōu)勢，越來越被各行各業(yè)所認(rèn)可和接受。本文以“貨到人”倉庫中的三個子問題為研究對象，以AGV行駛距離最小化為目標(biāo)函數(shù)建立數(shù)學(xué)模型，并根據(jù)問題特點設(shè)計改進(jìn)的匈牙利算法、改進(jìn)的遺傳算法與三維網(wǎng)格沖突檢測方法。數(shù)值實驗結(jié)果表明，本文算法能夠調(diào)度19臺AGV在配備148個托盤、18個揀選站的倉庫中處理675個訂單任務(wù)。此外，通過對AGV數(shù)量的靈敏度分析發(fā)現(xiàn)，14～16臺AGV數(shù)量配置是最為適宜的。在未來研究中，會考慮AGV電量約束和商品補貨情況。除此之外，會考慮在靜態(tài)環(huán)境下引入其他優(yōu)化算法對深度學(xué)習(xí)、強化學(xué)習(xí)等前沿算法進(jìn)行改進(jìn)，以解決“貨到人”揀選系統(tǒng)中的諸項難題。

參考文獻(xiàn)：

［1］Boysen N，Koster R D，F(xiàn)yuler D. The forgotten sons： warehousing systems for brick-and-mortar retail chains ［J］. European Journal of Operational Research，2021，288（2）： 361-381.

［2］Yang Xiying，Hua Guowei，Hu Linyuan，et al. Joint optimization of order sequencing and rack scheduling in the robotic mobile fulfilment system ［J］. Computers & Operations Research，2021，135： 105467.

［3］趙金龍，蔣忠中，萬明重，等. 考慮配送截止時間的“貨到人”訂單揀選優(yōu)化問題研究 ［J/OL］. 中國管理科學(xué). （2022-11-08） ［2023-06-08］. https：//doi. org/10. 16381/j. cnki. issn1003-207x. 2022. 1049. （Zhao Jinlong，Jiang Zhongzhong，Wan Mingzhong，et al. Optimization of parts-to-picker order picking with due dates ［J/OL］. Chinese Journal of Management Science. （2022-11-08） ［2023-06-08］. https：//doi. org/10. 16381/j. cnki. issn1003-207x. 2022. 1049.）

［4］Le-Anh T，Koster M B M. A review of design and control of automated guided vehicle systems ［J］. European Journal of Operational Research，2006，171（1）： 1-23.

［5］付建林，張恒志，張劍，等. 自動導(dǎo)引車調(diào)度優(yōu)化研究綜述 ［J］. 系統(tǒng)仿真學(xué)報，2020，32（9）： 1664-1675. （Fu Jianlin，Zhang Hengzhi，Zhang Jian，et al. Review on AGV scheduling optimization ［J］. Journal of System Simulation，2020，32（9）： 1664-1675.）

［6］胡曉陽，姚錫凡，黃鵬，等. 改進(jìn)迭代局部搜索算法求解多AGV柔性作業(yè)車間調(diào)度問題 ［J］. 計算機集成制造系統(tǒng)，2022，28（7）： 2198-2212. （Hu Xiaoyang，Yao Xifan，Huang Peng，et al. Improved iterative local search algorithm for solving multi-AGV flexible Job-Shop scheduling problem ［J］. Computer Integrated Manufacturing System，2022，28（7）： 2198-2212.）

［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］Zhou Binghai，He Zhaoxu. A novel hybrid-load AGV for JIT-based sustainable material handling scheduling with time window in mixed-model assembly line ［J］. International Journal of Production Research，2023，61（3）： 796-817.

［9］Lin Yishuai，Xu Yulong，Zhu Jiawei，et al. MLATSO： a method for task scheduling optimization in multi-load AGVs-based systems ［J］. Robotics and Computer-Integrated Manufacturing，2023，79：102397.

［10］Maoudj A，Kouider A，Christensen A L. The capacitated multi-AGV scheduling problem with conflicting products： model and a decentra-lized multi-agent approach ［J］. Robotics and Computer-Integrated Manufacturing，2023，81： 102514.

［11］官祥錦，陳娟，張為民. 基于改進(jìn)A*算法的多AGV路徑規(guī)劃研究 ［J］. 航空制造技術(shù)，2023，66（5）： 76-85，90. （Guan Xiangjin，Chen Juan，Zhang Weimin. Research on multi-AGVs path planning based on A* algorithm ［J］. Aeronautical Manufacturing Technology，2023，66（5）： 76-85，90.）

［12］劉暢，張承瑞，孫玉璽. 改進(jìn)自適應(yīng)遺傳算法在多載AGV調(diào)度的應(yīng)用研究 ［J］. 小型微型計算機系統(tǒng)，2021，42（11）： 2241-2245. （Liu Chang，Zhang Chengrui，Sun Yuxi. Research on application of improved adaptive genetic algorithm in multi-load AGV sche-duling ［J］. Journal of Chinese Computer Systems，2021，42（11）： 2241-2245.）

［13］毛文平，李帥永，謝現(xiàn)樂，等. 基于自適應(yīng)機制改進(jìn)蟻群算法的移動機器人全局路徑規(guī)劃 ［J］. 控制與決策，2023，38（9）： 2520-2528. （Mao Wenpin，Li Shuaiyong，Xie Xianle，et al. Global path planning of mobile robot based on adaptive mechanism improved ant colony algorithm ［J］. Control and Decision，2023，38（9）： 2520-2528.）

［14］Miao Changwei，Chen Guangzhu，Yan Chengliang，et al. Path planning optimization of indoor mobile robot based on adaptive ant colony algorithm ［J］. Computers & Industrial Engineering，2021，156：107230.

［15］黃巖松，姚錫凡，景軒，等. 基于DQN的多起點多終點AGV路徑規(guī)劃 ［J/OL］. 計算機集成制造系統(tǒng).（2023-01-05） ［2023-06-08］. http：//kns. cnki. net/kcms/detail/11. 5946. tp. 20230104. 0959. 002. html. （Huang Yansong，Yao Xifan，Jing Xuan，et al. DQN-based AGV path planning for situations with multi-starts and multi-targets ［J/OL］. Computer Integrated Manufacturing System.（2023-01-05） ［2023-06-08］. http：//kns. cnki. net/kcms/detail/11. 5946. tp. 20230104. 0959. 002. html.）

［16］Hu Hongtao，Yang Xurui，Xiao Shichang，et al. Anti-conflict AGV path planning in automated container terminals based on multi-agent reinforcement learning ［J］. International Journal of Production Research，2023，61（1）： 65-80.

［17］賀雪梅，匡胤，楊志鵬，等. 基于深度強化學(xué)習(xí)的AGV智能導(dǎo)航系統(tǒng)設(shè)計 ［J］. 計算機應(yīng)用研究，2022，39（5）： 1501-1504，1509. （He Xuemei，Kuang Yin，Yang Zhipeng，et al. Design of AGV intelligent navigation system based on deep reinforcement learning ［J］. Application Research of Computers，2022，39（5）： 1501-1504，1509.）

［18］Zhang Zheng，Guo Qing，Chen Juan，et al. Collision-free route planning for multiple AGVs in an automated warehouse based on collision classification ［J］. IEEE Access，2018，6： 26022-26035.

［19］Xiao Haining，Wu Xing，Qin Dejin，et al. A collision and deadlock prevention method with traffic sequence optimization strategy for UGN-based AGVS ［J］. IEEE Access，2020，8： 209452-209470.

［20］武星，翟晶晶，肖海寧，等. 多載量AGV系統(tǒng)防死鎖路口通行順序優(yōu)化及避碰 ［J］. 計算機集成制造系統(tǒng)，2022，28（4）： 979-989. （Wu Xing，Zhai Jingjing，Xiao Haining，et al. Deadlock-free intersection-access sequence optimization and collision avoidance for multi-load AGV system ［J］. Computer Integrated Manufacturing System，2022，28（4）： 979-989.）

［21］李昆鵬，劉騰博，賀冰倩，等. “貨到人”揀選系統(tǒng)中AGV路徑規(guī)劃與調(diào)度研究 ［J］. 中國管理科學(xué)，2022，30（4）： 240-251. （Li Kunpeng，Liu Tengbo，He Bingqian，et al. A study on routing and scheduling of automated guided vehicle in“cargo-to picker”system ［J］. Chinese Journal of Management Science，2022，30（4）： 240-251.）

［22］俞佳慧，欒萌. 改進(jìn)蟻群算法在無人艇路徑規(guī)劃中的應(yīng)用 ［J］. 控制工程，2022，29（3）： 413-418. （Yu Jiahui，Luan Meng. Application of improved ant colony optimization algorithm in path planning of unmanned surface vessels ［J］. Control Engineering of China，2022，29（3）： 413-418.）

［23］Kline A G，Ahner D K，Lunday B J. Real-time heuristic algorithms for the static weapon target assignment problem ［J］. Journal of Heuristics，2019，25： 377-397.

［24］劉興宇，郭榮化，任成才，等. 基于身份匈牙利算法的無人機蜂群分布式目標(biāo)分配方法 ［J］. 兵工學(xué)報，2023，44（9）： 2824-2835. （Liu Xingyu，Guo Ronghua，Ren Chengcai，et al. Distributed target assignment method of UAV swarm based on identity Hungarian algorithm ［J］. Acta Armamentarii，2023，44（9）： 2824-2835.）

［25］張歆悅，靳鵬，胡笑旋，等. 時間依賴型多配送中心帶時間窗的開放式車輛路徑問題研究 ［J/OL］. 中國管理科學(xué). （2022-03-18） ［2023-06-08］. https：//doi. org/10. 16381/j. cnki. issn1003-207x. 2021. 0203. （Zhang Xinyue，Jin Peng，Hu Xiaoxuan，et al. Research on the time-dependent multi-depot open vehicle routing problem with time windows ［J/OL］. Chinese Journal of Management Science. （2022-03-18） ［2023-06-08］. https：//doi. org/10. 16381/j. cnki. issn1003-207x. 2021. 0203.）