1　引言

自动化技术的快速发展，推动了自动导引车（automated guided vehicle，AGV）在制造业物流、电商物流等行业的大范围应用，并成为企业提高物流运作效率的主要手段。以近年来蓬勃发展的电商物流为例，不少企业在拣货环节大量引入AGV，来提升作业速度和准确性，满足客户对时效性的要求。例如，亚马逊引入Kiva 机器人系统，将订单拣选时间由1 小时缩短至15 分钟，效率提升4 倍左右。

仓库的自动化升级，使仓库管理由“人管人”的传统模式转变为“系统集中调度所有AGV”的自动化模式。类似的模式也普遍存在于半导体等制造工厂、港口码头、机场、危险品运输等行业。在该模式下，AGV 在线调度问题可定义为多AGV 的多周期循环任务指派和全局无碰撞路径规划。以电商仓库和制造工厂为例，该问题可具体描述为：给定一个封闭的自动化物流场景，如电商仓库中包括货架、拣选台、AGV 和导引道路等，制造工厂则包含多个工序的加工机台、AGV 与导引道路。在特定时间周期内，有一批货物需要从起点运输到指定位置（电商

仓库中将商品从货架运输至拣选台，或制造工厂中完成物料在不同工序之间的周转配送）。仓库或工厂内的所有AGV 由一套调度系统统一管控。当系统接收运输任务后，必须在秒级时间单位内为AGV迅速决策搬运任务和行驶路径，以在最短时间内满足所有任务的运输需求，且不允许发生碰撞等安全事故。AGV 按照系统指令行驶，直至下一周期，系统对空闲AGV 重新调度。循环上述过程，直至当天任务结束。上述过程同时涉及任务指派和路径规划，因此，AGV 在线调度问题具有高度复杂性。

尤其近年来，越来越多的仓库不断增加AGV 数量，规模的扩大进一步提高了调度系统的控制难度［1］。如何在有限的路网资源及AGV 时变状态等约束下，实现多AGV 在线调度系统安全高效地运作，是当前大规模发展智能仓库亟待解决的重要难题。任务指派和路径规划均属于典型的NP-hard问题［2］，现有研究通常聚焦于其中一个方面。针对AGV 任务指派问题，已有不少学者利用启发式算法展开详细讨论。Xu 等［3］融合遗传算法与蚁群算法，

对AGV 任务分配及执行顺序进行研究。Polten 和Emde［4］利用混合整数线性规划模型和大规模邻域搜索算法，研究了窄通道仓库中的AGV 任务分配问题。还有不少学者提出了多种基于启发式规则的指派方法［5，6］。其中，先到先得和最短行程距离优先是最常用的启发式规则［7］。但是，这些文献通常假设AGV 可以按照无碰撞的最短路径行驶，并未考虑AGV 的实际路径规划和冲突情况。另一方面，AGV 的路径规划问题是考虑因素更多的封闭场景车辆路径规划问题，具有三个明显区别于传统车辆路径问题的特征：（1）在自动化仓库中，路网环境

可看作栅格式，栅格间的距离按曼哈顿距离公式计算。（2）AGV 是全自动设备，多辆AGV 同时调度，必须考虑车辆碰撞、路口死锁等情况。（3）AGV 路径规划决策需要精确到每辆AGV 经过的栅格、AGV至每个栅格的到达时间及避撞等待时间、取货时间、运输任务完成时间等。由于AGV 无冲突路径规划问题求解难度较大，现有文献多采用启发式算法进行研究。Fransen 等［8］基于顶点权重动态变化的网格化路网模型，提出了一种多AGV 动态路径规划方法。张丹露等［9］则设计了一种基于交通规则和预约表的改进A*算法。同样采用A*算法，融合时间窗与优先级策略对算法进行改进，研究了AGV 动态避撞路径规划问题。但在此类研究中，大多数文献假设任务分配结果事先已知。综上，现有关于AGV 调度问题的研究多侧重于任务指派或路径规划等单个子问题，仅能实现调度系统的局部优化，同时研究AGV 任务指派及路径规划协同调度的文献较少。

在少数同时考虑多AGV 任务指派与路径规划问题的研究中，李昆鹏等［11，12］利用两阶段算法，研究了静态路网中的AGV 任务分配和路径规划问题。Wang 和Zeng［13］用分支定界算法进行AGV 的作业分配，并基于避撞规则设计启发式算法生成AGV的无冲突路径。但上述研究将任务指派与路径规划分割为两个相对独立的决策过程，仍然不能达到协同优化的效果。同时，由于求解过程涉及精确算法，无法满足在线调度的时间要求。基于此，余娜娜等［14］利用一种集中与分散决策相结合的在线协同调度算法，针对动态环境下多AGV 任务指派与路径规划协同优化问题展开研究。该研究假设路网为单向导引道路，这种路网布局相对简单可靠，却增加了AGV 绕行距离，降低路网效率［15］。相较之下，双向导引路网布局则能够有效提供路网资源利用率［16］，但是需要考虑更复杂的冲突情况，增加了问题复杂度，有关研究较少。此外，AGV 剩余电量、订单最佳服务时间窗等是影响仓库拣选系统安全高效运作，保障服务质量，降低管理成本和AGV损耗的重要因素，却鲜少有研究综合考虑上述约束。同时，一般情况下，AGV 完成任务后，在未指派新任务前，需返回停靠区等待下一任务或充电等。

