孙阳君，赵 宁

(北京科技大学 机械工程学院，北京 100083)

1 问题的提出

多机器人存取系统(Robotic Mobile Fulfillment System, RMFS)能够利用货架存储商品，通过自寻址机器人车(Autonomous Vehicle, AV)搬运货架至工作站，工作人员无需进入储区，在工作站内进行各种操作即可，完成操作后AV再将货架搬运回储区。相比传统拣货系统，RMFS具有更高的拣货效率、更好的系统可扩展性和柔性[1]。自2008年Kiva systems公司将其用于亚马逊的仓储作业以来[2]，RMFS被广泛用于各大电商企业。RMFS布局如图1所示[3]，中间的存储区域摆放货架，两边为工作站，承担拣货或补货任务。为避免RMFS内的AV相向冲突和死锁，大部分系统内的道路都是和图1类似的单向道。空载AV按照道路方向运行，并可在货架下穿行，负载AV只能按照道路方向运行。很多学者都针对RMFS内的调度和优化问题展开研究，包括订单指派问题[4-5]、任务分配问题[6]、路径规划问题[7]、无冲突调度问题[8-9]、储位优化问题[10]等，或是多种问题的结合问题[11-13]。但以上研究多是针对静态RMFS，而电商企业中的订单是实时到达并要求立即响应的，对系统的实时性要求高。

针对实时RMFS，大部分研究都集中于任务分配、路径规划和无冲突调度等问题。MA等[14]将AV路径规划问题建模为以最小任务完成时间为目标的多代理路径寻找问题，开发了令牌传递算法和带有任务交换的令牌传递算法，通过实验表明算法在实时调度系统中能够快速规划任务。YOSHITAKE等[15]以拣货人员空闲时间为目标，建立了一种实时整体调度方法，AV同时搬运RMFS中的货架和工作站中的拣货架。LEE等[16]在RMFS中验证了动态无冲突调度策略，对实时数据进行处理后得到当前AV状态，采用改进A*算法规划路径，利用离开、绕路和启动前等待3种方式避开AV间的持续冲突、对头冲突和交叉口冲突。KEUNG等[17]在LEE研究的基础上，对多层多深度仓库布局中的6种冲突进行处理，实现实时调度。GUNEY等[18]开发了一个基于优先级的AV车辆运动协调算法解决单向网络RMFS中的AV冲突问题，在实时调度中获得了鲁棒性更强的调度结果。以上研究多采用启发式规则和智能算法实现任务分配，利用动态路径规划算法规划AV的路径，通过启发式规则规避动态运行时AV间的冲突，调度结果表现很好。系统布局也不再局限于单向道，能够较好地在实时环境中解决AV之间的冲突问题。

但在实际运行时，除了实时到达的订单外，RMFS内常会出现很多动态不确定事件，导致AV调度计划与实际运行难以完全符合，甚至偏差过大导致系统停摆。因此，对RMFS内的动态事件进行分析并及时处理就成为研究的关键，这些动态事件包括紧急订单到达、AV故障、路块不可用等。部分学者对RMFS内的动态事件加以研究，GONG等[19]建立了多机器人存取系统的高维马尔可夫模型，考虑到加急订单的实时到达，探索了机器人速度、机器人数量和拣选站数量对系统吞吐量的影响。但是由于RMFS对实时性要求高，动态事件发生时系统情况复杂，加剧了系统内AV的冲突。因此，现有研究对动态事件的考虑不足，很少考虑到AV故障、路块不可用等事件以及对这类事件的处理。在其他类似的调度系统中，针对这类动态事件的处理方式可以被分为完全反应式调度、预反应式调度、预反应式鲁棒调度和主动鲁棒调度[20]。其中，预反应式调度是最常用的调度方法。

预反应式调度方法是首先生成一个预调度方案，发生动态事件时再触发重调度。该方法现已被用于作业车间[21-22]、混合流水车间[23]、车辆路径问题[24]等动态调度问题中，具有良好的表现，保证了动态事件发生后能够及时调整调度计划，得到新的调度方案。预反应式调度方法分为预调度和重调度两部分。预调度的方式和静态调度类似，重调度方式包括右移重调度、部分重调度和完全重调度等[25]。在RMFS实际应用时，也多是通过类似的方法确保调度计划顺利进行，即先确定AV调度计划，在运行中根据实际情况动态调整。但是，由于动态事件造成的后果复杂，受影响的AV和路块又会发生连锁反应，造成连环冲突和死锁。工业界应用时只能用简单的启发式规则处理动态事件发生后的重调度问题，其所用规则的有效性有待验证。如AV故障后，其他受影响的AV只有在即将进入故障路块时才能确定当前路块被占用，再进行重调度选择其他路线，由于重调度反应时间长，可能会造成死锁现象。本文针对实时RMFS系统建立了多机器人存取系统动态调度方法，提出动态调度算法进行实时到达订单的任务分配、路径选择和无冲突调度以生成预调度方案，再根据系统内出现的各类动态事件，通过分析动态事件的后果，确定不同事件的处理方式，确立重调度规则，最后通过实例验证了动态调度方法的有效性。

