基于数字孪生的多自动导引小车系统集中式调度

孙阳君，赵 宁

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

1 问题的提出

随着科学技术的发展和人力成本的增加，用机器人代替人工已经成为主流。据《2019年世界机器人报告》[1]显示，仅2018年全球就卖出了超过10万的多机器人系统，其中大多数用于电子商务仓库中的多机器人存取系统(Robotic Mobile Fulfillment System, RMFS)，RMFS已经成为机器人应用最广泛的领域之一。2008年，Kiva systems公司[2]首先将RMFS用于亚马逊的仓储作业，其利用货架存储商品，通过自动导引小车(Autonomous Guided Vehicle, AGV)搬运货架[3]。相比传统拣货系统，RMFS具有更高的拣货效率、更好的系统可扩展性和柔性[4]。如图1所示，在RMFS内，AGV扫描路块上的二维码，通过二维码确定当前位置和移动方向，工作人员只需在工作站等待AGV将货架搬运到固定位置，在固定位置拣货即可，而不用进入存储区域拣货，AGV等工作人员拣货完毕后再将货架搬运回存储区域，大大减少了工作人员的劳动强度，降低了人力成本，提升了系统的自动化和智能化程度。由于系统内的AGV数量众多，容易造成冲突和死锁，AGV的调度和协同运行成为系统的核心。

很多学者对RMFS的调度和协同问题展开研究。针对多辆AGV之间的冲突问题，一些学者采用单项网络布局减少冲突和死锁，Zou等[5]在单项网络的RMFS系统中提出一种AGV与拣选站匹配规则；邹碧攀[6]对比了基于作业速率、近似最优和最优指派策略3种不同的任务分配策略，利用单向道避免冲突和堵塞；Zhang等[7]将单项网络内的AGV调度问题建模为具有传输时间的资源受限项目调度问题，设计了遗传算法来分配任务；Merschformann等[8]用启发式规则进行任务分配，分析了选择工作站和货架的多种启发式规则对单位吞吐量的影响。这些研究默认在使用单项网络的情况下，系统内的AGV之间不存在冲突和死锁问题，对AGV运行路径不做规划，然而在AGV实际运行中依然会存在冲突问题，因此有学者研究了无冲突的路径规划，如Kamoshida等[9]提出一种深度强化学习的方法解决RMFS系统中的AGV路径规划问题，根据系统状态从多个候选路径中选择适合AGV的无冲突路径；Vivaldini等[10]在双向网络RMFS中采用Dijkstra’s算法和时间窗方法生成无冲突路径，采用禁忌搜索算法进行任务分配；Merschformann等[11]用时间窗分层协同A*(Windowed Hierachical Cooperative A*，WHCA*)算法进行无冲突路径规划；Ma等[12]通过搭建仿真模型实现单向网络中的AGV任务分配和无碰撞路径规划；Honig等[13]将单向网络RMFS中的AGV调度问题变为多代理路径寻找问题，利用动作依赖图进行无冲突路径规划。除了采用单向网络布局和构建无冲突的路径外，一些学者采用事后调度的方式消解AGV冲突，即在任务分配和路径规划完成后利用启发式规则化解冲突。Guo等[14]提出基于Dijkstra’s算法和A*算法的路径规划方法，通过优先级低的AGV避让的方式解决RMFS两个AGV间的冲突问题；Dou等[15]选择让剩余任务较少的AGV等待的方式解决AGV之间的冲突问题；Yuan等[16]用后到达车辆等待的方法解决同向冲突，用优先级低的车辆等待的方法解决路口冲突；Wang等[17]用优先级和重新规划路径的方法避开AGV间的冲突；Roy等[18]利用通道协议避免AGV冲突，即通道内有AGV时不允许其他AGV经过。这些研究多针对静态调度，集中在任务分配和路径规划与调度中，对系统的实时运行情况考虑不足，在系统发生动态变化时难以做到及时响应。