而现有文献只考虑AGV 从接收任务到完成任务的调度过程，忽略了完成任务后空载AGV 的返回路径，无法实现AGV 的实时闭环管控。在研究方法上，由于AGV 的任务指派和路径规划都是NP-hard 问题，大多数学者更倾向于采用启发式算法，通过比较不同启发式算法的结果，验证算法优劣性。但是，这种对比策略无法分析所提出的启发式算法与最优解的差距。因此，有必要建立可解的数学模型，设计精确算法为衡量启发式算法的效果提供参考。

基于以上分析：

①不同于已有文献仅侧重于任务指派或路径规划等单个子问题，本文研究规则路网环境下的多AGV 任务指派与路径规划协同优化问题。在数学建模中，同时进行任务指派与路径规划决策，以实现仓库的整体运营优化。②为更符合智能仓库实际运作情况，本文设置双向导引路网布局，并综合考虑AGV 电量约束和任务时间窗、无碰撞等特性。以智能仓库某一周期内的所有空载AGV 为研究对象，对“接收任务→取货→送货→返回停靠区”的整个过程展开研究，以实现AGV 的在线周期循环调度。③为满足实时调度的时间要求，本文设计了一套启发式解决方案。同时，还提出了一种分支切割算法，为验证启发式解决方案的质量提供更紧下界。本文主要工作包括：①以单周期内所有AGV 的总运行时间和任务延迟的惩罚成本之和最小为目标，建立了混合整数线性规划数学模型。

②提出了多AGV 任务指派与路径规划协同优化算法（multi-AGV task assignment and path plan⁃ning co-optimization algorithm， MA-TAPPCOA）。

考虑任务与AGV 双重优先规则设计任务指派算法，并设置AGV 优先级规则和多车冲突避免策略。同时提出“ 考虑等待时间、考虑转向代价、考虑重调度效率惩罚、考虑停靠区和货架栅格回避系数、强化方向因子”5 种策略改进传统A*算法，为AGV 设计适应全局路网环境的路径方案。

③利用三类有效不等式并提出相应的分离算法，设计出一种Branch-and-cut 算法，来提高模型求解下界。

④利用CPLEX、分支切割算法和MA-TA-PPCOA 进行算例测试。结果表明：本文引入的分支切割算法能够有效改善模型求解下界，提出的MA-TA-PPCOA算法能够在极短时间内，提供高质量近似最优解。通过进一步分析实验结果，得出了一些关于AGV引进数量和任务批次划分方面的管理启示。研究成果不仅能够为智能仓库的管理与AGV 调度提供决策支持，还能拓展应用到智能生产车间、自动化码头等路网相对规则、自动化程度较高的封闭场景中，为自动化车辆的无碰撞动态调度提供参考借鉴。沿栅格左右、前后移动；②所有AGV 同质且不考虑

刹车、启动过程；③ 在一个调度周期内，一辆AGV最多被指派一项任务。

2　问题描述及数学建模

2.1　问题描述

本文研究智能仓库中多AGV 任务指派与全局路径规划协同优化问题。环境建模是研究该问题的基础，考虑到在智能仓库场景中，路网相对规则、可行区域与非可行区域划分明确、运输任务的起止点及车辆位置精确度要求高，本文采取栅格法进行路网环境建模。如图1 所示，研究问题具体描述如下：给定一个封闭场景，场景路网可划分为等大的正方形栅格。灰色区域表示货架、拣选站台及AGV停靠区。设置双向导引道路，场景内共有K 辆AGV，由调度平台统一指挥。AGV 空载时可在任意栅格转向、暂停、行驶，但负载时，只能在非货架栅格活动。在周期T-1 内，不断有订单任务到达，订单对应的货架、拣选台、最晚服务时间信息已知。

订单处理系统将周期T-1 内的任务需求划为一个批次，并按照任务到达的先后顺序进行编号（先到的任务编号较小）。在周期T 开始时刻，调度系统将指派AGV 完成订单拣选任务，同时基于路网布局为每辆AGV 规划无碰撞的行驶路径。可调用AGV 包含停放在停靠区、空闲但在返回停靠区途中两种状态（小车已完成上一批次任务，但仍在返回停靠区途中时，可指派该批次新任务）。已分配任务的AGV 需从当前位置出发，依次到达所分配任务指定的货架与拣选站台，最终返回停靠区。未分配任务的AGV 需从当前位置出发回到停靠区或静止在停靠区。AGV

设有统一的阈值电量，当剩余电量降至阈值时，AGV需返回停靠区。优化目标是周期T 内，所有AGV 的总运作时间和任务时间窗违反惩罚之和最小。为方便建模，本文考虑以下假设：①AGV 只能沿栅格左右、前后移动；②所有AGV 同质且不考虑刹车、启动过程；③ 在一个调度周期内，一辆AGV最多被指派一项任务。

 2.2　数学模型

  本文建立了一个混合整数线性规划模型，使用的参数、变量符号和定义如表1 所示。

