基于改进NSGA-Ⅲ算法的多AGV任务分配

Multi-AGV Path Planning Based on an Improved NSGA-Ⅲ Algorithm

摘要

针对仓库多AGV协同调度的拓扑图法无法考虑行驶冲突，栅格图法需对各AGV行驶路径单独规划，从而浪费算力的问题，提出了一种在栅格地图中采用双通道的建模方法和以冲突路口建立拓扑点映射的方法进行路径规划，无需使用单车寻路算法。在算法方面，针对迭代算法过程中广度和深度不能在前后期合理地兼顾，优化目标单一的问题，提出了一种基于NSGA-Ⅲ的多目标优化算法；将算法中的遗传和交叉概率调整为自适应，交叉改为分段交叉，并保留优秀父代片段，从而提高算法的收敛速度；设置考虑AGV系统的能耗、运行时间、负载标准差3个目标函数，并在栅格地图中多AGV 调度问题上进行了仿真实验。结果表明，提出的NSGA-Ⅲ改进算法具有更好的优化结果，收敛代数分布更小；3个目标函数平均收敛速度相比改进前分别提升了26.7%、33.3%、23.5%。

Abstract

To address the limitations of conventional topological mapping methods for multi-AGV collaborative scheduling in warehouses—particularly the inability to resolve travel conflicts and the computational overhead of separate path planning for each AGV in grid-based approaches—we propose an innovative solution. This method employs dual-channel modeling in grid maps and establishes topological point mappings at conflict intersections for path planning, eliminating the need for single-agent routing algorithms. Algorithmically, we overcome the challenges of balancing breadth and depth during iterative processes and single-objective optimization by introducing a NSGA-III-based multi-objective optimization algorithm. The algorithm incorporates adaptive genetic and crossover probabilities,adopts a segmented crossover scheme, and retains superior parent segments to enhance the algorithm's convergence speed. Three objective functions were defined: energy consumption, operational time, and load standard deviation. Simulation experiments on multi-AGV scheduling in grid maps demonstrated that the improved NSGA-III algorithm achieves better optimization results with smaller convergence algebra distributions. The average convergence speeds of the three objective functions improved by 26.7%,33.3%, and 23.5% respectively compared to pre-improvement benchmarks.

Graphical abstract

关键词

AGV调度 / NSGA-Ⅲ / 路径规划 / 自适应交叉变异 / 分段交叉 / 多目标优化

Key words

AGV scheduling / NSGA-Ⅲ / path planning / adaptive crossover / segment crossover / multi-objective optimization

随着工业生产规模的扩大和电商行业的快速崛起，现代物流和仓储行业快速发展，仓库货物转运、入库、出库的效率要求日益提高。自动导引车（automated guided vehicle，AGV）作为一种重要的自动化运输设备，在提高工作效率和降低人力成本方面的作用日益明显^［1-3］。因此，在复杂的仓储环境中，如何高效地为多自动导引车分配任务和规划路径，确保AGV系统能够快速、准确地完成各类运输任务，是当前研究的一个热点问题。该问题需同时优化多个目标如任务完成时间、能耗、负载均衡等，属于典型的NP（non-deterministic polynomial）难问题^［4-5］。传统算法如遗传算法、粒子群优化在处理高维目标空间时易陷入局部最优且解集分布不均，而非支配排序遗传算法（non-dominated sorting genetic algorithm， NSGA）系列因其高效的帕累托前沿搜索能力成为研究热点，其中第三代非支配排序遗传算法（NSGA-III）通过引入参考点机制和动态种群管理策略，显著提升了高维目标优化问题的收敛性和解集多样性。

虽然NSGA-III算法在解决多目标优化方面表现出色，但其性能在很大程度上依赖于遗传算子的效率。标准的遗传操作如模拟二进制交叉SBX和多项式变异通常采用固定的参数，难以在收敛速度和种群多样性 之间实现动态平衡，从而影响了算法在复杂问题上的求解效果。为了克服这一局限性，本文对NSGA-III的遗传算子进行了2项关键改进：

1） 提出了一种自适应交叉与变异机制，该机制能够根据种群进化过程中的分布特性动态调整算子参数，从而在进化早期促进全局探索，在进化后期加速局部收敛；

