多搬运任务下考虑碰撞避免的AGV路径规划

张艳菊 吴俊 程锦倩 陈泽荣

摘 要：为提升自动导引小车在“货到人”倉库中的运行效率，针对AGV-托盘任务分配、单AGV路径规划及多AGV碰撞避免三个子问题的研究，以最小化AGV行驶距离为目标构建数学模型。首先，根据AGV与托盘的双边匹配问题特点设计改进的匈牙利算法求解匹配结果。其次，提出一种二维编码机制的改进遗传算法（improved genetic algorithm，IGA），采用一种局部搜索算子代替原变异操作，在提高算法搜索性能的基础上使其成功应用于单AGV路径规划问题。然后，利用时空数据设计一种三维网格冲突检测方法，并根据商品SKU数量设定AGV的优先级以降低多AGV执行任务时的碰撞概率。最后，在32 m×22 m的仓库中针对不考虑碰撞与考虑碰撞两种情形进行AGV路径优化分析，给出合理的行驶距离和碰撞次数。IGA与标准遗传算法的对比结果显示，IGA能够在合理的时间内获得更高质量的解，行驶距离减少约1.74%，算法求解时间缩短约37.07%。此外，针对AGV数量灵敏度分析，在不同目标托盘规模下测试不同数量的AGV对行驶距离和碰撞次数的影响，发现14～16台AGV数量是最佳配置，验证了模型的可行性和算法的有效性。

关键词：智能仓库；AGV路径规划；碰撞避免；双边匹配；改进的遗传算法

中图分类号：TP242   文献标志码：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 引言

近年来，我国电子商务行业发展迅猛。数据显示，2022年的网上零售额达到13.79万亿元，与2012年的1.304万亿元相比，增长了近十倍。随着电商订单向小批量、多品种、高频次转变［1］，传统的“人到货”拣选系统弊端日益凸显，主要体现在拣选员仅花费在货架间行走的时间就占据了总作业时间的60%左右，拣货的准确性也受到拣货员工作强度等因素的影响而大打折扣。为提升拣选作业效率，亚马逊首次将具有智能仓储机器人的Kiva系统应用到仓库中。随后，众多电商巨头也纷纷采用“货到人”拣选系统，将自动导引小车（automated guided vehicle，AGV）投入到仓库中使用［2］。在该系统中，AGV将托盘搬至拣选站、存储区或空托盘回收站，拣选员只需待在拣选站执行商品拣选作业，不仅大大缩减了拣货员的工作量和人工成本，订单拣选效率也有了质的飞跃［3］。

当前，众多学者针对“货到人”拣选系统的研究主要集中在AGV调度、路径规划和碰撞避免［4］方面。关于AGV调度的研究，付建林等人［5］将AGV调度总结为静态调度、动态调度与AGV联合其他资源调度三种类型。胡晓阳等人［6］针对多AGV柔性作业车间调度问题，设计了一种融合贪心启发式规则的改进迭代局部搜索算法。Boccia等人［7］研究了一种具有电池约束的AGV调度（ASP-BC）问题。近年来，多负载AGV任务调度［8，9］吸引了部分学者的研究兴趣。Maoudj等人［10］针对AGV容量和冲突产品约束的多AGV调度问题，提出了一种离散方法。

关于AGV路径规划问题的研究，传统A*算法和标准智能优化算法存在收敛速度慢且易陷入局部最优的缺陷，改进的A*算法［11］、改进的自适应遗传算法［12］和改进的自适应蚁群算法［13，14］被相继提出。与此同时，一些学者也开始将强化学习应用到AGV路径规划中。黄岩松等人［15］提出一种结合Q-learning与深度学习的DQN算法，用于求解AGV多起点多终点的路径规划问题。Hu等人［16］针对AGV反向冲突和相同点占用冲突，设计了一种多智能体深度确定性梯度策略（MADDPG）方法。贺雪梅等人［17］基于深度强化学习设计了一种改进的DL-DDPG算法，实现了AGV在大规模未知复杂环境中的自主导航和避障。然而，利用强化学习解决AGV路径规划问题大多是在仿真实验环境下进行的，与真实仓库环境有一定差距。此外，强化学习过程在探索阶段具有随机性，即使在相同的条件下，每次训练的结果也有一定的差异。

