欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2024119670070
申请人: 安徽大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种大规模车辆路径问题的路线规划方法,其特征在于,包括以下步骤:获取大规模车辆路径的多个任务节点;

将多个任务节点进行分组,确定每个组的聚类中心和任务节点组数;当该聚类中心所属的分组对应的车辆配送任务满足车辆容量限制要求时,将任务节点分配到对应的分组,并将各分组形成上层聚类方案的对应的种群;

确定每一个分组对应的种群中的每个个体对应的车辆数和路径总长,对每个个体进行非支配排序,确定每个个体非支配排序等级,作为标签构造训练样本;将训练样本输入SVM模型,对模型进行训练;

通过对当代种群执行差分变异操作,生成子代种群;

将子代种群输入训练后的SVM模型,获得子代种群中每个个体的分类结果,选出优秀子代并进行下层路径优化,获取优秀子代对应的最优路线;通过合并当代种群和优秀子代,在上层进行非支配排序,选出新一代种群;通过局部搜索算法对最优路线进行优化,迭代执行,直至新一代种群满足预设的终止条件时,输出最优的路线规划方案。

2.根据权利要求1所述的大规模车辆路径问题的路线规划方法,其特征在于,所述确定每个组的聚类中心和任务节点组数,具体包括以下步骤:确定当前代数,第代种群:

其中,表示第代第个个体的聚类方案,代表第代第个个体的聚类中心的个数,代表第代第个个体是否选择第个任务节点作为聚类中心,表示选择第个任务节点作为聚类中心,表示不选择第个任务节点作为聚类中心,表示种群规模;

初始化种群分组信息,表示第gen代第num个体的分组信息;

根据初始化个体任务节点分组,得到:

其中,,g表示任务节点组数,且。

3.根据权利要求2所述的大规模车辆路径问题的路线规划方法,其特征在于,所述将任务节点分配到对应的分组,并将各分组形成上层聚类方案的对应的种群,具体包括:根据任务需求量和车辆载重的比值确定最低分组数量,将任务按照需求量从大到小进行排序;

根据上层生成的聚类方案个体,将任务节点进行分组,在任务点分配时优先分配需求量最大的;

步骤3.1:初始化num=1;

步骤3.2:获取当前个体的分组信息;

步骤3.3:初始化= 1;

步骤3.4:计算任务节点与各聚类中心的距离,同时判断将任务节点分配至距离最小的分组j后,通过判断分组j的剩余容量是否满足仓库的容量限制要求,当满足车辆的容量限制要求时,将任务节点分配给分组j,在中记录;否则,将任务节点分配至距离次优的簇,并判断是否满足分组的剩余容量,重复步骤3.4,直至完成任务节点的分配且令j = ;

步骤3.5:取,当小于等于L时,执行第任务节点的分配流程中心,其中,L表示配送任务节点数量;当大于L时,证明第num个体的所有任务节点已分配到分组中,通过中记录的每个任务节点所属分组信息,更新当前个体的分组信息;

步骤3.6:取num=num+1,当num小于等于时,执行步骤3.2;当num大于时,表示当前种群中所有个体已完成任务节点的分组流程,迭代终止。

4.根据权利要求3所述的大规模车辆路径问题的路线规划方法,其特征在于,所述确定每一个分组对应的种群中的每个个体对应的车辆数和路径总长,包括以下步骤:步骤4.1:初始化;

步骤4.2:获取当前个体的分组信息;

步骤4.3:初始化;

步骤4.4:执行当前分组的下层优化过程,获取当前分组,,表示当前分组的任务节点数量,获取仓库和此分组中任务节点的坐标,通过蚁群算法寻求最优行驶路径;通过2-opt算法对最优行驶路径进行局部最优,得到任务节点的访问顺序={}和任务节点的路径总长;

步骤4.5:更新当前任务分组的路径总长和当前任务分组的节点访问顺序;

步骤4.6:令,当时,执行第j个分组的下层优化过程;当时,表示该个体的任务分组方案已完成下层优化过程,更新该个体的路径总长、个体的车辆数和任务节点组的访问顺序;

步骤4.7:令num=num+1,当num小于等于时,执行步骤4.2;当num大于时,表示当前种群中所有个体已完成下层优化过程,迭代终止。

5.根据权利要求4所述的大规模车辆路径问题的路线规划方法,其特征在于,所述对模型进行训练,具体包括:获取当前种群中各个个体的路径总长和所需车辆数;

根据每个个体的路径总长和车辆数,确定每个个体的非支配排序等级,其中,表示第代中第个个体的非支配排序等级;1≤≤;

将等级为1的个体标签设为1,其他等级的个体标签置为-1,得到当前种群的标签;

