(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111582647.6 (22)申请日 2021.12.2 2 (71)申请人 深圳市易 流科技股份有限公司 地址 518000 广东省深圳市南 山区粤海街 道海珠社区滨海 大道3369号有线信息 传输大厦9层 (72)发明人 康冠林　王高利　汪亮亮　魏晓梅　 (74)专利代理 机构 深圳市深佳知识产权代理事 务所(普通 合伙) 44285 代理人 吴欣蔚 (51)Int.Cl. G06Q 10/08(2012.01) G06Q 10/04(2012.01) (54)发明名称 一种配送路径生成方法、 装置、 电子设备及 存储介质 (57)摘要 本发明提供一种配送路径生成方法， 包括： 获取多个配送 点对应的距离矩阵； 距离矩阵中包 含配送点之间的导航距离； 判断配送 点的数量是 否大于预设阈值； 若数量大于预设阈值， 则利用 贪心法及距离矩 阵生成配送点对应的目标配送 路径； 若数量小于等于预设阈值， 则利用动态规 划法生成目标配送路径； 输出目标配送路径； 可 将动态规划法和贪心法混合使用， 并将配送点数 量作为选 择上述两种方法的依据， 进而能够有效 提升配送路径的生成效率。 本发 明还提供一种配 送路径生成装置、 电子设备及存储介质， 具有上 述有益效果。 权利要求书2页 说明书10页 附图1页 CN 114254979 A 2022.03.29 CN 114254979 A 1.一种配送路径生成方法， 其特 征在于， 包括： 获取多个 配送点对应的距离矩阵； 所述距离矩阵中包 含所述配送点之间的导 航距离； 判断所述配送点的数量是否大于预设阈值； 若所述数量大于所述预设阈值， 则利用贪心法及所述距离矩阵生成所述配送点对应的 目标配送路径； 若所述数量小于等于所述预设阈值， 则 利用动态规划法生成所述目标配送路径； 输出所述目标配送路径。 2.根据权利要求1所述的配送路径生成方法， 其特征在于， 所述利用贪心法及所述距离 矩阵生成所述配送点对应的目标配送路径， 包括： 将所述配送点添加至配送点 集合， 并判断所述配送点中是否包 含预设的起 点； 若否， 则利用所述距离矩阵查找所述导航距离最长的备选配送点， 并将任一所述备选 配送点设置为所述 起点； 利用所述贪心法、 所述配送点 集合、 所述起点及所述距离矩阵生成所述目标配送路径。 3.根据权利要求2所述的配送路径生成方法， 其特征在于， 所述利用所述贪心法、 所述 配送点集合、 所述起点及所述距离矩阵生成所述目标配送路径， 包括： 创建初始配送路径， 并将所述 起点添加至所述初始配送路径； 将所述起点设置为当前点， 并利用所述距离矩阵在所述配送点集合中查找与 所述当前 点距离最近且未在所述初始配送路径中出现过的目标配送点； 将所述目标配送点添加至所述初始配送路径， 并将所述当前点更新为所述目标配送 点； 进入所述利用所述距离矩阵在所述配送点集合中查找与所述当前点距离最近且未在 所述初始配送路径中出现过的目标配送点的步骤， 直至所述配送点集合中无法查找到所述 目标配送点时， 将所述初始配送路径设置为所述目标配送路径。 4.根据权利要求2所述的配送路径生成方法， 其特征在于， 在利用所述贪心法、 所述配 送点集合、 所述起点及所述距离矩阵生成所述目标配送路径之前， 还 包括： 判断所述配送点中是否包 含预设的终点； 若是， 则将所述终点移出 所述配送点 集合； 相应的， 当所述配送点中包含所述终点时， 所述利用所述贪心法、 所述配送点集合、 所 述起点及所述距离矩阵生成所述目标配送路径， 包括： 利用所述贪心法、 完成移出的配送点集合、 所述起点及所述距离矩阵生成所述目标配 送路径， 并将所述终点设置为所述目标配送路径中的最后一个 配送点。 5.根据权利要求1所述的配送路径生成方法， 其特征在于， 所述利用动态规划法生成所 述目标配送路径， 包括： 将所述配送点添加至配送点 集合， 并判断所述配送点中是否包 含预设的起 点； 若否， 则创建虚拟配送点， 将所述虚拟配送点与每一所述配送点的导航距离设置为零， 并将所述虚拟配送点设置为所述 起点； 利用所述动态规划法、 所述配送点集合、 所述起点及所述距离矩阵生成初始配送路径； 所述初始配送路径为从所述 起点开始经过每一所述配送点 一次并回到所述 起点的回路； 判断所述初始配送路径中是否包 含所述虚拟配送点；权　利　要　求　书 1/2 页 2 CN 114254979 A 2若否， 则将所述初始配送路径设置为所述目标配送路径； 若是， 则移除所述虚拟配送点， 并将完成移除的初始配送路径设置为所述目标配送路 径。 6.根据权利要求5所述的配送路径生成方法， 其特征在于， 在利用所述动态规划法、 所 述配送点 集合、 所述起点及所述距离矩阵生成初始配送路径之前， 还 包括： 判断所述配送点中是否包 含预设的终点且所述终点与所述 起点不同； 若是， 则将所述终点移出所述配送点集合， 同时将除所述起点外的其他配送点设置为 目标配送点， 并在所述距离矩阵中将从所述目标配送点到所述起点的导航距离修改为从所 述目标配送点到所述终点的导 航距离； 相应的， 当所述配送点中包含所述终点且所述终点与所述起点不同时， 所述利用所述 动态规划法、 所述配送点 集合、 所述起点及所述距离矩阵生成初始配送路径， 包括： 利用所述动态规划法、 完成移出的配送点集合、 所述起点及完成修改的距离矩阵生成 所述初始配送路径； 相应的， 当所述配送点中包含所述终点且所述终点与所述起点不同时， 在将完成移除 的初始配送路径设置为所述目标配送路径之后， 还 包括： 将所述终点设置为所述目标配送路径的最后一个 配送点。 7.根据权利要求1至6任一项所述的配送路径生成方法， 其特征在于， 在判断所述配送 点的数量是否大于预设阈值之前， 还 包括： 判断所述配送点中是否仅包 含预设的终点； 若是， 则对所述终点进行 标记， 并将所述终点 修改为起点； 相应的， 所述输出 所述目标配送路径， 包括： 判断所述目标配送路径的起 点是否被进行 过标记； 若是， 则倒序输出 所述目标配送路径； 若否， 则正常输出 所述目标配送路径。 8.一种配送路径生成装置， 其特 征在于， 包括： 获取模块， 用于获取多个配送点对应的距离矩阵； 所述距离矩阵中包含所述配送点之 间的导航距离； 判断模块， 用于判断所述配送点的数量是否大于预设阈值； 第一生成模块， 用于若所述数量大于所述预设阈值， 则利用贪心法及所述距离矩阵生 成所述配送点对应的目标配送路径； 第二生成模块， 用于若所述数量小于等于所述预设阈值， 则利用动态规划法生成所述 目标配送路径； 输出模块， 用于 输出所述目标配送路径。 9.一种电子设备， 其特 征在于， 包括： 存储器， 用于存 储计算机程序； 处理器， 用于执行所述计算机程序时实现如权利要求1至7任一项所述的配送路径生成 方法。 10.一种存 储介质， 其特 征在于， 所述存 储介质中存储 有计算机可 执行指令， 所述计算机 可执行指令被处理器加载并执行时， 实现如权利要求1至7任一项所述的配送路径生成方法。权　利　要　求　书 2/2 页 3 CN 114254979 A 3