基于通用变邻域搜索的多AGV分拣调度优化

郭超 陈香玲 郭鹏 王强

摘 要：為了解决物流仓储分拣中心多台AGV处理大量包裹调度优化困难的问题，在考虑分拣作业时间窗和充电需求的基础上，研究了大规模AGV调度问题。以最小化分拣作业周期为目标，提出了一种通用变邻域搜索（general variable neighborhood search，GVNS）算法，为各台AGV指定转运任务和作业排序，采用遍历插入启发式策略生成满足时间窗约束的初始解，设计了10种邻域算子对初始解迭代寻优，并对比不同规模算例的算法性能，分析AGV充电速率和数量配置对分拣效率的影响。结果表明，GVNS算法具有计算时间和求解性能方面的优势，能在较短时间内求得近似最优解，平均计算时间仅为532.78 s，明显优于混合整数规划模型和约束规划模型;当包裹数为100时，最合适的AGV配置为14辆。因此，GVNS可以有效解决分拣中心考虑充电需求和硬时间窗的大规模多AGV调度问题，提高物流分拣效率，帮助企业找到科学、合理的AGV配置方案。

关键词：物流系统管理;分拣作业;自动导引小车;调度;充电需求;变邻域搜索

中图分类号：F252.1;TP301   文献标识码：A

doi：10.7535/hbkd.2021yx05011

收稿日期：2021-08-20;修回日期：2021-09-19;责任编辑：张士莹

基金项目：国家重点研发计划项目（2020YFB1712200）;宜宾职业技术学院科研平台建设计划资助项目（YBZY21KYPT-03）;轨道交通运维技术与装备四川省重点实验室开放课题（2020YW004）

第一作者简介：郭 超（1984—），男，四川宜宾人，讲师，主要从事智能制造方面的研究。

通讯作者：郭 鹏副教授。E-mail：pengguo318@swjtu.edu.cn

General variable neighborhood search for the multi-AGV scheduling problem with sorting operations

GUO Chao1，2，CHEN Xiangling3，GUO Peng1，3，WANG Qiang2

（1.Technology and Equipment of Rail Transit Operation and Maintenance Key Laboratory of Sichuan Province，Chengdu，Sichuan 610031，China;2.School of Intelligent Manufacturing，Yibin Vocational and Technical College，Yibin，Sichuan 644003，China;3.School of Mechanical Engineering，Southwest Jiaotong University，Chengdu，Sichuan 610031，China）

Abstract：To solve the intractable multiple automatic guided vehicles （AGVs） scheduling problem encountered in the sorting processes of the logistics sorting centers，a large-scale AGV scheduling problem was studied on the basis of considering the sorting time windows and charging requirements.A general variable neighborhood search （GVNS） algorithm was proposed to minimize the makespan of the sorting operations，in which the assignment of transferring packages to AGVs and the sequence of sorting tasks for each AGV were determined.The traversal insertion heuristic was developed to generate the initial solution of the developed algorithm to ensure the constraint of time windows.Ten neighborhood operators were designed to optimize the initial solution for the iteration of the algorithm.Different sized test instances were compared，and the impacts of AGV charging rate and quantity configuration on sorting efficiency were analyzed.The results show that the GVNS algorithm is superior in computing time and solution performance.It can obtain the approximate optimal solution in a short time.The average computing time of GVNS is only 532.78 s，which is obviously better than the mixed integer and constraint programming models;when the number of packages is 100，the most suitable number of AGVs is 14.Therefore，GVNS can effectively solve the large-scale and multi-AGV scheduling problem with charging demand and hard time window，improve the efficiency of logistics sorting，and help enterprises find the scientific and reasonable AGV configuration scheme.

Keywords：

logistics system management;sorting operation;automatic guided vehicle;scheduling;charging demand;vari-able neighborhood search

