仓库拣选路径问题研究综述

颜伟，孙佳旭，崔若梁

(山东科技大学能源与矿业工程学院，青岛 266590)

随着经济的发展、人民生活水平的提高，人们的需求逐渐朝个性化、独特化的方向发展，为了适应市场需求，制造业的生产模式也逐渐转变为多品种、小批量的生产方式，逐渐增多的货品种类给仓库的存储及运输带来了巨大的挑战。据统计，仓储活动占据企业经营总成本的20%以上[1]，根据中国物流与采购联合会公布的《2020年全国物流运行情况通报》显示，2020年中国保管费用(即仓储费用)5.1万亿元，同比增长7.4%，且近年来呈持续增长状态[2]。中国制造业中原材料及半成品的拣选作业时间占整个运输时间的30%～40%，拣选作业成本约占仓库运作总成本的55%。货物拣选是整个仓储作业系统中工作量最多、复杂度最高的环节。因此，提高拣选环节的作业效率是降低仓储成本的有效途径。

拣选作业是指根据订单明细对订单处理，确定拣选策略，准确、高效的拣选货物，并运送到相应位置的过程[3]。许多学者从货位分配、订单分批、车辆调度、路径选择等多个方面进行了研究。由于合理的规划货物拣选路径能够直接、有效地提高货物拣选效率，所以诸多学者针对货物拣选路径问题进行了研究。

为此，查阅近年来中外文献，从两个角度对仓库拣选路径问题进行阐述。一方面，从作业类型的角度出发，对仓库拣选路径问题综述，重点对单一作业进行分析；另一方面，从研究应用的方法技术的角度出发，对求解算法进行综述，重点对算法的分类及改善进行讨论。

1 库拣选路径问题综述

首先从作业类型的角度出发，将作业模式分为单一作业和复合作业两种，对近年来的文献数据进行统计，得出图1所示的统计图。可以看出，对单一作业的研究始终多于对复合作业的研究，并且对单一作业的研究近年来有了大幅度增长。总体来看，有关仓库拣选路径问题的研究文献呈增长趋势，这说明随着仓储问题的突出，如何有效提升仓库拣选效率的问题日益受到关注。

图1 仓库拣选路径问题文献统计图

1.1 单一作业问题研究

单一作业表示仅进行出库作业或进库作业，主要流程如图2所示。单一作业主要研究内容是通过路径选择[4-7]、拣选排序[8-11]及车辆分配[12-13]等举措，提高货物的拣选效率。按照研究的复杂程度由简到繁，可以把单一作业分为3种类型：单车辆拣选单货物作业、单车辆拣选多货物作业及多车辆拣选多货物作业。

图2 单一作业流程图

单车辆拣选单货物作业是最简单的作业方式，在近年的研究中，段建民等[4]将人工势场的思想引入强化学习算法中，对拣选单货物作业的路径进行了研究，以达到快速找到一条较优的拣选路径的目的；Lee等[5]提出了利用改进的Q-Learning算法和Dyna-Q算法，对单车辆拣选单货物的路径问题进行研究。单车辆拣选单货物作业的作业效率相对较低，随着经济的快速发展，逐渐不符合时代的发展要求，因此，针对该作业方式的研究也逐渐减少。

一些学者考虑更加符合实际的单车辆拣选多货物的作业方式，对货物拣选顺序及路径选择进行了研究。张新艳等[8]对鱼骨型仓库建立数学模型，以最小化总作业距离为目标，利用启发式算法对货物拣选顺序进行了优化。传统的启发式算法常面临收敛较慢、计算时间较长的问题，因此，王华东等[9]在对出货量较大的电商仓库研究时，采用了动态时间窗分拣策略，建立拣货模型，同时设计了拣货距离优化算法，极大地提高了多货物的分拣效率；陈磊等[11]针对生产车间线边库存区进行了研究，利用贪婪算法优化堆垛机的拣选顺序及行走路径。

