图信息和改进型遗传算法相结合的路径规划方法、系统

摘要

本发明涉及仓储路径规划领域，公开了一种图信息和改进型遗传算法相结合的路径规划方法、系统，将不同输送设备布局转化为有向图，并通过有向图对遗传算法所需的种群个体进行编码，根据输送设备参数构建遗传算法中的适应度函数，并能够根据具体业务场景改变适应度函数中的权重，更加贴近实际业务场景；此外，对个体中的固定输送设备节点进行交叉，更加贴近业务实际情况，对个体中的移动输送设备节点进行变异，减少变异后的异常情况。

权利要求

1.一种图信息和改进型遗传算法相结合的路径规划方法，用于为入库和出库规划运行路径，包括以下步骤：

根据仓库内输送设备布局得到有向图，有向图用不同颜色的节点分别代表固定输送设备和移动输送设备；

以出发点在有向图中对应的节点为起始、以目标点在有向图中对应的节点为末端对有向图中节点组成的不同路径进行二进制编码，得到包含不同个体的初始种群，每条二进制编码对应一个个体；对路径L进行二进制编码时，以从出发点到目标点的各必经节点作为分割，将有向图划分为多个层，拥有不同节点数量的层用不同的字母表示，且每个字母后具有表示该层各个节点是否被路径L选中的二进制编码：该层被路径L选中的节点编码为1，未被路径L选中的节点编码为0；

根据每个个体包含节点的信息，构建个体的适应度函数；其中节点信息包括：当前节点去下一个节点的概率值、节点占用情况、节点运行时间、节点长度；

在个体其中一层的固定输送设备节点间进行交叉，并在每个个体其中一层的移动输送设备节点上进行变异，得到候选路径；

通过验证候选路径的路径长度、运行时间来确定最优路径；

适应度函数为 ，其中t0为单次运行最短时间，t为当前路径的运行时间， 为单次运行最短路径长度，为当前路径运行的长度，λ、γ为根据不同输送设备布局和不同业务场景设置的权重；当所有候选路径的路径长度、运行时间无法达到要求时，需要更改权重λ、γ。

2.根据权利要求1所述图信息和改进型遗传算法相结合的路径规划方法，其特征在于：节点信息中节点运行时间与节点长度和输送设备的参数有关；输送设备参数包括最大输送速度、输送加速度。

3.根据权利要求1所述图信息和改进型遗传算法相结合的路径规划方法，其特征在于：所述固定输送设备为板链输送线、滚筒输送线、皮带输送线中的任意一种或者多种；所述移动输送设备为有轨输送车或无轨输送车；当移动输送设备为无轨输送车时，节点信息中的节点长度为无轨输送车的输送距离。

4.根据权利要求1所述图信息和改进型遗传算法相结合的路径规划方法，其特征在于，建立图节点信息：初始状态下有向图各节点之间的转移概率相同，持续统计有向图各节点的条件概率值 ，其中 表示节点i被候选路径选中的概率值， 表示节点i、j同时被候选路径选中的概率值，节点j为节点i的下个节点中的某一候选节点；将候选路径上的所有节点被选中的概率值 ，与非候选路径上所有节点被选中的概率值进行比较，如果两者差值未大于一定值，则提高候选路径上各节点的条件概率值。

5.根据权利要求4所述图信息和改进型遗传算法相结合的路径规划方法，其特征在于：当所有候选路径的路径长度、运行时间无法达到要求时，删除所有候选路径，并更新图节点信息：重置有向图各节点的条件概率，并根据后续得到的路径，重新统计有向图各节点的条件概率值 ；并重新计算各节点的运行时间、节点长度。

6.一种图信息和改进型遗传算法相结合的路径规划系统，包括：图生成模块，根据仓库内输送设备布局得到有向图，有向图的节点代表固定输送设备和移动输送设备；

编码模块，以出发点在有向图中对应的节点为起始、以目标点在有向图中对应的节点为末端对有向图中节点组成的不同路径进行二进制编码，得到包含不同个体的初始种群，每条二进制编码对应一个个体；对路径L进行二进制编码时，以从出发点到目标点的各必经节点作为分割，将有向图划分为多个层，拥有不同节点数量的层用不同的字母表示，且每个字母后具有表示该层各个节点是否被路径L选中的二进制编码：该层被路径L选中的节点编码为1，未被路径L选中的节点编码为0；