一些学者考虑到系统运行的动态环境，对系统内的车辆进行无冲突调度。张丹露等[19]利用改进的A*算法、预约表和动态加权地图进行动态协同路径规划，通过集中分配任务、分布式进行路径规划，利用预约表和交通规则来避免AGV冲突；Yoshitake等[20]建立了一种实时整体调度方法进行RMFS实时调度；Lee等[21]基于网络物理系统，根据AGV当前状态采用改进A*算法规划路径，然后选择完成时间最短的路径作为AGV路径，利用时间窗检测冲突，并采用离开、绕路和启动前等待3种方式避开双向网络中的持续冲突、对头冲突和交叉口冲突，在RMFS系统中验证了动态无冲突调度策略；董朝瑞等[22]通过机器人模块从中央控制模块处获得冲突协调信息和地图环境，帮助AGV解决动态运行中的冲突问题；Guney等[23]开发了一个基于优先级的AGV车辆运动协调算法解决单向网络RMFS中的AGV冲突问题，算法可以实时调整AGV的优先级，当AGV之间发生冲突时，优先级最高的AGV继续运行而其他AGV停车等待。这些研究多用动态调度方法解决系统中的AGV冲突问题，调度结果表现很好。

然而，这些研究对AGV的运行情况预测不足，大部分研究均在冲突发生后进行协调，造成AGV出现不必要的等待和停顿，因此建立在精准仿真预测基础上的集中式调度成为系统进一步提升的关键。虽然AGV的运行情况能够预测，但是RMFS中有人参与的作业完成时间是变化且不可预测的；另外，在实际运行中，物理系统很难完全符合调度方案的预期，系统内的AGV运行和人员操作会受各种干扰，并非完全可控。现有调度模型基本不考虑这些变化和干扰，例如AGV发生故障或工作站工人不到位，然而这些事件容易影响系统原有的调度方案，对原有方案造成扰动。原有调度方案若不能依计划实行，则容易导致后续调度方案出现问题，最终造成系统内出现更加严重的冲突和死锁。另外，由于RMFS中的订单为实时到达，AGV执行的任务随订单确定，大大增加了调度的难度，对调度提出了新要求。在此背景下，数字孪生技术的发展为提高预测水平、解决扰动和实时调度提出了新思路。

数字孪生是利用数字化手段构建如同物理系统实体的孪生体一般的虚拟系统，从而借助物理实体数据、实时运行数据、历史数据等在虚拟系统中模拟物理系统的运行，通过仿真优化和虚实交互促进物理系统智能运行[24]，其在智能工厂建设[25]、智能制造[26]、生产车间[27]、分布式智能车间[28]、车间生产过程[29]及智能生产管理和控制[30]中有广泛的应用。数字孪生能够在真实的物理世界和虚拟的信息世界之间架起一座实时同步且高度保真的桥梁[31-32]。北京航空航天大学的陶飞教授团队[33]建立了数字孪生技术五维模型，探索了其在车辆、立体仓库等十大领域的应用；Zhang等[34]提出基于数字孪生技术的中空玻璃生产线的快速个性化设计，以及生产过程中耦合问题的解耦算法，解决了生产过程中的冲突；Liu等[35]利用数字孪生驱动流水车间的个性化设计，实现了系统静态配置和动态执行机制的互相迭代优化；Fang等[36]利用数字孪生技术解决作业车间调度中突发的动态问题并进行预测；李浩等[37]利用数字孪生技术预测设备的动态性能；郭飞燕等[38]通过数字孪生技术预测产品装配情况，实现了“以虚控实”的过程；Luo等[39]建立数字孪生模型对数控机床的道具寿命进行预测。以上研究可以看出，数字孪生技术可以联通虚拟世界和现实世界，已经在制造车间等集中调度领域取得了较好的研究成果，其能够实现实时调度并响应物理系统变化，保证虚拟系统和物理系统一致，避免出现调度方案不符合实际的情况，而且利用虚拟系统仿真验证各方案能够降低系统运行成本，实现系统的高效运转。

2 基于数字孪生的集中式调度模型

2.1 整体架构

基于数字孪生的RMFS由4部分组成，即物理系统、虚拟系统、联系两者的孪生数据中心，以及确保三者互相映射的系统支撑服务，如图2所示。

(1)物理系统 是真实的系统，主要接收数据中心传递的指令，根据指令运行，并利用传感器等采集实时运行数据和物理系统数据。物理系统内部的人员操作系统、AGV控制系统、传感器等系统和装置将实时运行数据传送到孪生数据中心。

(2)虚拟系统 是根据物理系统建立的虚拟模型，为物理系统的孪生体，主要功能包括建立虚拟系统模型、生成初始调度方案、运行仿真调度方案和实时调整调度方案。虚拟系统模型是根据孪生数据中心的虚拟系统数据和实时运行数据建立并持续维护的模型，其涉及的虚拟系统数据是将物理系统中的物理系统数据进行处理后得到的。虚拟系统模型可用于仿真调度方案的运行，能够根据方案在不同评价指标下的表现选择合适的方案。最后，将合适的调度方案传递到孪生数据中心指导物理系统运行。

