(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211185618.0 (22)申请日 2022.09.27 (71)申请人 阿里巴巴 （中国） 有限公司 地址 311121 浙江省杭州市余杭区五常街 道文一西路969号3幢5层5 54室 (72)发明人 张永亮　王惠林　廖响林　陈吉　 (74)专利代理 机构 北京博思佳知识产权代理有 限公司 1 1415 专利代理师 靳玫 (51)Int.Cl. G06Q 10/06(2012.01) G06Q 10/08(2012.01) (54)发明名称 一种配送任务的分配方法及装置 (57)摘要 本说明书一个或多个实施例提供一种配送 任务的分配方法及装置， 其中， 所述方法包括： 分 别获取N个任务地址信息、 以及M个配送服务方中 每个配送 服务方的配送起点位置， 所述N和M 是正 整数； 根据所述M个配送服务方的配送起点位置， 构建得到M个泰森多边形， 每个泰森多边形的内 部包括一个所述配送服务方的配送 起点位置； 将 所述N个任务地址信息分配至所述M个泰森多边 形中。 权利要求书3页 说明书17页 附图9页 CN 115511302 A 2022.12.23 CN 115511302 A 1.一种配送任务的分配方法， 其特 征在于， 所述方法包括： 分别获取N个任务地址信息、 以及M个配送服务方中每个配送服务方的配送起点位置， 所述N和M是正整数； 每个所述任务地址信息对应一笔配送任务， 所述配送起点位置表示负 责执行配送任务的配送服 务方的配送起 点； 根据所述M个配送服务方的配送起点位置， 构建得到M个泰森多边形， 每个泰森多边形 的内部包括 一个所述配送服 务方的配送起 点位置； 将所述N个任务地址信 息分配至所述M个泰森多边形中， 以使得每个泰森多边形内包括 的配送起点位置对应的配送服务方执行分配至所述泰森多边形的各任务地址信息对应的 配送任务。 2.根据权利要求1所述的方法， 其特征在于， 所述根据所述M个配送服务方的配送起点 位置， 构建得到M个泰森多边形， 每个泰森多边形的内部包括一个所述配送服务方的配送 起 点位置， 包括： 根据所述M个配送服务方的配送起点位置， 构建三角网， 所述三角网包括相邻 接的多个 三角形， 每 个三角形中的三个顶点分别对应三个 配送服务方的配送起 点位置； 遍历所述 三角网中的各个三角形， 分别获取每 个三角形的外心点； 对于任一顶点， 将包括所述顶点的各个三角形的外心点组成的外心点集合， 作为与所 述顶点对应的外心点 集合； 根据每一个顶点对应的外心点集合， 计算由所述外心点集合中的外心点组成的凸包， 所述凸包作为包括所述顶点对应的配送服 务方的配送起 点位置的泰 森多边形。 3.根据权利要求2所述的方法， 其特征在于， 所述根据每一个顶点对应的外心点集合， 计算由所述外心点 集合中的外心点组成的凸包， 包括： 基于所述外心点 集合中的各个外心点的坐标， 按照坐标从小到大的顺序进行排序； 将排序在前两位的外心点的坐标放入上凸包集合， 并依照排序遍历剩余的外心点坐 标， 将剩余的外心点坐标中满足右转定理的外心点坐标逐个加入所述上凸包集合， 当剩余 外心点坐标遍历结束时得到上凸包集 合； 将排序在后两位的外心点的坐标放入下凸包集合， 并依照排序遍历剩余的外心点坐 标， 将剩余的外心点坐标中满足右转定理的外心点坐标逐个加入所述下凸包集合， 当剩余 外心点坐标遍历结束时得到下凸包集 合； 组合所述上凸包集 合和下凸包集 合中的各个外心点， 得到所述外心点组成的凸包。 4.根据权利要求1所述的方法， 其特征在于， 所述将所述N个任务地址信息分配至所述M 个泰森多边形中， 包括： 对于任一个任务 地址信息， 以所述任务 地址信息为 起点做单向射线； 统计所述单向射线与参与判断的泰森多边形的各条边之间的交点的总数量， 所述泰森 多边形的每条边的两个端点中去除其中一个端点不参与所述统计， 且各条边去除的是同向 端点； 响应于所述交点的总数量满足预设数量条件， 确定所述任务地址信 息在所述参与判断 的泰森多边形内， 将所述任务 地址信息分配至所述泰 森多边形。 5.根据权利要求 4所述的方法， 其特 征在于， 所述泰森多边形的每条边的两个端点中去除其中一个端点不参与所述统计， 且各条边权　利　要　求　书 1/3 页 2 CN 115511302 A 2去除的是同向端点， 包括： 所述泰森多边形中的每条边的两个端点中， 去除y坐标较大 的端 点； 或者， 所述泰 森多边形中的每条边的两个端点中， 去除y坐标较小的端点； 所述统计所述单向射线与参与判断的泰森多边形的各条边之间的交点的总数量， 包 括： 若所述泰森多边形的一条边的两个端点的y坐标相等， 则确定所述单向射线与所述边 的交点的数量是0 。 6.根据权利要求1所述的方法， 其特征在于， 所述将所述N个任务地址信息分配至所述M 个泰森多边形中， 包括： 若所述任务地址信 息位于所述泰森多边形的其中一条边上， 则将所述任务地址信 息分 配至所述泰 森多边形。 7.根据权利要求1～6任一所述的方法， 其特征在于， 所述分别获取N个任务地址信息、 以及M个配送服务方中每 个配送服务方的配送起 点位置， 包括： 获取M个配送服务方中每个配送服务方的实时定位位置， 作为所述配送服务方的配送 起点位置； 获取待分配的N个配送任务， 每个配送任务包括： 一个供货地址和一个收货地址， 所述 供货地址用于表示提供配送货物的商家 地址， 所述收货地址用于表示收取所述配送货物的 用户地址； 对于所述N个配送任务中的每一配送任务， 基于所述供货地址和收货地址确定重心位 置， 并将所述重心位置作为所述配送任务对应的任务 地址信息 。 8.根据权利要求7所述的方法， 其特征在于， 所述将所述N个任务地址信息分配至所述M 个泰森多边形中之后， 所述方法还 包括： 对于任一泰森多边形， 获取分配至所述泰森多边形内的配送任务节点集合， 所述配送 任务节点集合中的各配送任务节点， 包括： 分配至所述泰森多边形内的各任务地址信息对 应的配送任务的供货地址和收货地址； 根据所述配送任务节点集合， 确定所述泰森多边形内的配送服务方由配送起点位置到 所述配送任务节点集合中的各个配送任务节点的最短配送路线； 并且， 确定的所述最短配 送路线满足： 对于任一配送任务， 所述配送服务方到达所述配送任务中的供货地址的时间 先于收货地址 。 9.一种配送任务的分配装置， 其特 征在于， 所述装置包括： 数据获取模块， 用于分别获取N个任务地址信息、 以及M个配送服务方中每个配送服务 方的配送起点位置， 所述N和M是正整 数； 每个所述任务地址信息对应一笔配送任务， 所述配 送起点位置表示负责执 行配送任务的配送服 务方的配送起 点； 泰森图构造模块， 用于根据所述M个配送服务方的配送起点位置， 构建得到M个泰森多 边形， 每个泰森多边形的内部包括 一个所述配送服 务方的配送起 点位置； 任务分配模块， 用于将所述 N个任务地址信息分配至所述M个泰 森多边形中。 10.一种电子设备， 其特 征在于， 包括： 处理器； 用于存储处理器可执行指令的存 储器； 其中， 所述处理器通过运行所述可执行指令以实现如权利要求1 ‑8中任一项所述的方权　利　要　求　书 2/3 页 3 CN 115511302 A 3