适应度函数构建模块，根据每个个体包含节点的信息，构建个体的适应度函数；其中节点信息包括：当前节点去下一个节点的概率值、节点占用情况、节点运行时间、节点长度；

候选路径生成模块，在个体其中一层的固定输送设备节点间进行交叉，并在每个个体其中一层的移动输送设备节点上进行变异，得到候选路径；

最优路径生成模块，通过验证候选路径的路径长度、运行时间来确定最优路径；

适应度函数为 ，其中t0为单次运行最短时间，t为当前路径的运行时间， 为单次运行最短路径长度，为当前路径运行的长度，λ、γ为根据不同输送设备布局和不同业务场景设置的权重；当所有候选路径的路径长度、运行时间无法达到要求时，需要更改权重λ、γ。

说明书

图信息和改进型遗传算法相结合的路径规划方法、系统

技术领域

[0001] 本发明涉及仓储路径规划领域，具体涉及一种图信息和改进型遗传算法相结合的路径规划方法、系统。

背景技术

[0002] 遗传算法（Genetic Algorithm，GA）最早是由美国的 John holland于20世纪70年代提出,该算法是根据大自然中生物体进化规律而设计提出的。是模拟达尔文生物进化论
的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索
最优解的方法。该算法通过数学的方式,利用计算机仿真运算,将问题的求解过程转换成类
似生物进化中的染色体基因的交叉、变异等过程。在求解较为复杂的组合优化问题时,相对
一些常规的优化算法,通常能够较快地获得较好的优化结果。遗传算法已被人们广泛地应
用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。

[0003] 自动化立体仓库中，在同一楼层既有出库操作，又有入库操作，如何使得出入库不堵和出入库整体时间减少成为一大难题。现有技术中将遗传算法应用在仓储领域路径规划
时，均以固定布局为基础，无法针对不同的设备布局进行适应性调整，扩展性差。

发明内容

[0004] 为解决上述技术问题，本发明提供一种图信息和改进型遗传算法相结合的路径规划方法、系统。

[0005] 为解决上述技术问题，本发明采用如下技术方案：

[0006] 一种图信息和改进型遗传算法相结合的路径规划方法，用于为入库和出库规划运行路径，包括以下步骤：

[0007] 根据仓库内输送设备布局得到有向图，有向图的节点代表固定输送设备和移动输送设备；

[0008] 以出发点在有向图中对应的节点为起始、以目标点在有向图中对应的节点为末端对有向图中节点组成的不同路径进行二进制编码，得到包含不同个体的初始种群，每条二
进制编码对应一个个体；对路径L进行二进制编码时，以从出发点到目标点的各必经节点作
为分割，将有向图划分为多个层，拥有不同节点数量的层用不同的字母表示，且每个字母后
具有表示该层各个节点是否被路径L选中的二进制编码：该层被路径L选中的节点编码为1，
未被路径L选中的节点编码为0；

[0009] 根据每个个体包含节点的信息，构建个体的适应度函数；其中节点信息包括：当前节点去下一个节点的概率值、节点占用情况、节点运行时间、节点长度；

[0010] 在个体其中一层的固定输送设备节点间进行交叉，并在每个个体其中一层的移动输送设备节点上进行变异，得到候选路径；

[0011] 通过验证候选路径的路径长度、运行时间来确定最优路径。

[0012] 具体地，节点信息中节点运行时间与节点长度和输送设备的参数有关；输送设备参数包括最大输送速度、输送加速度；移动输送设备，例如RGV输送车，具有货叉，则输送设
备参数还包括货叉伸叉速度、货叉伸叉加速度。节点长度即输送设备的轨道长度。

[0013] 具体地，所述固定输送设备为板链输送线、滚筒输送线、皮带输送线中的任意一种或者多种；所述移动输送设备为有轨输送车或无轨输送车；当移动输送设备为无轨输送车
时，节点信息中的节点长度为无轨输送车的输送距离。

[0014] 具体地，适应度函数为 ，其中t0为单次运行最短时间，t为当前路径的运行时间， 为单次运行最短路径长度，为当前路径运行的长度，λ、γ为根据不同输送设备
布局和不同业务场景设置的权重；当所有候选路径的路径长度、运行时间无法达到要求时，
需要更改权重λ、γ；单次运行最短时间是通过传统的遗传算法，以运行时间最短为目标函
数计算得出的固定时间，单次运行最短路径长度是通过传统的遗传算法以运行距离最短为
目标函数计算得出的固定时间。