(3)孪生数据中心 是沟通物理系统和虚拟系统的桥梁，其功能包括数据处理、数据存储、数据对比和传输。数据处理包括将物理系统数据转化为虚拟系统数据、将订单数据转化为任务数据、将虚拟系统仿真结果数据转化为运行指令，存储的数据包括物理系统数据、物理系统实时运行数据、订单数据、任务数据、虚拟系统数据、虚拟系统仿真结果数据等，数据对比是对比物理系统实时运行数据和虚拟系统仿真结果数据，这些数据通过数据传输协议和无线网通讯来保证传输的安全性、及时性和可靠性。

(4)系统支撑服务 系统支撑服务能够确保以上三部分互相映射，包括为物理系统人员提供的操作系统和为AGV提供的控制系统、为虚拟系统提供的模型搭建方法和方案生成方法、为孪生数据中心提供的数据处理方法等。物理系统、虚拟系统和孪生数据中心除了根据各自需求调用支撑服务内的各个模块外，还会根据当前系统状态集中调用多个模块。系统支撑服务内各模块提供的不只是单个服务，其还将物理系统、虚拟系统和孪生数据中心三者进行结合，保证三者互相映射，从而支撑整个系统运行，是基于数字孪生的集中式调度系统运行的重要保障，决定了系统整体运行的效率。

2.2 集中式调度流程

基于数字孪生的RMFS系统集中式调度流程图如图3所示，具体步骤如下：

步骤1当在孪生数据中心处理输入的订单时，将订单转变为相应的拣货任务和补货任务，将任务信息转化为任务数据并传输到虚拟系统进行后续操作。其中，订单处理方法由系统支撑服务提供。

步骤2在虚拟系统中，根据任务数据和实时运行数据集中生成初始调度方案，即扰动发生前的调度方案，初始调度方案的生成方法由系统支撑服务提供，需要利用任务分配、路径规划和调度优化等多个模块。

步骤3在虚拟系统中，采用搭建好的虚拟系统模型仿真步骤2中生成的多个调度方案。其中，虚拟系统模型的搭建方法由系统支撑服务提供。

步骤4在虚拟系统中，根据仿真结果确定最优调度方案，并将仿真结果数据传送到孪生数据中心。

步骤5孪生数据中心根据接收到的仿真结果数据生成相应的指令传送给物理系统。

步骤6在物理系统读取孪生数据中心传递的指令，根据指令指导人员操作和AGV运行。例如，通过看板展现人员需要操作的商品和数量，向AGV控制系统发送AGV的启动、停止、转弯、等待、升/降货架等指令。

步骤7在物理系统，通过人员操作系统、AGV控制系统、传感器等系统或装置搜集实时运行数据，将其上传到孪生数据中心。

步骤8在孪生数据中心对比虚拟系统的仿真结果数据和物理系统的实时运行数据，若出现异常数据，则进入步骤9；若未出现数据异常，则依次循环步骤6～步骤8，直到所有指令都完成，从而完成订单，系统运行结束。

步骤9在孪生数据中心，通过对比数据确定有异常的数据，将异常数据上传到虚拟系统，并根据异常数据对虚拟系统模型进行更新。

步骤10在虚拟系统根据接收的异常数据确定扰动原因，根据不同的原因，依靠不同的重调度规则生成重调度方案，重调度方案的生成方法由系统支撑服务提供，需要利用订单处理、任务分配、路径规划和调度优化等多个模块，然后返回步骤3。

3 工作机制

3.1 物理系统的接收指令和采集数据机制

物理系统是实际运行的系统，其主要功能是接收指令和采集数据，图4所示为物理系统的工作机制。

物理系统接收孪生数据中心下发的运行指令，即物理系统的输入，接收指令的对象是系统内的工作人员和AGV两大实体。工作人员通过人员操作系统获取操作指令，根据看板上的显示确定操作类型以及涉及的商品、位置和数量；AGV通过控制系统接收指令，确定在路块上的启动时间和停止时间，以及在路块上的转弯、等待、升/降货架等动作。工作人员和AGV接收指令后根据指令运行，而且人员操作系统和AGV控制系统均在系统支撑服务中开发。