式（1）为目标函数，表示T 时段内，所有AGV的总运行时间和任务延迟惩罚之和最小。式（2）表示一个任务只能分配给一辆AGV，式（3）表示每辆AGV 最多负责同一批次的一个任务，式（4）表示任务m 的延迟时间。式（5）表示AGV 都要在时刻１离开当前位置到达下一栅格，式（6）表示AGV 最终返回停靠区。式（7）表示避免点冲突，即每个栅格同一时刻只能容纳一辆AGV，式（8）表示避免边冲突，即不允许多辆AGV 逆向行驶。式（9）表示每辆AGV 在同一时刻最多经过一条边。式（10）表示每个栅格的AGV 进出流量平衡。式（11）表示AGV 总体路径方案和各阶段路径方案的关系。式（12）表示AGV 运输任务前，第一阶段的路径栅格进出流量平衡，式（13）表示AGV 完成任务后，第三阶段的路径栅格进出流量平衡，式（14）~式（16）保证AGV 第二阶段路径的连续性。式（17）表示AGV k未被指派任务时，第二阶段和第三阶段的路径不存在。式（18）~式（21）表示AGV 一定经过所分配订单的起点和终点。式（22）表示AGV k 负载后，将无法在货架对应的栅格区域通行。式（23）表示AGV k停靠后，其他AGV 将无法在k 对应的停靠栅格通行。式（24）表示执行任务m 的AGV k 在第二阶段到达fm 的时刻即是任务m 的完成时刻。式（25）为AGV 电量约束。式（26）、式（27）表示决策变量。

3　多AGV 任务指派与路径规划协同优化算法

3.1 基于任务与AGV 双重优先规则的指派算法

                     考虑到任务设有最佳服务时间窗，AGV 行驶时间受电量限制，不合适的匹配结果可能导致AGV任务中断或任务延误时间过长。本文提出一个基于任务与AGV 双重优先规则的指派算法。其中，任务优先规则考虑最小最晚服务时间窗优先规则（规则1）、最短负载时间优先（规则2）、最长负载时间优先（规则3）、最大（负载时间/最晚服务时间） 优先（ 规则4）4种，AGV优先规则考虑任务-AGV唯一匹配优先和最短空载时间优先（即优先指派距离任务起点最近的AGV）2 种。需要特别说明：① 每次算法只选定一种任务优先规则，但同时考虑两种

AGV 优先规则。②此外，当任务优先规则与AGV优先规则出现冲突时，规则的优先级顺序为：任务-AGV 唯一匹配优先规则> 任务优先规则>最短空载时间优先规则。如：根据任务优先规则，任务3应优先于任务1 指派AGV。但任务3 可由多辆AGV 搬运，任务1 只能由AGV_1 搬运，则首先考虑将任务1 指派至AGV_1，确定任务1 与AGV_1 的匹配关系，更新待搬运任务和AGV 集。再考虑为任务3 指派距离其最近的AGV。

指派算法具体流程如下：

        步骤1：选定一种任务优先规则i，输入待调度订单集Task 和AGV 集AGV 的状态信息。执行步骤2。

   步骤2：订单排序。将Task 中的所有订单按照任务优先规则i 排序。执行步骤3。

   步骤3：构建Task-AGV 匹配对。针对Task 中的每一个订单，依次判断每辆空闲AGV 执行该订单后，能否在电量允许时间内回到停靠点。

        若能，则将该AGV 归到可执行该项订单的AGV  集合中。执行步骤4。

   步骤4：识别订单与AGV 的唯一匹配。若某项订单m 只能由某一辆AGV k 执行，则确定订单m 的唯一匹配对（m，k），将订单m 指派给AGV k。更新待调度订单集和剩余订单对应的可执行AGV 集，如无法找到唯一匹配对，执行步骤5，否则重复步骤4。

   步骤5：若Task 为空集，则转至步骤7，否则执行步骤6。

   步骤6：空闲AGV 排序。从Task 的第一个订单m 开始，按照“空载时间最短”规则，依次为其分配AGV。更新Task 集和剩余订单的可执行AGV集，返回步骤4。

    步骤7：算法停止，输出订单-AGV 指派结果。

3. 2　多车避撞算法

    避撞和防死锁是实现多辆AGV 路径规划需要考虑的重要内容。本文将根据AGV 任务指派结果和剩余电量等约束，设计车辆优先级规则和冲突避免策略。

  3.2.1 车辆优先级规则

                        规则1：负载AGV 与空载AGV 冲突：

        （1）如空载AGV 的剩余工作时间为0，即剩余电量小于阈值电量，则空载AGV 优先级高；

        （2）如不满足（1），则负载AGV 的优先级高于空载AGV。

     规则2：两辆负载AGV 冲突：

         （1）负载时间窗较小的任务的AGV 优先级高；

         （2）如不满足（1），即任务时间窗相同，则预计最先完成当前搬运任务的AGV 优先级高；

         （3）如不满足（1）和（2），则剩余工作时间较小的AGV 优先级高；

         （4）如不满足（1）~（3），则累计已等待时间较长的AGV 优先级高；

         （5）如不满足上述四种规则，则随机指定AGV 优先通行。

    规则3：若两辆空载AGV 冲突：

            （1）剩余电量小于阈值电量的AGV 优先级高。如两辆AGV 的剩余电量都小于阈值电量，则剩余电量小的AGV 优先级高；

            （2）如不满足（1），则剩余路程较短的AGV优先级高；

            （3）如不满足上述两种规则，则随机指定AGV 优先通行。