随着电子商务产业的不断发展壮大，中国快递包裹经历了连续十多年的爆炸式增长，从2010年的不足24亿件迅速攀升到2020年的833.6亿件，目前快递总量已超过美国、日本及欧洲发达国家的快递量总和，成为名副其实的“快递大国”。逐年增长的快递业务量对高效配送提出了更高要求。快递包裹从卖家手中到达买家手中需要经历一系列步骤，包括订单确认，快递揽件、转运、分拣、运输，再分拣、转运与送达等。在完整的快递配送流程中，至少要经历2次分拣，且每次分拣均会耗费大量时间。因此，提高物流中心的分拣效率，可以在一定程度上缩短快递整体配送时间，让买家在更短时间内收到包裹。为了应对暴增的业务量，原有的人工分拣或传送带式仓储物流相继被自动导引车（automatic guided vehicle，AGV）或自主移动机器人（autonomous mobile robot，AMR）拣选作业系统替代。各大快递公司（包括菜鸟、申通、顺丰等）相继引入了类似于亚马逊Kiva机器人（见图1）的作业系统[1-2]。采用上述分拣系统能够实现无人化、自动化与智能化，但面临的管理决策也更加复杂。因此，对多台机器人开展调度优化成为物流机器人领域研究的热点问题之一。早期AGV在单个项目或者场景中应用尚可，但其依赖于磁条等固定导航方式，只能在作业区域内按照固定的路径循环运行，应用相对简单，且不需要系统具备较高的调度能力。类Kiva机器人的出现，使得对多AMR集群调度的需求越来越大[3]。多AMR调度除了要为每个AMR合理分配任务从而达到预期目标，还要考虑到任务时间窗、优先级、充电需求等各种限制因素。在仓储物流中，AMR或者AGV调度主要依赖于最短队列或最短走行距离等启发式规则进行决策[4]。为了实现对AGV集群调度的优化，人们提出了多种元启发式算法，包括粒子群-遗传混合算法[5]、差分进化算法[6]、Memetic算法[7]、大规模邻域搜索[8]、自适应大规模邻域搜索[9]等。但这些研究对于实际场景中的栅格地图和充电约束等考虑尚不充分，缺乏有效的求解手段。为了分析AGV调度规则，仿真手段也被用于调度分析和对比中[10]。

变邻域搜索（variable neighborhood search，VNS）算法具有良好的通用性和寻优能力，已在调度、设施布局、设施选址、车辆路径等问题中取得了良好效果[11-17]。然而目前还鲜有文献报道使用VNS解决考虑充电需求和时间窗的多AGV调度问题。为实现对大规模问题实例的求解，笔者基于文献[18]的研究工作，在多AGV调度优化建模基础上提出采用通用变邻域搜索（general variable neighborhood search，GVNS）算法，针对多AGV作业场景下的分拣调度优化问题，设计了一种启发式规则，为通用变邻域搜索算法提供初始解，采用10个不同的邻域结构用于局部搜索和扰动阶段，分析AGV充电速率和数量配置对优化目标的影响，通过算例测试，验证了算法的求解性能。

1 物流分拣流程

围绕分拣作业流程，物流分拣中心分为入库区、出库区和分拣区3部分。分拣区由分拣台、投放口和设备充电/停放区组成，如图2所示，其中a和b分别代表栅格的行数和列数。在分拣区内，来自不同地区的包裹入库后随着传送带到达各个分拣台，AGV接收到搬运任务后前往包裹所在分拣台。AGV到达分拣台后需要根据包裹上的运单信息，将包裹运送至相应的投放口，每个投放口代表不同的城市或地区。在投放口的下方是漏斗和传送带，它们会收集包裹并将其运送至出库区，在出库区会有车辆进行下一阶段的配送。

基于以上应用场景，给定任务集合J={1，2，…，n}，其中J为包含所有任务的集合，n为任务总数。给定AGV集合K={1，2，…，m}，其中K为所有AGV集合，m为其数量（m=|K|）。AGV不工作时均停靠在充电区，当接收到分拣作业指令时，其从充电区出发执行分拣任务。每个包裹i（i∈J）都有相应的最早到达时间ei、搬运时间ti和最晚完工时间di，最晚完工时间用于保证包裹分拣出库后的准时派送。

AGV在运送包裹时需经历3个阶段：1）从当前位置前往包裹所在的分拣台;2）若AGV在ei之前到达分拣台，则需等待，否则直接装载包裹;3）AGV运送包裹到对应的投放口。每运送完一个包裹，AGV会检查当前电量是否低于安全电量g。当电量充足时，AGV直接前往下一包裹所在分拣台;当电量不足时，其需前往充电区充电，充电完成后再去到下一个包裹所在分拣台。如此反复，直至所有运输任务执行完毕，最后返回充电区。具体描述与数学规划模型详见文献[18]。

2 GVNS算法的主要步骤及邻域结构