采集数据包括采集物理系统数据和采集物理系统实时运行数据：

(1)物理系统数据主要包括系统内各个设备和区域的尺寸、人员完成不同操作时的时间、AGV在不同情况下的速度和加速度、货架和商品的位置数量信息等。这部分数据会传输到孪生数据中心，用来建立虚拟系统，保证虚拟系统和物理系统形如孪生体。

(2)物理系统实时运行数据包括工作人员的操作数据、AGV的实际运行数据和状态数据。工作人员通过人员操作系统上的各个按钮确定当前任务完成，并将任务信息和操作时间等数据作为实时运行数据。AGV通过自身携带的各种传感器检测运行情况，包括视觉传感器确定AGV进入的路块代号和时间，力学传感器确定AGV是否转弯和负载/空载状态，AGV的运行数据和状态数据将作为实时运行数据；利用工作站的RFID可以监控AGV是否准时准确进入工作站，AGV进入工作站的时间和工作站信息也将作为实时运行数据。将这些实时运行数据上传到孪生数据中心，用于和仿真数据比对。一些特定的数据，如人员拣货时间和任务完成时间，会直接传递到虚拟系统，辅助虚拟系统进行下一步决策。

另外，物理系统还有针对环境的监控，其根据监控到的温度、湿度、压力等数据进行自动调节和预警，以增加员工工作的舒适程度，确保货品保存得更好，防止出现火灾等意外情况。利用摄像头对路块路面进行监控，确定是否有障碍物，并在出现商品跌落、人员走动等情况时及时响应。

3.2 虚拟系统方案生成与仿真机制

虚拟系统是物理系统的孪生体，其能够模仿物理系统的运行，并为物理系统的运行提供支撑，还能够根据物理系统反馈的结果进行及时调整，以处理物理系统中的各种突发状况。虚拟系统主要由虚拟系统模型、实时生成和调整调度方案、仿真调度方案3部分组成，通过这3部分实现方案的生成和仿真功能。虚拟系统的运行机制如图5所示。

虚拟系统模型是虚拟系统的基础，模型的基础数据为经过数据中心处理的物理数据，根据物理实体对应的物理数据在虚拟平台上建立多个子模块，再根据物理实体之间的关联连接各模块，最终组合为虚拟系统模型。所建立的子模块包括人员操作模块、AGV运行模块、货架存储模块和商品库存模块。虚拟系统模型还会通过实时运行数据进行修正，以保证其更接近物理系统，尤其在发生意外事件之后，虚拟系统模型需要及时根据异常数据进行调整，按照物理系统的实时运行数据进行更新，以保证仿真调度方案的真实性。如果物理系统内有部分实体如AGV或工人出现异常，则需要按照出现的异常情况修改虚拟模型中对应实体的状态，例如AGV出现故障时，需要将AGV状态从可用调为不可用，将AGV出现故障的路块调为持续占用中。虚拟系统模型的搭建方法由系统的支撑服务提供。

实时生成和调整调度方案的主要输入是物理系统运行数据、任务数据和实时运行数据，根据现有数据和系统状态，以及实时到达的任务和可能的扰动能够确定当前可以执行的调度方案。实时生成和调整调度方案分为生成初始调度方案和生成重调度方案两部分。初始调度方案在任务到达之后对任务进行分配，确定执行任务的AGV和运行路径，即AGV需要经过的路块顺序，以及AGV在运行中的其他动向，包括启动、停止、转弯、等待、升/降货架等。物理系统按照调度方案运行时上传实时运行数据，孪生数据中心在对比时如果发现异常数据，即任务不能顺利完成，则需要生成重调度方案。在实际运行中，导致异常数据的扰动是不同的，这些扰动包括AGV故障、工作站工人不到位、AGV路径前方有突发障碍、AGV运行时间发生变化等。孪生数据中心将异常数据传送到虚拟系统后，虚拟系统确定发生扰动的原因，根据不同的原因调用系统支撑服务中的不同模块生成重调度方案。在实时生成和调整调度方案这一阶段生成的初始调度方案和重调度方案均需在虚拟系统模型中进行仿真验证。

