路径规划方法、装置、电子设备和计算机可读存储介质.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN113848936A(43)申请公布日2021.12.28(21)申请号202111192602.8(22)申请日2021.10.13(71)申请人京东科技信息技术有限公司地址100176北京市北京经济技术开发区科创十一街18号院2号楼6层601(72)发明人陈恭彦刘维妙易津锋王答明(74)专利代理机构北京清亦华知识产权代理事务所(普通合伙)11201代理人罗岚(51)Int.Cl.G05D1/02(2020.01)权利要求书3页说明书10页附图5页(54)发明名称路径规划方法、装置、电子设备和计算机可读存储介质(57)摘要本公开提出一种路径规划方法、装置、电子设备和计算机可读存储介质，其中，方法包括：获取多个收货点的位置，以及多个发货点的位置，根据多个收货点的位置，对多个收货点进行聚类，以得到与发货点个数匹配的多个聚簇，根据各聚簇的中心位置与各发货点的位置之间的距离，确定各发货点对应的聚簇，分别对各发货点规划经过对应聚簇中各收货点的目标路径，通过对多个收货点进行聚类，确定各个发货点对应的聚簇，对各发货点规划经过对应聚簇中各收货点的目标路径，实现了将多中心路径规划拆分为多个单中心路径规划，提高了路径规划的效率和准确度。CN113848936ACN113848936A权利要求书1/3页1.一种路径规划方法，其特征在于，包括以下步骤：获取多个收货点的位置，以及多个发货点的位置；根据所述多个收货点的位置，对所述多个收货点进行聚类，以得到与发货点个数匹配的多个聚簇；根据各聚簇的中心位置与各所述发货点的位置之间的距离，确定各所述发货点对应的聚簇；分别对各所述发货点规划经过对应聚簇中各收货点的目标路径。2.根据权利要求1所述的方法，其特征在于，所述分别对各所述发货点规划经过对应聚簇中各收货点的目标路径，包括：对任意的一发货点，将所述一发货点和对应聚簇中的各收货点分别作为节点，根据各所述节点的位置，确定各所述节点之间的距离成本；根据各所述节点之间的距离成本和车辆数量生成单中心路径规划任务的目标函数，以及根据设定的车辆负载量、车辆数量和各所述收货点的货品需求量，生成所述单中心路径规划任务的约束条件；采用遗传算法求解符合所述约束条件，且使得所述目标函数取值最小化的所述目标路径。3.根据权利要求2所述的方法，其特征在于，所述采用遗传算法求解符合所述约束条件，且使得所述目标函数取值最小化的所述目标路径，包括：随机获取从所述一发货点出发经过对应聚簇中各收货点的多个候选路径；执行多轮迭代，其中，在每一轮迭代中，采用所述约束条件对所述多个候选路径进行筛选，以得到符合所述约束条件的参考路径，采用所述目标函数对符合所述约束条件的各所述参考路径计算各所述参考路径的总距离成本，根据各所述参考路径的总距离成本，从所述多个参考路径中选定部分所述参考路径进行随机调整，以作为下一轮迭代的候选路径；将最后一轮迭代随机调整后的候选路径之中，总距离成本最小的候选路径作为所述目标路径。4.根据权利要求2所述的方法，其特征在于，所述约束条件，包括各车辆的路径上，各所述收货点的货品需求量之和不大于所述车辆负载量；以及还包括下列中的一个或多个组合：对于任一所述收货点，驶入的次数和驶出的次数相等；对于任一所述收货点，驶入的次数为1；各车辆的路径中不包含闭合的子回路。5.根据权利要求2所述的方法，其特征在于，所述根据设定的车辆负载量、车辆数量和各所述收货点的货品需求量，生成所述单中心路径规划任务的约束条件之前，还包括：针对任意的一收货点，根据配送日之前所述一收货点的历史需求量，和所述配送日的属性信息，采用所述一收货点对应的预测模型，预测得到所述一收货点的货品需求量；其中，所述属性信息包括星期信息和促销信息。6.根据权利要求5所述的方法，其特征在于，所述针对任意的一收货点，根据配送日之前所述一收货点的历史需求数据，和所述配送日的属性信息，采用所述一收货点对应的预测模型，预测得到所述一收货点的货品需求量之前，还包括：2CN113848936A权利要求书2/3页针对所述一收货点，根据历史需求记录，确定各采样时刻的实际需求量和各所述采样时刻之前的历史需求量；将每个所述采样时刻之前的历史需求量和对应采样时刻的属性信息作为一个训练样本，并采用对应采样时刻的实际需求量进行标注；采用各所述训练样本，对所述一收货点对应的预测模型进行训练，以使所述预测模型预测的货品需求量与标注的实际需求量之间差异最小化。7.一种路径规划装置，其特征在于，包括：获取模块，用于获取多个收货点的位置，以及多个发货点的位置；聚类模块，用于根据所述多个收货点的位置，对所述多个收货点进行聚类，以得到与发货点个数匹配的多个聚簇；确定模块，用于根据各聚簇的中心位