2） 设计了一种分段交叉策略，该策略让决策变量根据自身特性进行分段，并在不同段上应用不同的交叉方法，以更精细地挖掘解空间的结构信息，提升生成后代的质量。

这些改进显著增强了算法维持多样性和逼近帕累托前沿的能力。通过上述改进，本文提出了自适应分段交叉与变异的NSGA-III算法，通过引入先进的优化算法和策略，实现对AGV系统的智能化调度和管控。

1 路径规划模型

1.1 建模假设

在利用自动导引车对仓储货物运输时，为节约成本、降低能耗，需要对小车行驶路径进行规划。为研究小车最优行驶路径，需要对行驶路径进行规划建模。为此，特作出如下假设：

1） 仓库内不存在人为或其他障碍物干扰，AGV可以按照计算的最优路线行驶；

2） 任务点之间存在不少于一条通路，所有任务点之间的距离都是已知量；

3） 每台任务车都是由起始点出发，依次到达各任务点后再返回起始点；

4） 所有任务点的作业时间均相同，所有AGV均是相同型号并具有相同性能。

根据上述假设，本文利用栅格法将物流仓库抽象成一个50×50的栅格地图^［6］，每个栅格的边长为栅格最小单位1，栅格中心点坐标为（x，y）；仓库货架与货架之间设计成双通道，所有的AGV在行驶过程中均采用靠右行驶的规则，不存在因狭窄路段而发生对向行驶冲突的问题；利用拓扑图表示AGV行驶的路径段，省去了使用单车寻路算法的时间，提高了协同调度算法的运行效率。物流仓库栅格图和拓扑图如图1所示。

1.2 目标函数构造

在以往的多AGV协同调度中，为研究能耗方便，多默认AGV处于匀速直线和停止2种状态。本文考虑AGV待机状态下各种控制系统及散热系统仍在工作，且AGV在加速、转弯、减速、匀速状态的能耗不同，推导出更符合AGV实际工作状态的能耗公式。

在推导公式之前，需对模型参数及变量进行定义。为此，定义模型参数如下：（x₀，y₀）为AGV的起点坐标；m₀为AGV自重，m为AGV数量，AGV集合为C=｛m_{\mathrm{1}},m_{\mathrm{2}},\cdots ,m_m｝；n为任务数量，任务集合为T=｛n_{\mathrm{1}},n_{\mathrm{2}},\cdots ,n_n｝，每个任务n_p 都是一个包含任务序号p、任务点坐标（x^p，y^p ）、货物质量m^p 的3个元素的集合；第k辆AGV的任务数量为l，则第k辆AGV的任务集合为C_k=｛n_{\mathrm{1}}^k,n_{\mathrm{2}}^k,\cdots ,n_l^k｝；AGV运行速度为v_k 、最大载重为m_max。同时规定单个AGV运输任务总质量不大于小车最大载重，即

{\displaystyle \sum _{i=\mathrm{1}}^l}{m}_i^k\le m_{\mathrm{m}\mathrm{a}\mathrm{x}}（1）

则AGV系统内部额定能耗E₀为

E₀=PT_k， （2）

式中：P为AGV内部各系统的额定效率；T_k 为第k辆AGV的运行时长。

在转弯过程中，由于本文研究的AGV是潜伏式AGV，要先减速至转弯速度，再加速至原速度且转弯半径为0，因此整个转弯过程消耗的能量可以理想化为匀速直线运动消耗的能量，加上加速运动额外消耗的能量，减去减速过程少消耗的能量，再加上全过程内部系统的额定能耗。

AGV在匀速直线运动状态下的驱动力方程为^［7］：

F=C_{\mathrm{r}}Mg(3)

式中：F为AGV的驱动力；C_r表示滚动阻力系数；M表示AGV和运输货物的质量之和；g表示重力加速度。

AGV在加速状态下的驱动力方程为^［7］：

F=C_{\mathrm{r}}Mg+Ma(4)

式中：a表示小车的加速度。

结合AGV行驶过程中的做功W=Fd（d为AGV行驶的位移），可得到AGV从起点到第一个任务点的匀速能耗为：

E_{k\mathrm{1}}=\frac{\left(\left|x_{\mathrm{1}}^k-x_{\mathrm{0}}\right|+\left|y_{\mathrm{1}}^k-y_{\mathrm{0}}\right|\right)\left({\displaystyle \sum _{i=\mathrm{1}}^l}{m}_i^k+m_{\mathrm{0}}\right)g}{\eta }(5)

