(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211216237.4 (22)申请日 2022.09.30 (71)申请人 胜斗士 （上海） 科技 技术发展有限公 司 地址 200120 上海市浦东 新区牡丹路60号 10-11层 (72)发明人 戚成亮　 (74)专利代理 机构 北京博思佳知识产权代理有 限公司 1 1415 专利代理师 康莹 (51)Int.Cl. G06Q 10/06(2012.01) G06Q 10/08(2012.01) G06Q 30/06(2012.01) (54)发明名称 规划配送路径的方法、 装置、 设备及存储介 质 (57)摘要 本发明公开了一种规划配送路径的方法、 装 置、 设备及存储介质， 所述方法包括： 基于配送地 址对多个待配送订单进行聚类， 得到初始已聚类 订单和初始未聚类订单； 基于所述初始未聚类订 单的配送 地址进行初步路径规划， 得到初步规划 路径； 将所述初始已聚类订单的配送 地址插入所 述初步规划路径， 得到目标规划路径。 本发明相 比于现有的直接通过全部待配送订单进行整体 路径规划的方式， 可以提高配送路径规划的效 率， 并可以确保配送路径规划的合理性， 有利于 提升平台调度系统的调度效率和调度质量。 权利要求书3页 说明书12页 附图7页 CN 115392789 A 2022.11.25 CN 115392789 A 1.一种规划配送路径的方法， 其特 征在于， 包括： 基于配送地址对多个待配送订单进行聚类， 得到初始已聚类订单和初始未聚类订单； 基于所述初始未聚类订单的配送地址进行初步路径规划， 得到初步 规划路径； 将所述初始已聚类订单的配送地址插 入所述初步 规划路径， 得到目标规划路径。 2.根据权利要求1所述的方法， 其特征在于， 所述基于配送地址对多个待配送订单进行 聚类， 得到初始已聚类订单和初始未聚类订单， 包括： 基于所述多个待配送订单的配送地址确定聚类半径； 响应于确定所述多个待配送订单中第一订单的配送地址与第二订单的配送地址之间 的距离小于或等于所述聚类半径， 将所述第一订单和所述第二订单划分为一类， 并分别确 定为所述初始已聚类订单； 响应于确定所述多个待配送订单中第三订单的配送地址与其他任一订单的配送地址 之间的距离均大于所述聚类半径， 将所述第三 订单确定为所述初始未聚类订单。 3.根据权利要求2所述的方法， 其特征在于， 所述基于所述多个待配送订单的配送地址 确定聚类半径， 包括： 确定所述多个待配送订单中任意两个订单的配送地址之间的最大距离； 基于所述 最大距离与所述多个待配送订单的订单 数量确定所述聚类半径。 4.根据权利要求1所述的方法， 其特 征在于， 所述初始已聚类订单属于 至少一个簇； 所述将所述初始已聚类订单的配送地址插入所述初步规划路径， 得到目标规划路径， 包括： 在所述簇中选取第四订单； 将所述第四订单的第四配送地址插入所述初步规划路径中的第 一目标路径， 以形成新 的规划路径； 在剩余已聚类订单中， 循环第一目标过程， 直至所述剩余已聚类订单的数量为0； 其中， 所述第一目标过程包括选择第五订单， 并将所述第五订单的第五配送地址插入所述簇中其 他订单的配送地址位于所述新的规划路径中的第二目标路径， 以及形成最新的规划路径的 过程， 所述剩余已聚类订单包括所述簇中配送地址在当前最新形成的规划路径以外的订 单， 所述第二目标路径包括在所述当前最新形成的规划路径中确定的路径长度增量最小的 路径； 将当前最 新形成的规划路径确定为所述目标规划路径。 5.根据权利要求 4所述的方法， 其特 征在于， 所述在所述簇中选取第四订单， 包括： 在所述簇中随机 选取第四订单； 或， 在所述簇中选取与所述初步 规划路径中订单的配送地址最近的第四订单。 6.根据权利要求1所述的方法， 其特 征在于， 所述多个待配送订单同属于目标门店； 所述基于所述初始未聚类订单的配送地址进行初步路径规划， 得到初步规划路径， 包 括： 确定所述初始未聚类订单中距离所述目标门店最近的第六订单的第六配送地址； 基于所述第六配送地址与所述目标门店的门店地址形成子回路； 在剩余未聚类订单中， 循环第二目标过程， 直至所述剩余未聚类订单的数量为0； 其中， 所述第二目标过程包括确定距离当前最新形成的子回路中订单的配送地址最近的第七订权　利　要　求　书 1/3 页 2 CN 115392789 A 2单， 并将所述第七订单的第七配送地址插入所述当前最新形成的子回路中的第三目标路 径， 以及形成新的子回路的过程， 所述剩余未聚类订单包括所述初始未聚类订单中配送地 址在所述当前最新形成的子回路以外的订单， 所述第三目标路径包括在所述当前最新形成 的子回路中确定的路径长度增量 最小的路径； 将当前最 新形成的子回路确定为所述初步 规划路径。 7.根据权利要求6所述的方法， 其特征在于， 所述第 三目标路径的两个端点为第八订单 的第八配送地址和第九订单的第九配送地址； 所述将所述第七订单的第七配送地址插入所述当前最新形成的子回路中的第三目标 路径， 包括： 形成所述第八配送地址到所述第七配送地址的第 一段路径， 以及所述第七配送地址到 所述第九配送地址的第二段路径， 并删除所述第三目标路径。 8.一种规划配送路径的装置， 其特 征在于， 包括： 订单聚类模块， 用于基于配送地址对多个待配送订单进行聚类， 得到初始已聚类订单 和初始未聚类订单； 初步路径确定模块， 用于基于所述初始未聚类订单的配送地址进行初步路径规划， 得 到初步规划路径； 目标路径确定模块， 用于将所述初始已聚类订单的配送地址插入所述初步规划路径， 得到目标规划路径。 9.根据权利要求8所述的装置， 其特 征在于， 所述 订单聚类模块， 包括： 半径确定单 元， 用于基于所述多个待配送订单的配送地址确定聚类半径； 第一聚类单元， 用于响应于确定所述多个待配送订单中第 一订单的配送地址与第 二订 单的配送地址之间的距离小于或等于所述聚类半径， 将所述第一订单和所述第二订单划分 为一类， 并分别确定为所述初始已聚类订单； 第二聚类单元， 用于响应于确定所述多个待配送订单中第 三订单的配送地址与其他任 一订单的配送地址之间的距离均大于所述聚类半径， 将所述第三订单确定为所述初始未聚 类订单。 10.根据权利要求9所述的装置， 其特 征在于， 所述半径确定单 元还用于： 确定所述多个待配送订单中任意两个订单的配送地址之间的最大距离； 基于所述 最大距离与所述多个待配送订单的订单 数量确定所述聚类半径。 11.根据权利要求8所述的装置， 其特 征在于， 所述初始已聚类订单属于 至少一个簇； 所述目标路径确定模块， 包括： 第四订单选取 单元， 用于在所述簇中选取第四订单； 路径形成单元， 用于将所述第四订单的第四配送地址插入所述初步规划路径中的第 一 目标路径， 以形成新的规划路径； 第一过程循环单元， 用于在剩余已聚类订单中， 循环第 一目标过程， 直至所述剩余已聚 类订单的数量为0； 其中， 所述第一目标过程包括选择第五订单， 并将所述第五订单的第五 配送地址插入所述簇中其他订单的配送地址位于所述新的规划路径中的第二目标路径， 以 及形成最新的规划路径的过程， 所述剩余已聚类订单包括所述簇中配送地址在当前最新形 成的规划路径以外的订单， 所述第二目标路径包括在所述当前最新形成的规划路径中确定权　利　要　求　书 2/3 页 3 CN 115392789 A 3