2 问题描述

RMFS的调度首先需要根据系统实时输入的订单，将一段时间的订单到达后统一拆分成任务。即订单是实时到达的，但待分配的任务是周期性到达的。然后，为每个可接取任务的AV确定当前情况下要执行的任务，完成任务分配。再为接取任务的AV确定途经的各个路块，完成路径规划。最后，为AV确定各路块的进入时间和离开时间，保证多辆AV间运行时互不干扰，完成无冲突调度。调度的目的是先确定到达的任务，哪些AV接取哪些任务，如何完成这些任务，保证完成任务时不产生碰撞和死锁现象。当出现动态事件时，需要根据调度计划和当前的动态事件进行重调度，以保证任务顺利完成，继而完成所有订单。

在调度中，路径规划部分的路径和AV接取的任务相关。如图2所示，AV接取任务后，分3个阶段完成任务：①从当前路块到货架所在路块；②从货架路块到工作站；③从工作站返回储区。AV完成任务需要对这3个阶段的路径进行规划。由于任务的货架所在路块和工作站不会变动，即无论哪个AV接取任务都需要经过这两段路径，则这两段路径规划可以提前进行，即在任务到达后分配前进行规划。为了提高计划的柔性，在这两个阶段的路径规划时不只规划单条路径，而是规划出路径集。在后续调度中，对任务的第二阶段和第三阶段的路径只在路径集内进行路径选择。通过提前规划路径集，减少不必要的路径规划时间，以提高调度的效率。此外，还能在系统中单个或几个路块无法通行时，为AV提供备选路径。调度中的路径规划只包括在AV接取任务之后从当前路块到货架所在路块这一段的路径，这大大减少了实时调度中所需的时间。

2.1 动态事件分析

在实际运行中，RMFS系统内的对象众多，会发生很多不确定的扰动事件。按照发生事件的因素是否位于系统内，可以分为外部因素和内部因素两类，每种因素都会发生不同的动态事件，这些事件导致的后果和对调度的影响也不同，具体描述如图3所示。

(1)内部因素 包括系统内的路块、货架、AV、工作站等因素。不同因素发生动态事件时，可能产生相同的后果，例如路块二维码污损、货架上货物跌落和AV长时间故障都会导致路块不可用。路块和路径规划息息相关，有不可用的路块，意味着之前的路径规划受到影响，调度方案也需要因为路径规划的改动而改动。同样的，某个因素的动态事件可能会导致多个后果，如AV长时间故障除了AV本身不可用之外，还会造成路块不可用，影响到AV接取的任务，这些任务只能被分配给其他AV完成。AV故障时间长，甚至影响其他AV和其接取的任务，这些AV原本的调度方案因为前方路块不可用而不得不选择其他道路，路径规划和调度方案都要改动;若AV故障时间短，虽然影响路块，但只是占用时间过长，不会造成路块不可用，也不会让AV本身已经接取的任务受到太大影响。其他还需要经过这个路块的AV，最多只需要多等待一段时间，无需改变路径规划和调度方案。而AV无论是短时间故障还是长时间故障，都有可能产生新任务，因为故障后AV需要前往检修区，在检修区进行检查。工作站的情况又和AV故障不同，虽然都是短时间不可用或者长时间不可用，但两者的影响完全不同。短时间不可用的工作站，只需要AV等待一段时间，即可恢复运行;长时间不可用的工作站，原本需要在工作站操作的任务只能取消，然后被分配到其他工作站，即产生了新任务。新任务需要重新分配，AV按照任务需求规划路径并在原有调度方案的基础上生成新调度方案。

(2)外部因素 包括作为系统输入的订单和补货货物。这两者主要影响系统内的任务，例如订单取消或者补货货物未按时到达会导致任务取消，紧急订单会导致新任务到达且优先级最高等。若任务取消，按照任务分配情况和当前任务状态，其造成影响的轻重程度不同。例如，当任务没有分配时，对调度基本无影响；任务已经分配但AV还没有搬运货架时，只需要取消AV接取的任务即可；如果AV已经搬运货架，必须将货架放回才能进行之后的调度。新任务到达也包括了普通任务和紧急任务两类，紧急任务优先级最高，两类任务都由AV接取完成。

通过分析动态事件，这些动态事件对系统内部的影响按照因素不同可以归类为路块是可用或不可用的，AV是可用或不可用的，工作站是可用或不可用的，以及任务是取消、继续执行、还是换AV执行，新到达的任务是紧急任务还是普通任务等。因为动态事件对系统内部产生影响，同样也会影响到系统的调度计划，通过分析以上不同内部和外部因素，对调度的影响可以归结为3种情况：影响任务分配、影响路径规划、影响调度方案。虽然这3种情况中影响了任务分配就一定影响路径规划，影响了路径规划一定影响调度方案，但影响因素不同，对调度的影响程度不同。图4针对这3种情况进行了详细分析，确定了其对调度的影响程度。图中将影响程度分为影响很轻、影响一般、影响较大。