式中：E_k1表示第k辆AGV从起点到第一个任务点的匀速能耗；（x{}_{\mathrm{1}}^k，y{}_{\mathrm{1}}^k）表示第k辆AGV第一个任务点的坐标；η表示驱动电机功率因数。

AGV在任务之间匀速运动的能耗为：

E_{k\mathrm{2}}=\frac{{\displaystyle \sum _{i=\mathrm{1}}^{l-\mathrm{1}}}\left(\left(\begin{array}{l}\left|x_{i+\mathrm{1}}^k-x_i^k\right|+\\ \left|y_{i+\mathrm{1}}^k-y_i^k\right|\end{array}\right)\left({\displaystyle \sum _{j=\mathrm{1}}^l}{m}_j^k-{\displaystyle \sum _{j=\mathrm{1}}^i}{m}_j^k\right)g\right)}{\eta }(6)

式中：E_{k\mathrm{2}}表示第k辆AGV在任务之间匀速运动的能耗；i表示第k辆AGV的第i个任务。

AGV完成最后一个任务返回起点的匀速能耗为：

E_{k\mathrm{3}}=\frac{\left(\left|x_{\mathrm{0}}-x_l^k\right|+\left|y_{\mathrm{0}}-y_l^k\right|\right)m_{\mathrm{0}}g}{\eta }(7)

式中：E_k3表示第k辆AGV完成最后一个任务返回起点的匀速能耗；（x{}_l^k，y{}_l^k）表示第k辆AGV最后一个任务点的坐标。

假设第k辆AGV在起点和第一个任务点之间、每两个任务点之间、最后一个任务点到起点之间均存在u₁、u₂、\cdots、u_l+1个加减速点和v₁、v₂、\cdots、v_l+1个转弯处，则AGV小车的加速距离d₁为：

d_{\mathrm{1}}=\frac{v^{\mathrm{2}}}{\mathrm{2}a}(8)

式中：v为AGC匀速直线运动的速度。

AGV小车的减速距离d₂为：

d_{\mathrm{2}}=vt+\frac{\mathrm{1}}{\mathrm{2}}{a}_{\mathrm{1}}{t}^{\mathrm{2}}(9)

式中：a₁代表AGV小车减速过程中的加速度。

则第k辆AGV因加速而增加的能耗E_e为：

E_{\mathrm{e}}=\frac{v^{\mathrm{2}}\left[\begin{array}{l}\left(m_{\mathrm{0}}+{\displaystyle \sum _{i=\mathrm{1}}^l}{m}_i^k\right)\left(u_{\mathrm{1}}+v_{\mathrm{1}}\right)+\\ {\displaystyle \sum _{i=\mathrm{1}}^l}\left(m_{\mathrm{0}}+{\displaystyle \sum _{j=\mathrm{1}}^l}{m}_j^k-{\displaystyle \sum _{j=\mathrm{1}}^i}{m}_j^k\right)\left(u_{i+\mathrm{1}}+v_{i+\mathrm{1}}\right)\end{array}\right]}{\mathrm{2}\eta }(10)

减速状态下，由于驱动电机的输出功率会迅速降低到接近于0，且可能会存在制动力，因此本文假设减速过程的耗能和匀速时相同，则第k辆AGV原地转弯过程中旋转消耗的能量为：

E_{\mathrm{s}}=e_{\mathrm{s}}\left[\left(m_{\mathrm{0}}+{\displaystyle \sum _{i=\mathrm{1}}^l}{m}_i^k\right)v_{\mathrm{1}}+{\displaystyle \sum _{i=\mathrm{1}}^l}\left(m_{\mathrm{0}}+{\displaystyle \sum _{j=\mathrm{1}}^l}{m}_j^k-{\displaystyle \sum _{j=\mathrm{1}}^i}{m}_j^k\right)v_{i+\mathrm{1}}\right](11)

式中：E_s表示第k辆AGV原地旋转消耗的能量；e_s为旋转单位质量货物θ角度时消耗的能量；v₁表示起点到第一个任务点的转弯数量；v_i+1表示第i个任务点到第i+1个任务点的转弯数量，当i=l时表示最后一个任务点到起点的转弯数量。