[0015] 具体地，建立图节点信息：初始状态下有向图各节点之间的转移概率相同，持续统计有向图各节点的条件概率值 ，其中 表示节点i被候选路径选中的概率值，
表示节点i、j同时被候选路径选中的概率值，节点j为节点i的下个节点中的某一候选
节点；将候选路径上的所有节点被选中的概率值
，与非候选路径上所有节点被选中的概率值进
行比较，如果两者差值未大于一定值，则提高候选路径上各节点的条件概率值；还可以验证
某个候选路径中的各个节点，是否为有向图中上个节点去往下个节点的候选集中，如果下
个节点T2并非上个节点T1的候选集中，则调整下个节点T2的条件概率值；节点T2为上个节
点T1的候选集中即P（T2|T1）大于设定值；因为节点T2和T1均为候选路径中的节点，说明节
点T1更倾向于节点T2，故需要调整节点T2的条件概率值，一般来说，需要提高该值。

[0016] 具体的，当所有候选路径的路径长度、运行时间无法达到要求时，删除所有候选路径，并更新图节点信息：重置有向图各节点的条件概率，并根据后续得到的路径，重新统计
有向图各节点的条件概率值 ；并重新计算各节点的运行时间、节点长度。因为当运行
时间值以及路径长度值达不到现场要求值时，可能是适应度函数中的权重值不合适，也有
可能是图节点信息中的条件概率分布不合理，故需要重新迭代优化遗传算法以及图节点信
息。

[0017] 一种图信息和改进型遗传算法相结合的路径规划系统，包括：

[0018] 图生成模块，根据仓库内输送设备布局得到有向图，有向图的节点代表固定输送设备和移动输送设备；

[0019] 编码模块，以出发点在有向图中对应的节点为起始、以目标点在有向图中对应的节点为末端对有向图中节点组成的不同路径进行二进制编码，得到包含不同个体的初始种
群，每条二进制编码对应一个个体；对路径L进行二进制编码时，以从出发点到目标点的各
必经节点作为分割，将有向图划分为多个层，拥有不同节点数量的层用不同的字母表示，且
每个字母后具有表示该层各个节点是否被路径L选中的二进制编码：该层被路径L选中的节
点编码为1，未被路径L选中的节点编码为0；

[0020] 适应度函数构建模块，根据每个个体包含节点的信息，构建个体的适应度函数；其中节点信息包括：当前节点去下一个节点的概率值、节点占用情况、节点运行时间、节点长
度；

[0021] 候选路径生成模块，在个体其中一层的固定输送设备节点间进行交叉，并在每个个体其中一层的移动输送设备节点上进行变异，得到候选路径；

[0022] 最优路径生成模块，通过验证候选路径的路径长度、运行时间来确定最优路径。

[0023] 本发明中的系统与方法为对应的，对于方法的优选方案，均可以应用于系统。

[0024] 与现有技术相比，本发明的有益技术效果是：

[0025] 将不同输送设备布局转化为有向图，并通过有向图分层的方法对遗传算法所需的种群个体进行编码，根据输送设备参数构建遗传算法中的适应度函数，并能够根据具体业
务场景改变适应度函数中的权重，更加贴近实际业务场景；此外，对个体中的固定输送设备
节点进行交叉，更加贴近业务实际情况，对个体中的移动输送设备节点进行变异，减少变异
后的异常情况（例如路径不通）；整个训练过程中结合图节点信息可以进行自学习整个过
程，打破传统的静态规则优化。

附图说明

[0026] 图1为本发明的流程示意图；

[0027] 图2为本发明将输送设备布局转化为有向图的示意图；

[0028] 图3为本发明对有向图进行分层的示意图；

[0029] 图4为本发明对适应度函数权重进行更新的流程图。

具体实施方式

[0030] 下面结合附图对本发明的一种优选实施方式作详细的说明。

[0031] 如图1所示，一种图信息和改进型遗传算法相结合的路径规划方法，用于为入库和出库规划运行路径，包括以下步骤：

[0032] S1：根据仓库内输送设备布局得到有向图，有向图的节点代表固定输送设备和移动输送设备。

[0033] 固定输送设备为板链输送线、滚筒输送线、皮带输送线中的任意一种或者多种；所述移动输送设备为有轨输送车或无轨输送车；当移动输送设备为无轨输送车时，节点信息
中的节点长度为无轨输送车的输送距离。本实施例中，固定输送设备为板链输送线，移动输
送设备为具有货叉的有轨输送车；图2中的黑色填充节点代表移动输送设备，无填充节点代
表固定输送设备。