(1)影响任务分配 包括删除任务和接取新任务，如果任务因为某些原因需要更换目的货架或工作站，则都可被删去原任务后增加新任务。删除任务也有几种情况：任务未分配、任务已分配未开始和任务已分配已开始。未分配和已分配未开始的任务可以直接删除，删除这些任务对调度的影响程度都很轻。其中，已分配未开始的任务如果已经有调度计划，删除调度计划即可。但已分配已开始的任务，删除后续调度计划的同时，还需要考虑到AV是否接取货架，如果接取货架，AV需要将货架搬运回原位，在删除调度方案后可以接取新任务，但只有将货架搬运回原位后AV才能前往新任务要求的货架所在路块，删除已分配已开始的任务对调度影响一般。AV接取新任务对调度影响一般，可以按照任务类型分为普通任务和紧急任务，二者的任务优先级不同，紧急任务需要尽快完成。

(2)影响路径规划 如果AV接取了新任务，一定会影响路径规划，因为AV需要按照任务要求规划路径。新路径规划导致后续需要在原有调度方案的基础上，新增调度方案，对调度影响一般。此外，如果有路块不可用，一些AV的后续又会按调度计划经过这个路块，造成调度计划不能顺利完成，原有的调度方案不可避免地发生偏差，即影响到了已完成的路径规划，这时需要重新确定AV路径，生成新的调度方案，此时对调度影响较大。

(3)影响调度方案 由于影响的因素不同，影响调度方案可被分为删除部分方案、新增调度方案和修改部分方案。删除部分方案是删除部分AV的调度方案，或者删除部分任务的调度方案，主要针对故障的AV或被取消的任务。故障AV的调度方案删除后还需要进行后续处理，因此对调度影响一般。删除被取消的任务调度方案后，造成的影响和影响任务分配中删除任务类似，删除未分配和已分配未开始的任务对调度影响很轻，删除已分配已开始的任务对调度影响一般。新增调度方案是在原有调度方案上新增方案，主要针对新分配的任务，对调度影响一般。修改部分方案是在原有调度方案上进行改动，例如因为某个路块上的时间改变而改动调度方案，只对调度影响一般。更改路径规划后，需要删去旧路径的调度方案并按照新路径生成新的调度方案，与影响路径规划中的重规划路径类似，对调度影响较大。

由于这些动态事件对调度的影响程度不同，在处理时也需要采用不同的方式。针对动态事件进行处理的重调度包括：重分配任务、重规划路径和重生成调度方案3种。

2.2 符号定义

符号定义见如表1所示。

表1 符号定义

续表1

2.3 数学模型

为方便研究，提出以下假设条件：

(1)只发生订单到达和AV故障这两类动态事件；

(2)一波任务按照一定时间间隔到达；

(3)任务间互相独立，没有优先级；

(4)AV在0时间准备就绪；

(5)路块间的通行是双向的；

(6)不考虑AV充电情况；

(7)货架在工作站拣选完成后直接返回原储位。

针对RMFS动态调度问题，建立了以最小的所有任务完成时间为目标的数学模型。

minT=maxTc,c∈[1,2,…,q]。

(1)

s.t.

(2)

(3)

(4)

∀i∈[1,2,…,n],c∈[1,2,…,q],

p∈[1,2,…,u],

(5)

∀i∈[1,2,…,n],

c∈[1,2,…,q],

p∈[1,2,…,u]，

(6)

∀i∈[1,2,…,n],c∈[1,2,…,q],

p∈[1,2,…,u]，

(7)

i≠i′,c≠c′，

(8)

(9)

其中:式(2)表示系统内所有任务完成情况和调度计划无偏差，即输入的任务结束时间等于任务运行的最后一个路块的完成时间；式(3)表示所有任务的到达时间小于等于任务的开始时间，任务只有到达之后才能被调度；式(4)表示对于每个任务，只有一个AV接取，只用路径集中的一条路径，且AV运行的节点只包含一个路块；式(5)计算路块上的完成时间，为当前路块的操作时间和上一路块的完成时间之和；式(6)计算任务在路块上的操作时间，由通过、启停、升降、转向和等待用时组成，在工作站路块加入拣货/补货用时；式(7)确定每个任务的路径内路块的情况，路径内初始路块为AV所在路块，其中需要依次经过货架所在路块、工作站所在路块和货架所在路块，AV空载和负载时可以通行的路径不同；式(8)避免两AV同时占用一个路块；式(9)避免AV间发生相向冲突。

由于系统是动态的，为了实现最小化所有任务完成时间这一目标，在每次动态调度时以最小的当前调度完成时间为目标，利用式(10)求解最小的当前调度完成时间：

(10)