假设AGV每次到达任务点作业时长为t₁、减速时长为t₂、转弯时长为t₃、加速时长为t₄，则第k辆AGV的匀速运动时长t_k 为

t_k=\frac{\left(\begin{array}{l}\left|x_{\mathrm{0}}-x_{\mathrm{1}}\right|+\left|y_{\mathrm{0}}-y_{\mathrm{1}}\right|+\\ {\displaystyle \sum _{i=\mathrm{1}}^{l-\mathrm{1}}}(\left|x_{i-\mathrm{1}}-x_i\right|+\left|y_{i-\mathrm{1}}-y_i\right|)-\\ (d_{\mathrm{1}}+d_{\mathrm{2}}){\displaystyle \sum _{i=\mathrm{1}}^{l-\mathrm{1}}}(u_i+v_i)\end{array}\right)}{v}(12)

第k辆AGV运动总时长T_k 为：

T_k=l\times t_{\mathrm{1}}+t_{\mathrm{2}}{\displaystyle \sum _{i=\mathrm{1}}^{l+\mathrm{1}}}\left(u_i+v_i\right)+t_{\mathrm{3}}{\displaystyle \sum _{i=\mathrm{1}}^{l+\mathrm{1}}}{v}_i+t_{\mathrm{4}}{\displaystyle \sum _{i=\mathrm{1}}^{l+\mathrm{1}}}\left(u_i+v_i\right)+t_k(13)

第k辆AGV的总能耗E_k 为：

E_k=E_{k\mathrm{1}}+E_{k\mathrm{2}}+E_{k\mathrm{3}}+E_{\mathrm{e}}+E_{\mathrm{s}}+E_{\mathrm{0}}(14)

所有小车的总能耗为：

E_{\mathrm{s}\mathrm{u}\mathrm{m}}={\displaystyle \sum _{k=\mathrm{1}}^m}{E}_k(15)

1.3 路径规划

AGV在交叉路口经常碰到路径冲突问题，本文使用了一种基于时间窗（time window）的调度优化方法，通过为每辆AGV分配路径占用时间片，并结合全局优化算法，最小化所有AGV的总通行时间，确保无路径冲突，避免死锁和碰撞，其流程图如图2^［8］所示。

图2中的算法设计主要分为3个层面，第一是将路径资源进行划分，将交叉路口区域划分为路径资源R_j；第二是对时间窗进行分配，采用启发式算法为每辆AGV分配时间窗，确保无冲突；第三是全局优化，使用遗传算法（GA）调整时间窗分配，最小化总通行时间T。

根据图2的流程图，将交叉路口定义为路径资源R_j，每个路径资源的时间窗为W_j=［t_j，start，t_j，end］，AGV小车V_i 在路径资源R_j 上占用时间窗为W_i，j=［t_{i，j，start}，t_i，j，end］。为保证AGV小车顺利通过各交叉路口，路径资源需同时满足以下3个约束条件：

1） 无冲突约束，对于同一路径资源R_j，任意两辆AGV的时间窗W_{i， j} 和W_{k， j} 不得重叠；

2） 顺序约束，AGV必须按照任务顺序依次通过路径资源；

3） 时间连续性约束，AGV在相邻路径资源上的时间窗满足时间连续性。

根据上述规则建立数学模型为^［9］：

\mathrm{m}\mathrm{i}\mathrm{n}T=\mathrm{m}\mathrm{a}\mathrm{x}\left\{t_{\mathrm{1}},t_{\mathrm{2}},\cdots ,t_m\right\}(16)

约束条件为：

