(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210978861.1 (22)申请日 2022.08.16 (71)申请人 上海聚水潭网络科技有限公司 地址 200040 上海市 静安区新闸路1418号5 幢214室 申请人 杭州聚水潭网络科技有限公司 (72)发明人 周旭　骆海东　颜嘉梁　 (74)专利代理 机构 北京高沃 律师事务所 1 1569 专利代理师 万慧华 (51)Int.Cl. G06Q 10/04(2012.01) G06Q 10/08(2012.01) (54)发明名称 一种分拣行 走路径优化方法及系统 (57)摘要 本发明公开一种分拣行走路径优化方法及 系统， 涉及电商拣货技术领域， 方法包括： 确定拣 货起始点； 所述拣货起始点为任一拣货点； 针对 每个拣货起始点， 以所述拣货起始点为起点， 基 于广度优先搜索算法遍历所有拣货点， 以确定第 一距离组； 所述第一距离组包括多个第一距离； 所述第一距离为所述拣货起始点与所述拣货点 之间的最短距离； 根据每个所述拣货起始点以及 所述拣货起始点对应的第一距离组， 基于克里斯 托菲德斯算法， 计算经过所有拣货点的最短行走 路径。 本发明能够大大提高拣货人员的拣货效 率。 权利要求书3页 说明书7页 附图2页 CN 115456249 A 2022.12.09 CN 115456249 A 1.一种分拣行 走路径优化方法， 其特 征在于， 所述分拣行 走路径优化方法包括： 确定拣货起始点； 所述拣货起始点 为任一拣货点； 针对每个拣货起始点， 以所述拣货起始点为起点， 基于广度优先搜索算法遍历所有拣 货点， 以确定第一距离组； 所述第一距离组包括多个第一距离； 所述第一距离为所述拣货起 始点与所述拣货点之间的最短距离； 根据每个所述拣货起始点以及所述拣货起始点对应的第 一距离组， 基于克里斯托菲德 斯算法， 计算经 过所有拣货点的最短行 走路径。 2.根据权利要求1所述的分拣行走路径优化方法， 其特征在于， 所述以所述拣货起始点 为起点， 基于广 度优先搜索算法遍历所有拣货点， 以确定第一距离组， 具体包括： 确定分拣行 走地图； 所述分拣行 走地图上记录有所有拣货点和障碍点； 建立与所述分拣行走地图对应的二维矩阵； 所述二维矩阵中的点阵数据分别与所述拣 货点、 所述障碍点对应； 以所述拣货起始点对应的点阵数据为原点， 结合预设点值规则， 对所述二维矩阵进行 广度优先搜索， 以得到更新后的二维矩阵； 根据更新后的二维矩阵中的点阵数据， 确定多个第一距离 。 3.根据权利要求2所述的分拣行走路径优化方法， 其特征在于， 所述预设点值规则包括 拣货起始点阵赋值 规则、 障碍物点阵赋值 规则和拣货点阵赋值 规则； 所述以所述拣货起始点对应的点阵数据为原点， 结合预设点值规则， 对所述二维矩阵 进行广度优先搜索， 以得到更新后的二维矩阵， 具体包括： 根据所述拣货起始点阵赋值规则， 对所述拣货起始点对应的点阵数据赋值， 以得到起 始点阵值； 根据所述起始点阵值、 所述障碍物点阵赋值规则和所述拣货点阵赋值规则， 计算所述 起始点阵值对应的四方向点阵组； 所述四方向点阵组包括第一点阵数据、 第二点阵数据、 第 三点阵数据和 第四点阵数据； 所述第一点阵数据 表示在二维矩阵中的向上方向上相邻的点 阵数据； 所述第二点阵数据表示在二维矩阵中的向下方向上相邻的点阵数据； 所述第三点 阵数据表示在二 维矩阵中的向左方向上相 邻的点阵数据； 所述第四点阵数据 表示在二维矩 阵中的向右方向上相邻的点阵数据； 针对所述起始点阵值对应的四方向点阵组中的每个点阵数据， 根据所述障碍物点阵赋 值规则和所述拣货点阵赋值规则， 分别计算每个点阵数据对应的四方向点阵组， 直至所述 二维矩阵中的所有点阵数据确定； 所有点阵数据被赋值确定后的二 维矩阵为更新后的二 维 矩阵。 4.根据权利要求1所述的分拣行走路径优化方法， 其特征在于， 所述根据每个所述拣货 起始点以及所述拣货起始点对应的第一距离组， 基于克里斯托菲德斯算法， 计算经过所有 拣货点的最短行 走路径， 具体包括： 根据每个所述拣货起始点以及所述拣货起始点对应的第一距离组， 构造最小生成树； 根据度数从所述最小生成树中确定点集O； 所述度数表示所述最小生成树中节点的连 接边数； 所述 点集O包括多个度数为奇数的节点； 构造所述点集O对应的最小完全匹配； 所述最小完全匹配包括多个至多与一条边相连 的节点；权　利　要　求　书 1/3 页 2 CN 115456249 A 2根据所述最小完全匹配和所述最小生成树， 构造重 图； 所述重 图中的每个节点的度数 均为偶数； 根据所述重图， 确定出 经过所有拣货点的最短行 走路径。 5.一种分拣行 走路径优化系统， 其特 征在于， 所述分拣行 走路径优化系统包括： 起始点确定模块， 用于确定拣货起始点； 所述拣货起始点 为任一拣货点； 距离计算模块， 用于针对每个拣货起始点， 以所述拣货起始点为起点， 基于广度优先搜 索算法遍历所有拣货点， 以确定第一距离组； 所述第一距离组包括多个第一距离； 所述第一 距离为所述拣货起始点与所述拣货点之间的最短距离； 路径计算模块， 用于根据每个所述拣货起始点以及所述拣货起始点对应的第一距离 组， 基于克 里斯托菲德斯 算法， 计算经 过所有拣货点的最短行 走路径。 6.根据权利要求5所述的分拣行走路径优化系统， 其特征在于， 所述距离计算模块， 具 体包括： 地图确定子模块， 用于确定分拣行走地图； 所述分拣行走地图上记录有所有拣货点和 障碍点； 矩阵确定子模块， 用于建立与所述分拣行走地图对应的二维矩阵； 所述二维矩阵中的 点阵数据分别与所述拣货点、 所述障碍点对应； 矩阵更新子模块， 用于以所述拣货起始点对应的点阵数据为原点， 结合预设点值规则， 对所述二维矩阵进行广 度优先搜索， 以得到更新后的二维矩阵； 距离确定 子模块， 用于根据更新后的二维矩阵中的点阵数据， 确定多个第一距离 。 7.根据权利要求6所述的分拣行走路径优化系统， 其特征在于， 所述预设点值规则包括 拣货起始点阵赋值 规则、 障碍物点阵赋值 规则和拣货点阵赋值 规则； 所述矩阵更新子模块， 具体包括： 起始点值计算单元， 用于根据所述拣货起始点阵赋值规则， 对所述拣货起始点对应的 点阵数据赋值， 以得到起始点阵值； 四方向点值计算单元， 用于根据所述起始点阵值、 所述障碍物点阵赋值规则和所述拣 货点阵赋值规则， 计算所述起始点阵值对应的四方向点阵组； 所述四方向点阵组包括第一 点阵数据、 第二点阵数据、 第三点阵数据和 第四点阵数据； 所述第一点阵数据 表示在二 维矩 阵中的向上方向上相 邻的点阵数据； 所述第二点阵数据表示在二 维矩阵中的向下方向上相 邻的点阵数据； 所述第三点阵数据表示在二维矩阵中的向左方向上相邻的点阵数据； 所述 第四点阵数据表示在二维矩阵中的向右方向上相邻的点阵数据； 矩阵更新计算单元， 用于针对所述起始点阵值对应的四方向点阵组中的每个点阵数 据， 根据所述障碍物点阵赋值规则和所述拣货点阵赋值规则， 分别计算每个点阵数据对应 的四方向点阵组， 直至所述二维矩阵中的所有点阵数据确定； 所有点阵数据被赋值确定后 的二维矩阵为更新后的二维矩阵。 8.根据权利要求5所述的分拣行走路径优化系统， 其特征在于， 所述路径计算模块， 具 体包括： 树生成子模块， 用于根据每个所述拣货起始点以及所述拣货起始点对应的第一距离 组， 构造最小生成树； 点集确定子模块， 用于根据度 数从所述最小生成树中确定点集O； 所述度 数表示所述最权　利　要　求　书 2/3 页 3 CN 115456249 A 3