变邻域搜索算法在应用过程中衍生处理诸多拓展算法，包括变邻域深度搜索算法、变邻域分解搜索算法和偏态变邻域搜索算法等[19-20]。本文所提出的通用变邻域搜索（GVNS）是在局部搜索阶段采用VND的变邻域搜索算法，相比其他的VNS拓展算法拥有非常优秀的求解性能，目前已被用于求解单分配集线器定位[21]、带时间窗约束的多目标车辆路径与装载[22]和取送货一体的旅行商[23]等复杂组合优化问题。GVNS算法的基本思想是在搜索过程中通过变换不同的操作算子尽可能多地探索解空间，寻找局部最优解，然后通过扰动跳出局部最优，经过多次迭代，不断更新最优解直至达到终止条件。

2.1 编码方式

采用由整數构成的编码列表来表示每辆AGV待执行的任务序列，其中每个整数表示AGV需要搬运的包裹编号。每个AGV必须从充电区出发，在执行完所有的任务后返回充电区。

因此每个AGV的编码列表首尾位置都设置为0，分别表示虚拟开始任务和虚拟结束任务。所有AGV的编码列表即为问题的一个解。如图3所示，以10个包裹3辆AGV为例，其中包裹[1，3，10]由第1辆AGV负责搬运，包裹[5，2，8，4]由第2辆AGV搬运，同理，包裹[6，9，7]由第3辆AGV负责搬运，共计3条路径列表构成了一个完整的解。

由图3可以看出，在编码阶段并没有将充电任务加入到任务列表中，这是为了便于后续的邻域操作。对于是否需要执行充电任务，会在遍历AGV的每条路径时加以判断，进而获得目标函数值。

2.2 初始解

初始解的质量会影响整个算法的求解效率。为了找到较好的初始可行解，设计了一种启发式方法，其伪代码算法如表1所示。

首先生成m个仅包含虚拟开始任务和虚拟结束任务的空路径[0，0];然后遍历所有任务，计算每个任务在每条路径的每个位置的适应度值，同时记录下每个任务的适应度值和对应的插入位置;找到拥有最小适应度值的任务后，将该任务插入此位置，然后从任务列表中删除该任务;遍历完所有的任务并全部插入到路径列表后，输出初始解。表1中步骤8的适应度值计算公式为

f=α×Cmax+（1-α）（s′i-si），i∈N。

式中：Cmax为分拣完成时间;点i为路径中插入点后面的点;si为点i在插入前的路径中的开始时间;s0为点i在插入后路径中的开始时间。对权重α进行取值，使初始可行解尽可能地实现最小化分拣完成时间和时间窗更紧凑，得到不错的初始解。

2.3 邻域结构

GVNS算法涉及10个不同的操作算子。为了便于后续操作，为每个操作算子进行标号处理。需要特别说明的是，每种操作算子在选择任务节点时都不会选择位于路径首尾位置的虚拟开始任务点和虚拟结束任务点。常用的操作算子包括Cross，2-opt，Relocate，Exchang和ICross，各自操作方式如下。

1）Cross算子（N1） 选择任意2条路径，分别从2条路径任选1个点作为路径的断点，然后交换2条路径的后半段，形成2条新的路径，操作示例见图4。

2）2-opt算子（N2） 选择任意1条路径，在该路径中选择2个不同的点作为断点，使得路径形成3个片段，然后对中间片段进行逆序操作，形成1条新的路径，操作示例见图5。

3）Relocate算子（N3） 重新定位结构，是指任意选择2条路径，从1条路径中任意选择1个点插入到另1条路径的任意位置，形成2条新的路径，操作示例见图6。

4）Exchange算子（N4） 选择任意2条路径，分别从2条路径中选择1个点进行交换，操作示例见图7。

5）ICross算子（N5） 选择任意2条路径，分别取2条路径任意长度的中间片段，将2条路径的中间片段进行逆序操作然后交换，形成2条新的路径，操作示例见图8。

此外，为了扩大邻域解的解空间，还使用了Or-opt算子、GENI算子、λ-Interchange算子3种扩展邻域结构[24]，通过多次迭代保证对最优解的搜索能力。