3.2.2 多车冲突避免策略

     本文考虑3 种冲突情况：节点冲突，即AGV 在同一时刻到达同一栅格；相向冲突，即在双向导引道路中，两辆相向而行的AGV 在同一栅格发生碰撞；追击冲突，即一辆AGV 停靠在栅格等待其他AGV 通行时，被另一辆AGV 追击而发生碰撞。同时，本文考虑两种避撞策略：等待法和更换路径。

针对节点冲突，优先考虑优先级较低的AGV 在前一栅格停靠等待；针对相向冲突和追击冲突，则选择优先级低的AGV 更换路径。

3.3　考虑五种改进策略的A*算法     

    A*算法是经典的最短路径搜索算法。在该算法中，代价函数的选取直接决定搜索的效率和质量。传统A* 算法的代价函数为F ( n )= g ( n )+h ( n )，其中，F（n）

 表示从起点到终点的估计代价，g（n）表示从起点到位置n 的估计代价，h（n） 表示从位置n 到终点的估计代价。在寻找最短路径问题中，通常以移动距离作为估计代价。

但是，本文研究目标是求解使得所有AGV 运行时间、转向效率惩罚和全部任务延误时间之和最小的解决方案。路网存在多辆AGV 时，单一追求距离最短可能导致AGV 之间的冲突加剧，产生大量的等待时间和任务延迟。因此，本文结合问题特性，从时间维度设置代价函数，对传统A*算法进行改进，具体策略如下：

（1）考虑等待时间。规划AGV 路径时，需要考

虑以下情况：AGV 从当前栅格前往栅格n1，可能与已

规划路径AGV 冲突，进而导致AGV 需要在当前栅

格等待。但AGV 前往另一栅格n2，不会与其他任何AGV 产生冲突。由于AGV 暂停等待，会降低路网通行效率，增加绕路和重调度概率。因此，本文在计算AGV 从当前位置到下一位置的估计代价时，考虑预计等待时间（如图2（a）所示），用wk ( i → n )表示。

    （2）考虑转向代价。频繁转向会大大增加绕路和冲突概率，同时也会损耗AGV 使用寿命。此外，转向代价也是目标函数的组成部分。为更快找到最优解，本文用pk ( i → n )表示车辆v 从栅格i 到栅格n、栅格n 到终点的最小转向代价，其中α 表示单次转向惩罚因子（如图2（b）所示）。

    （3）考虑重调度效率惩罚。当为AGV k1规划路径时，存在k1 驶向栅格n1，会与已规划路径的AGVk2 发生相向碰撞或追击碰撞，且k1 的优先级较高，k2需要重调度的情况。如果重调度情况频繁发生，则会降低算法整体效率。因此，本文考虑加入重调度效率惩罚，用ek ( i → n ) 表示，其中β 表示单车重调度效率惩罚因子（如图2（c）所示）。

    （4）考虑停靠区及货架栅格回避系数。AGV 返回停靠区后将保持静止直到下一调度周期被指派任务，AGV 优先级规则对已停靠AGV 的栅格不起作用。因此，为已停靠AGV 栅格设置回避系数ak ( i → n )。当AGV 下一栅格即将进入停靠区时，检查下一栅格到目标栅格之间是否有AGV 已停靠（完全不可行）。如有，则将下一栅格的回避代价设置为3，否则为0。此外，当AGV 处于搬运状态时，禁止从货架栅格通行。因此，当出现如图2（d）所示的情况时，设置前往栅格n2的回避代价为3。

    （5）强化方向因子。当前栅格和目的栅格一旦确定，两地之间的方向关系随之确定。若AGV 背离目的栅格逆向绕路行驶时，很大程度上会增加转向和全局行驶时间，

       避开最优解。虽然A*算法中，h（n）起到了一定的方向引导作用（式28，其中min Infk表示从n 到目的栅格至少经过的栅格数），但由于行驶时间和等待时间，

       h（n）的导向作用被弱化。因此，本文在代价函数中进一步强化方向因子，增加背离目的栅格的代价。用dk ( i → n ) 表示AGV 从i到n 的方向代价，

      采用式（29）进行计算，其中γ 表示方向惩罚因子，正向行驶为负，逆向行驶为正。

3.4　MA-TA-PPCOA 算法流程

    本文提出的多AGV 任务指派与路径规划协同优化算法具体流程如下：

        步骤1：输入算例信息，调用3. 1 指派算法完成任务指派。执行步骤2。

        步骤2：根据任务指派顺序决定AGV 路径规划顺序：Om 表示排序后的订单集合，Ak 表示Om 对应的搬运AGV 集合，Bk 表示按最小移动距离由小到大排列的空闲AGV              集合，Dk 表示已规划路径的AGV 集合，Rk 表示需要重新调度的AGV 集合。执行步骤3。

        步骤3：若Ak ≠ ∅，则按顺序选择AGVk 为其规划行驶路径，执行步骤5。否则执行步骤4。

        步骤4：若Bk ≠ ∅，则按顺序选择AGVk 为其规划行驶路径，执行步骤5。否则执行步骤6。

        步骤5：调用3. 3“ 改进A*算法”为AGVk 规划路径（具体流程如图3 所示），更新Ak 或Bk，以及Dk、Rk，返回步骤3。

        步骤6：完成所有AGV 的初始路径规划，执行步骤7。

        步骤7：若Rk ≠ ∅，则进入重调度流程：选择Rk首位元素AGV k1 作为重调度车辆k。执行步骤8。若Rk = ∅，跳转至步骤10。

        步骤8：判断与AGV k1 冲突的AGV k2 是否属于Rk。若属于，则k= k2。重复该过程，直至与重调度车辆k 的冲突车辆不在重调度集合中。

            如找不到满足条件的AGV，则k= k1。执行步骤9。

        步骤9：设置重调度AGV k 重调度节点的前一节点作为当前位置，调用3. 3“ 改进A* 算法”为

        AGVk 规划路径，更新Dk、Rk。返回步骤7。步骤10：算法终止，输出任务指派和路径规划结果。