由于系统内有动态事件发生，可能会造成路径重规划，通过式(11)计算重规划路径后新增的路径长度，即对调度计划的改动程度。重规划后的路径依然要满足式(7)，这些路径还要根据当前调度计划进行无冲突调度，调度结果和实际运行情况要满足式(2)。

(11)

3 动态调度方法

动态调度方法包括预调度和重调度两部分。预调度不考虑动态事件，主要包括任务分配、路径规划和无冲突调度3部分；只有在动态事件如AV故障发生时才进行重调度，重调度时需要分析故障情况，选取合适的重调度规则，最后得到新的调度方案。动态调度方法流程如图5所示。初始输入包括初始任务数据和AV数据;实时输入包括新到达任务数据、离开工作站时间t1、任务完成时间t2、产生异常时间t3和异常情况。实时输出的是当前时间调度方案。如果有紧急订单到达，到达后立刻确定紧急任务的各项信息。考虑到调度方案的稳定性，调度中将紧急任务的优先级提高，在新一轮任务分配时和其他任务一起调度。动态调度方法的具体步骤如下：

步骤1开始，t=0。确定可开始任务的AV，如果所有任务都被完成，调度结束；否则，转步骤2。

步骤2确定可接取任务的AV，判断所有任务是否被分配，若是，则转步骤3；否则，转步骤4。其中，可接取任务的AV包括本身没有任务的AV和本身任务执行到第三阶段的AV。

步骤3判断是否有任务还在工作站等待工作人员完成操作，若任务还在工作站，即没有第三阶段的调度方案，则转步骤5；否则，让可接取任务的AV原地等待，转步骤1，重新确定可开始任务。

步骤4有任务没有分配，根据可开始任务和可接取任务的AV，利用禁忌搜索进行任务分配、路径规划和无冲突调度，生成当前时间的调度方案。若调度方案在执行中无异常，则转步骤5，否则，转步骤7。

步骤5t1时有AV离开工作站，确定工作站操作完成的任务，当前时间t=t1；对离开工作站的AV进行无冲突调度，生成当前时间的调度方案。若调度方案在执行中无异常，则转步骤6，否则，转步骤7。

步骤6t2时有AV完成任务，确定下次任务分配时间，当前时间t=t2，转步骤1，重新确定可开始任务。

步骤7在调度中，时间t3时发生异常，先对动态事件进行评估，确定重调度方式，当前时间t=t3；利用重调度规则进行调整，生成当前时间的调度方案，调整后的调度方案执行时，有AV先离开工作站，转步骤5，否则，转步骤6。

3.1 预调度

根据图5的动态调度流程，在动态调度中，不考虑动态事件的预调度被分为两步，即步骤4的禁忌搜索和步骤5的无冲突调度。这是由于RMFS是动态运行的，在工作站内工作人员的操作时间是不固定的。因此，在第一步利用禁忌搜索完成任务分配、路径规划和AV的前两阶段的无冲突调度，生成调度方案。离开工作站后，确定AV的可开始时间后，再进行第3阶段的无冲突调度，增加新的调度方案。即在调度中，根据离开工作站时间t1和任务完成时间t2两种事件驱动调度机制，触发动态调度方法并得到新的调度方案。此外，在动态调度中，发生故障后立即触发动态调度方法得到新的调度方案。因此，触发调度时间包括0时刻、拣货完成时间、AV上所有任务完成时间、AV故障发生时间。

预调度的具体时间线如图6所示。0时刻通过禁忌搜索，为AV1、AV2、AV3集中分配任务并完成路径规划，无冲突调度。由于任务到达之后，就已经确定任务的第2阶段和第3阶段的可用路径集。因此，在禁忌搜索中的路径规划是规划第一阶段的路径，选择第二阶段的路径。随后，在AV1、AV2、AV3完成拣货时分别进行第三阶段的路径选择和无冲突调度。在AV1完成任务回到储区后，再次集中分配任务，由于AV2和AV3已经完成拣货，在返回储区的路上，被视为可分配任务的AV，和AV1一起进行集中分配任务。

由图5的动态调度流程和图6的预调度时间线可知，在动态调度中包括两次预调度。第一次调度需要进行任务分配、路径规划和无冲突调度，生成当前时间的调度方案，完成任务的第一阶段和第二阶段;第二次调度只需要进行路径选择和无冲突调度，完成任务的第三阶段。在第一次调度中，包括nfea个可接取任务的AV和qfea个可开始的任务，只为一辆AV分配一个任务，即任务分配的结果是某辆AV接取某个任务。在只有一个可开始任务或只有一个可接取任务AV的情况下，任务分配的结果只有max{nfea,qfea}种。由于任务分配结果有限，路径集内可用路径数量ufea有限，无冲突调度时AV只需避让前序调度情况，因此调度的可行解是有限个，数量为max{nfea,qfea}×ufea，可以采用穷举的方式探讨所有可能。在为任务选择AV或为AV接取任务后，将路径集内所有路径都进行无冲突调度，从中选择完成时间最短的调度方案作为本次调度的新增调度方案。