Or-opt算子（N6， N7，N8）：从任意1条路径中随机选择1个点i，然后选择1个距离i点给定长度x的点j（j=i+x），再从路径中随机选择1个点k。路径被i，j，k 3个点截成4个片段，如果k<i或k>j，则交换路径的2个中间片段的位置，从而形成1条新路径。通过为该算子设置3个不同长度参数x（x=1，2，3），形成了3个不同的邻域结构。当x=2且k>j时，操作过程如图9所示。

GENI算子（N9）：选择任意2条路径，从第1条路径中选择1个点i插入第2条路径中的任一位置，然后从第2条路径中选择1个点k插入i点后面，形成2條新路径，操作示例见图10。

λ-Interchange算子（N10）：选择任意2条路径，分别从2条路径中选择任意一点随机长度为λ1和λ2的片段进行交换，形成2条新的路径。若路径1的长度为l1，选定点的位置为a，路径2的长度为l2，选定点的位置为b，则λ1和λ2分别从整数均匀分布[1，l1-a-1]和[1，l2-b-1]中随机选择。当λ1=λ2=2时，操作示例如图11所示。

2.4 局部搜索阶段

令Nl（l=1，2，…，lmax）为一组用于局部搜索阶段的邻域结构集合，令Nl（s）为当前解s在第l个邻域结构中的解集合。采用上述10个邻域结构（lmax=10）构成VND获得邻域解集。基于文献[19]的算法机制，局部搜索阶段从邻域N1开始，到邻域N10结束。将当前解s传入一个邻域结构后会产生一组邻域解Nl（s），其中必然存在一个局部最优解s′。若该局部最优解s′优于当前解s，则将s替换为s′，并且返回到第一个邻域结构进行搜索;否则，进入下一个邻域结构进行搜索，直到搜索完最后一个邻域，若仍未能找到更优解，则结束局部搜索阶段。VND算法流程伪代码如表2所示。

2.5 扰动阶段

局部搜索阶段容易使算法陷入局部最优。当多次迭代仍然无法对解进行改善时，通常可对当前解进行适当的扰动操作，生成下一次进入局部搜索阶段的起始解。若当前解在经过连续η次迭代后仍未能找到更优，则说明算法陷入了局部最优，没有必要继续进行局部搜索，需要对当前解进行扰动操作。令Nk（k=1，2，…，kmax）为一组用于扰动阶段的邻域结构集合，令Nk（s）为当前解s在第k个邻域结构中的解集合，该阶段同样是上述的10个邻域结构（kmax=10）。为了使解空间得到有效扩展，选择随机生成10个邻域结构的搜索顺序。每次扰动操作时，只需选择一个操作算子，与局部搜索阶段不同的是，操作算子随机选择路径和节点进行操作，而不是遍历，当找到一个可行解时即可结束扰动阶段。

2.6 算法框架

GVNS算法流程如表3所示，GVNS在定义了邻域结构Nk和Nl后（第1行），利用启发式规则生成初始解s0，并将其传递给当前解s（第2行），然后进行初始化操作（第3行）。随后开始迭代搜索，在扰动阶段找到一个可行解s′后（第5行），带着该可行解s′进入局部搜索阶段（第6行）。在局部搜索阶段，通过目标函数值的大小评价解的质量。目标函数值越小，表示解的质量越好。如果找到的局部最优解s″优于可行解s′，则将s′替换为s″。结束局部搜索阶段后，需要判断找到的局部最优解s′是否优于当前解s （第7行）。如果是，则将s替换为s′，并且依然使用扰动阶段定义的第一个邻域结构进行扰动操作（第8行），否则进一步判断是否继续进行迭代搜索。如果达到算法终止条件，则返回当前最优解s （第10—17行）。算法的终止条件为当前解连续Inip次迭代仍未能得到改善（第11行），若满足该条件，则立即终止算法并输出当前最优解。在GVNS算法中，设置Inip=10。需要特别说明的是，达到最大未优化迭代次数Inip是指连续扰动了Inip次，且每次扰动后都会经历局部搜索阶段，但当前解都未得到改善。

3 算例分析

通过一系列的算例数值实验验证所提出的GVNS算法的性能，算法由Python语言实现，在配置为AMD Ryzen 5-4600U with Radeon Graphics CPU @ 2.10 GHz，16.0 GB的个人电脑上运行。为了对比所提出GVNS算法的性能，文献[11]中提到的混合整数规划（mixed integer programming，MIP）模型和约束规划（constraint programming，CP）模型也被用于求解算例。在算例分析中，MIP采用Gurobi求解器求解，CP采用CPLEX Optimization Studio 12.10.0中的CP Optimizer求解。引入相对百分比偏差（relative percentage difference，RPD）分析算法的性能，RPD计算公式如下：