4　分支切割算法

4.1 预处理   

     在大规模整数线性规划问题中，设计一些简单的有效不等式缩减可行域，能够加速模型求解。考虑到本文问题高度复杂且AGV 每一阶段的路径方案均具有明显的“下界”限制，本文提出3 个有效不等式：式（31）~式（34）表示每辆AGV 在三个阶段至少经过的栅格数目。

4.2　有效不等式及分离算法

    本文参考Lam 等［17］，提出有效不等式，并设计对应的分离算法。规定X ke 为布尔变量，当AGV k 经过时空边e（e = {( i1，t - 1 )，( i2，t ) }）时为1，否则为0；e1= {( i2，t - 1 )，( i1，t ) }是与边e 方向互逆的边。4. 2. 1　等待边冲突不等式边e1 和e11是一对互逆边，即e1 = {( i1，t-1 )，( i2，t ) }，e11= {( i2，t - 1 )，( i1，t ) }，e2 ={( i1，t-1 )，( i1，t )}。则任意可行解应当满足以下不等式：

    该式对应的分离算法为：首先，随机选取一条小数边(( i1，t - 1 )，( i2，t ) )，依次检查每个AGV 是否经过该小数边的逆边或在该边的入口栅格处停留（即e2）。令集合S 表示路径与小数边冲突的AGV 集合，如果找到相应的AGV，则将其添加至S中。直至找出所有的冲突AGV，检查是否违反式（35）。然后，选取新的小数边，重复以上过程。

4.2.2　两辆AGV 等待边冲突不等式

   式（36）对应的分离算法为：首先，随机选取一条小数边(( i1，t - 1 )，( i2，t ) )，S1 记录经过边e1 e2 的AGV 集合，S2记录经过边e11或集合E2中任意一边的AGV 集合。对于S1中的每一个元素，依次检查集合S2中的元素是否与其构成违反不等式。然后，选取新的小数边，重复以上过程。式（37）对应的分离算法为：首先，随机选取一条小数边(( i1，t - 1 )，( i2，t ) )，S3记录经过边e1 的AGV 集合，S4记录经过集合E3中任意一边的AGV 集合。对于S3中的每一个元素，依次检查集合S4中的元素是否与其构成违反不等式。然后，选取新的小数边，重复以上过程。

4.2.3 AGV 停靠冲突不等式

4.3　算法流程

5　仿真实验

    本文进行两次实验：①设置12 组小规模算例，分别利用CPLEX 默认算法、本文设计的Branchand-cut 算法、启发式算法进行测试，以验证BC 算法和启发式算法的有效性。②设置48 组、144 个大规模算例。初步实验结果表明，当栅格规模增大到10×10 时，CPLEX 及Branch-and-cut 算法无法启动。因此，第二次实验仅验证启发式算法性能。两次实验环境均为Intel Core i7-10510U 4. 1GHzCPU，RAM 为12GB 的个人计算机，模型求解器为CPLEX 22. 1，启发式算法采用C++ 编码，在Visual Studio2022 平台上实现，Branch-and-cut 在C++中使用ILOG CPLEX 22. 1 的回调实现。参数设置规则：随机生成任务对应的货架栅格和拣选台栅格、每辆AGV 的起点栅格和停靠栅格（不重复）。设定AGV 单位栅格通行时间vt 为1 个时间单位，ct = vt，max Tk = U [ 0，300 ]，lm= U [ 0. 3T，T ]，小规模算例周期T=30，大规模算例周期T=300。问题规模设置见表2。

5.1　基于小规模算例的模型与算法效果测试

             针对12 组小规模算例，设置CPLEX 和Branchand-cut 算法最大运行时间为1800 秒、3600 秒、5400秒三种情况，进行三次实验。MA-TA-PPCOA

算法中单次转向惩罚因子α、单车重调度效率惩罚因子β、方向惩罚因子γ 取值为｛1，1，3｝，结果取四种指派规则下的较优解。最终测试结果如表3 所示。其中，LB1、LB2 分别表示在最大时间限制为3600秒时，CPLEX 和Branch-and-cut算法所得下界值，LB1-1800秒、LB1-5400秒、LB2-1800秒、LB2-5400秒分别表示最大时间限制为1800 秒和5400 秒情况下的下界值。Obj表示启发式算法目标函数值，Time1、Time2、Time3 表示求解时间，Δ1=（LB2-LB1）/LB1×100%、Δ2=（Obj-LB2）/LB2×100%，Ave为平均值。加粗算例行，表示求得最优解。