仿真调度方案借助虚拟模型仿真之前生成的调度方案，再将调度方案的仿真结果返回到孪生数据中心。仿真的调度方案由生成初始调度方案和实时调整调度方案这两部分生成，目的是验证生成的多个调度方案能否无冲突地运行，并从中选择平衡多目标的调度方案，如果调度方案运行不能保证无冲突，则返回重新生成调度方案。仿真过程中将统计相关的运行数据，包括完成时间、AGV利用率、AGV启停次数、工作站任务平衡程度等，这些数据中的一部分会被作为评价指标。仿真方案的评价选择方法与系统中不同的决策倾向相关，应根据系统中不同的决策倾向选择不同的评价指标和评价方法，例如用Pareto解确定最优边界后，再用层次分析法选择最优调度方案；通过给定评价指标之间的优先级进行选择；采用线性加权的方法处理多个评价指标，选择权重和最优的调度方案等。另外，还会利用实时运行数据优化选择方法。

3.3 孪生数据中心的数据处理和对比机制

孪生数据中心能够联系物理系统和虚拟系统，主要用于存储数据、处理数据、对比数据等，其通过数据传输协议和无线网通讯保证系统间的交互。孪生数据中心的运行机制如图6所示。

存储的数据包括物理系统数据、物理系统实时运行数据、订单数据、任务数据、虚拟系统数据、虚拟系统仿真结果数据等。物理系统数据和物理系统实时运行数据均传输自物理系统；订单数据由RMFS输入的订单生成；任务数据由订单数据经过孪生数据中心处理后得到；虚拟系统数据由物理系统数据经过孪生数据中心处理后得到；虚拟系统仿真结果数据传输自虚拟系统。

数据处理包括将物理系统数据转化为虚拟系统数据、将订单数据转化为任务数据、将虚拟系统仿真结果数据转化为运行指令：

(1)将物理系统数据转化为虚拟系统数据 是针对搜集到的物理系统数据，采用系统支撑服务中的数据处理方法转化为建立虚拟系统模型必备的数据，即虚拟系统数据。

(2)将订单数据转化为任务数据 是针对RMFS实时输入的订单，采用系统支撑服务中的订单处理方法转化为相关的任务数据。任务数据包括任务类型、货架代号、工作站代号、商品存储位置、拣货数量等。

(3)将虚拟系统仿真结果数据转化为运行指令 包括针对AGV的启动、停止等运行指令，转弯、等待、升/降货架等动作指令，以及针对人员的拣货、补货、盘点等操作指令。

数据对比是对比物理系统的实时运行数据和虚拟系统的仿真结果数据，主要包括仿真中AGV启动、停止的路块和时间与实际运行中AGV进入、离开路块的时间，仿真中AGV在路块上的动作情况和实际运行中AGV转弯、等待、升/降货架的路块，以及仿真中人员操作类型、对象和实际运行中人员拣货、补货、盘点的货架与商品，如果出现异常，则需上报虚拟系统，确定扰动原因后进行重调度操作。这些异常数据可以辅助更新虚拟模型，以避免物理系统和虚拟系统出现偏差，减少实际运行和调度计划之间的差异。

4 系统支撑服务

系统支撑服务为物理系统、虚拟系统和孪生数据中心的运行提供支撑，是数字孪生系统的基石和保障。系统支撑服务包括为物理系统的人员提供的操作系统和为AGV提供的控制系统、为虚拟系统提供的模型搭建方法和方案生成方法、为孪生数据中心提供的数据处理方法等，详细模块如图7所示。

为物理系统的人员提供的操作系统和为AGV提供的控制系统分别帮助人员和AGV在物理系统中读取指令并实现系统运行：

(1)人员操作系统的开发流程 通过分析物理系统确定人员操作逻辑，按照逻辑分析系统需求，再根据需求确定系统功能模块，然后针对各模块设计相应的操作流程，根据操作流程设计系统界面，完成所有设计后部署系统的运行环境，最后完成系统开发与实现，将系统交付工作人员使用。

(2)AGV控制系统的开发流程 通过分析物理系统确定AGV的运行逻辑，按照逻辑分析AGV的运行需求，再根据需求确定系统功能模块，然后针对各模块设计AGV对自身其他零部件系统的控制方式，根据控制方式设计系统界面，完成所有设计后部署系统的运行环境，最后完成系统开发与实现，将系统用于AGV控制。