RPD=Ccurrent-CbestCbest×100%。（2）

式中：Ccurrent表示当前方法求得的目标值，Cbest为该算例在所有方法中取得的最优目标值。RPD值越小，表示该方法求解效果越好。

3.1 算例设计

算例生成采用文献[11]所述方法，分为小规模算例和大规模算例。针对小规模算例，设置包裹数n={8，10，14};针对大规模算例，设置包裹数n={50，100，200}。表4为算例中包裹数与AGV数的关系，可以得到18组不同规模的算例，每组随机生成4个算例，共计72个。

3.2 参数调试

参数设置会直接影响算法效果，不同权重α取值的Rinit均值图见图12。在本文所提的GVNS算法中，权重α作为唯一变量需要进行参数调试。在此，考虑不同的取值水平：0，0.1，0.2，0.3，0.4，0.5，0.6，0.7，0.8，0.9，1。选择包裹数n=50，AGV数m取值{5，6，7，8，9，10，11，12，13，14，15}的11个大规模算例来调试权重α的取值。

权重α只会影响初始解，因此需观察初始解目标函数值的大小。为了简化数据量，取所有算例在某一α值下初始解目标函数值的平均值Rinit，Rinit值越小，表示初始解的质量越好。由图12可知，每个α的取值点均对应参数测试算例集的平均值;从图12中还可以看出，当α为0.9时，Rinit值最小，因此设置权重α值为0.9。

3.3 计算结果与分析

将Gurobi和CP Optimizer的最大求解时间设置为1 800 s，若在给定时间内未找到最优解，则停止计算并返回当前的最好可行解。GVNS算法的求解性能用RPD值进行评价，此外，计算时间也作为求解性能评价指标。为了消除启发式算法可能存在的随机性影响，GVNS算法对每个算例计算10次，然后取平均计算时间和平均RPD值。表5给出了小规模算例的计算结果，大规模算例的计算结果如表6所示，其中“J”表示包裹数量，“V”表示AGV数量，“No.”表示该组算例序号，“MIN”表示该算例求得的最小目标函数值，“—”表示未在规定时间内找到可行解。每个方法均列出了计算时间和RPD，对比小规模算例和大规模算例分别在MIP模型、CP模型和GVNS算法中的计算结果。

从表5可以看出，与启发式方法相比，精确算法仍存在明显的差距。MIP模型有8个算例未能找到最优解，CP模型有9个算例未能找到最优解，而GVNS仅有1个算例未能找到最优解。从计算时间上来看，GVNS平均计算时间仅为0.42 s，远小于MIP和CP的计算时间。从求解质量上来看，GVNS的平均RPD值仅为0.09，也远小于另外2个模型的RPD值。由小规模算例计算结果可知，GVNS在计算时間和求解质量上都具有明显优势。

由表6可知，由于本问题的NP-hard特性，当包裹数为50时，MIP模型和CP模型还有部分算例能找到最优解或近似解，但当包裹数达到100及以上时，MIP模型和CP模型在所有算例中均无法在1 800 s内找到可行解，可见优化求解器无法求解大规模问题。而GVNS在所有大规模算例中均能在较短时间内求得近似最优解，平均计算时间仅为532.78 s，明显优于MIP模型和CP模型。由此可知，GVNS可以有效解决分拣中心考虑充电需求和硬时间窗的大规模多AGV调度问题。

3.4 AGV配置分析

不同配置的AGV会有不同的充电速率，配置越高充电率越大，即充电速度越快。不同的AGV充电率会导致AGV充电所需时间不同，从而影响分拣完成时间。此外，在一定分拣作业量下，不同AGV数量配置同样会影响分拣完成时间。对于企业而言，AGV的配置越高，采购成本就越高，但如果AGV的配置过低，又会导致分拣任务无法按时完成或分拣效率过低。因此，找到合适的AGV充电率配置和数量配置对于物流中心来说是非常有必要的。本文以包裹数n=100，AGV数m=10的算例来分析不同的AGV充电率对分拣完成时间的影响。以包裹数n=100，AGV数m={10，12，14，16，18，20}的算例来分析AGV数量对分拣完成时间的影响。由于算例规模较大，因此使用GVNS算法进行求解。为了简化数据量，同时消除算法随机性带来的影响，每个算例都要计算10次，然后取分拣完成时间的平均值。