对于多辆AV可接取任务且有多个任务可开始的情况，由于任务分配结果、可用路径数量、避让情况等组合数量众多，利用禁忌搜索确定AV和任务之间的分配情况、任务选择的路径集和无冲突调度时的先后顺序。禁忌搜索流程如图7所示。在禁忌搜索时保留全局最优解，在调度结束后，作为当前时间调度方案输出。

(1)个体编码 由AV码、任务码和路径码组成，分别代表AV接取任务顺序、任务被接取顺序和任务的路径选择。如[1 2 3 | 5 1 3 2 4 | 1 2 1 2 2]代表可接取任务的AV有[1 2 3]三辆，AV接取任务的顺序就是AV码顺序；代号为1～5的任务可开始，任务被接取的顺序参考任务码的顺序；路径选择是对应任务的路径集内可用路径代号之一，若有任务在路径集内的路径因为动态事件不可用，在个体编码时不考虑这些不可用的路径代号。

(2)禁忌表 利用两张禁忌表，禁忌对象分别是AV选择任务的代号和任务选择的路径代号。在评估个体时使用禁忌表1，在邻域搜索时使用禁忌表2。禁忌表1是AV选择任务的代号，在同一时间可开始AV数量为2,…,qfea，为了保证搜索到可行解，禁忌步长取1。禁忌表2是任务选择的路径代号，为了保证搜索到可行解，禁忌步长为u/2。在每代结束后更新禁忌表，既原禁忌表禁忌步长-1，最优个体的任务选择和路径选择加入两张禁忌表。

(3)邻域搜索 针对个体的三段编码采用不同的邻域搜索方式探寻解空间，其中AV码和任务码从交换、插入、反转、位移中随机选择一种生成新的AV码和任务码，路径码采用单点变异的方式，为当前任务选择另一个不在禁忌表中的其他可用路径代号。

(4)个体评估 按照个体编码进行评估，确定当前情况下的任务分配、选择的路径和AV调度信息。个体评估流程如图8所示。因为紧急任务和普通任务一起调度，所以先考虑紧急任务，对最先到达的紧急任务分配距离最近的可用AV。若所有紧急任务都被分配完毕，再分配普通任务给所有可接取任务的AV。按照个体编码确定AV先后顺序，AV按照禁忌表情况、可开始任务的距离和个体编码选择任务。AV选择不在禁忌表中，到达时间最小的任务中的，曼哈顿距离最近的任务。选择好AV和任务后，以AV的当前路块和任务的货架所在路块为起终点，利用改进的A*算法规划路径并选择最短路径。这是AV完成任务的第一阶段的路径，对于任务的第二阶段的路径，按照个体编码中的路径码，选择任务对应路径集内的路径代号。根据任务分配和路径规划，利用无冲突调度方法生成调度方案。

(5)无冲突调度 根据当前时间的AV状态和路径规划，利用甘特图确定AV间是否发生冲突。如果发现冲突，通过后调度AV在上次停止的路块主动等待的方式，调整甘特图，最终生成无冲突的调度结果。无冲突调度的目的是确保AV按照调度方案运行时不发生冲突，不产生为了躲避其他AV运行的被动等待。

(6)改进A*算法 A*算法在RMFS的路径规划问题中应用广泛[7-8,13,16]。在动态调度前，针对任务的第二阶段和第三阶段的路径采用改进A*算法提前规划路径集，在调度时选择可用路径代号。在动态调度中，任务分配完成后，对任务第一阶段的路径进行规划，但只选择最短路径作为AV的运行路径。改进A*算法是多次运行A*算法，选择下一路块的方式包括曼哈顿距离最小的路块、不转弯的路块、随机选择3种。获得多次运行结果后，选取路径运行时间最短的u条路径组成路径集，以供后续调度时选择。通过改进A*算法生成的路径集，能够在调度中提供多种选择，即使出现动态事件导致某些路径不可用，路径集内还有其他备选路径以供选择。

3.2 重调度规则

除了紧急订单到达外，其他动态事件发生时会造成调度计划和实际运行结果不相符。为了保证调度的可持续性，需要对现有调度进行调整，即重调度。在3.1节中已经确定动态事件对调度的影响可以归结为影响任务分配、影响路径规划、影响调度方案3种情况。因此，当发生动态事件时，重调度规则包括任务重分配、路径重规划和生成重调度方案3种。本文考虑的AV故障这类动态事件，根据AV故障的情况不同，会涉及到多个重调度规则的使用。AV故障发生在任务的不同阶段，对当前路块、AV和其接取任务以及受影响的AV和任务等有不同影响，调整调度方案的重调度规则也不同。AV故障影响到的不同因素的分析和重调度规则如下：

(1)当前AV和其接取的任务

由于AV故障时间不确定，AV可能在执行任务，也可能没有任务处于闲置状态。若处于闲置状态，AV只会停留在故障路块，导致一个或多个路块不可用，对其他AV造成影响。如果AV上接取了任务，根据接取任务的不同阶段，重调度规则不同。具体情况如下：