[0034] S2：以出发点在有向图中对应的节点为起始、以目标点在有向图中对应的节点为末端对有向图中节点组成的不同路径进行二进制编码，得到包含不同个体的初始种群，每
条二进制编码对应一个个体；对路径L进行二进制编码时，以从出发点到目标点的各必经节
点作为分割，将有向图划分为多个层，拥有不同节点数量的层用不同的字母表示，且每个字
母后具有表示该层各个节点是否被路径L选中的二进制编码：该层被路径L选中的节点编码
为1，未被路径L选中的节点编码为0。

[0035] 因为最终选取的路径需要从出发点指向目标点，故进行个体编码时，需要以出发点在有向图中对应的节点为起始、以目标点在有向图中对应的节点为末端，目标点可以是
仓库出口（即图2中的出口），也可以是某个货架（即图2中的小出入口）。入库和出库时，由于
仓库区域划分的特点，两个区域之间的货物传输时，会存在一定途径的输送设备，就以这些
设备为分割点，将不同区域的输送设备进行分层。

[0036] 在上述分层的基础上，对个体进行编码，由于分层的依据为“从出发点到目标点的各必经节点”，所以本发明中每个个体必然包含有向图的所有层；以字母代表分层，例如：编
码A0A1B01C100D0001，对应一个个体，也是一个从出发点到目标点的路径L，A表示一个节
点，B表示两个节点，C表示三个节点，D表示四个节点，依次类推；该编码表示共分为5层，A1
表示这一层存在一个节点，且该节点被路径L选中；A0表示这一层存在一个节点，且该节点
未被路径L选中；B01表示该层存在两个节点，且有一个节点被路径L选中，另一个节点未被
路径L选中；C100表示该层存在三个节点，第一个节点被路径L选中，剩余两个节点未被路径
L选中；D0001表示该层有四个节点，最后一个节点被路径L选中，剩余三个节点未被路径L选
中。上述编码仅为举例，并不代表实际技术方案会采用与A0A1B01C100D0001相同的编码，仅
用于理解方案使用。

[0037] 如图3所示，第一、二、三层分别存在一个节点，第四层存在两个节点。

[0038] 每层中的节点顺序应当视具体情况而定，一般来说，将移动输送设备与固定输送设备对应的节点交错间隔设置，相当于由固定输送设备到移动输送设备。

[0039] S3：根据每个个体包含节点的信息，构建个体的适应度函数；其中节点信息包括：当前节点去下一个节点的概率值、节点占用情况、节点运行时间、节点长度。

[0040] 节点信息中节点运行时间由节点长度和输送设备的参数有关；输送设备参数包括轨道长度、最大输送速度、输送加速度。移动输送设备，例如RGV输送车，具有货叉，则输送设
备参数还包括货叉伸叉速度、货叉伸叉加速度。

[0041] 适应度函数为 ，其中t0为单次运行最短时间，t为当前路径的运行时间， 为单次运行最短路径长度，为当前路径运行的长度，λ、γ为根据不同输送设备布局
和不同业务场景设置的权重；当所有候选路径的路径长度、运行时间无法达到要求时，需要
更改权重λ、γ，λ为时间权重，γ为路径权重；单次运行最短时间是通过传统的遗传算法，以
运行时间最短为目标函数计算得出的固定时间，单次运行最短路径长度是通过传统的遗传
算法以运行距离最短为目标函数计算得出的固定时间。

[0042] S4：在个体其中一层的固定输送设备节点间进行交叉，并在每个个体其中一层的移动输送设备节点上进行变异，得到候选路径；进行交叉时，本发明随机选择个体相同的一
层，在该层中的固定输送设备节点之间进行交叉，更加的贴近业务实际情况。传统遗传算法
中的变异采用固定的概率值或者自适应的概率值，对于每个个体，本发明随机选择该个体
的一层，对该层中移动输送设备节点进行变异，更加符合实际业务情况，也减少变异后的异
常情况发生，如路径不通等情况。有向图用不同颜色的节点分别代表固定输送设备和移动
输送设备，故进行交叉、变异操作时，根据有向图节点颜色确定每层中各节点代表的输送设
备类型。经过选择、交叉、变异后得到的个体如果不满足条件，则需要重新迭代优化遗传算
法。

[0043] S5：通过验证候选路径的路径长度、运行时间来确定最优路径。

