矩阵制造车间车辆路径规划方法、装置、电子设备及存储介质

1.本发明涉及智能制造技术领域和智能计算技术领域，具体涉及一种矩阵制造车间车辆路径规划方法、装置、电子设备及计算机可读存储介质。


背景技术：

2.随着社会生产力以及科技的快速发展，智能制造车间已成为了未来工业生产线发展的必然趋势。在智能制造产业中，车辆路径问题是物流运输和运输组织优化中的核心问题之一，其研究受到了众多研究学者和制造企业的关注。针对车辆路径规划问题，企业中大多数采用先叫先到原则和最短路径方法对车间进行规划。在该调度方法下，控制系统根据生产设备呼叫时间规划agv调度顺序，该方法容易导致绕路，使缓冲器的总等待时间大大延长。考虑到该问题是一个np-hard的组合优化问题，启发式和元启发式方法比精确算法更加适合问题。
3.对于组合优化问题，混合多种智能优化算法是提高算法求解性能的重要手段之一。因而，如何有效组合多种算法的机制，提取各种算法的局部搜索方法进行有效组合，成为了目前车辆路径问题研究的重点问题之一。


技术实现要素：

4.针对上述至少一个技术问题，本发明提供了一种矩阵制造车间车辆路径规划方法、装置、电子设备及计算机可读存储介质。
5.本发明的第一个目的是在于提供一种矩阵制造车间车辆路径规划方法。
6.本发明的第二个目的是在于提供一种矩阵制造车间车辆路径规划装置。
7.本发明的第三个目的在于提高一种电子设备。
8.本发明的第四个目的在于提供一种计算机可读存储介质。
9.本发明的第一个目的可以通过采取如下技术方案达到：
10.一种矩阵制造车间车辆路径规划方法，所述矩阵制造车间包括多台agv以及多个任务，所述方法包括：
11.根据agv的行驶距离和任务的交货时间，通过最近邻算法和随机算法生成n条染色体向量，将n条染色体向量作为初始化的种群；
12.采用改进的遗传算法对初始化的种群进行迭代处理，直到满足迭代条件，获得总成本最小的多条agv路径；
13.所述采用改进的遗传算法对初始化的种群进行迭代处理，包括：
14.采用交叉操作和变异操作更新初始化的种群；
15.基于约束条件，将更新后种群中的染色体向量转化为agv的路径解，计算路径解的总成本，保留总成本最小的n条染色体向量作为后代；
16.根据保留的n条染色体向量，将路径解中最少任务的路径合并到其他路径中，得到合并后染色体向量；将合并后染色体向量作为下一次迭代的初始化的种群。
17.进一步地，所述根据agv的行驶距离和任务的交货时间，通过最近邻算法和随机算法生成n条染色体向量，包括：
18.根据agv的行驶距离和任务的交货时间，通过最近邻算法生成n1条染色体向量；若n为偶数，则n1＝n/2，否则n1＝int(n/2)+1；
19.通过随机算法生成int(n/2)条染色体向量；
20.将最近邻算法生成的染色体向量和随机算法生成的染色体向量合并成完整的n条染色体向量，作为初始化的种群。
21.进一步地，所述根据agv的行驶距离和任务的交货时间，通过最近邻算法生成n1条染色体向量，包括：
22.根据agv的行驶距离、任务的交货时间以及α值，计算适应度值；其中，α∈[0,1]表示平衡行驶距离和交货时间的权重参数；
[0023]
寻找适应度值最低的任务作为下一个服务对象；
[0024]
若所有任务都分配完成，则所有任务按服务顺序构成一条染色体向量，否则，将所述服务对象所在位置作为agv当前位置，并返回根据agv的行驶距离、任务的交货时间以及α，继续执行后续操作；
[0025]
若已生成n1条染色体向量，则结束操作，否则，更新α值，并返回根据agv的行驶距离、任务的交货时间以及α，继续执行后续操作。
[0026]
进一步地，所述采用交叉操作和变异操作更新初始化的种群，包括：
[0027]
从所述种群中随机选择两条染色体向量作为父代，采用交叉操作生成两条染色体向量的后代；
[0028]
对交叉操作生成的两条染色体向量分别采用变异操作，生成新的染色体向量；
[0029]
若已执行交叉操作和变异操作n次，则将所有新生成的2n条染色体向量作为更新后种群，否则，返回从所述种群中随机选择两条染色体向量作为父代，并继续执行后续操作。
[0030]
进一步地，所述变异操作，具体为：
[0031]
从染色体向量中选择两组相连的l个任务，并将这两个任务进行交换，得到新染色体向量，其中，l取{1,2,3}中的任意一个值。
[0032]
进一步地，所述从所述种群中随机选择两条染色体向量作为父代，采用交叉操作生成两条染色体向量的后代，包括：
[0033]
将两条染色体向量中的一个作为第一条染色体向量，将第一条染色体向量的第一个任务作为参考任务；将另一条染色体向量从左到右进行移动，直至第一个任务与所述参考任务一致；
[0034]
针对第一条染色体向量和移动后的染色体向量，在α为设定值时，根据染色体向量的头两个任务的行驶距离、任务的交货时间以及α值，分别计算两条染色体向量的头两个任务的适应度值；选择适应度值较小的染色体向量的第二个任务作为参考任务，将另一条染色体向量从左到右进行移动且保持第一任务不变，直至第二个任务与所述参考任务一致，此时两条染色体向量的头两个任务一致；将头两个任务一致的两条染色体向量作为所述两条染色体向量的后代；其中α∈[0,1]表示平衡行驶距离和交货时间的权重参数。
[0035]
进一步地，所述约束条件包括时间窗约束和装载量约束，所述时间窗约束为agv必
须在任务的叫料时间和交货时间的时间窗内达到指定任务，所述装载量约束指每台agv服务的所有任务所需的物料重量不得超过每台agv的总装载量；
[0036]
所述更新后种群包括2n条染色体向量；
[0037]
基于约束条件，将更新后种群中的一条染色体向量转化为agv的路径解，包括：
[0038]
依次判断染色体向量中的多个任务是否满足所述约束条件；
[0039]
若满足，则将当前任务加入到当前agv路径中，否则，重新生成一条新路径，并将当前任务加入到新路径中；
[0040]
若所有任务遍历完毕，则得到染色体向量对应的agv路径解。
[0041]
进一步地，所述根据保留的n条染色体向量，将路径解中最少任务的路径合并到其他路径中，包括：
[0042]
获取n条染色体向量中最佳agv使用数量以及当前解agv使用数量r；
[0043]
若则结束操作；否则，继续执行后续操作；
[0044]
根据各路线中客户数量对r条路线由大到小进行排序；
[0045]
将客户最少的路线插入到其他条路线中；
[0046]
若不满足约束条件，则：返回若并继续执行后续操作；否则，结束操作；所述约束条件包括时间窗约束和装载量约束，所述时间窗约束为agv必须在任务的叫料时间和交货时间的时间窗内达到指定任务，所述装载量约束指agv服务的所有任务所需的物料重量不得超过总装载量。
[0047]
进一步地，所述路径解的总成本包括agv的行驶成本f1、使用成本f2以及惩罚时间成本f3，各个成本计算公式如下：
[0048][0049][0050][0051]
其中，m表示任务的数量，k表示agv的总台数；d
ij
表示任务i(xi,yi)和任务j(xj,yj)之间的行驶距离；l
ijk
用于表示第k台agv和任务i，j之间的关系，当l
ijk
＝1表示第k台agv的路径是从任务i到任务j，否则代表第k台agv未经过任务i和任务j；ud表示agv的行驶单位成本；uv表示单台agv的调用成本；u
p
表示agv的早到惩罚单位成本；t
id
表示任务i的交货时间；表示第k台agv到达任务i的时间。
[0052]
本发明的第二个目的可以通过采取如下技术方案达到：
[0053]
一种矩阵制造车间车辆路径规划装置，所述矩阵制造车间包括多台agv以及多个任务，所述装置包括：
[0054]
种群初始化模块，用于根据agv的行驶距离和任务的交货时间，通过最近邻算法和随机算法生成n条染色体向量，将n条染色体向量作为初始化的种群；
[0055]
路径目标最优生成模块，用于采用改进的遗传算法对初始化的种群进行迭代处
理，直到满足迭代条件，获得总成本最小的多条agv路径；所述采用改进的遗传算法对初始化的种群进行迭代处理，包括：采用交叉操作和变异操作更新初始化的种群；基于约束条件，将更新后种群中的染色体向量转化为agv的路径解，计算路径解的总成本，保留总成本最小的n条染色体向量作为后代；根据保留的n条染色体向量，将路径解中最少任务的路径合并到其他路径中，得到合并后染色体向量；将合并后染色体向量作为下一次迭代的初始化的种群。
[0056]
本发明的第三个目的可以通过采取如下技术方案达到：
[0057]
一种电子设备，包括处理器以及用于存储处理器可执行程序的存储器，所述处理器执行存储器存储的程序时，实现上述的矩阵制造车间车辆路径规划方法。
[0058]
本发明的第四个目的可以通过采取如下技术方案达到：
[0059]
一种计算机可读存储介质，存储有程序，所述程序被处理器执行时，实现上述的矩阵制造车间车辆路径规划方法。
[0060]
本发明相对于现有技术具有如下的有益效果：
[0061]
本发明提供的多矩阵制造车间车辆路径规划方法、装置、电子设备及存储介质，所述矩阵制造车间包括多台agv以及多个任务，根据agv的行驶距离和任务的交货时间，通过最近邻算法和随机算法生成n条染色体向量，将n条染色体向量作为初始化的种群；采用改进的遗传算法对初始化的种群进行迭代处理，直到满足迭代条件，获得总成本最小的多条agv路径；所述采用改进的遗传算法对初始化的种群进行迭代处理，包括：采用交叉操作和变异操作更新初始化的种群；基于约束条件，将更新后种群中的染色体向量转化为agv的路径解，计算路径解的总成本，保留总成本最小的n条染色体向量作为后代；根据保留的n条染色体向量，将路径解中最少任务的路径合并到其他路径中，得到合并后染色体向量；将合并后染色体向量作为下一次迭代的初始化的种群。在初始化种群时，将行驶距离和交货时间作为评价指标，通过利用最近邻算法和随机算法获得高质量的初始化路径解，可以有效地引导改进的遗传算法进行高效的搜索，有利于获取最优解决方案解；通过采用改进的遗传算法对多agv进行综合调度，避免绕路，确保在较短路程里准时交付。
附图说明
[0062]
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图示出的结构获得其他的附图。
[0063]
图1为本发明实施例1的矩阵制造车间车辆路径规划方法的流程图；
[0064]
图2为本发明实施例1的矩阵制造车间结构图；
[0065]
图3为本发明实施例1的最近邻算法和随机算法的流程图；
[0066]
图4为本发明实施例1的交叉变异方法的流程图；
[0067]
图5为本发明实施例1的交叉操作的原理图；
[0068]
图6为本发明实施例1的变异操作的原理图；
[0069]
图7为本发明实施例1的合并操作的流程图；
[0070]
图8和图9为本发明实施例1的车辆路径规划结果；
[0071]
图10为本发明实施例2的矩阵制造车间车辆路径规划装置的结构框图；
[0072]
图11为本发明实施例3的电子设备的结构框图。
具体实施方式
[0073]
为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明的一部分实施例，而不是全部的实施例，基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。应当理解，描述的具体实施例仅仅用以解释本技术，并不用于限定本技术。
[0074]
实施例1：
[0075]
为了求解多agv在拥有时间窗和装载量约束的矩阵制造车间路径规划问题，如图1所示，本实施例提供了一种矩阵车间多agv路径规划方法，包括以下步骤：
[0076]
s1、基于最近邻算法与随机算法的种群初始化。
[0077]
初始化的种群包括n条染色体向量。
[0078]
在执行步骤s1之前，确定矩阵制造车间的类型，参考图2。本实施例所采用矩阵制造车间由k台agv以及m个任务构成，所述任务即工作站在生产过程中根据任务缓冲区中的物料剩余情况，向控制中心发送请求信息，所述工作站由多台数控机床和一个缓冲区构成，所述请求信息包括叫料时间、交货时间、缓冲区库存。总成本包括agv的行驶成本f1、使用成本f2以及惩罚时间成本f3，各个成本计算公式如下：
[0079][0080][0081][0082]
其中，d
ij
表示任务i(xi,yi)和任务j(xj,yj)之间的行驶距离；l
ijk
用于表示agvk和任务i，j之间的关系，当l
ijk
＝1时表示，agvk的路径是从任务i到任务j，反之，则代表agvk未经过任务i和任务j；ud表示agv的行驶单位成本；uv表示单台agv的调用成本；u
p
表示agv的早到惩罚单位成本；t
id
表示任务i的交货时间；表示agvk到达任务i的时间；agvk表示第k台agv。
[0083]
在本实施例中，设置矩阵车间基本参数为：agv数量k为10，任务个数m分别为10和20，agv缓冲区总库存为50，agv总载重为250，ud为1，uv为200，u
p
为0.1。
[0084]
在执行步骤s1之前，对遗传算法参数进行初始化。本实施例中，设置算法各项基本参数为：染色体数量n为150，算法终止条件为最大运行时间设为5s。
[0085]
进一步地，如图3所示，步骤s1通过最近邻算法和随机算法获得n条染色体向量，具体包括：
[0086]
s101、基于最近邻算法，根据agv在制造车间的位置(初始位置为仓库)，计算agv与
未分配任务之间的行驶距离。
[0087]
s102、通过下式计算agv与未分配任务的适应度值：
[0088]fci
＝αd
ci
+(1-α)t
id
[0089]
其中，d
ci
表示agv当前位置c(xc,yc)与任务i(xi,yi)之间的行驶距离，c,i∈{0,1,2,...,m}，其中0表示仓库；α∈[0,1]表示平衡行驶距离和交货时间t
id
的权重参数。
[0090]
s103、寻找适应度值最低的任务作为下一个服务对象，并将服务对象所在位置作为agv当前位置，继续执行步骤s101～s102，直至所有任务都分配完成，此时，所有任务的服务顺序构成一条染色体向量。
[0091]
执行一次步骤s101～s103，可以生成一条染色体向量；重复执行n/2次步骤s101～s103，且在执行的过程中通过更新步骤s102中的α值，则可以生成n/2条染色体向量。通过更新α生成具有多样性的染色体向量。
[0092]
在一个实施例中，α的取值选择为[0,1]之间的n/2等份值，即每个值对应生成一条染色体向量。
[0093]
s104、通过随机算法生成n/2条染色体向量。
[0094]
计算公式如下：
[0095]
p＝sort(rand(1,m))
[0096]
其中，rand(1,m)表示生成m个[0,1]之间的随机数，sort(
·
)将随机数按从小到大的顺序返回对应的排序序号，所述排序序号则可作为一条染色体向量。例如生成的一组随机数为：0.2 0.4 0.1 0.5 0.3，则对应的排序序号是2 4 1 5 3(0.1最小，所以排序是1)，即生成的一条染色体向量为[2,4,1,5,3]。
[0097]
利用上述公式可以生成n/2条染色体向量。
[0098]
将最近邻算法生成的n/2条染色体向量和随机算法生成的n/2条染色体向量合并成完整的n条染色体向量，作为初始化的种群。
[0099]
本步骤s1中的n若为偶数，则通过最近邻算法和随机算法各生成n/2条染色体向量；n若为奇数，则通过最近邻算法生成int(n/2)+1条染色体向量，通过随机算法生成int(n/2)条染色体向量。
[0100]
本实施例通过基于最近邻算法和随机算法对任务进行排序，获得初始化的种群；在种群的初始化过程中将行驶距离和交货时间作为评价指标，以获得高质量的初始化路径解，有效地引导算法进行高效的搜索，有利于最优解决方案解的获取。
[0101]
s2、对初始化的种群，采用交叉变异方法进行更新。
[0102]
进一步地，如图4所示，步骤s2具体包括：
[0103]
s201、从种群的n条染色体向量中随机选择两条染色体向量作为父代，采用交叉操作生成两条染色体向量的后代。
[0104]
对两条染色体向量采用交叉操作产生新的一代，以继承父代的基本特征，具体包括：
[0105]
(1)将第一条的染色体向量的第一个任务作为参考任务，按照所述参考任务，将另一条染色体向量从左到右进行移动，直至所述另一条染色体向量的第一个任务与所述参考任务一致；将第一条染色体向量和移动后的染色体向量作为下一步骤的操作对象；
[0106]
(2)计算两条染色体向量在α＝0.5时的头两个任务的适应度值，选择适应度值较小的一组的第二个任务作为参考任务；按照所述参考任务将另一组的染色体向量从左到右进行移动(保持第一任务不变)，直至另一组染色体向量的头两个任务与适应度值较小的染色体向量一致，此时两条染色体向量的头两个任务一致；将头两个任务一致的两条染色体向量作为两条染色体向量的后代。
[0107]
采用交叉操作产生新的两条染色体向量的过程参见图5。
[0108]
s202、对交叉操作生成的两条染色体向量分别采用变异操作，生成新的染色体向量。
[0109]
变异操作具体为：
[0110]
从{1,2,3}中随机选择一个赋值给l，选择染色体向量中的两组相连的l个任务，并将这两组任务进行交换，得到一个新染色体向量。
[0111]
采用变异操作产生新一条染色体的过程参见图6。
[0112]
判断上述步骤s201～s202是否重复执行n次，若是，则执行步骤s203，否则，返回步骤s201并继续执行后面的操作。
[0113]
s203、通过执行步骤s201～s202的交叉变异方法，获得2n条染色体向量。
[0114]
s204、基于约束条件将染色体向量转化为agv的路径解，计算所述路径解的总成本，保留更优的染色体向量作为后代。
[0115]
约束条件包括时间窗约束和装载量约束，其中，时间窗约束为agv必须在任务的叫料时间和交货时间的时间窗内达到指定任务，装载量约束指每台agv的总装载量，一台agv服务的所有任务所需的物料重量不得超过总装载量。
[0116]
进一步地，步骤s204具体包括：
[0117]
(1)针对交叉变异后的染色体向量，依次判断所述染色体向量中的任务是否满足所述约束条件；
[0118]
(2)若所选任务符合所述约束条件，则，将其加入到当前agv路径中；否则：重新生成一条路径，并将所述任务加入到新路径中；
[0119]
(3)通过以上过程，将2n条染色体向量转化为2n个agv的路径方案。
[0120]
s205、计算路径解的总成本，选择总成本最小的n条染色体向量作为染色体后代。
[0121]
总成本计算公式如下：
[0122]
minf＝f1+f2+f3[0123]
本实施例通过交叉变异方法充分挖掘和利用父代染色体中的优质信息。
[0124]
s3、通过合并操作进一步优化所述agv的路径解。
[0125]
合并操作是通过将路径解中最少任务的路径合并到其他路径中。将最少任务的路径中的任务依次加入到其他路径中，若满足所述约束条件，则更新对应的染色体向量。
[0126]
进一步地，如图7所示，步骤s3具体包括：
[0127]
s301、获取种群中最佳agv使用数量r以及当前解agv使用数量r；
[0128]
若则执行步骤s302，反之，则结束操作；
[0129]
s302、根据各路线中客户数量对r条路线由大到小进行排序；
[0130]
s303、尝试将客户最少的路线插入到其他条路线中；若不满足约束条件，则更新返回，若并继续执行步骤s302；
[0131]
若满足约束条件，则结束操作；
[0132]
将经过合并操作后的染色体向量作为下一次迭代的初始化种群。
[0133]
本实施例通过合并操作，最大程度地减少解中agv的使用数量，从而获得矩阵制造车间总成本最小的多条agv路径。
[0134]
s4、根据迭代结束条件，输出全局最优解。
[0135]
在本实施例中，在执行完步骤s1～s3后，判断是否满足迭代结束条件，如果满足迭代结束条件，则输出全局最优解，全局最优解便是要确定的路径目标最优值。如果不满足迭代结束条件，则转入下次迭代过程，即重新执行步骤s2～s3。
[0136]
其中迭代结束条件可以设置为达到预设的最大迭代次数或者最大运行时间。
[0137]
图8和图9是矩阵制造车间多agv的路径规划结果。图中圆圈代表任务所在位置，
△
为仓库位置，默认为(0,0)，数字代表agv的服务顺序。其中，图8的矩阵制造车间任务信息如表1。
[0138]
表1矩阵制造车间任务信息表
[0139][0140]
本实施例中，所获得的车辆路径规划方案可应用于矩阵制造车间的物流运输中，也就是将矩阵制造车间的物料运输路线设定为通过执行上述步骤所确定的最优方案解。在矩阵制造车间类型不变的情况下，通过有效规划agv的行驶路径和使用数量，可以减少矩阵制造车间的劳动力成本和提高车间生产效率。
[0141]
本实施例中，首先，通过基于最近邻算法和随机算法对任务进行排序，获得初始化的种群；在初始化的过程中将行驶距离和交货时间作为评价指标，获得高质量的初始化路径解，可以有效地引导改进的遗传算法进行高效的搜索，有利于最优解决方案解的获取；其次，在改进的遗传算法中通过交叉操作和变异操作充分挖掘和利用父代染色体中的优质信息；最后，改进的遗传算法中通过合并操作，最大程度地减少解中agv的使用数量。
[0142]
本领域技术人员可以理解，实现上述实施例的方法中的全部或部分步骤可以通过程序来指令相关的硬件来完成，相应的程序可以存储于计算机可读存储介质中。
[0143]
应当注意，尽管在附图中以特定顺序描述了上述实施例的方法操作，但是这并非要求或者暗示必须按照该特定顺序来执行这些操作，或是必须执行全部所示的操作才能实现期望的结果。相反，描绘的步骤可以改变执行顺序。附加地或备选地，可以省略某些步骤，将多个步骤合并为一个步骤执行，和/或将一个步骤分解为多个步骤执行。
[0144]
实施例2：
[0145]
如图10所示，本实施例提供了一种矩阵制造车间车辆路径规划装置，所述矩阵制造车间包括多台agv以及多个任务，所述装置包括种群初始化模块1001和路径目标最优生成模块1002，其中：
[0146]
种群初始化模块1001，用于根据agv的行驶距离和任务的交货时间，通过最近邻算法和随机算法生成n条染色体向量，将n条染色体向量作为初始化的种群；
[0147]
路径目标最优生成模块1002，用于采用改进的遗传算法对初始化的种群进行迭代处理，直到满足迭代条件，获得总成本最小的多条agv路径；所述采用改进的遗传算法对初始化的种群进行迭代处理，包括：采用交叉操作和变异操作更新初始化的种群；基于约束条件，将更新后种群中的染色体向量转化为agv的路径解，计算路径解的总成本，保留总成本最小的n条染色体向量作为后代；根据保留的n条染色体向量，将路径解中最少任务的路径合并到其他路径中，得到合并后染色体向量；将合并后染色体向量作为下一次迭代的初始化的种群。
[0148]
本实施例中各个模块的具体实现可以参见上述实施例1，在此不再一一赘述；需要说明的是，本实施例提供的装置仅以上述各功能模块的划分进行举例说明，在实际应用中，可以根据需要而将上述功能分配由不同的功能模块完成，即将内部结构划分成不同的功能模块，以完成以上描述的全部或者部分功能。
[0149]
实施例3：
[0150]
本实施例提供了一种电子设备，该电子设备可以为计算机，如图11所示，其通过系统总线1101连接的处理器1102、存储器、输入装置1103、显示器1104和网络接口1105，该处理器用于提供计算和控制能力，该存储器包括非易失性计算机可读存储介质1106和内存储器1107，该非易失性计算机可读存储介质1106存储有操作系统、计算机程序和数据库，该内存储器1107为非易失性计算机可读存储介质中的操作系统和计算机程序的运行提供环境，处理器1102执行存储器存储的计算机程序时，实现上述实施例1的矩阵制造车间车辆路径规划方法，如下：
[0151]
根据agv的行驶距离和任务的交货时间，通过最近邻算法和随机算法生成n条染色体向量，将n条染色体向量作为初始化的种群；
[0152]
采用改进的遗传算法对初始化的种群进行迭代处理，直到满足迭代条件，获得总成本最小的多条agv路径；
[0153]
所述采用改进的遗传算法对初始化的种群进行迭代处理，包括：
[0154]
采用交叉操作和变异操作更新初始化的种群；
[0155]
基于约束条件，将更新后种群中的染色体向量转化为agv的路径解，计算路径解的总成本，保留总成本最小的n条染色体向量作为后代；
[0156]
根据保留的n条染色体向量，将路径解中最少任务的路径合并到其他路径中，得到合并后染色体向量；将合并后染色体向量作为下一次迭代的初始化的种群。
[0157]
实施例4：
[0158]
本实施例提供了一种计算机可读存储介质，该计算机可读存储介质为计算机可读计算机可读存储介质，其存储有计算机程序，所述计算机程序被处理器执行时，实现上述实施例1的矩阵制造车间车辆路径规划方法，如下：
[0159]
根据agv的行驶距离和任务的交货时间，通过最近邻算法和随机算法生成n条染色
体向量，将n条染色体向量作为初始化的种群；
[0160]
采用改进的遗传算法对初始化的种群进行迭代处理，直到满足迭代条件，获得总成本最小的多条agv路径；
[0161]
所述采用改进的遗传算法对初始化的种群进行迭代处理，包括：
[0162]
采用交叉操作和变异操作更新初始化的种群；
[0163]
基于约束条件，将更新后种群中的染色体向量转化为agv的路径解，计算路径解的总成本，保留总成本最小的n条染色体向量作为后代；
[0164]
根据保留的n条染色体向量，将路径解中最少任务的路径合并到其他路径中，得到合并后染色体向量；将合并后染色体向量作为下一次迭代的初始化的种群。
[0165]
需要说明的是，本实施例的计算机可读计算机可读存储介质可以是计算机可读信号介质或者计算机可读计算机可读存储介质或者是上述两者的任意组合。计算机可读计算机可读存储介质例如可以是但不限于电、磁、光、电磁、红外线、或半导体的系统、装置或器件，或者任意以上的组合。计算机可读计算机可读存储介质的更具体的例子可以包括但不限于：具有一个或多个导线的电连接、便携式计算机磁盘、硬盘、随机访问存储器(ram)、只读存储器(rom)、可擦式可编程只读存储器(eprom或闪存)、光纤、便携式紧凑磁盘只读存储器(cd-rom)、光存储器件、磁存储器件、或者上述的任意合适的组合。
[0166]
综上所述，本发明提供了一种多矩阵制造车间车辆路径规划方法、装置、电子设备及存储介质，所述矩阵制造车间包括多台agv以及多个任务，所述方法包括：根据agv的行驶距离和任务的交货时间，通过最近邻算法和随机算法生成n条染色体向量，将n条染色体向量作为初始化的种群；采用改进的遗传算法对初始化的种群进行迭代处理，直到满足迭代条件，获得总成本最小的多条agv路径；所述采用改进的遗传算法对初始化的种群进行迭代处理，包括：采用交叉操作和变异操作更新初始化的种群；基于约束条件，将更新后种群中的染色体向量转化为agv的路径解，计算路径解的总成本，保留总成本最小的n条染色体向量作为后代；根据保留的n条染色体向量，将路径解中最少任务的路径合并到其他路径中，得到合并后染色体向量；将合并后染色体向量作为下一次迭代的初始化的种群。首先，通过最近邻方法和随机方法初始化种群，在初始化过程中将行驶距离和交货时间作为评价指标，以获得高质量的初始化路径解，有效地引导算法进行高效的搜索，有利于最优解决方案解的获取；其次，通过交叉操作和变异操作充分挖掘和利用父代染色体中的优质信息；最后，通过合并操作，最大程度地减少路径解中agv的使用数量。通过本发明提供的方法能够在较短时间内对多台agv进行综合调度，避免绕路，确保在较短路程里准时交付，实现了更高的车间自动化工作效率。
[0167]
以上所述，仅为本发明专利较佳的实施例，但本发明专利的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明专利所公开的范围内，根据本发明专利的技术方案及其发明构思加以等同替换或改变，都属于本发明专利的保护范围。

