(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211144852.9 (22)申请日 2022.09.20 (71)申请人 江南大学 地址 214122 江苏省无锡市滨湖区蠡湖大 道1800号 (72)发明人 刘洋　赵旭远　王崇邺　顾成远　 (74)专利代理 机构 苏州市中南伟业知识产权代 理事务所(普通 合伙) 32257 专利代理师 李柏柏 (51)Int.Cl. G06Q 10/08(2012.01) G06Q 10/04(2012.01) (54)发明名称 仓库拣货路径规划方法及系统 (57)摘要 本发明提供一种仓库拣货路径 规划方法， 包 括将每个订单号视为一个点， 将一维的拣货路径 规划问题 转换为二维点聚簇问题； 使用快速聚簇 算法对所有点进行第一次聚簇； 使用最小货架成 簇算法将经过第一次聚簇后无法成簇的点进行 第二次聚簇； 使用全局优化算法在簇团内进行多 次点交换操作， 直到遍历完所有簇团为止， 得到 新簇团； 将新簇团输出为拣货单， 同时计算各簇 的路径和拣货单的总路径。 本发 明能够将仓库收 到的大量订单分类成多个子订单， 使得各子订单 间重复路径较小， 从而一次完成多个订单拣货， 极大的降低拣货总路径， 大 大提高了 工作效率。 权利要求书3页 说明书9页 附图1页 CN 115456537 A 2022.12.09 CN 115456537 A 1.一种仓库拣货路径规划方法， 其特 征在于， 包括： S1、 基于货架的一维排列特性将每个订单号视为一个点， 将一维的拣货路径规划问题 转换为二维点聚簇问题； S2、 使用快速聚簇算法对所有点进行第一次聚簇， 得到第一簇团； S3、 使用最小货架成簇算法将经过第一次聚簇后无法成簇的点进行第二次聚簇， 得到 第二簇团； S4、 将第一簇团和第二簇团合并为总簇团， 使用全局优化算法在总簇团内进行多次点 交换操作， 直到遍历完所有总簇团为止， 得到优化后的簇团； S5、 将优化后的簇团输出为拣货单， 计算各簇的路径和拣货单的总路径。 2.根据权利要求1所述的一种仓库拣货路径规划方法， 其特征在于， 使用快速聚簇算法 对所有点进行第一次聚簇的方法包括： S21、 定义每个订单号的拣货 路径区间为[x,y]， 其中， x表示所述订单号的最小货架号， y表示所述 订单号的最大货架号， 对于其中任意 一点得到其路径长度； S22、 对所有点按其链接的路径长度降序排列， 得到点的降序表， 取所述降序表中第一 个点作为第一个簇的初始点Ci,j＝C1,1， 其中Ci,j代表第i个簇的第j个点； S23、 将点C1,1对应的路径区间作为限定区间， 并将降序表中路径区间不包含在限定区 间的点去除， 得到新的降序表， S24、 按簇内缺点的数目从新的 降序表中依次取点与 点C1,1成簇， 得到第一簇团， 一个簇 团即为一个拣货子单； S25、 保存已成簇的簇团， 对剩下点重复S2 2‑S24， 直到无法得到 簇团为止 。 3.根据权利要求2所述的一种仓库拣货路径规划方法， 其特征在于： 在对所有点进行第 一次聚簇时， 优先选择路径长度较大 的点成簇， 使得路径长度大 的点均在同一个拣货子单 内。 4.根据权利要求2所述的一种仓库拣货路径规划方法， 其特征在于， 使用所述最小货架 成簇算法将经 过第一次聚簇后无法成簇的点进行第二次聚簇的方法包括： S31、 取剩下 未成簇的点， 根据点的x值对所有点进行升序排列， 得到 升序表； S32、 根据每个拣货子单内要求的订单数量， 从所述升序表中依次取点成簇， 得到第二 簇团。 5.根据权利要求1所述的一种仓库拣货路径规划方法， 其特征在于， 在使用所述全局优 化算法在簇团内进行多次点交换操作前， 对簇团进行筛选， 判断簇内包含的重复点数占总 点数的百分比是否大于等于预设值， 若判断结果为是， 则将该簇从簇团中剔除， 并对簇团中 剩下的簇进行点交换操作， 若判断结果 为否， 则对簇团中的簇进行点交换操作。 6.根据权利要求5所述的一种仓库拣货路径规划方法， 其特征在于， 使用所述全局优化 算法在簇团内进行多次点交换操作的方法包括： S41、 从簇i开始， 寻找其相邻的所有簇， 记作簇团A， 若A不包含任何簇， 则i+1， 返回筛选 操作， 其中i的初始值 为1； S42、 取簇i内第m个点Ci,m作为被交换的点， m的初始值 为1； S43、 从簇团A中， 取簇j内第n个点Cj,n作为交换点， j和n的初始值 为1； S44、 若Cj,n在簇j内为交换点， 则n+1， 若n已为 最大值， 则j+1， 返回S43；权　利　要　求　书 1/3 页 2 CN 115456537 A 2S45、 计算簇i和簇j初始路径和Z1， 在簇i和簇j内交换Ci,m和Cj,n的位置， 即得到点Ci,n和 点Cj,m； S46、 计算簇i和簇j的新路径和Z2， 若Z2<Z1,则在两簇内进行此次点交换， 否则， 撤销此 次点交换， n+1， 若n已为 最大值， 则j+1， 返回S43； S47、 若j已为 最大值， 则m+1， 返回S42； S48、 若m已为 最大值， 则i+1， 返回筛 选操作； S49、 若i已为 最大值， 则全局优化已完成。 7.一种仓库拣货路径规划系统， 其特 征在于， 包括： 路径规划转换模块， 所述路径规划转换模块用于基于货架的一维排列 特性将每个订单 号视为一个点， 将一维的拣货路径规划问题转换为 二维点聚簇问题； 第一次聚簇模块， 所述第 一次聚簇模块用于使用快速聚簇算法对所有点进行第 一次聚 簇， 得到第一簇团； 第二次聚簇模块， 使用最小货架成簇算法将经过第 一次聚簇后无法成簇的点进行第 二 次聚簇， 得到第二簇团； 全局优化模块， 所述全局优化模块用于将第一簇团和第二簇团合并为总簇团， 使用全 局优化算法在总簇团内进行多次点交换操作， 直到遍历完所有总簇团为止， 得到优化后的 簇团； 拣货单输出模块， 所述拣货单输出模块用于将优化后的簇团输出为拣货单， 同时计算 各簇的路径和拣货单的总路径。 8.根据权利要求7所述的一种仓库拣货路径规划系统， 其特征在于： 所述第 一次聚簇模 块使用快速聚簇算法对所有点进行第一次聚簇的方法包括： S21、 定义每个订单号的拣货 路径区间为[x,y]， 其中， x表示所述订单号的最小货架号， y表示所述 订单号的最大货架号， 对于其中任意 一点得到其路径长度； S22、 对所有点按其链接的路径长度降序排列， 得到点的降序表， 取所述降序表中第一 个点作为第一个簇的初始点Ci,j＝C1,1， 其中Ci,j代表第i个簇的第j个点； S23、 将点C1,1对应的路径区间作为限定区间， 并将降序表中路径区间不包含在限定区 间的点去除， 得到新的降序表， S24、 按簇内缺点的数目从新的 降序表中依次取点与 点C1,1成簇， 得到第一簇团， 一个簇 团即为一个拣货子单； S25、 保存已成簇的簇团， 对剩下点重复S2 2‑S24， 直到无法得到 簇团为止 。 9.根据权利要求7所述的一种仓库拣货路径规划系统， 其特征在于： 所述第 二次聚簇模 块使用所述最小货架成簇算法将经过第一次聚簇后无法成簇的点进行第二次聚簇的方法 包括： S31、 取剩下 未成簇的点， 根据点的x值对所有点进行升序排列， 得到 升序表； S32、 根据每个拣货子单内要求的订单数量， 从所述升序表中依次取点成簇， 得到第二 簇团。 10.根据权利要求7所述的一种仓库拣货路径规划系统， 其特征在于： 所述全局优选模 块使用所述全局优化 算法在簇团内进行多次点交换操作的方法包括： S41、 从簇i开始， 寻找其相邻的所有簇， 记作簇团A， 若A不包含任何簇， 则i+1， 返回筛选权　利　要　求　书 2/3 页 3 CN 115456537 A 3