[0044] 路径长度值 ；运行时间值；T(n)为第n个节点的节点运行时间，L(n)为第n个节点
的节点长度；有轨输送设备的节点长度为轨道长度，无轨输送设备的节点长度为输送距离。

[0045] 建立图节点信息：由于缺乏训练数据，开始各节点之间的转移概率值为均分的，随着改进型遗传算法持续候选路径，可以在候选路径中统计各个节点下的条件概率值；步骤
S5中，持续统计有向图各节点的条件概率值 ，其中 表示节点i被候选路径选
中的概率值， 表示节点i、j同时被候选路径选中的概率值，节点j为节点i的下个节点中
的某一候选节点；将候选路径上的所有节点被选中的概率值
，与非候选路径上所有节点被选中的概率值进
行比较，如果两者差值未大于一定值，则提高候选路径上各节点的条件概率值（例如提高
1.2倍，并保持概率值低于1）；因为候选路径相较于非候选路径较优，应当提高候选路径上
各节点的条件概率值，提高这些节点后续被选中的概率。另外持续统计各节点的条件概率
值，便于查看整个有向图的节点被选中概率分布情况，便于后期反向调整有向图各节点的
条件概率值。

[0046] 当运行时间值以及路径长度值达不到现场要求值时，可能是适应度函数中的权重值不合适，也有可能是图节点信息中的条件概率分布不合理，故需要重新迭代优化遗传算
法以及图节点信息，即更改权重λ、γ，删除所有候选路径，并更新图节点信息，更新图节点
信息时：重置有向图各节点的条件概率值，并根据后续得到的候选路径，重新统计有向图各
节点的条件概率值 ，以及各节点的运行时间、节点长度。

[0047] 如图4所示，本实施例中，更改权重λ、γ的流程为：

[0048] 运行时间值、路径长度值超出预期时，λ‑0.05且γ+0.05；运行时间值、路径长度值低于预期时，λ+0.05且γ‑0.05；

[0049] λ低于0.2或者γ低于0.1，确保λ、γ大于下限值，且保证λ+γ之和为1；例如：更新后的λ低于下限值0.1，则λ设为0.1，同时将γ设为0.9；

[0050] λ不低于0.2且γ不低于0.1，则确定权重。

[0051] 一种图信息和改进型遗传算法相结合的路径规划系统，包括：

[0052] 图生成模块，根据仓库内输送设备布局得到有向图，有向图的节点代表固定输送设备和移动输送设备；

[0053] 编码模块，以出发点在有向图中对应的节点为起始、以目标点在有向图中对应的节点为末端对有向图中节点组成的不同路径进行二进制编码，得到包含不同个体的初始种
群，每条二进制编码对应一个个体；对路径L进行二进制编码时，以从出发点到目标点的各
必经节点作为分割，将有向图划分为多个层，拥有不同节点数量的层用不同的字母表示，且
每个字母后具有表示该层各个节点是否被路径L选中的二进制编码：该层被路径L选中的节
点编码为1，未被路径L选中的节点编码为0；

[0054] 适应度函数构建模块，根据每个个体包含节点的信息，构建个体的适应度函数；其中节点信息包括：当前节点去下一个节点的概率值、节点占用情况、节点运行时间、节点长
度；

[0055] 候选路径生成模块，在个体其中一层的固定输送设备节点间进行交叉，并在每个个体其中一层的移动输送设备节点上进行变异，得到候选路径；

[0056] 最优路径生成模块，通过验证候选路径的路径长度、运行时间来确定最优路径。

[0057] 本发明中的系统与方法为对应的，对于方法的实施方式，均可以应用于系统。

[0058] 对于本领域技术人员而言，显然本发明不限于上述示范性实施例的细节，而且在不背离本发明的精神或基本特征的情况下，能够以其他的具体形式实现本发明。因此无论
从哪一点来看，均应将实施例看作是示范性的，而且是非限制性的，本发明的范围由所附权
利要求而不是上述说明限定，因此旨在将落在权利要求的等同要件的含义和范围内的所有
变化囊括在本发明内，不应将权利要求中的任何附图标记视为限制所涉及的权利要求。

[0059] 此外，应当理解，虽然本说明书按照实施方式加以描述，但并非每个实施方式仅包含一个独立技术方案，说明书的这种叙述方式仅仅是为了清楚起见，本领域技术人员应当
将说明书作为一个整体，各实施例中的技术方案也可以经适当组合，形成本领域技术人员
可以理解的其他实施方式。