技术特征：
1.一种矩阵制造车间车辆路径规划方法，所述矩阵制造车间包括多台agv以及多个任务，其特征在于，所述方法包括：根据agv的行驶距离和任务的交货时间，通过最近邻算法和随机算法生成n条染色体向量，将n条染色体向量作为初始化的种群；采用改进的遗传算法对初始化的种群进行迭代处理，直到满足迭代条件，获得总成本最小的多条agv路径；所述采用改进的遗传算法对初始化的种群进行迭代处理，包括：采用交叉操作和变异操作更新初始化的种群；基于约束条件，将更新后种群中的染色体向量转化为agv的路径解，计算路径解的总成本，保留总成本最小的n条染色体向量作为后代；根据保留的n条染色体向量，将路径解中最少任务的路径合并到其他路径中，得到合并后染色体向量；将合并后染色体向量作为下一次迭代的初始化的种群。2.根据权利要求1所述的矩阵制造车间车辆路径规划方法，其特征在于，所述根据agv的行驶距离和任务的交货时间，通过最近邻算法和随机算法生成n条染色体向量，包括：根据agv的行驶距离和任务的交货时间，通过最近邻算法生成n1条染色体向量；若n为偶数，则n1＝n/2，否则n1＝int(n/2)+1；通过随机算法生成int(n/2)条染色体向量；将最近邻算法生成的染色体向量和随机算法生成的染色体向量合并成完整的n条染色体向量，作为初始化的种群。3.根据权利要求2所述的矩阵制造车间车辆路径规划方法，其特征在于，所述根据agv的行驶距离和任务的交货时间，通过最近邻算法生成n1条染色体向量，包括：根据agv的行驶距离、任务的交货时间以及α值，计算适应度值；其中，α∈[0,1]表示平衡行驶距离和交货时间的权重参数；寻找适应度值最低的任务作为下一个服务对象；若所有任务都分配完成，则所有任务按服务顺序构成一条染色体向量，否则，将所述服务对象所在位置作为agv当前位置，并返回根据agv的行驶距离、任务的交货时间以及α，继续执行后续操作；若已生成n1条染色体向量，则结束操作，否则，更新α值，并返回根据agv的行驶距离、任务的交货时间以及α，继续执行后续操作。4.根据权利要求1所述的矩阵制造车间车辆路径规划方法，其特征在于，所述采用交叉操作和变异操作更新初始化的种群，包括：从所述种群中随机选择两条染色体向量作为父代，采用交叉操作生成两条染色体向量的后代；对交叉操作生成的两条染色体向量分别采用变异操作，生成新的染色体向量；若已执行交叉操作和变异操作n次，则将所有新生成的2n条染色体向量作为更新后种群，否则，返回从所述种群中随机选择两条染色体向量作为父代，并继续执行后续操作。5.根据权利要求4所述的矩阵制造车间车辆路径规划方法，其特征在于，所述变异操作，具体为：从染色体向量中选择两组相连的l个任务，并将这两个任务进行交换，得到新染色体向
量，其中，l取{1,2,3}中的任意一个值。6.根据权利要求4所述的矩阵制造车间车辆路径规划方法，其特征在于，所述从所述种群中随机选择两条染色体向量作为父代，采用交叉操作生成两条染色体向量的后代，包括：将两条染色体向量中的一个作为第一条染色体向量，将第一条染色体向量的第一个任务作为参考任务；将另一条染色体向量从左到右进行移动，直至第一个任务与所述参考任务一致；针对第一条染色体向量和移动后的染色体向量，在α为设定值时，根据染色体向量的头两个任务的行驶距离、任务的交货时间以及α值，分别计算两条染色体向量的头两个任务的适应度值；选择适应度值较小的染色体向量的第二个任务作为参考任务，将另一条染色体向量从左到右进行移动且保持第一任务不变，直至第二个任务与所述参考任务一致，此时两条染色体向量的头两个任务一致；将头两个任务一致的两条染色体向量作为所述两条染色体向量的后代；其中α∈[0,1]表示平衡行驶距离和交货时间的权重参数。7.根据权利要求1所述的矩阵制造车间车辆路径规划方法，其特征在于，所述约束条件包括时间窗约束和装载量约束，所述时间窗约束为agv必须在任务的叫料时间和交货时间的时间窗内达到指定任务，所述装载量约束指每台agv服务的所有任务所需的物料重量不得超过每台agv的总装载量；所述更新后种群包括2n条染色体向量；基于约束条件，将更新后种群中的一条染色体向量转化为agv的路径解，包括：依次判断染色体向量中的多个任务是否满足所述约束条件；若满足，则将当前任务加入到当前agv路径中，否则，重新生成一条新路径，并将当前任务加入到新路径中；若所有任务遍历完毕，则得到染色体向量对应的agv路径解。8.根据权利要求1所述的矩阵制造车间车辆路径规划方法，其特征在于，所述根据保留的n条染色体向量，将路径解中最少任务的路径合并到其他路径中，包括：获取n条染色体向量中最佳agv使用数量以及当前解agv使用数量r；若则结束操作；否则，继续执行后续操作；根据各路线中客户数量对r条路线由大到小进行排序；将客户最少的路线插入到其他条路线中；若不满足约束条件，则：返回若并继续执行后续操作；否则，结束操作；所述约束条件包括时间窗约束和装载量约束，所述时间窗约束为agv必须在任务的叫料时间和交货时间的时间窗内达到指定任务，所述装载量约束指agv服务的所有任务所需的物料重量不得超过总装载量。9.根据权利要求1～8任一项所述的矩阵制造车间车辆路径规划方法，其特征在于，所述路径解的总成本包括agv的行驶成本f1、使用成本f2以及惩罚时间成本f3，各个成本计算公式如下：
其中，m表示任务的数量，k表示agv的总台数；d
ij
表示任务i(x
i
,y
i
)和任务j(x
j
,y
j
)之间的行驶距离；l
ijk
用于表示第k台agv和任务i，j之间的关系，当l
ijk
＝1表示第k台agv的路径是从任务i到任务j，否则代表第k台agv未经过任务i和任务j；u
d
表示agv的行驶单位成本；u
v
表示单台agv的调用成本；u
p
表示agv的早到惩罚单位成本；t
id
表示任务i的交货时间；表示第k台agv到达任务i的时间。10.一种矩阵制造车间车辆路径规划装置，所述矩阵制造车间包括多台agv以及多个任务，其特征在于，所述装置包括：种群初始化模块，用于根据agv的行驶距离和任务的交货时间，通过最近邻算法和随机算法生成n条染色体向量，将n条染色体向量作为初始化的种群；路径目标最优生成模块，用于采用改进的遗传算法对初始化的种群进行迭代处理，直到满足迭代条件，获得总成本最小的多条agv路径；所述采用改进的遗传算法对初始化的种群进行迭代处理，包括：采用交叉操作和变异操作更新初始化的种群；基于约束条件，将更新后种群中的染色体向量转化为agv的路径解，计算路径解的总成本，保留总成本最小的n条染色体向量作为后代；根据保留的n条染色体向量，将路径解中最少任务的路径合并到其他路径中，得到合并后染色体向量；将合并后染色体向量作为下一次迭代的初始化的种群。

技术总结
本发明公开了一种矩阵制造车间车辆路径规划方法、装置、电子设备及存储介质，矩阵制造车间包括多台AGV和多个任务，所述方法包括：根据AGV的行驶距离和任务的交货时间，通过最近邻算法和随机算法获得初始化的种群；采用改进的遗传算法对种群进行迭代处理直到满足迭代条件，获得总成本最小的多条AGV路径；采用改进的遗传算法对种群进行迭代处理，包括：采用交叉操作和变异操作更新种群；基于约束条件，对更新后种群进行优化，对优化后的后代采用合并操作进行优化并将结果作为下一次迭代的种群。本发明将行驶距离和交货时间作为评价指标，通过采用最近邻算法和随机算法获得高质量的初始化路径解，以有效地引导改进的遗传算法进行高效搜索。高效搜索。高效搜索。


技术研发人员：谢巍 曾俊海 张浪文 孙莹莹
受保护的技术使用者：华南理工大学
技术研发日：2023.05.30
技术公布日：2023/9/14