针对多车辆拣选多货物的情况，学者们在订单批处理、车辆调度、车辆避碰及路径选择等方面进行了研究。王秀红等[14]将车辆调度与路径优化相结合，通过对比各车辆的最优路径实现车辆的调度；Aaya等[15]提出了一种新的订单批处理启发式算法，将订单进行批处理，实现订单拣选总距离最小化。但是上述文献缺乏对多货物拣选顺序以及车辆避碰的研究。Bao等[16]利用Dijkstra算法对车辆调度进行研究，同时设置了停留节点避免车辆碰撞的发生；孙兆臣等[17]提出了将Logistic函数融入A*算法对无人搬运车(automated guided vehicle，AVG)小车路径优化，引入频次负载因子降低车辆碰撞的可能，并提出了优先级避让的方法。

1.2 复合作业问题研究

复合作业是指即进行入库作业又进行出库作业，并且先执行入库作业，然后再进行出库作业，且每次仅运输一个单位的货物，主要流程如图3所示。复合作业的研究重点是如何将入库作业与出库作业合理搭配，提高货物运输效率。

图3 复合作业流程图

一些学者对仓库的复合作业进行了研究。王姗姗等[18]以穿梭车仓储系统为研究对象，提出将复合作业问题视为任务指派问题，对出入库作业合理搭配，从而达到总作业时间最小；杨玮等[19]针对双载式多层穿梭车仓储系统中的多个穿梭车，考虑实际调度路径及启停速度，对复合作业问题建立数学模型进行了研究；蔡安江等[20]对立体仓库的堆垛机建立基于复合作业的多车辆调度模型，同时提出了统筹分配的分配原则，避免车辆碰撞。

综上所述，有关仓库拣选路径问题的研究文献中，以单一作业问题的研究居多，研究内容由原来的对单车辆拣选单货物的研究，到对单车辆拣选多货物的研究，再到对多车辆拣选多货物进行研究，研究中考虑的因素逐渐增多，问题的复杂性越来越高，同时也更加符合实际情况。复合作业研究的主要是利用堆垛机或穿梭车进行出入库作业，比单一作业问题的研究更加复杂，虽然近年来对于复合作业的研究较少，但其作业效率比单一作业高是不可否认的，因此，对复合作业问题的研究也是十分有必要的。无论是对单一作业的研究还是有关复合作业的研究，多数文献是以最小化作业距离或者最小化作业时间为研究目标，提高作业效率固然重要，但把它作为唯一的研究目标是不可取的，所以今后的研究应朝着多元化研究目标的方向发展。

2 求解方法综述

路径规划问题的求解方法在近几十年里得到了飞速的发展。在研究初期，学者多利用图形学的方法求解，如可视图法[21]、自由空间法[22]等。随着技术的发展，虚拟力场法(virtual force field，VFF)[23]、模糊综合评价法(Fuzzy)[24]等传统算法逐渐被应用。随后，路径规划问题应用了更加先进的遗传算法(genetic algorithm，GA)[25-27]、蚁群算法(ant colony optimization，ACO)[28-29]等启发式算法求解。近年来，新兴的Q-Learning算法[30-32]、DQN(deepQnetwork)算法[33-34]等机器学习的方法也逐渐被应用。路径规划问题求解方法的发展历程如图4所示。

粒子群优化算法(particle swarm optimization，PSO)；深度Q网络算法(deep Q network，DQN)；向量场直方图算法(vector field histogram，VFH)

在近年来的研究中，仓库拣选路径问题通常被看作NP-hard问题，此类问题求解过程复杂，难以遍历所有解，多数中外学者将此类问题抽象为TSP(travelling salesman problem)问题，利用启发式算法进行求解。此外，随着人工智能领域的不断发展，机器学习的方法也逐渐被应用到拣选路径问题上来。对近年来仓库拣选路径问题的求解方法进行统计，如图5所示。可以看出，在解决仓库拣选路径问题的方法中，启发式算法的应用最为普遍，并且在近几年的研究中猛烈增长，机器学习作为新兴的方法，从2016年开始也逐渐被应用，并且在稳步发展之中。因此，将从应用最为普遍的启发式算法和机器学习方法对拣选路径问题的求解方法进行阐述。