图13为不同的AGV充电率与分拣完成时间关系折线图。从图13可以看出，当充电率大于1.6时，分拣完成时间不再明显减少，因此当包裹数为100，AGV数为10时，最合适的AGV充电率为1.6。图14是不同AGV数量配置与分拣完成时间关系折线图。由图14可知，当AGV数量大于22时，分拣完成时间不再发生变化。因此，当包裹数为100时，最多只需配置22辆AGV。当AGV数量大于14时，分拣完成时间不再明显减少，因此，当包裹数为100时，最合适的AGV数量配置为14辆。

4 结 语

1）为了提高物流分拣中心的作业效率，在考虑充电需求和时间窗约束的基础上，研究了大规模作业场景下的多AGV调度优化问题。

2）基于所研究问题的复杂性，提出利用GVNS实现对大规模算例的有效求解。在GVNS算法的基本框架下，结合问题特性，设计了满足时间窗约束的启发式方法生成初始解，并为算法设计了10个邻域操作算子，生成局部最优解。

3）使用不同规模的算例进行数值实验，并与混合整数规划模型和约束规划模型进行对比，计算结果验证了所提出的GVNS算法求解大规模问题的可行性和高效性。考虑到不同的AGV充电率和数量配置会影响多AGV的调度方案，采用控制变量法分别分析了不同的AGV充电率和数量配置下的分拣完成时间，并给出了合理的配置方案。

本文仅考虑分拣中心有一个充电区的情况，在实际应用场景中，当分拣场地很大且AGV数量很多时，AGV需要频繁地返回充电区充电，合理的充电区布局方案是一个值得深入研究的问题。实际AGV分拣过程中还有很多问题需要考虑，例如AGV充电和放电的规律、AGV速度变化和AGV故障停机等。目前有关此方面的研究数据尚未见公开报道，笔者也在尝试通过实验获得真实的运行数据，以使所讨论的算法更具实际应用价值。此外，在未来的研究中，还可通过仿真分析探讨更多的不确定情况，譬如单个AGV的意外故障或包裹的紧急分拣作业等;同时还需对诸如遗传算法、自适应大规模邻域搜索等算法之间的性能进行对比分析的相关工作。

参考文献/References：

[1] WEIDINGER F，BOYSEN N，BRISKORN D.Storage assignment with rack-moving mobile robots in KIVA warehouses[J].Transportation Science，2018，52（6）：1297-1588.

[2] 沈博闻，于宁波，刘景泰.仓储物流机器人集群的智能调度和路径规划[J].智能系统学报，2014，9（6）：659-664.

SHEN Bowen，YU Ningbo，LIU Jingtai.Intelligent scheduling and path planning of warehouse mobile robots[J].CAAI Transactions on Intelligent Systems，2014，9（6）：659-664.

[3] FRAGAPANE G，de KOSTER R，SGARBOSSA F，et al.Planning and control of autonomous mobile robots for intralogistics：Literature review and research agenda[J].European Journal of Operational Research，2021，294（2）：405-426.

[4] da COSTABARROS  R，NASCIMENTO T P.Robotic mobile fulfillment systems：A survey on recent developments and research opportunities[J].Robotics and Autonomous Systems，2021，137：103729.

[5] 岳笑含，許晓健，王溪波.面向FMS基于改进的混合PSO-GA的多AGV调度算法研究[J].计算机科学，2018，45（Z2）：167-171.

YUE Xiaohan，XU Xiaojian，WANG Xibo.Research on muti-AGV sechduling algorithm based on improved hybrid PSO-GA for FMS[J].Computer Science，2018，45（Z2）：167-171.

[6] 余娜娜，李铁克，王柏琳，等.自动化分拣仓库中多AGV调度与路径规划算法[J].计算机集成制造系统，2020，26（1）：171-180.

YU Nana，LI Tieke，WANG Bailin，et al.Multi-AGVs scheduling and path planning algorithm in automated sorting warehouse[J].Com-puter Integrated Manufacturing Systems，2020，26（1）：171-180.

[7] JUN S，LEE S，YIH Y.Pickup and delivery problem with recharging for material handling systems utilising autonomous mobile robots[J].European Journal of Operational Research，2021，289（3）：1153-1168.