为虚拟系统提供的模型搭建方法是借助孪生数据中心的虚拟系统数据和物理系统总结得到的系统运行逻辑，利用模块化建模方法分别建立人员操作模块、AGV运行模块、货架存储模块和商品库存模块。模块建立所需的相关数据是物理系统中获得的虚拟数据，在物理系统运行中，所建立的各模块还应根据实时运行数据进行修正，以确保和物理系统虚实一致。确定各模块的功能逻辑和输入输出后，建立模块间的关联模型，并通过RFID、传感器等装置维持不同模块之间的通信。然后统计和分析模型运行数据，利用3D设计软件完成模型可视化和数据可视化。另外，还可通过实时运行数据对模型中的部分参数进行调整。

为虚拟系统提供的方案生成方法主要用于虚拟系统中实时生成和调整调度方案，主要包括任务分配、路径规划和调度优化3个模块：

(1)任务分配 即将已经确定好的任务分配给AGV执行。任务分配的方法包括利用不同智能算法编码、不同的启发式规则等，可以根据所反馈的实时运行数据，在不同情况下使用不同的任务分配方法。

(2)路径规划 是为AGV规划完成任务的三段路径，包括AGV从当前位置到货架所在位置、从货架所在位置到工作站、从工作站返回存储区域。三段路径并非一次规划完成，而是在实际运行中按照调度需求在不同时间规划不同阶段的路径。路径规划算法一般采用深度强化学习、Q-learning算法、蒙特卡洛树搜索等。实时运行数据可以对这些路径规划算法内的参数进行调整，根据AGV实时运行情况选择不同的路径规划算法。

(3)调度优化 是对多AGV的协同运作进行优化，采用一种或几种算法和规则生成多个可行且较优的调度方案。调度优化可以和任务分配协同编码，使用智能算法生成调度方案。在生成调度方案时，利用启发式规则处理AGV之间的冲突问题，启发式规则可以采用提前主动等待、允许修改路径、遇到冲突时根据优先级决定通过和停止的AGV等。另外，实时运行数据能够优化智能算法和启发式规则。

在为虚拟系统提供支撑时，这3个模块并非分开调用，而是按照一定规则多次集中调用。

例如，生成初始调度方案的步骤分为为未完成的任务集中分配AGV、对AGV完成任务的路径进行规划、生成多个可用的调度方案3步。生成的初始调度方案即没有扰动发生的调度方案，当前时间t时系统数据的不同，初始调度方案不同，具体流程如图8所示，步骤如下：①根据当前时间t，按照任务数据确定可以开始的任务，按照AGV数据确定可以接取任务的AGV，进入②，如果所有任务都被分配给AGV，则转③；②对这些AGV进行任务分配，根据分配到的任务规划AGV从当前位置到货架所在位置和从货架所在位置到工作站的路径，按照调度优化方法确定AGV的调度方案，并输出调度方案；③根据传递来的拣货完成时间t1这一实时运行数据，令t=t1，执行下一步；④对拣货完成的AGV规划从工作站返回存储区域的路径，按照调度优化方法确定AGV的调度方案，并输出调度方案；⑤根据传递来的任务完成时间t2这一实时运行数据，令t=t2，返回①，直到所有任务都被完成，生成初始调度方案的流程结束。

如果孪生数据中心向虚拟系统传递了异常数据，则需在虚拟系统中实时调整调度方案，即生成重调度方案。由于不同的扰动原因对系统的影响程度不同，需要根据不同的扰动原因、借助不同的重调度规则生成重调度方案，再仿真调度方案，根据仿真结果得到可行的调度方案作为指导物理系统运行的重调度方案。重调度规则包括重生成任务数据、重分配任务、重规划路径和重调度，对于不同的扰动原因，适用的重调度规则不同，如图9所示。

对于AGV故障这一扰动，首先进行故障诊断，如果为短时间内可自行修复的故障，则修复后AGV可以继续执行任务，直接从受影响时刻起重新调度即可。如果需要长时间检修，则考虑AGV是否有负载，是则意味着任务还未完成，但AGV已经不可用，先将负载的AGV拖离原路块，这一步要规划移动AGV的路径，根据路径规划利用调度优化方案生成重调度方案。然后，将这辆损坏AGV当前在执行的任务和后续所有任务都重新分配给其他AGV，并为这些任务进行路径规划，执行后续的调度操作。不负载的AGV暂时留在原地，等到时机合适再拖离当前路块。在AGV没有离开故障位置之前，这一路块或者几个路块将不可用，可能造成某一条通道不可用，其他遭受影响的AGV也需要重新调度，此时按照AGV路径前方有突发障碍的情况进行重调度。对于这种情况，直接重规划AGV路径，再生成重调度方案。