关于AGV碰撞避免的研究，Zhang等人［18］提出四种AGV碰撞类型，并设计了三种解决方案。Xiao等人［19］针对AGV单向导引路径网络，提出了一种基于流量顺序优化策略的碰撞和死锁预防方法。武星等人［20］基于多载量AGV变长特性和交叉路口冲突，分别设计了变长度AGV路径空间冲突避免方法和带防死锁策略的交叉路口通行顺序优化方法。李昆鹏等人［21］针对可能发生冲突的路径交叉点，设计的碰撞避免及检测算法实现了AGV的主动避撞。

综合对AGV调度、路径规划和碰撞避免问题的研究成果进行回顾发现，现有文献多针对某一环节进行研究，对于多环节问题的研究较少。此外，关于AGV与托盘的一对多双边匹配关系还未得到充分研究。同时考虑托盘任务分配与AGV路径规划两个环节，更具实际应用价值。此外，在“货到人”仓库的高峰运行期间，往往会安排多台AGV同时执行搬运作业，一旦发生碰撞事件就会影响仓库的整体运作效率。因此，如何在AGV与托盘的最佳匹配上实现AGV总行驶距离最短且碰撞避免，是重点研究内容。

本文的贡献包括：a）为更好实现AGV与托盘的匹配，引入双边匹配模型，并利用最大贪心思想对匈牙利算法进行改进；b）考虑到不同托盘由不同AGV搬运的问题特点，设计一种二维编码方式的改进遗传算法（improved genetic algorithm，IGA）解决单AGV路径规划问题，并用局部搜索算子替换变异算子，增强了算法寻优能力并跳出局部最优；c）在AGV的时空数据的基础上，设计碰撞检测算法检测可能发生的路径冲突，并划分AGV的优先级作为避让规则。

1 问题描述及模型建立

1.1 问题描述

“货到人”仓库订单拣选流程如图1所示。首先，仓库接收包含商品SKU编号和数量等信息的o个订单，在确定储位后，按照既定的任务分配方式将仓库内的p个托盘分配给a台AGV搬运。其次，AGV接到任务指令后，按照既定的优化路线与交通规则先从初始位置移至目标托盘处，确认托盘信息无误后将托盘搬至相应的拣选站。然后，拣货员按照订单要求执行各项商品的拣选任务。最后，对于已完成拣选作业的托盘，AGV有两种选择：若托盘上的商品仍有剩余，则将其搬至原儲位；否则，将其搬至空托盘回收站。

为进一步理解“货到人”仓库的订单拣选流程，下面给出相关要素的形式化定义。

定义1 订单。一个订单定义为o={Io，Uo，No}。Io为订单编号，Uo表示订单所需商品的SKU编号，订单所需商品数量为正整数No。

定义2 托盘。一个托盘定义为p={Xp，Yp，Jp，Sp}。以Xp为横坐标、Yp为纵坐标表示托盘的位置，Jp为托盘编号，拖盘的状态Sp∈{0，1}。若Sp=1表示托盘正被AGV搬运，处于忙碌状态；若Sp=0表示托盘未被AGV搬运，处于空闲状态。

定义3 AGV。一个AGV定义为a={Xa，Ya，Sa}。Xa、Ya分别为AGV的横坐标与纵坐标，AGV的状态Sa∈{0，1}。若Sa=1表示AGV正执行托盘搬运工作，处于忙碌状态；若Sa=0表示AGV当前无搬运任务，处于空闲状态。

定义4 拣选站。一个拣选站定义为w={Iw，Xw，Yw，Sw}。Iw为拣选站编号，拣选站以Xw为横坐标、以Yw为纵坐标，拣选站的状态Sw∈{0，1}。若Sw=1表示拣选站正在执行商品拣选任务，处于忙碌状态；若Sw=0表示拣选站无拣选任务，处于空闲状态。

基于实际情况，考虑了如下假设：a）所有订单信息均已知，不存在订单拆分；b）每个托盘上有多个货位可供存放商品，商品也可以存放在多个托盘上；c）一台AGV一次只能搬运一个托盘；d）托盘上的商品SKU种类和数量能够满足工作期间所有订单的需求；e）出于安全考虑，每台AGV每秒匀速行驶1个单元格，且所有AGV在工作期间无须进行充电操作。

1.2 模型建立

基于上述问题描述、定义及相关假设，模型中涉及的集合、参数与决策变量如下：

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）参数：Tos为订单o对商品s的需求量；T为订单的总商品需求量；Qps为托盘p存放商品s的数量；Q为托盘存放的总商品数量；gpsw为托盘p上的商品s在拣选站w被拣选的数量；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）目标函数

e）约束条件

目标函数式（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-托盘匹配思路设计

2.1 仓库栅格化地图建立