1)第一阶段 AV还未到达任务所在货架路块，任务还可以被其他AV接取。造成的其他后果和重调度规则包括：①AV故障所处的一个或者多个路块不可用，其他任务提前规划的路径集可能受影响，导致部分路径可能不可用；②当前AV不可用，后续调度计划删除；③由于AV只接取了当前任务，任务没有完成，但可以被其他AV接取，在后续调度时将该任务加入可开始任务，重分配给其他AV，完成后续调度。

2)第二阶段 AV在搬运任务货架到工作站的途中，任务已经不能被其他AV接取。造成的其他后果和重调度规则包括：①与第一阶段调度①②一样；②AV只接取了当前任务，任务虽然完成了一部分，但货架在短时间内无法进入工作站，因此取消当前任务；③按照订单要求的货物找到系统内其他存储该货物的货架，生成新任务，新任务的目标工作站与原工作站相同，以当前时间为任务到达时间，新任务的优先级和其他任务一样。同时为新任务进行路径集规划，确定任务的第二阶段和第三阶段的路径集。

3)第三阶段 AV在将货架送回储区的途中，任务已经离开工作站，但货架无法返回储区。造成的其他后果和重调度规则包括：①与第一阶段调度①②一样。②由于任务已经离开工作站，在从工作站到货架所在路块的中途出现问题，当前任务可以被视为已完成。货架由于AV故障，暂时留在原地不动，等待后续处理。③AV在执行任务的第三阶段时，已经被视为可接取任务的AV。若在调度计划中接取了新任务，因为AV故障，新任务无法完成，所以这个接取的新任务需要重分配。在后续调度时将接取的新任务加入可开始任务即可。

(2)受影响AV和其接取的任务

除了影响当前AV和其接取的任务之外，由于故障AV在当前路块停留，导致其他AV无法按照计划通行。即按照原本调度方案，有些AV会在一定时间后经过故障路块，但由于故障路块上有AV故障且短时间内无法移动，这些AV的后续调度计划已经不能按时执行，本文称这些AV为“受影响AV”。有AV发生故障后，遍历先前故障时间后所有AV的调度方案，若有AV在一段时间后经过故障路块，则被认定为“受影响AV”。受影响时间为这些“受影响AV”按照原本调度方案运行时经过故障路块的时间。故障时间和受影响时间不一定一致，受影响AV接取的任务所处的阶段不同，对应的重调度规则不同。如表2所示，针对受影响AV在故障和受影响时的任务阶段情况，根据对调度计划、任务和AV的不同影响，设立不同的重调度规则。

表2 受影响AV重调度规则

续表2

(3)受影响的路径集

由于AV故障所处的一个或者多个路块不可用，其他任务提前规划的路径集可能受影响，导致部分路径可能不可用。因此，在后续调度中，生成个体和寻找邻域个体时，需要删除不可用路径的路径代号，在可用路径代号中搜索。例如，原路径集路径代号为[1 2 3 4 5]，由于AV故障，受影响路径代号为[2 3]，则新路径集路径代号为[1 4 5]，如果禁忌表禁忌路径代号为1，则[4 5]是寻找邻域个体时的搜索空间。由于部分路径被放弃，导致搜索空间变小，寻优能力下降，但路径集可以减少调度的时间，则只有当路径集内所有路径都不可用时，才通过改进A*算法重新进行路径规划。

4 应用实例

实验在Intel Core i7-5557、3.10 GHz CPU、4.00 G RAM、64位Windows 10操作系统和MATLAB 2016a编程环境下编译运行。AV运行参数包括：Tst=0.5，Tturn=2.5，Tacross=0.5，Tlr=3。每次禁忌搜索参数包括：种群数量为5，代数为50。MERSCHFORMANN等[3]设计了图1所示的系统布局，通过单行道的方式避免系统内的相向冲突，但也造成了不必要的绕路。本文的数学模型可以用于任何道路方向，能够处理AV间的相向冲突，因此在存储区内道路可以任意通行。对图1的布局进行修改后，本文RMFS布局和道路方向如图9所示，图中箭头表示道路方向，G为工作站。布局图中间的存储区域全部为双向道，空载AV可以无障碍地穿行，负载AV在过道中运行。为避免工作站内的死锁，左右两侧工作站道路仍为单向道。8辆AV同时在系统内运行，随机给定AV初始位置，将一定时间内的订单拆分成任务，按照一定时间间隔作为任务输入系统。任务分5波到达，随机生成货架点和工作站，共包括50个任务数据。