[8] POLTEN L，EMDE S.Scheduling automated guided vehicles in very narrow aisle warehouses[J].Omega，2021，99：102204.

[9] ULJ I，SALEWSKI H，GOEKE D，et al.Order batching and batch sequencing in an AMR-assisted picker-to-parts system[J].European Journal of Operational Research，2021.doi：10.1016/j.ejor.2021.05.033.

[10]陳敏，黎展滔，陈庆新，等.考虑有限物流运输能力的智能车间AGV调度算法研究[J].工业工程，2019，22（4）：49-57.

CHEN Min，LI Zhantao，CHEN Qingxin，et al.AGV scheduling algorithm of intelligent workshop considering limited logistics transportation capacity[J].Industrial Engineering Journal，2019，22（4）：49-57.

[11]陈香玲，郭鹏，温昆，等.考虑充电需求和时间窗的多AGV调度优化建模[J].河北科技大学学报，2021，42（2）：91-100.

CHEN Xiangling，GUO Peng，WEN Kun，et al.Optimized mathematical models for multi-AGV scheduling problem with charging requirements and time windows[J].Journal of Hebei University of Science and Technology，2021，42（2）：91-100.

[12]范厚明，刘鹏程，吴嘉鑫，等.集货需求随机的同时配集货VRP及混合变邻域搜索算法[J].系统工程理论与实践，2019，39（10）：2646-2659.

FAN Houming，LIU Pengcheng，WU Jiaxin，et al.Hybrid genetic algorithm with variable neighborhood descent for the vehicle routing problem with simultaneous stochastic pickup and deterministic delivery[J].Systems Engineering：Theory & Practice，2019，39（10）：2646-2659.

[13]WU X Q，CHE A.Energy-efficient no-wait permutation flow shop scheduling by adaptive multi-objective variable neighborhood search[J].Omega，2020，94：102117.

[14]徐立云，程赞，宓宏，等.基于改进变邻域搜索算法的成型机分批重调度优化[J].同济大学学报（自然科学版），2020，48（10）：1460-1469.

XU Liyun，CHENG Zan，MI Hong，et al.Molding machines batch rescheduling optimization based on improved variable neighborhood search[J].Journal of Tongji University（Natural Science），2020，48（10）：1460-1469.

[15]CUI L Q，LIU X B，LU S J，et al.A variable neighborhood search approach for the resource-constrained multi-project collaborative scheduling problem[J].Applied Soft Computing，2021，107：107480.

[16]HERRN A，MANUEL C J，DUARTE A.An efficient variable neighborhood search for the space-free multi-row facility layout problem[J].European Journal of Operational Research，2021，295（3）：893-907.

[17]HOOGERVORST R，DOLLEVOET T，MARTI G，et al.A variable neighborhood search heuristic for rolling stock rescheduling[J].EURO Journal on Transportation and Logistics，2021，10：100032.

[18]SADATI M E H，ATAY B.A hybrid variable neighborhood search approach for the multi-depot green vehicle routing problem[J].Transportation Research Part E：Logistics and Transportation Review，2021，149：102293.

[19]MLADENOVI N，HANSEN P.Variable neighborhood search[J].Computers & Operations Research，1997，24（11）：1097-1100.

[20]董紅宇，黄敏，王兴伟，等.变邻域搜索算法综述[J].控制工程，2009，16（sup2）：1-5.

DONG Hongyu，HUANG Min，WANG Xingwei，et al.Review of variable neighborhood search algorithm[J].Control Engineering of China，2009，16（sup2）：1-5.

[21]MIKI M，TODOSIJEVI R，UROEVI D.Less is more：General variable neighborhood search for the capacitated modular hub location problem[J].Computers & Operations Research，2019，110：101-115.

[22]SONG X，JONES D，ASGARI N，et al.Multi-objective vehicle routing and loading with time window constraints： A real-life application[J].Annals of Operations Research，2020，291（1）：799-825.

[23]MLADENOVI N，UROEVI D，HANAFI S，et al.A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem[J].European Journal of Operational Research，2012，220（1）：270-285.

[24]de ARMAS J，MELIN-BATISTA B，MORENO-PREZ J A，et al.GVNS for a real-world rich vehicle routing problem with time windows[J].Engineering Applications of Artificial Intelligence，2015，42：45-56.