栅格化是一种将对象的空间数据以二维矩阵的形式进行表示的方法。利用栅格化可以将仓库地图划分为大小均等的小栅格，每个小栅格对应仓库内的一种要素，如图2所示。

规定每个小栅格的长度为1，将中心点位置作为每个小栅格的位置［22］。假设第i个小栅格的坐标为（bi，ci），当mod（bi，ci）≠0，计算公式如下：

其中：mod为求余运算；ceil（j）为不小于j的最小整数；ε为每一行的小栅格数。当mod（bi，ci）=0时，小栅格位置的计算公式依据式（15）进行更新：

利用收集到的数据集，选取曼哈顿距离度量AGV与托盘间的远近程度，如表1所示。规定AGV编号为1～19，托盘编号为20～167。

2.2 AGV-托盘的一对多双边匹配

在“货到人”仓库中，出于成本考虑，AGV数量要远少于托盘的数量。因此，研究的AGV-托盘任务分配问题（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 改进的匈牙利算法

匈牙利算法（Hungarian algorithm，HA）是Kuhn在引用康尼格一个关于矩阵中0元素定理的基础上提出来的，被认为是解决分配指派问题的标准解法［23］。分配指派问题可细分为平衡指派问题和非平衡指派问题［24］，研究的APTAP问题属于非平衡指派问题。为降低求解难度，需要将APTAP问题转换为平衡指派问题。具体做法为：将数据集中的148个托盘进行拆解，前七组属于19×19的平衡指派，第八组为19×15的不平衡指派，需增设4个虚拟托盘（托盘与AGV间的曼哈顿距离设为M，一个极大的值）。传统匈牙利算法首先会对初始效率矩阵进行变换，直至各行各列均出现0元素，然后才进行试指派。需要注意的是，如果需要进行多次矩阵变换，计算时间就会增加。基于此，为保证AGV-托盘的匹配结果更优，利用一种最大贪心策略对匈牙利算法进行改进，即每次选择能够最大程度地减少目标函数值的要素，具体的计算步骤为：

a）依据对148个托盘的拆解结果，计算出每组中每台AGV与托盘间的曼哈顿距离，并将曼哈顿距离作为匹配值矩阵。其中，行代表AGV，列代表托盘。

b）依次计算出匹配值矩阵中各行和各列的最小距离值和次小距离值的差额。

c）从行或列差额中选出最大的元素，选择它所在行或列中的最小距离值，并划掉最小距离值所在的行和列。

d）将未划去的距离值再分别计算出各行、各列的最小距离值和次小距离值的差额。

e）重复步骤b）和c），直至所有托盘均已指派给AGV，输出最终指派结果。

利用改进的匈牙利算法求解托盘和AGV数量皆为4的平衡指派问题，如图4所示，最终的指派结果为（a3，p32）、（a7，p28）、（a10，p21）、（a12，p25）。虽与传统匈牙利算法计算出的结果一致，但改进的匈牙利算法大大提高了计算效率。

在AGV与托盘进行匹配前，通过验证订单数据和托盘数据发现，大部分托盘上存储的商品正好满足用户的实际需求，只有少量托盘上的商品有些许存量。例如，p160剩有2类商品SKU的数量分别为24和15；p161剩有2类商品SKU的数量分别为14和25；p162剩有2类商品SKU的数量分別为30和11；p163剩有1类商品SKU的数量为20；p164剩有2类商品SKU的数量分别为33和54；p165剩有2类商品SKU的数量分别为2和34；p166剩有2类商品SKU的数量分别为31和24；p167剩有2类商品SKU的数量分别为52和4。有趣的是，p160、p161、p162、p164、p165、p166和p167剩余的商品SKU种类与数量等于其初始的商品SKU种类与数量。因此，编号为p160、p161、p162、p164、p165、p166和p167的托盘无须进行搬运。利用改进的匈牙利算法求出的AGV与托盘匹配结果如表2所示。可以看出，a3、a4、a5、a7、a8、a9、a14、a15、a17、a18和a19搬运的托盘数量为7个，其他AGV搬运的托盘数量均为8个。匹配结果总体上比较均衡，仓库资源的利用较为合理。

3 AGV路径规划与避碰算法设计

3.1 AGV任务划分

一般来说，AGV在仓库内有三项任务：一是将目标托盘搬至拣选站；二是在拣选任务完成后将托盘从拣选站搬至原储位；三是在拣选任务完成后将托盘从拣选站搬至空托盘回收站。其中，任务二和任务三只选择其中一个执行，图5为一台AGV在仓库内执行三种任务的示例。