对于工作站工人不到位这一扰动，首先确定工作站故障的时间长短，如果是短时间的，则不改变任务分配和路径规划，从受影响时刻起重新调度；如果时间长，则影响该工作站分配到的所有订单，需要从订单处理开始重新生成任务数据，再重分配其他AGV执行任务，根据新任务要求和AGV运行情况重新进行路径规划，最后生成重调度方案。对于其他影响较小的扰动，如果时间上发生变化，例如AGV运行时间发生变化，则从受影响时刻开始重新调度，生成重调度方案，此时系统支撑服务会按照不同情况为虚拟系统提供不同的服务。

为孪生数据中心提供的数据处理方法，包括将物理系统数据转化为虚拟系统数据的数据处理方法和将订单数据转化为任务数据的订单处理方法：

(1)数据处理方法 将物理数据通过数据清洗、特征提取、数据分析等方式，处理为适合建立虚拟系统模型的虚拟系统数据。

(2)订单处理方法 通过订单整合为订单分配工作站，如果商品库存不足则生成相应的补货任务，将工作站分配到的订单拆分为相应的拣货任务，根据系统需求确定拣选后的盘点任务。订单处理完成后得到补货、拣货、盘点任务，即可生成任务数据。

5 应用实例

在多AGV系统中，采用本文所提基于数字孪生的集中式调度方法，根据当前情况预测系统未来状态，针对不断到达的订单进行实时调度，达到实时处理订单并转化成任务，根据任务生成调度结果并转化为AGV运行指令，最终完全控制AGV运行的效果。当物理系统中发生的扰动时进行重调度，解决调度计划和实际运行存在偏差的问题。

首先，分析物理系统数据，在AGV上安装传感器和控制系统，为工作站配备人员操作系统；其次，根据物理系统各实体的数据并分析系统作业流程，基于e-plant软件建立如图10所示的RMFS虚拟仿真系统。

假设系统中有3辆AGV，位于路块[292,384,430]处，完成实时到达的两波订单数量分别为[3,5]，到达时间分别为[0,10]。采用孪生数据中心的订单处理方法将订单数据转化为任务数据，第一波任务的货架所在路块为[272,409,433]，工作站为[436,390,321]；第二波任务的货架所在路块为[432,318,295,387,410]，工作站为[275,436,390,436,367]。根据任务数据和AGV运行数据，在虚拟系统中预测AGV未来的动向，并化解AGV间冲突，最终生成初始调度方案。任务分配方法采用就近分配规则，如图11a所示，横坐标表示时间，纵坐标表示路块。在这一步生成的初始调度方案，AGV只从当前位置到货架所在位置，再从货架所在位置到工作站，在0 s只有任务[1,2,3]被分配。图中竖线表示当前时间，竖线右侧的甘特图是预测的AGV运行情况，通过预测未来情况来化解AGV冲突。

人员操作完毕后，AGV将货架运送回存储区域。在调度中，物理系统将一些特定的实时数据通过数据传输协议和无线网通讯直接传输到虚拟系统，即人员拣货时间和任务完成时间。根据图11a所示的初始调度方案，AGV3所在的工作站工作人员最先完成任务的拣选，人员拣货时间数据会直接传输到虚拟系统，在先前调度方案的基础上，在25.5 s生成如图11b所示的调度方案。图中竖线左侧甘特图表示AGV过去的运行情况，右侧甘特图表示预测的情况。此时，AGV1即将进入工作站拣货，AGV2的运行预测到了31 s ，AGV3的运行预测到了45 s。

当物理系统将任务完成时间传输到虚拟系统后，该任务被视为已完成，根据任务数据，将已经从工作站离开的AGV作为可接取任务的AGV，再次生成初始调度方案。如图11c所示，在45 s AGV3完成了任务，此时虽然AGV1和AGV2上还有任务未完成，但是这两辆AGV已经离开工作站，离开时间分别是33 s和39 s，预测到达货架存储点的时间是53.5 s和66 s。因此，将AGV1和AGV2同空闲的AGV3一起视为可接取任务的AGV，集中为其进行任务分配，分配后AGV运行情况的甘特图如图11c所示。通过为现有AGV集中分配任务，能够提前预测可能出现的冲突并处理，AGV可以按照预测结果提前避让，减少了不必要的启停。