获取种群的聚类方案,表示第代第个个体;

将聚类方案和标签输入到SVM模型中,对模型进行训练。

6.根据权利要求5所述的大规模车辆路径问题的路线规划方法,其特征在于,所述生成子代种群,具体包括:步骤6.1:初始化子代种群;

步骤6.2:初始化num=1;

步骤6.3:获取当前个体的聚类方案,随机选择一个非支配排序等级的个体的聚类方案,随机从该聚类方案中获取一个个体且;

步骤6.4:执行差分操作,得到差分操作后的子代种群中的个体:其中,为差分缩放因子;

步骤6.5:判断差分操作后的子代种群中的个体中的变量值是否超过限制,当大于上限时修改变量值为上限,当小于下限时修改变量值为下限;

步骤6.6:对执行多项式变异操作,并再次检查操作后的变量是否满足要求,不满足则按照步骤6.5对变异操作后的变量进行修改;

步骤6.7:令,判断是否成立,若成立,则表示得到第代子代种群,否则,执行步骤6.3。

7.根据权利要求6所述的大规模车辆路径问题的路线规划方法,其特征在于,所述获取优秀子代对应的最优路线,具体包括:将子代种群输入训练好的模型中,得到子代种群标签;

计算中大于0的标签数量,并获取对应索引,当数量大于或等于时,执行获取优秀子代操作;当数量小于时,选择预测结果为负类、表现良好的个体补齐,;

通过优秀子代的索引获取对应的优秀子代:

对优秀子代执行下层优化过程,当该优秀子代中的所有个体已完成下层优化过程时,获取该优秀子代对应的车辆数和路径总长。

8.根据权利要求7所述的大规模车辆路径问题的路线规划方法,其特征在于,所述选出新一代种群,包括以下步骤:将父代种群和子代种群合并为临时种群;

将该临时种群的大小记为,对该临时种群按照路径总长和车辆数这两个目标值进行非支配排序,计算每个个体的非支配排序等级和拥挤距离;

拥挤距离计算公式如下:

其中,为临时种群中的第个个体,,为目标数量,j=0表示目标为车辆数,j=1表示目标为车辆行驶的路径总长,当非支配等级相同时,第个解的拥挤距离为与其相邻两个解各维目标之差的和,其中第一个个体与最后一个个体的拥挤距离被设置为无穷大;

根据非支配等级和拥挤距离对临时种群进行筛选,筛选第一前沿面的个体,当筛选的第一前沿面个体超过时,通过拥挤距离筛选出个个体,否则选择前沿面上所有个体;当筛选的第一前沿面个体小于时,根据规则继续选择剩余前沿面的个体,直到选择结束,输出最终种群为新一代种群;

将输出的新一代种群输入到模型中,对模型进行更新。

9.根据权利要求8所述的大规模车辆路径问题的路线规划方法,其特征在于,所述输出最优的路线规划方案,具体包括以下步骤:根据新一代种群,取,判断当前迭代代数是否大于预设的种群代数Gen,当不满足预设的种群代数Gen条件时,继续执行迭代优化过程;当满足条件时,计算最近的Gen代种群的超体积HV值,即,获取中的最大值和最小值并分别记为和;

通过计算新一代种群的多样性变化程度:

当大于预设的种群的多样性变化程度阈值时,继续执行迭代优化过程;否则,从当前的新一代种群中随机选择一个支配等级的个体,将其索引即为,获取其最优路线方案,并输出该新一代种群的最优路径对应的车辆数和路径总长,作为最优的路线规划方案。

10.一种大规模车辆路径问题的路线规划系统,其特征在于,包括:任务节点获取模块,用于获取大规模车辆路径的多个任务节点;

上层聚类模块,用于将多个任务节点进行分组,确定每个组的聚类中心和任务节点组数;当该聚类中心所属的分组对应的车辆配送任务满足车辆容量限制要求时,将任务节点分配到对应的分组,并将各分组形成上层聚类方案的对应的种群;

下层路径优化模块,用于确定每一个分组对应的种群中的每个个体对应的车辆数和路径总长,对每个个体进行非支配排序,确定每个个体非支配排序等级,作为标签构造训练样本;将训练样本输入SVM模型,对模型进行训练;通过对当代种群执行差分变异操作,生成子代种群;将子代种群输入训练后的SVM模型,获得子代种群中每个个体的分类结果,选出优秀子代并进行下层路径优化,获取优秀子代对应的最优路线;通过合并当代种群和优秀子代,在上层进行非支配排序,选出新一代种群;通过局部搜索算法对最优路线进行优化,迭代执行,直至新一代种群满足预设的终止条件时,输出最优的路线规划方案。