3.2 基于改进遗传算法的单AGV路径规划

求解AGV路径规划这类组合优化问题时，利用遗传算法（genetic algorithm，GA）虽能在合理时间内获取较优方案，但也存在收敛速度慢、易陷入局部最优等不足。“货到人”仓库中的AGV路径规划问题，就是为AGV规划出一条能安全且快速地从起点到达目标点的路径。在不考虑AGV碰撞的前提下，为实现所有AGV在仓库内的总行驶距离最短，设计改进的遗传算法（improved genetic algorithm，IGA），算法的流程如图6所示。

3.2.1 编码机制

结合不同托盘由不同AGV搬运的问题特点，本文设计一种二维编码方式。如图7所示，AGV1搬运托盘35、52、71和94，AGV2搬运托盘29、41、70和88。

3.2.2 适应度函数

适应度函数是遗传算法中评价个体优劣的有效工具。本文将目标函数值映射成适应度值，适应度值越大，代表个体越优。

3.2.3 种群初始化

初始种群大小反映种群中的个体数量。种群过大，算法计算复杂，导致运行效率低；而种群过小，则容易陷入局部最优。种群初始化的示例如图8所示，具体步骤如下：

a）将托盘集合P中的托盘进行随机排列，得到排列集合Pr，形成染色体的第一维编码；

b）针对Pr中的每一个托盘，依据表2的结果从AGV集合A中选择出相应的AGV进行搬运，形成染色体的第二维编码；

c）按照托盘与AGV间的曼哈顿距离进行降序排列，从而得到每台AGV的托盘搬运任务序列Bx；

d）重复步骤a）～c），直至达到预设的种群规模Yz，输出初始种群。

3.2.4 遗传操作

1）交叉算子。

种群初始化后的每条染色体代表一个搬运方案。交叉操作将种群中的两个个体按照一定的交叉概率交换部分染色体，从而得到新的个体。具体步骤为：首先，利用轮盘赌机制从种群中选择2条染色体作为父代染色体；其次，随机选择1个托盘作为交叉点位置；最后，根据交叉概率对2条父代染色体执行交叉操作，如图9所示。

2）局部搜索算子。

在完成交叉操作后，标准遗传算法通常会进行变异操作。然而，有时由于变异概率设置过低，可能会导致算法的搜索能力较差［25］。基于此，本文设计一种局部搜索算子（single-segment operator，SSO）以提升算法的搜索能力。具体步骤为：首先，随机从子代种群中挑选出1个子代染色体，并从染色体中选择一个片段；其次，从选择的染色体片段中选择一个托盘p（p∈P），将其插入到片段中除起始位置的一个可行位置。最后，将插入新位置产生的新解与初始解进行比较。若优于初始解，则用新解替换初始解，如图10所示。

3.3 多AGV碰撞检测与避免算法

3.3.1 多AGV网格化碰撞检测

在“货到人”仓库中，托盘占据了仓库的大部分面积，这使得AGV通行的通道宽度受到限制。当多台AGV同时在仓库内执行任务时，路径冲突是不可避免的。这会导致碰撞与拥堵情况的出现，进而影响正常的拣选工作。常见的四种AGV冲突类型如图11所示。其中，图11（a）为两台AGV在垂直方向同时经过十字小栅格引发的垂直冲突；图11（b）为两台AGV在水平方向同时朝着同一条直线行驶，最终会在某个小栅格引发相向冲突；图11（c）为两台AGV在同一窄通道内行驶，由于无法调整行驶方向进行避让引发的相向死锁；图11（d）为前往1处的AGV和前往2处的AGV在窄通道引发死锁导致双方都无法到达各自的目的地。

为提高AGV的冲突检测效率，利用AGV的时空数据设计一种基于三维网格的AGV冲突检测方法，如图12所示。三维网格是在二维网格的基础上考虑了时间因素。对于路径routei中的第a台AGV，可以根据其行驶过程中的三维坐标（ti， j，xi， j，yi， j），确定它所在的网格单元nete，f，g。

假定一个网格单元以自身为中心，能够检测自身及空间维度内的（32-1）+1=9个网格，并组成该网格单元的邻域，如式（16）所示。如果在该邻域内检测到其他AGV，表明该路径可能会发生冲突。针对这种情况，本文需要确定这种可能性冲突的类别，并采取相应的碰撞避免策略。如果在邻域内未检测到其他AGV，则表明该路径不会发生冲突。