根据表3 结果可知：①两种精确算法都仅能求得一个算例的最优解。对于该算例， MA-TAPPCOA算法也可求得最优解。②最大运行时间限制会影响CPLEX 获得的LB 质量。在绝大多数算

例中，增加求解时间能够改善LB 值。尤其将求解时间从1800 秒增加至3600 秒时，LB 值改善相对明显。但从3600 秒增加至5400 秒后，LB 值改善效果不大。而对于Branch-and-cuts 算法，求解时间在1800 秒左右，LB 值基本固定。这也进一步说明，本文设计的Branch-and-cut 算法能够在较快时间内，获得比CPLEX 更高质量的LB 值。③在最大求解时间限制=3600 秒情况下，针对未能求得最优解的11 个算例，本文的Branch-and-cut 算法可将CPLEX 下界值平均提高59. 89%，下界改善效果明显。说明本文的Branch-and-cut 算法能够为验证启发式解决方案提供有效参考。④ MA-TAPPCOA最大求解时间不超过0. 1 秒，求解结果与时间限制为3600 秒的Branch-and-cut 算法下界平均gap 值在7% 左右。其中，有3 个算例结果等于下界，为可证明的最优解。因此，本文设计的MATA-PPCOA 算法求解效率极高，同时，提供的可行解绝大部分近似最优，验证了该算法的有效性。

5. 2　基于大规模算例的算法有效性测试

    5.2.1　4 种指派规则对比测试

                        在路径规划阶段，本文提出的改进A*算法中包含三个重要参数：单次转向惩罚因子α、单车重调度效率惩罚因子β、方向惩罚因子γ。为保证参数设置的合理性，考虑8 种情况：( α，β，γ )=｛（1，1，2），（1，1，3），（1，2，2），（1，2，3），（2，1，2），（2，1，3），（2，2，2），（2，2，3）｝，分别测试4 种指派规则下的96 个算例。测试结果表明：① 在10×10 和20×20 两种路网规模下，( α，β，γ ) 设置为（1，1，2）或（1，1，3）时，4种指派规则的求解效果均较好。但同种参数设置下，4 种指派规则的求解效果差别极小。②在40×40 和60×60 两种路网规模下，对于4 种指派规则，( α，β，γ ) 设置为（1，1，3）时，求解效果最好。设置为（2，1，2） 或（2，1，3）时，求解效果最差。这是由于，当转向惩罚过高时，AGV 极易发生为避免转向而绕路行驶，从而进一步增加行驶时间和碰撞概率等。

综合以上情况，最合理的参数设置为( α，β，γ )= (1，1，3)。下文所有实验均采取该参数设置。表4 展示了参数设置为( α，β，γ )= (1，1，3) 的算例测试结果，指派规则对应3. 1 中4 种任务优先规则，算例“10-3-2”表示（路网规模10×10、3 辆AGV、2 个任务）。表4 中展示的数据为每种规模下3个测试算例的平均目标值，Ave 表示每种路网规模下的平均值。根据表4 结果可知：在小、中规模路网中，4种指派规则的求解效果总体相差不大，规则3 和规则1的求解效果略显优势。而在60×60 的大规模路网中，规则1 求解效果明显优于其他三种指派规则。因此，总体来看，规则1 的求解效果和稳定性优于其他三种指派规则。下文所有实验均采用指派规则1。

 5.2.2　5 种改进策略效果测试        

    为测试5 种改进策略的效果，本部分进行5 次实验，每次实验加入一种新的改进策略，测试结果如表5 和图4 所示。Obj1_1~Obj1_5 分别表示添加“ 考虑等待时间”策略、同时添加“ 考虑等待时间+考虑转向代价”策略、同时添加“考虑等待时间+考虑转向代价+ 考虑重调度效率惩罚”策略、同时添加“考虑等待时间+考虑转向代价+考虑重调度效率惩罚+考虑停靠区和货架栅格回避系数”策略、 同时添加5 种改进策略的目标值。Time1_1~Time1_5表示相应的求解时间，其中Time=0. 00 表示求解时间不足0. 01 秒。此外，考虑到AGV 转向过多会造成车体损耗与碰撞概率增加，因此，在本部分及5. 2. 3 的实验中，将AGV 转向次数统计到结果中。图4 为5 次实验结果的堆积折线图，相邻折线之间的差距可表示新增策略的改进效果。

结合表5 和图4 的结果可知：①整体来看，同时添加5 种策略的算法能够获得绝大部分算例的较优解，同时能够在2 秒内求出所有算例的可行解，效率较高。②根据图4，“考虑转向代价”策略对算法的改进效果最为明显，其次是“考虑重调度效率惩罚”策略，“考虑停靠区和货架栅格回避系数”策略的改进效果相对较弱，而“强化方向因子”策略的改进效果最弱。

5.2.3　与传统A*算法对比测试

    本文将添加5 种改进策略的算法实验结果与传统A* 算法对比，结果如图5（主坐标轴表示目标值，次坐标轴表示求解时间）和图6（主坐标轴表示转向次数，次坐标轴表示等待时间）所示：①本文算法求解效果明显优于传统A*算法，可将传统A* 算法的实验结果平均改善27. 69%，且随着算例规模的增大，改善效果更加明显。②本文算法求解效率更高。改进A*算法可在2 秒内得到所有算例的解决方案，平均求解时间为0. 25 秒，对比传统A*算法效率提升130. 01%。③本文算法能够极大降低AGV 转向次数和等待时间，提高路网运作效率和安全性。尤其在大规模路网中，算法改进效果明显。