\left\{\begin{array}{l}{t}_{i,j,\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}\ge t_{i,j-\mathrm{1},\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}\\ t_{i,j,\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}\ge t_{k,j,\mathrm{e}\mathrm{n}\mathrm{d}}\mathrm{o}\mathrm{r}{t}_{k,j,\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}\ge t_{i,j,\mathrm{e}\mathrm{n}\mathrm{d}}\\ t_i={\displaystyle \sum _j^K}(t_{i,j,end}-t_{i,j,start})\end{array}\right.

式中：K为全局路口总数。

为了验证时间窗调度算法的效果，本文选取3组不同的AGV数量和路口数量，通过随机生成各AGV的起点和终点坐标，对时间窗法和固定优先级法进行了对照实验，结果如表1所示。

表1中的实验初始参数为AGV运行速度1 格/s，时间步长1 s。由表1可知，时间窗法的3组对照试验平均等待时长相比较固定优先级的分别减少了62.5%、66.0%、73.3%。实验结果表明采用时间窗法可以大幅度减少路口等待时长，提升路口通行效率。

2 NSGA-Ⅲ算法调度方案

2.1 算法流程

NSGA-Ⅲ算法作为一种改进的非支配排序遗传算法，在解决多目标优化问题方面具有显著优势。通过结合参考点机制，该算法能够更有效地引导种群进化，从而在复杂的决策空间中寻找到多个优秀的非支配解^［10］。

本研究将NSGA-Ⅲ算法应用于多AGV任务分配与路径规划问题，充分考虑了AGV系统的能耗、运行时间和路径冲突等多个目标，通过构建相应的数学模型（式（5）~（14））和目标函数（式（15）），使得算法能够更准确地评估不同路径和任务分配方案下的能耗情况。此外，本研究还针对AGV任务分配问题的特殊性，对于标准遗传算法的二进制编码不适用于AGV的调度问题，设计了一种能够自然表达任务分配方案且便于遗传操作的结构化编码方式。该方式采用双层混合编码：第一层采用整数编码，表示任务到AGV的分配关系（每个基因位代表任务，值代表分配的AGV编号）；第二层采用排列编码，表示每台AGV内部的任务执行顺序。这种编码方式清晰分离了“分配决策”与“排序决策”，符合调度问题的决策逻辑。另外，通过引入基于时间窗的调度策略，有效解决了AGV在交叉路口的路径冲突问题；同时，为减少迭代次数，在NSGA-Ⅲ算法中引入自适应交叉和变异概率。

改进后的NSGA-III算法流程如图3所示，具体步骤如下：

1） 初始化种群，采用拉丁超立方采样生成初始种群P₀，确保解空间的均匀分布。

2） 进行混合整数编码（路径规划为整数序列，速度参数为实数）。

3） 非支配排序，对种群P_t （第t代种群，为初始种群P₀迭代t次所得）进行Pareto分层，计算个体间的支配关系，生成非支配前沿F₁、F₂、……。

4） 按前沿层级逐层填充下一代候选池，直至个体数超过种群容量N。

5） 采用Das and Dennis系统化方法，在归一化超平面上生成结构化参考点集R，再对目标值进行归一化。归一化公式为^［11］：

f_{\mathrm{i}}^{\mathrm{\text{'}}}=\frac{f_i-z_i^{\mathrm{m}\mathrm{i}\mathrm{n}}}{z_i^{\mathrm{m}\mathrm{a}\mathrm{x}}-z_i^{\mathrm{m}\mathrm{i}\mathrm{n}}},i\in \left\{\mathrm{1,2},\mathrm{3}\right\}(17)

式中：z_i^{\mathrm{m}\mathrm{a}\mathrm{x}}\mathrm{、}{z}_i^{\mathrm{m}\mathrm{i}\mathrm{n}}分别为当前种群各目标的最大值与最小值；f_i 代表某个个体第i个目标函数，分别为总能耗、总时长和负载标准差

6） 将个体映射至参考点，计算个体（即每个候选解）与参考线的垂直距离，并选择最近的参考点。

7） 统计每个参考点关联的个体数，优先选择关联较少的参考点区域的解。

8） 若候选解数量∣P_t+1∣<N，按低层级前沿个体（优先F₁）、参考点关联密度低的区域个体进行填充，然后使用自适应交叉变异算子（SBX、多项式变异）生成的子代种群Q_t；若候选解数量∣P_t+1∣≥N，按前沿等级从低到高删除，即先保留F₁，再从最低等级前沿开始，在同一前沿内删除关联到最拥挤参考点的个体（参考点关联个体数最多的区域）；

9） 循环执行非支配排序、选择、交叉变异等操作，直至满足最大迭代次数T_max^［12］。

2.2 交叉变异改进

假设存在10个任务，任务序列如图4所示。为适应本问题的特点，通过图5中的映射表（4↔7，5↔2，6↔1，7↔4）改进了遗传算法的交叉算子，修复非交叉段的冲突元素，使得父代个体P1=｛\mathrm{1,2},\mathrm{3,4},\mathrm{5,6},\mathrm{7,8},\mathrm{9,10}｝和图4中的任务序列

P2=｛\mathrm{9,10,5},\mathrm{7,2},\mathrm{1,4},\mathrm{6,3},\mathrm{8}｝经交叉段交换后，形成子代C1=｛\mathrm{9,10,2},\mathrm{4,5},\mathrm{6,7},\mathrm{1,3},\mathrm{8}｝、C2=｛\mathrm{6,5},\mathrm{3,7},\mathrm{2,1},\mathrm{4,8},\mathrm{9,10}｝。这种通过建立映射关系并按照映射表改变任务编号，使得交叉之后生成的子代不会出现任务重复完成或任务遗漏的问题，既避免了原本就存在的任务编号与交换来的任务编号相冲突的问题，又确保任务调度序列的完整性和唯一性，从而保留了优秀的任务序列

片段。

为平衡多目标优化过程中全局探索与局部开发的矛盾，本文提出了一种基于参考点分布的自适应交叉与变异概率调整机制。该机制通过动态感知种群多样性状态，自适应调整遗传操作，从而在算法前期增强全局搜索能力，在后期聚焦局部开发效率。自适应调整机制的有关公式定义如下：

1） 平均拥挤度：

C_{\mathrm{a}\mathrm{v}\mathrm{g}}\left(t\right)=\frac{\mathrm{1}}{W}{\displaystyle \sum _{i=\mathrm{1}}^W}{C}_i(18)

式中：C_avg（t）表示平均拥挤度；W为参考点总数；C_i 为第i个参考点关联的个体数量。

2） 历史最大拥挤度：

C_{\mathrm{m}\mathrm{a}\mathrm{x}}\left(t\right)=\mathrm{m}\mathrm{a}\mathrm{x}\left(C_{\mathrm{m}\mathrm{a}\mathrm{x}}\left(t-\mathrm{1}\right),C_{\mathrm{a}\mathrm{v}\mathrm{g}}\left(t\right)\right)(19)

式中：C_max（t）、C_max（t-1）分别表示第t代、第t-1代历史最大拥挤度。

3） 多样性比率：

d\left(t\right)=\frac{C_{\mathrm{a}\mathrm{v}\mathrm{g}}\left(t\right)}{C_{\mathrm{m}\mathrm{a}\mathrm{x}}\left(t\right)}(20)

式中：d（t）表示第t代多样性比率。

4） 交叉概率：

P_{\mathrm{c}}\left(t\right)=P_{\mathrm{c}\mathrm{m}\mathrm{a}\mathrm{x}}-\left(P_{\mathrm{c}\mathrm{m}\mathrm{a}\mathrm{x}}-P_{\mathrm{c}\mathrm{m}\mathrm{i}\mathrm{n}}\right)\times \left(\mathrm{1}-d\left(t\right)\right)(21)

式中：P_{\mathrm{c}}\left(t\right)为交叉概率；P_{\mathrm{c}\mathrm{m}\mathrm{a}\mathrm{x}}为最大交叉概率；P_{\mathrm{c}\mathrm{m}\mathrm{i}\mathrm{n}}为最小交叉概率。

5） 变异概率：

P_{\mathrm{m}}\left(t\right)=P_{\mathrm{m}\mathrm{m}\mathrm{i}\mathrm{n}}+\left(P_{\mathrm{m}\mathrm{m}\mathrm{a}\mathrm{x}}-P_{\mathrm{m}\mathrm{m}\mathrm{i}\mathrm{n}}\right)\times \left(\mathrm{1}-d\left(t\right)\right)(22)

式中：P_{\mathrm{m}}\left(t\right)为变异概率；P_{\mathrm{m}\mathrm{m}\mathrm{a}\mathrm{x}}为最大变异概率；P_{\mathrm{m}\mathrm{m}\mathrm{i}\mathrm{n}}为最小变异概率。

具体的实现步骤为：首先通过统计每个参考点关联的个体数量来反映种群的分布情况；其次，当某些参考点关联的个体过多时，说明种群在这些区域过于集中，需要增强变异概率以增强多样性，当参考点关联的个体数量分布均匀，说明种群多样性好，可以增加交叉概率以促进收敛；最后，根据具体的需要调整概率范围和计算方法。实现步骤的伪代码如下：

Algorithm1：NSGA-Ⅲ

Input：种群大小N，参考点集R，最大进化代数T

Output：近似Pareto最优解集

1： 初始化种群P₀，生成参考点集R

2： 计算P₀的参考点关联，得到C_avg（0），C_max=C_avg（0）

3： for t = 1 to T， do

4： 选择父代个体，基于P_c（t）和P_m（t）通过分段交叉和

多项式变异生成子代Q

5： 合并种群R_t= P_t ∪ Q_t

6： 对R_t进行非支配排序，归一化目标空间，关联参考

点C_avg（t）

7： 计算参考点拥挤度C_avg（t），C_max=max（C_max，C_avg（t））

8： 多样性比率计算d（t）=C_avg（t）/C_max

9： 调整概率：

P_c（t）=P_cmax-（P_cmax-P_cmin）*（1-d（t））

P_m（t）=P_mmin+（P_mmax-P_mmin）*（1-d（t））

10： 选择新一代P_t+1

11： end for

3 仿真实验与分析

3.1 交叉和变异概率仿真实验

为了验证本文提出的基于改进的NSGA-Ⅲ算法在多AGV协同调度上的效果，利用传统的NSGA-III算法及其改进算法，以及NSGA-II算法进行了2组不同的交叉和变异概率仿真实验，实验条件如下：AGV在50×50的栅格地图上运输货物，并随机生成30个任务点，每个任务点货物质量为100~200 kg，AGV自重215 kg、最大负载600 kg、额定运行速度2 m/s、旋转速度150^ο/s。3种算法交叉与变异参数如表2所示。

按表2的实验参数和前面的实验条件，当种群规模为100，随机初始化30个任务时，在MATLAB软件中编写程序代码，并使用orgin软件绘制初始种群与各算法最终种群的分布，以及不同目标函数维度下的种群映射分布，结果如图6所示。

由图6a可知，与初始种群相比，3种算法的最终种群在三维目标空间中显著聚集于左下角并勾勒出前沿边界，这一空间分布特征印证了该解集的非支配性，即任意一个Pareto解均未被其他解所全面超越（即无法在保持其他目标不恶化的前提下，于任一目标上获得进一步改善），该前沿面为决策者提供了一组处于最佳权衡关系的候选方案集合；相比于NSGA-Ⅱ和传统NSGA-Ⅲ算法，改进后的NSGA-Ⅲ算法所求得的Pareto最优解集（球形散点）的位置更靠近左下方，更具有竞争力。由图6b可知，总能耗与总时长呈现反比的趋势，这是因为当AGV任务分配较均匀时，最后完成任务的AGV所用时间相较于任务分配不均匀的最后完成任务的AGV所用时间较长；由图6c可知，负载标准差与总时长呈现正比趋势，这是因为当任务分配均匀时，各AGV完成任务时间比较接近，最后完成任务的AGV所用时间较短；由图6d可知，总能耗与负载标准差呈现反比的趋势，这是因为当AGV采用“就近执行”策略时，在它执行完一个任务后会就近执行距离较近的任务，从而节约能耗，但这会导致与任务较少的AGV的负载质量差值增大。

3.2 稳定性比较

本文以30个任务对上面3种算法进行10次300代迭代计算，获得平均值如图7所示。由图7可知：改进后的NSGA-Ⅲ算法获得的目标函数值最低，收敛速度更快，总能耗、总时长、负载标准差分别大约在110、100、130代趋于稳定，平均收敛速度比对照组（传统NSGA-III和NSGA-II）分别提升约26.7%、33.3%、23.5%（对照组关于总能耗、总时长、负载标准差趋于稳定的最小迭代次数分别约为150、150、170）。因此，相比于其他两种算法，改进后的NSGA-Ⅲ算法收敛速度更快、稳定性更好。

3.3 适应性比较

为验证算法的适应性，采用和上文30个任务相同的基本参数，分别验证了在10、20、40个任务时3种算法迭代300次时，总能耗、总时长、负载标准差的平均最小值如表3所示。由表3可知：在不同任务数量下，改进后的NSGA-Ⅲ算法的3个指标均为最小，说明该算法在不同任务数量下都具有良好的迭代效果。

3.4 IGD、HV指标分析

IGD和HV是多目标优化领域中用于评估算法性能的2个最重要、最常用的性能指标。在多目标问题上，IGD越小，算法的综合性越好；HV值越大，算法的综合性也越好。为验证改进的NSGA-III算法性能，本文从4~40个任务中，每间隔4个任务设计一组试验，共设计10组，结果如表4、表5所示。由表4、表5可以看出，改进后的NSGA-III算法求得的性能指标均优于NSGA-III与NSGA-II算法。显然，改进的NSGA-III算法使种群的收敛性和多样性得到了提高。

为验证性能提升的统计显著性，对表4、表5中的数据采用Wilcoxon符号秩检验，并设置显著性水平α=0.05，各指标统计结果如表6所示，检验结果如表7所示。

从表6可以看出，改进后的NSGA-III算法的IGD平均值、标准差、最大和最小值均小于对比算法，HV平均值、标准差、最大和最小值均大于对比算法。从表7可知，由于改进后的NSGA-III算法在10组对照实验中均取得了最优的IGD和HV值，故检测结果的Z值和P值均为-2.803和0.005，说明改进后的NSGA-III算法使种群收敛性和多样性的提高符合统计显著性。

4 结论

针对标准NSGA-III算法在复杂多目标优化中存在的不足，提出了一种改进的自适应分段交叉与变异的NSGA-III算法。通过自适应遗传算子调整机制，无需人工预先设置参数，能够根据种群的进化状态智能地调整交叉和变异概率，有效平衡了全局探索和局部开发过程，加快了收敛速度；通过引入一种新颖的分段交叉操作，充分考虑了解的空间结构，并对决策变量分段实施差异化交叉，从而生成了更多高质量、多样化的候选解，显著提升了对帕累托前沿的表征能力；最后通过仿真实验，表明本文所提出的改进的NSGA-III算法相比于改进前的NSGA-Ⅲ算法，不仅提高了的搜索广度和收敛速度，在解决多AGV协同调度上还拥有更高的稳定性和迭代效率。但对于更合理的仓库布置以及更具迭代效率的自适应交叉与变异函数设计仍然需要深入研究。

参考文献

[1] 张中伟， 高增恩， 王菁锐， 等. 分布式AGV调度研究综述与发展趋势分析［J］. 制造技术与机床， 2024（11）： 55-61.

[2] 杨凯. AGV发展现状及关键技术综述［J］. 机电工程技术， 2025， 54（13）： 24-30.

[3] 颜伟， 黄冠鹏， 高玉萍， 等. 仓库多AGV路径冲突问题研究综述［J］. 科学技术与工程， 2025， 25（18）： 7465-7474.

[4] 刘燕丽. 基于冲突的NP难问题完备算法的研究［D］. 武汉： 华中科技大学， 2019.

[5] 王健. 危险化学品车辆路径问题及算法研究［D］. 北京： 北京化工大学， 2016.

[6] 徐晗， 金隼， 罗磊， 等. 基于拓扑栅格建模的AGV路径规划算法优化［J］. 计算机工程与设计， 2022， 43（1）： 101-109.

[7] 王占山， 陈晓华， 赵瑞， 等. AGV机器人越障与爬坡驱动力计算分析［J］. 装备制造技术， 2022（10）： 30-33.

[8] 耿焕同， 戴中斌， 王天雷， 等. 基于参考点选择策略的改进型NSGA-III算法［J］. 模式识别与人工智能， 2020， 33（3）： 191-201.

[9] ZARE-REISABADI​​ E， HAMID MIRMOHAMMADI S. Site dependent vehicle routing problem with soft time window： Modeling and solution approach［J］. Computers & Industrial Engineering， 2015， 90： 177-185.

[10] XU X H， CHENG D， WANG D， et al. An improved NSGA-III with a comprehensive adaptive penalty scheme for many-objective optimization［J］. Symmetry， 2024， 16（10）： 1289.

[11] 陈先亮， 黄元君， 范勤勤. 基于多模态多目标进化算法的无人机三维路径规划［J］. 火力与指挥控制， 2023， 48（11）： 32-39.

[12] 毕晓君， 王朝. 一种基于参考点约束支配的NSGA-Ⅲ算法［J］. 控制与决策， 2019， 34（2）： 369-376.

基金资助

安徽省重点实验室开放基金项目(QCKJJ202505)

芜湖市重点研发计划项目(2023ly05)