3.3.2 基于优先级规划法的多AGV碰撞避免

为避免多台AGV发生碰撞，传统做法是让AGV在原地等待。尽管这种做法确保了AGV的安全性，但对订单的准时交付率影响较大。当AGV搬运托盘时，若托盘上的商品SKU数量为13以上（包括13）的用户订单，则设定AGV等级为1。若托盘上的商品SKU数量为13以下的用户订单，则设定AGV等级为2。具体的AGV等级划分如表3所示。规定避让原则为：当低优先级的AGV与高优先级的AGV在经过冲突检测后可能会发生碰撞时，低优先级的AGV要主动避让并调整路径。例如，如果发生类似图11（a）中的碰撞，低优先级的AGV需向下移动1个单元格。当AGV的优先级一致时，则以托盘上的具体商品SKU数量为判定依据。此外，为防止发生如图11（d）所示的死锁现象，高优先级的AGV在规划路径时，要避免占用未进行路径规划的低优先级AGV的连通节点。

4 数值实验与结果分析

4.1 数据描述与实验参数设置

本文实验数据来自公开数据集，仓库是一个大小为32 m×22 m的矩形区域，如图13所示。

仓库内共有18个拣选站。当AGV将托盘搬至拣选站时，拣选员开始执行商品拣选工作。仓库需处理675个用户订单，每个订单皆为一单一品，共计有185种商品SKU种类。仓库内托盘呈两列一组排列，共计有148个托盘。托盘上可存放1～5种不同的商品SKU。托盘间的白色小栅格为AGV的单行通道。仓库内停靠着19台可用AGV，它们分布在仓库内的不同位置。假定每台AGV每秒匀速行驶一个单元格（1 m），将四方向（上、下、左、右）搜索节点法作为AGV的行驶方向依据。此外，仓库内还有2个空托盘回收站、6个固定障碍物和6个保留节点。托盘与拣选站间的曼哈顿距离、拣选站与空托盘回收站间的曼哈顿距离如表4和5所示。

图14和15为数据集中关于用户订单商品SKU数量分布情况和托盘存储SKU种类分布情况。可以看出，商品SKU数量为［1，5］的用户订单有381个，占比超过了一半以上。商品SKU数量为［6，10］、［11，15］、［16，20］和［21，219］的用户订单分别有92、50、34和118个，占比分别为13.63%、7.41%、5.04%和17.48%。这表明用户订单多以小批量为主。存储的商品SKU种类为［1，3］的托盘有142个，占比高达95.95%。而存储的商品SKU种类为［4，5］的托盘只有6个，仅占4.05%。

实验通过Python 3.7 编程實现，在搭载Intel Core i7（2.80 GHz）CPU和16 GB RAM并运行Windows 11系统的笔记本电脑上进行求解计算。经过大量测试，最终确定算法的最佳参数设置为：种群大小为50，最大迭代次数为200次，交叉概率为0.9。

4.2 实验结果

4.2.1 算法有效性分析

两台AGV（AGV3和AGV17）的具体无冲突搬运路线如图16所示。其中，除目标托盘（②）外，其他托盘都设置为障碍物（黑色小栅格），③为拣选站，①为AGV，④为空托盘回收站。AGV3的任务是将（24，16）处的托盘②搬至（31，16）处的拣选站③，并在拣选任务结束后将托盘②搬至（31，20）处的空托盘回收站④。AGV17的任务是将（12，5）处的托盘②搬至（9，0）处的拣选站③，并在拣选任务结束后将托盘②搬至（1，0）处的空托盘回收站④。图17为两台AGV的无冲突路径时间窗。可以发现，利用所提算法规划出的路径不存在交叉节点和重合节点。因此，这两台AGV在仓库内同时执行托盘搬运任务时不会发生路径冲突。

结合表2的AGV-托盘匹配结果，将AGV执行任务分成两种情况：不考虑碰撞的情况和考虑碰撞的情况。每台AGV行驶的距离如表6所示。具体来看，在考虑碰撞的情况下，AGV出于避让或改向等因素，19台AGV的总行驶距离为6 754 m，比不考虑碰撞情况下多行驶179 m。所有AGV从各自的初始位置出发，在任务结束后返回到各自的初始位置。

为评估所提IGA的有效性，将其与标准遗传算法在不同订单数量下的AGV行驶距离和求解时间进行对比，结果如表7所示。其中，order表示订单数，pallet表示目标托盘数，distance表示AGV行驶距离（m），time表示算法求解耗时（s），gap1表示两种算法在不同订单数量下的AGV行驶距离差异度（%），gap2表示两种算法在不同订单数量下的求解耗时差异度（%）。