5.3　灵敏度分析

    （1）订单数量/AGV 数量对各项成本的影响。本文设置｛0. 8，1，1. 2｝三种订单数量与AGV 数量的比例，实验结果如图7 所示，图7 中主坐标轴折线数据表示不同规模算例下，订单与AGV 比例由0. 8上升为1、1 上升为1. 2 时，单车行驶时间（ADT）、转弯次数（ATU）的增加比例。例如，单车行驶时间的计算方式为ADT1-0. 8=100×（ADT1-ADT0. 8）/ADT0. 8。次坐标轴柱状图数据表示单车等待时间（AWT）和订单延误时间（ADA）的增加量。由图7可知：

①当订单数量与AGV 数量比例由0.8 上升为1 时，单车行驶时间和单车转向次数变化趋势一致，但随路网规模增大，增加幅度逐渐稳定在15% 左右。当订单数量/AGV 数量由1 上升至1. 2 时，单车行驶时间和转向次数的增加幅度减弱。

② 当订单数量/AGV 数量由1 上升至1. 2 时，等待时间的增长幅度较大。尤其当AGV 数量/单列栅格数量=1.2时，等待时间增长明显。③当订单数量/AGV 数量=0.8 时，几乎不会出现订单延误情况。但当比例上升至1 时，在大规模路网情况下，订单延误时间增长较多。当比例上升至1. 2 时，延误时间急剧上升。

此外，同比例下AGV 和订单数量越多，延误情况越严重。以上结论可用于指导仓库实践：日常运营中，仓库可通过计算不同时段内空闲AGV 的平均数量，考虑动态调整调度周期间隔或采用动态调整订单批次数量的方法，减少订单延误，提高AGV 利用率。当订单延误对企业运营影响严重且仓库规模较大时，订单批次可设置为0. 8×平均空闲AGV数量，以保证按时完成订单出库任务。

    （2）AGV 密度对路网效率的影响。本文通过设置不同的AGV 数量，分析AGV 密度对路网运作效率的影响，其中AGV 密度=AGV 数量/单列栅格数量。结果如表6 所示。AGV 密度增加对单车总成本的影响较小，但会导致单车等待成本和转向次数的增加，即会产生更多的碰撞和转向情况。尤其在大规模路网中，AGV 密度升高，对路网效率影响更大。考虑到AGV 数量过少，则会造成订单响应不及时，但AGV 数量过多，又会造成路网效率大幅降低。结合表6 中结果，当AGV 数量/单列栅格数量=1. 5 时，三项成本的增长幅度较小，更利于权衡订单响应速度与路网运作效率。因此，建议管理者在导入AGV 时，可优先考虑将AGV 数量设置为仓库单列栅格规模的1. 5 倍。

6　结语

本文以智能仓库为背景，针对规则路网双向导引环境下的AGV 在线任务指派与全局路径规划问题展开研究。首先，采用栅格法进行环境建模，基于双向导引道路、AGV 电量与任务时间窗约束、无碰撞等问题特性，以最小化周期T 内所有AGV 的总运行时间和任务时间窗违反惩罚之和为目标，建立混合整数线性规划模型。

其次，设计了多AGV 任务指派和路径规划协同优化算法：

①同时考虑任务与AGV 双重优先级规则设计4 种指派算法。

②根据AGV 优先级规则和多车冲突避免策略设计避撞算法；

③针对AGV 路径规划，在传统A*算法的基础上设计了5 种改进策略，为AGV 设计适应全局路网状态的路径方案，进而形成一套从任务指派到路线规划的完整调度算法MA-TA-PPCOA。④引入分支切割算法，为验证MA-TA-PPCOA 算法的效果提供高质量下界。最后，利用CPLEX、分支切割算法和MA-TA-PPCOA 算法，针对12 组小规模算例和96 组大规模算例进行测试。

结果表明：①本文引入的分支切割算法能够有效改善模型求解下界，提出的MA-TA-PPCOA 算法能够在极短时间内，提供高质量近似最优解。②4 种优先级规则中，采用“最小最晚服务时间窗优先规则”求解效果最好。此外，5 种A*改进策略均能提升算法求解效果，其中“ 考虑转向惩罚”的改进效果最为显著。③本文算法求解效果和效率明显优于传统A*算法。本文算

法可将传统A*算法的实验结果平均改善27. 69%，效率提升130. 01%。且随着算例规模的增大，改善效果更加明显。④单批次订单数量与AGV 数量的比例和AGV 密度对路网运作效率的影响较大，是仓库管理者重点决策和优化的内容。本文研究成果不仅能够为智能仓库中的任务分配与车辆调度问题提供协同优化决策支持，还能拓展应用到智能生产车间、自动化码头、无人驾驶物流园区等路网相对规则、自动化程度较高的封闭场景中，为自动化车辆的无碰撞动态调度提供参考借鉴。在下一步研究中，可探索直接在目标函数中考虑转弯次数，并深入探讨该问题的数学特性，设计更高效的精确算法或者更有效的启发式策略。