图5 研究方法统计图

2.1 启发式算法在仓库拣选路径问题上的应用

近年来，仓库拣选路径问题中启发式算法的应用情况如图6所示，可以明显看出，常用的启发式算法有：遗传算法、蚁群算法等。常用的启发式算法的优缺点如表1所示。利用启发式算法求解有时会得到很坏的解或搜索效率极差，因此，将从改进算法和混合算法两个方面对启发式算法的优化进行论述。

图6 启发式算法应用情况

表1 常用算法优缺点

针对启发式算法存在的缺点，一些学者对算法进行了改进。

(1)改进遗传算法。田欣等[35]针对遗传算法收敛过慢问题，引入先验知识并提出参数自适应调整方式，加快算法的收敛速度，并针对易陷入局部最优的问题，将模拟退火算法的Metropolis准则引入，减少搬运机器人的行走时间。利用实例进行验证，结果证明改进后的算法在收敛速度、寻有能力上都有明显的提升。Han等[36]为解决遗传算法易陷入局部最优的缺点，提出采用三交换交叉启发式算子产生最优子代的方法改进遗传算法，通过对AGV行驶总路径和单AGV行驶路径两方面最小化的约束，求得最优路径；易琦等[37]将某个鱼骨型仓库作为研究对象，考虑车辆的载重和体积限制，将拣选路径问题看作多目标问题进行研究，在多种约束条件下建立多目标数学模型，采用多层编码遗传算法进行求解，同时利用MATLAB软件进行仿真模拟，从而证明了该算法的有效性；此外，还有学者通过多层嵌套[38-39]、适应性函数[40]等方法提高遗传算法的性能。

(2)改进蚁群算法。蚁群算法存在的最大的缺点是收敛速度过慢，对于此，李龙澍等[41]针对蚁群算法，提出利用方向指导信息优化初始信息素的分布情况，改善了算法前期收过慢的缺点，同时利用区域安全因素对转移概率进行改进，避免陷入局部最优，最后通过在多个不同复杂程度的模拟仓库中实验，从而验证了改进效果；贺智明等[42]提出了一种自适应动态搜索蚁群算法，将伪随机分布和自适应转移概率相结合，加快收敛过程，同时将信息素强度分段化，避免陷入局部最优；Santis等[43]提出将运筹学的方法Floyd-Warshall(FW)算法融入传统的蚁群算法中，增强识别最短路径的能力。

(3)改进其他算法。除了常用的算法之外，还有学者利用其他启发式算法进行相关研究。罗如学等[44]利用人工鱼群算法对路径规划进行了研究，为防止算法陷入局部最优，对算法中的视野范围进行了改进，同时修改拥挤度函数加快算法收敛速度；徐翔斌等[45]为解决多AGV拥堵问题，设计了系统优化策略，建立考虑避碰的数学模型，同时设计了时空模拟退火算法求解，通过实验验证了算法的有效性；Wu等[46]将图像处理与路径规划避碰技术相结合，将障碍物的顶点转化为网络节点，改进Dijkstra算法，利用代价函数寻找最优路径。