由表7可知，IGA求解出的AGV行驶距离较GA更短，并且随着订单规模的增大，这种差距也呈现出逐渐扩大的趋势。其次，在算法求解耗时方面，当订单数量从50增加到300时，GA消耗的时间从12.1 s增加到90.5 s。GA和IGA的平均运行时间分别为52.05 s和31.05 s。这表明IGA使用局部搜索算子替换了传统的变异算子，在一定程度上提高了求解效率。此外，两种算法的gap值存在一定差异。其中，gap1相差约1.74%，gap2相差约37.07%，这两项指标可作为评估IGA性能的重要参考。

4.2.2 AGV数量灵敏度分析

在32 m×22 m的仓库中，选取AGV行驶距离和碰撞次数两个指标，利用本文算法探究不同目标托盘规模下最优AGV数量的调度问题，以更有效地利用仓库内有限的AGV资源。结果如表8和图18、19所示。其中，P为目标托盘数。

从表8中可以看出：a）在不同托盘数量下，随着AGV数量的增加，AGV行驶距离整体呈现出递减的趋势。例如，在托盘数量为20个和40个的情况下，当AGV数量为10台时，AGV的行驶距离分别为703 m和1 485 m。但当AGV数量增加至14台时，AGV的行驶距离分别为688 m和1 370 m，各减少了15 m和115 m。这可能是因为当AGV数量较少时，部分托盘与AGV间的距离太长，导致路径距离的增加。b）当托盘数量一致时，AGV数量越多，AGV发生碰撞的可能性就越高，碰撞次数也就越多。基于此，综合考虑AGV的行驶距离和碰撞次数，在32 m×22 m的仓库中，合理的AGV数量应为14～16台。这种配置既能够高效地完成托盘的搬运任务，对于提升仓库资源的利用率和企业的经济效益也有一定的帮助。

5 结束语

在电商订单需求激增的背景下，仅依靠人力拣选的“人到货”仓库费时又费力。相比之下，加入AGV的“货到人”仓库具有拣选效率高、人工成本低等优势，越来越被各行各业所认可和接受。本文以“货到人”仓库中的三个子问题为研究对象，以AGV行驶距离最小化为目标函数建立数学模型，并根据问题特点设计改进的匈牙利算法、改进的遗传算法与三维网格冲突检测方法。数值实验结果表明，本文算法能够调度19台AGV在配备148个托盘、18个拣选站的仓库中处理675个订单任务。此外，通过对AGV数量的灵敏度分析发现，14～16台AGV数量配置是最为适宜的。在未来研究中，会考虑AGV电量约束和商品补货情况。除此之外，会考虑在静态环境下引入其他优化算法对深度学习、强化学习等前沿算法进行改进，以解决“货到人”拣选系统中的诸项难题。

参考文献：

［1］Boysen N，Koster R D，Fyuler 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］赵金龙，蒋忠中，万明重，等. 考虑配送截止时间的“货到人”订单拣选优化问题研究 ［J/OL］. 中国管理科学. （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］付建林，張恒志，张剑，等. 自动导引车调度优化研究综述 ［J］. 系统仿真学报，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］胡晓阳，姚锡凡，黄鹏，等. 改进迭代局部搜索算法求解多AGV柔性作业车间调度问题 ［J］. 计算机集成制造系统，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］官祥锦，陈娟，张为民. 基于改进A*算法的多AGV路径规划研究 ［J］. 航空制造技术，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］刘畅，张承瑞，孙玉玺. 改进自适应遗传算法在多载AGV调度的应用研究 ［J］. 小型微型计算机系统，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］毛文平，李帥永，谢现乐，等. 基于自适应机制改进蚁群算法的移动机器人全局路径规划 ［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路径规划 ［J/OL］. 计算机集成制造系统.（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］贺雪梅，匡胤，杨志鹏，等. 基于深度强化学习的AGV智能导航系统设计 ［J］. 计算机应用研究，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系统防死锁路口通行顺序优化及避碰 ［J］. 计算机集成制造系统，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］李昆鹏，刘腾博，贺冰倩，等. “货到人”拣选系统中AGV路径规划与调度研究 ［J］. 中国管理科学，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］. 控制工程，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］刘兴宇，郭荣化，任成才，等. 基于身份匈牙利算法的无人机蜂群分布式目标分配方法 ［J］. 兵工学报，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］. 中国管理科学. （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.）