参考文献：

［1］ Yan R D， Jackson L， Dunnett S. A study for furtherexploring the advantages of using multi-load automatedguided vehicles［J］. Journal of Manufacturing Systems，2020， 57： 19-30.

［2］ Jia X， Meng M Q-H. A survey and analysis of task allo⁃cation algorithms in multi-robot systems［C］// Proceed⁃ings of 2013 IEEE international conference on roboticsand biomimetics （ROBIO）， Shenzhen， China，Decem⁃

            ber 12-14， IEEE， 2013： 2280-2285.

［3］ Xu W X， Guo S S， Li X X， et al. A dynamic schedulingmethod for logistics tasks oriented to intelligent manufac⁃turing workshop［J］. Mathematical Problems in Engineer⁃ing， 2019， 2019（1）： 1-18.［4］ Polten L， Emde                     S. Scheduling automated guided vehiclesin very narrow aisle warehouses［J］. Omega， 2021， 99：1-20.

［5］ Chawla V K， Chanda A K， Angra S， et al. Simultane⁃ous dispatching and scheduling of multi-load AGVs inFMS-A simulation study［J］. Materials Today： Pro⁃ceedings， 2018， 5（11）： 25358-25367.

［6］ Heger J， Voss T. Reducing mean tardiness in a flexiblejob shop containing AGVs with optimized combinations

                    of sequencing and routing rules［J］. Procedia CIRP，

［7］ Singh N， Dang Q V， Akcay A， et al. A matheuristic forAGV scheduling with battery constraints［J］. EuropeanJournal of Operational Research， 2022， 298 （3） ：855-873.

［8］ Fransen K J C， Eekelen J A W M V，   Pogromsky A，et al. A dynamic path planning approach for dense，large， grid-based automated guided vehicle systems［J］. Computers & Operations Research， 2020， 123：1-10.

［9］ 张丹露， 孙小勇， 傅顺， 等. 智能仓库中的多机器人协同路径规划方法［J］. 计算机集成制造系统， 2018， 24（2）：410-418.Zhang D L， Sun X Y， Fu S， et al. Cooperative pathplanning in multi-robots for                   ·                                intelligentwarehouse    ［J］.Computer Integrated Manufacturing Systems， 2018， 24（2）：410-418.

［10］ 张新艳， 邹亚圣. 基于改进A*算法的自动导引车无碰撞路径规划［J］. 系统工程理论与实践， 2021， 41（1）：240-246.Zhang X Y， Zou Y S. Collision-free path planning forautomated guided vehicles based on improved A* algo⁃

rithm［J］. Systems Engineering-Theory & Practice，2021， 41（1）： 240-246.［

［11］ 李昆鹏， 刘腾博， 阮炎秋. 半导体生产车间智能AGV路径规划与调度［J］. 计算机集成制造系统， 2022， 28（9）： 2970-2980.Li K P， Liu T B， Run Y Q. Intelligent AGV routingscheduling with applications in semi-conductor         produc⁃tion［J］. Computer Integrated Manufacturing Systems，2022， 28（9）： 2970-2980.

［12］ 李昆鹏， 刘腾博， 贺冰倩， 等 .“ 货到人”拣选系统中AGV 路径规划与调度研究［J］. 中国管理科学， 2022，30（4）： 240-251.Li K P， Liu T B， He B Q， et al. A study on routingand scheduling of automated guided vehicle in“ Cargoto-Picker” system［J］. Chinese Journal of Manage⁃ment Science， 2022， 30（4）： 240-251.

［13］ Wang Z H， Zeng Q C. A branch-and-boundapproach for AGV dispatching and routing problems inautomated container terminals［J］. Computers & Indus⁃trial Engineering， 2022， 166： 1-25.

［14］ 余娜娜， 李铁克， 王柏琳. 自动化分拣仓库中多自动导引小车在线协同调度算法［J］. 计算机集成制造系统， 2022， 28（11）： 3340-3353.Yu N N， Li T K， Wang B L. Multi-AGV online col⁃laborative scheduling algorithm in automated sortingwarehouse［J］. Computer Integrated Manufacturing Sys⁃tems， 2022， 28（11）： 3340-3353.

［15］ 王江华， 楼佩煌， 钱晓明. 基于改进遗传算法的AGVS 单双向混合路径规划［J］. 机械设计与制造工程， 2015， 44（6）： 20-26.Wang J H， Lou P H， Qian X M. Configuring mixeduni/bidirectional guide-path network for automatedguided vehicle system based on improved genetic algo⁃rithm［J］. Machine Design and Manufacturing Engineer⁃ing， 2015， 44（6）： 20-26.

［16］ Kim C W， Tanchocoj J M A. Operational control of abidirectional automated guided vehicle system［J］. Inter⁃national Journal of Production Research， 1993， 31（9）：2123-2138.

［17］ Lam E， Bodic P L， Harabor D， et al. Branch-andcut-and-price for multi-agent path finding［J］. Com⁃puters & Operations Research， 2022， 144： 1-13.

 注释：本文源自中国管理科学期刊，摘录于华中科技大学管理学院（李昆鹏，韩雪芳）

    《智能仓库中多AGV 在线任务指派与全局路径规划问题研究》论文。