此外，一些学者将两个甚至多个算法结合，形成混合算法。针对遗传算法收敛速度较慢的问题，Maryam等[47]提出了将遗传算法与粒子群算法混合，充分发挥粒子群算法收敛速度快的优点，解决AGV车辆调度及路径选择的问题；闫军等[6]为了解决遗传算法易陷入局部最优的缺点，将模拟退火算法与遗传算法相结合，充分发挥模拟退火算法局部寻优的特性，改善遗传算法易于“早熟”的缺点，为了验证效果，采用实例分别利用遗传算法和遗传模拟算法求解计算，结果表明：遗传模拟算法的拣选路径更优，用时更短。针对粒子群算法易陷入局部最优的问题，杨玮等[48]提出了粒子群算法和模拟退火算法相结合，从而防止因过早收敛陷入局部最优；朱永强等[49]将A*算法与蚁群算法相结合，首先利用A*算法预先搜索出来一条最短路径作为较优解，然后利用蚁群算法继续寻找更优解；唐磊等[50]考虑旅行商问题(travelling salesman problem，TSP)货位仅能访问一次的缺陷，将贪心算法与遗传算法相结合，提高混合算法的寻优能力。

启发式算法作为解决路径问题最常用的求解方法，在解决仓库拣选路径问题上发挥着重大作用。但不可否认，启发式算法也存在诸多问题，虽然通过各式各样的改进，最大可能的减少了收敛过慢、局部最优等不足之处，但同样也增加了运算的复杂度，因此在解决复杂的路径问题时，容易出现运算时间过长、解的质量较差等问题。因此，启发式算法更适用于求解较为简单的路径问题。

2.2 机器学习在仓库拣选路径问题上的应用

机器学习是研究机器如何模仿人类的动作、语言等活动的一门学科。近年来，强化学习作为机器学习的重要分支逐渐发展起来，它被认为是未来人工智能的核心技术之一[51]。

正是具有较强的学习能力和可以与环境交互的特点，强化学习逐渐被应用到路径选择问题的研究中。与启发式算法相比，强化学习具有不同的优缺点，如表2所示。可以看出，强化学习在仓库拣选路径问题上的应用更加灵活，适应性更强。Q-Learning算法[52]作为强化学习中最为经典、成熟的算法之一，成为中外学者在研究路径选择问题上应用最多的算法。同样，Q-Learning算法也存在前期收敛过慢及易出现维数灾难的缺点，因此，诸多学者针对这两点不足进行大量的研究和优化。

表2 启发式算法和强化学习优缺点对比

强化学习是一种试错学习，在前期需要不断地尝试学习，积累经验，从而找到最优路径。所以，计算前期漫无目的的搜索导致前期收敛过慢。针对此问题，中外学者采取各种措施加快收敛速度。

(1)优化Q-Learning算法。近年来，学者们针对Q-Learning算法提出诸多优化方法。徐晓苏等[53]将引力势场应用到算法之中，在初始环境下，目标点附近设置引力场，并构造势场函数，同时增加了动作数量和动作步长，提高了路径的平滑度，加快了算法的收敛速度，以达到缩短了收敛时间的目的；毛国君等[54]提出对Q-Learning算法中的贪婪因子进行改进，将传统的算法中固定的贪婪因子动态化，当探索以失败告终时增大贪婪因子的值，当探索成功时减小贪婪因子的值，在加快收敛速度的同时保证算法的探索性；Zhao等[55]提出将神经网络与Q-Learning算法相结合，用于无人机路径规划与避碰，使得无人机能够获得先验知识，提高算法的学习效率。

(2)构造新算法。唐恒亮等[56]在Q-Learning算法的基础上结合时序差分[temporal-difference，TD(λ)]的回报思想，考虑采样后λ个状态，同时引入了启发因子和调和函数，并对ε-greedy(ε为贪婪因子)探索策略加入调和函数，设计出改进的多步Q学习算法[Q(λ)算法]，加快了寻找最优路径的速度。利用MATLAB设计仿真实验，验证新算法在搜寻速度、探寻次数、路径质量等方面更优。成怡等[57]为解决强化学习方法在未知环境下收敛速度慢的问题，提出了一种基于深度图像信息的深度强化学习算法，提高机器人的探索能力，加快了收敛速度。