为验证动态调度方法在实时系统的可行性和有效性，对比了本文提出的动态调度方法和传统调度方法在解决订单实时到达情况下的表现。传统方法中，AV运行在图1所示的单向道上，完成任务后再接取下一个任务，出现冲突后停车等待冲突结束。实验包括3种任务情况：①无动态事件，实时调度只包括第3.1节中的预调度，所有任务间无优先级，50个任务全部为普通任务；②5个紧急订单到达，假设每波有1个紧急订单，即原本的普通任务有1个为紧急任务，共5个紧急任务；③10个紧急订单到达，假设每波有2个紧急订单，即原本的普通任务有2个为紧急任务，共有10个紧急任务。实验②和实验③验证了动态调度方法对不同数量紧急任务的调度情况。同样，调度只包括第3.1节中的预调度，在实验中不触发重调度。

表3对比了本文方法和传统方法在3种任务情况下重复30次实验的调度结果。可以看出，本文方法在多种不同任务情况下，多次实验能获得更小的完成时间，但3种任务情况下的平均完成时间和传统方法相当。在多种不同任务情况下，本文方法的路径长度更短，分别平均节约了9.3%、9.3%和8.9%的路径长度。这就意味着AV接取的指令更少，在实际运行中，可以减少信息传输耗时。动态系统实时性要求高，在全为普通任务时，动态调度方法平均节约了44%的调度时间，有紧急任务后，调度所需时间增长，但实验②和实验③依然能平均节约31%和10.5%的调度时间。由于动态调度方法是在任务完成后集中分配，任务到达后平均等待时间多于传统方法。但动态调度方法在紧急任务到达之后，很快接取并完成紧急任务，实验②和实验③中紧急任务的平均等待时间分别为传统方法的51%和35.5%。

表3 本文方法和传统方法在3种任务情况下的调度结果

对比3种任务情况下的结果，可以发现有紧急任务后，AV平均运行路径更长，调度时间也相应变长。普通任务的等待时间更长，任务的平均完成时间略有增加。紧急任务的等待时间不到普通任务的四分之一，即紧急任务被优先完成。增加紧急订单后，考虑到紧急任务需要优先调度，调度计划的优化程度不如全部任务为普通任务的情况，因此紧急任务的平均完成时间略高于所有任务的平均完成时间。当紧急任务增加时，紧急任务的平均完成时间减少，接近所有任务的平均完成时间。

在实验③的基础上，考虑AV故障这一动态事件。假设AV在某一随机时间故障，通过分析故障AV和其任务、受影响的AV和其任务，以及受影响的路径集，确定重调度规则，进行重调度，确保后续调度无误。表4列举了不同时间AV故障时，涉及到的重调度方法和对调度计划的改动情况。从表4可以看出，无论故障发生时AV在任务的哪个阶段，都可以通过重调度避免当前任务受影响，减少对其他AV原本调度计划的影响。改进A*算法生成的路径集内虽然有路径受到AV故障的影响导致不可用，但无任务路径集需要重规划，足以看出路径集内包含了多种可行路径，为调度提供了足够的选择。在调度即将完成时发生故障(实例1)，大部分任务都已经完成，对总完成时间的影响很小。但在调度开始后不久就发生故障(实例3)，此时还有很多任务未完成，由于AV数量减少，总完成时间的增加幅度较大，任务的平均完成时间也略有增加。从实例3可以看出，由于系统内运行的AV数量减少，AV间冲突减少，重调度时，受影响的AV重调度后新调度方案的完成时间还有所减少。

表4 不同故障实例及重调度情况

续表4

在实例3中出现了受影响的AV和其接取的任务进行重调度时，重调度后完成时间更短的情况。在实际应用中，由于很难从全局角度进行调度优化，AV的重调度多是在接近故障路块时触发重调度，以受影响路块之前路块为起点重规划路径。本文的重调度规则是在故障发生时间后立刻触发重调度，以AV运行的下一个路块为起点重规划路径。为了对比传统方法中在故障路块前重调度和本文提出的受影响时间后重调度两种重调度时机的优劣程度，设置了受影响任务重调度时机实验。假设AV故障发生时间分别为[10，15，20，25，30，35]。在这些时间发生故障，受影响的任务基本处于(二，二)阶段，需要重新进行路径规划。在不同故障发生时间下进行30次实验，不同重调度时机的180组实验的平均结果如表5所示。两种重调度时机虽然都进行了180组实验，但每次影响的AV不只有一辆，可能会有两辆甚至更多AV被影响后进入重调度。因此，受影响AV重调度次数大于180。平均来看，在故障路块前重调度，增加的当前阶段任务完成时间远多于在故障时间后重调度，增加的路径长度略高于在故障时间后重调度。因此，当受影响任务的故障发生时间和受影响时间的任务阶段处于(二，二)或(三，三)等需要重规划路径的阶段时，AV的重调度时机选择在故障时间后重调度更能减少重调度后增加的当前阶段任务完成时间和路径长度，更快完成当前任务，减少对AV原先指令的改动。