在没有其他扰动的情况下，按照本文所提生成初始调度方案的方法，对这8个任务进行集中式调度，最终的调度结果如图11d所示，完成所有任务的时间是173 s。

在集中式调度中，物理系统的数据通过数据传输协议和无线网通讯传输到孪生数据中心，孪生数据中心通过比对确定是否发生扰动，如果发生扰动，则根据重调度规则对扰动进行处理。以图11c所示的初始调度方案为例，如果在73 s发现AGV1的运行情况和调度计划不符，其未按时到达路块343，而是在74 s才到达，则需要生成重调度方案。所生成的重调度方案如图12所示，其中竖线表示重调度发生的时间，即系统运行的当前时间。

这些生成的初始调度方案和重调度方案均需利用虚拟系统模型进行仿真，通过仿真调度方案得到仿真结果数据，传输到孪生数据中心生成指令，指导物理系统中的AGV运行和人员操作。

为了验证集中式调度方法在订单数量较多时的表现，随机生成6辆AGV初始位置和订单数据，订单按照5个波次到达，每个波次的任务数量分别为[6,10,8,14,12]，共50个任务。采用所提方法进行调度，最终结果的甘特图如图13所示，完成时间为721 s。从图中可以证明，本文方法能够完成大量任务的集中式调度并生成无冲突的调度方案，为物理系统中的人员和AGV提供调度指令，保证物理系统无误运行。

为了验证本文所提集中式调度方法的调度效果，将集中式调度与现在常用的分布式调度方法进行对比。图14所示为图13案例中的30次重复实验下，采用两种调度方法获得的调度方案完成时间分布情况。可以看出，虽然集中式调度方法获得的完成时间最小值大于分布式调度方法，但是多次重复实验中，其总体上优于分布式调度方法，找到较小完成时间调度方案的几率更大，两者完成时间的平均值分别为732.7 s，734.8 s。

在实际运行中，因为AGV数量多，任务繁忙，RMFS内冲突严重，所以针对订单数量较多且系统内冲突严重的情况进行实验，30次实验结果如表1所示。从表中可以看出，集中式调度和分布式调度这两种方法都能得到很稳定的调度结果，多次实验的完成时间保持不变。然而相比分布式调度，集中式调度完成任务的时间更短，节约时间14.4%，而且AGV的运行总路程和总启停次数更少，这意味着采用集中式调度方法能够显著提升系统效率，降低AGV的运行长度和启停次数，减少完成任务的能耗。

表1 集中式调度和分布式调度对比(冲突严重)

6 结束语

本文提出一种基于数字孪生的集中式调度方法。建立了以物理系统、虚拟系统、孪生数据中心、系统支撑服务为核心的数字孪生模型；确定了物理系统接收指令和采集数据机制，包括AGV接收运行指令并利用传感器等传输数据，人员接收操作指令并利用操作系统传递数据；建立了虚拟系统方案生成与仿真机制，包括虚拟系统模型、实时生成和调整调度方案及仿真调度方案3部分；提出孪生数据中心数据处理和对比机制，用于存储数据、处理数据、对比数据，连接物理系统和虚拟系统。利用系统支撑服务为各模块提供支撑，包括物理系统内的人员操作系统和AGV控制系统、虚拟系统内的模型搭建方法和方案生成方法、孪生数据中心内的数据处理方法等。与现有调度方法相比，基于数字孪生的集中式调度方法能够及时响应物理系统内的变化，通过维持虚拟系统和物理系统的一致性，保证虚拟系统在物理系统发生变化时实时调整调度方案。因为虚拟系统能够实时反映物理系统状态，所以可以对物理系统的未来变化进行预测，借助提前预测的方式避免AGV运行过程发生冲突，集中优化系统内的AGV运行，提升系统效率。实验证明，利用本文方法可以根据当前系统状态预测未来AGV动向，实现订单实时到达下的RMFS实时调度。在物理系统和调度计划有偏差的情况下，针对物理系统内产生的扰动，能够按照重调度规则进行处理，生成重调度方案并更改物理系统的指令，使物理系统继续运行并避免冲突和死锁。通过对比集中式调度和分布式调度两种调度方法在大量订单实时到达情况下的表现，证明集中式调度能够提升系统效率，获得更好和更稳定的调度结果，而且在系统内冲突严重时，集中式调度能够节约14.4%的完成时间。下一步将围绕快速生成方案的调度优化方法展开研究，加快数字孪生模型的落地实施。