在复杂环境中利用Q-Learning算法容易出现维数灾难的问题，这是因为在传统的Q-Learning算法中，会内置一个Q表用于储存产生的Q值信息，智能体每进行一个动作，环境就会变化一次，Q表也会更新一次。因此，当环境十分复杂，智能体的动作数量将十分庞大，导致Q无法储存全部的Q值，造成维数灾难。为了解决这一问题，一些学者也进行了相关研究。针对维数灾难的问题，现行最佳解决办法是与深度学习相结合。李辉等[58]将神经网络与Q-Learning算法相结合，提出改进的深度强化学习算法，利用值函数近似法代替了Q-learning算法中的动作值函数，利用神经网络代替Q表，从而避免了Q-learning算法在复杂环境中容易出现的维数灾难问题；董永峰等[33]提出了动态融合深度双Q算法，利用神经网络代替Q表，对DQN算法进行改进；Kim等[59]提出了不预先生成Q表，根据所需的学习速度调整探索策略，从而降低了维数灾难发生的可能性，同时加快了收敛。

与启发式算法相比，利用强化学习解决路径问题不需要建立复杂的数学模型，同时强化学习在未知环境下具有较强的探索能力。但传统的强化学习算法同样也面临着收敛过慢的问题，因此也仅适用于较为简单的路径问题。随着深度学习的发展，学者们创建了像DQN等深度强化学习的算法，更加适用于较为复杂的环境中。

2.3 其他方法在仓库拣选路径问题上的应用

除传统的启发式算法和新兴的机器学习外，还有一些学者利用射频识别技术(radio frequency identification，RFID)、偏移度、整数规划等知识对仓库拣选路径问题进行研究。李军等[60]利用RFID技术对出入库及拣选过程自动识别，从而对仓库状态实时更新，并提出了基于偏离度的路径优化方法，提高拣选效率；Miao等[61]针对存在较多障碍物的复杂环境，提出基于矩形映射分解的路径规划方法，促进全覆盖的路径规划；Zhen等[62]利用拓扑法创建仓库地图模型，提出Floyd算法搜索仓库中任意两个储位的最优路径。

综上所述，在针对仓库拣选路径问题的求解方法中，以启发式算法为主。此外，近年来仓库拣选路径问题的求解方法呈多元化方向发展，其中，强化学习的相关算法应用最为突出，在未来具有较大的发展空间。

3 结论与展望

根据中外学者对仓库拣选路径问题的研究，主要从作业类型和研究方法进行了论述。从仓库拣选路径问题的研究现状以及发展前景来看，未来的研究主要集中在以下三个方面。

(1)多样化的研究目标。目前对仓库拣选路径问题的研究中，多数文献以最小化作业时间或作业距离为目标。但一味地追求高效并非最佳策略，例如，危险品储存仓库要在最大化安全性的前提下高效运输，易碎品储存仓库要以最大化稳定性为目标，同时，一些仓库还会以最大化绿色度等为目标。因此，如何平衡多种目标之间的比重，以符合仓库的实际情况，成为在今后研究中需要解决的问题。

(2)多元化的研究方法。自对路径规划问题研究以来，图形学方法、启发式算法、强化学习等知识逐渐被应用。目前，启发式算法作为仓库拣选路径问题中应用最多的算法，但大部分启发式算法在收敛性、求解速度、求解质量等方面存在不足。另外，强化学习在路径规划领域的应用依然处于初始阶段，具有较强的自我学习能力和试错能力，因此在仓库拣选路径领域有很大的发展潜力，但也存在前期收敛过慢、易出现维数灾难等缺点。因此，为了求解更加复杂多样的研究目标，探寻更加优秀求解方法或混合算法是今后研究中的难点之一。

(3)更加符合实际的作业模式。在目前的研究中，多数文献仅研究了单车辆拣选货物或拣选单个货物的情况。而在实际仓库中，多个车辆同时拣选多个货物为常态。随着研究的深入，拣选任务及仓库环境将逐渐变得复杂多变，也更加符合实际情况。例如，考虑多车辆协同、订单的紧急程度等因素。因此，未来的研究将朝着复杂化、动态化发展。