随后，对不同的故障发生时间进行更详细的比对。不同故障发生时间下进行的30组实验中，重调度后平均增加的当前阶段任务完成时间和平均增加的路径长度如图10所示。由图10可以看出，相比在故障路块前重调度，选择在故障时间后立即重调度，能够更快完成当前任务。无论故障发生在什么时间，选择在故障时间后立即重调度，平均增加的当前阶段任务完成时间都更少，甚至还能获得更早完成当前任务的调度方案。如故障时间在30时，重调度后的调度时间平均减少了2.44。在大部分故障发生时间，在故障时间后立即重调度，平均增加的路径长度都要少于在故障路块前重调度。两种重调度时机规则生成的重调度方案平均增加的路径长度都会随着故障发生时间的增加而减少，这是因为故障发生在早期时，AV离目的地的距离大于故障发生在晚期时。而重调度后平均增加的当前阶段任务完成时间则和故障发生时间没有明显关联。

不同动态事件可能对调度造成不同的影响。在2.1节的动态事件分析中，将影响分为影响任务分配、影响路径规划和影响调度方案3种。这3种影响不是并列关系，影响任务分配一定会影响路径规划，继而影响调度方案。前文分析中将这些对调度的影响程度分为很轻、一般和较大3种。表6以50个任务全部为普通任务为基准，对比了紧急订单到达、AV故障和紧急订单到达的同时AV发生故障等动态事件对调度方案的完成时间、路径长度和所有任务平均完成时间的影响情况，每一种影响原因都是30组实验的平均结果。紧急订单和之前的实验一样，分为每波1个紧急任务和每波2个紧急任务两组，紧急任务优先级最高。

表6 不同动态事件对调度的影响

平均来看，同样是50个任务，相比全为普通任务，5个紧急任务和10个紧急任务分别增加了0.97%和0.24%的完成时间，0.08%和1.2%的路径长度，0.68%和0.75%的所有任务平均完成时间。新任务除影响任务分配外，还需要实时规划路径，由平均增加的完成时间和路径长度可以发现，此时对调度影响一般。之后，考虑AV故障这一动态事件，假设AV1在0时刻故障，即系统内只有7辆AV可用，AV的故障不影响其他AV的运行，只有AV1当前所在的路块不可用，会对已经规划好的路径集造成一定影响。和8辆AV接取的普通任务相比，因为完成任务的AV数量少了，完成时间增长了11.2%，但路径长度和所有任务平均完成时间都因为系统内冲突发生的频率减少而减少，AV故障且不影响其他AV的运行时对调度影响一般，主要影响完成时间。假设紧急订单和AV故障同时发生，没有受影响AV时，仅当前AV需要重调度，有受影响AV时，受影响AV也需要重调度，就对当前调度方案影响较大。对比了两种情况，没有受影响AV，即10个紧急任务到达和AV1在0时刻故障的情况；有受影响AV，同样有10个紧急任务到达，AV在35时故障且受影响AV需要在故障时间后更改路径规划的情况。没有受影响AV时，相比无动态事件，完成时间增加了12.03%，完成所有任务的路径长度和所有任务平均完成时间都减少了，主要影响完成时间。AV故障有受影响AV时，完成时间增加了16.25%，完成所有任务的路径长度增加了2.65%，所有任务平均完成时间增加了0.89%，多于其他动态事件增加的完成时间和路径长度，对调度影响较大。综合来看，相比紧急订单到达，AV故障对系统总完成时间的影响较大，因为AV数量减少导致系统内冲突减少，路径长度和所有任务平均完成时间都可能减少。在AV故障时，如果有受影响AV，则调度方案的平均完成时间和路径长度都更长，所有任务的平均完成时间也更长，对调度的影响最大。

5 结束语

针对多机器人存取系统中存在的订单实时到达、紧急订单到达、AV故障等问题，本文提出了一种动态调度方法。首先分析了系统内的不同动态事件并确定其对调度的影响，提出以最小完成时间为目标的多机器人存取系统动态调度模型。建立了实时系统的动态调度方法，利用动态调度算法实现系统内的预调度和重调度。通过禁忌搜索、改进A*算法和无冲突调度方法解决任务分配、路径规划和无冲突调度问题。根据动态事件的不同影响，确立重调度规则。实例证明动态调度方法能够解决订单实时到达即任务分波次到达情况下的AV调度问题，保证系统内的AV顺利完成所有任务，且多辆AV运行时无冲突死锁现象。相比传统方法，动态调度方法获得的调度方案完成时间更小，调度时间更短，紧急订单到达时能够确保紧急订单优先完成。当出现AV故障时，能够顺利完成重调度并保证当前任务受到的影响最小。对比不同故障时间重调度的触发时机，相比传统方法中在故障路块前重调度，在故障时间后重调度任务的当前阶段完成时间更小，重调度路径长度更短，甚至能够获得比重调度前完成时间更短的调度方案。通过对比证实，若AV故障时有受影响AV，对调度的影响最大。本文目前的研究还集中于紧急订单到达和AV故障两种动态事件中，缺少对人员相关的动态事件的预测和重调度规则的研究，下一步将结合数字孪生技术，针对人员暂停工作、人员突然进入系统内等事件进行预测并研究相关重调度规则。