(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211122690.9 (22)申请日 2022.09.15 (71)申请人 江南大学 地址 214122 江苏省无锡市滨湖区蠡湖大 道1800号 (72)发明人 刘洋　王崇邺　 (74)专利代理 机构 苏州市中南伟业知识产权代 理事务所(普通 合伙) 32257 专利代理师 李柏柏 (51)Int.Cl. G06Q 10/08(2012.01) G06Q 10/04(2012.01) G06K 9/62(2022.01) (54)发明名称 面向订单聚合的拣货路径动态优化方法及 系统 (57)摘要 本发明公开了一种面向订单聚合的拣货路 径动态优化方法， 包括根据库位布局生成仓储 单， 基于仓储单货物货架信息生成拣货单； 提取 拣货单中每个订单的货架信息， 根据提取到的订 单货架信息生成一 以最大货架编号为纵轴和最 小货架编号为横轴的二维正交坐标轴， 将每一个 订单的最大货架编号和最小货架编号转换成二 维正交坐标轴上的点； 选取初始点， 使用欧氏距 离选择相邻点路径差小的订单聚类形成簇， 并对 全部簇的总路径进行优化， 确定最佳仓库 拣货路 径， 输出同一簇订单号及相应的货架号。 本发明 能够解决传统K ‑Means算法K值和初始簇中心不 确定性导致产生误差的问题， 实现了缩短拣货行 走总路径的技 术效果， 提高了 仓库拣货的效率。 权利要求书3页 说明书8页 附图2页 CN 115439064 A 2022.12.06 CN 115439064 A 1.一种面向订单聚合的拣货路径动态优化方法， 其特 征在于， 包括以下步骤： S1、 根据库位布局生成仓储单， 基于 仓储单货物货架信息生成拣货单； S2、 提取所述拣货单中每个订单的货架信 息， 对每个订单采取区间化操作， 根据提取到 的订单货架信息生成一以最大货架编号为纵轴和最小货架编号为横轴的二维正交坐标轴， 将每一个订单的最大货架编号和最小货架编号转换成二 维正交坐标轴上的点， 以将拣货单 的批量订单聚合 寻优问题转 化为对正交坐标轴上点聚类的问题； S3、 选取初始点， 使用欧氏距离选择相邻点路径差小的订单聚类形成簇， 并对全部簇的 总路径进行优化， 确定最佳仓库拣货路径， 输出同一簇订单号及相应的货架号。 2.根据权利要求1所述的一种面向订单聚合的拣货路径动态优化方法， 其特征在于， 所 述S2中每个订单均包含最小货架号和最大货架， 其中最小货架号为初始位置， 最大货架号 为终点位置， 对于只取单个货物的订单， 其最大货架 号和最小货架号相同， 均为货物所在的 货架号。 3.根据权利要求1所述的一种面向订单聚合的拣货路径动态优化方法， 其特征在于， 所 述S3中选取初始点的方法包括： 使用改进的DBSCAN算法将二维正交坐标轴上所有订单点按密度大小划分， 得到需要分 成的扇区簇的个数和初始聚类中心。 4.根据权利要求3所述的一种面向订单聚合的拣货路径动态优化方法， 其特征在于， 所 述S3中聚类成簇以及对 全部簇的总路径进行优化的方法包括： S31、 计算 二维正交坐标轴上 所有订单点的密度系数； S32、 选取其中K个密度较大的订单点作为聚类中心； S33、 扩大以聚类中心为圆心的圆， 将包 含的点划归到圆形簇内； S34、 计算 新的簇中心， 再聚簇； S35、 判断新的聚类结果是否与上一次的聚类结果相同， 若相同则转入S36， 若不相同则 转入S33； S36、 舍去圆形簇的左上、 右上和左下扇区的点； S37、 对得到 的每个簇采用改进的K ‑Means算法分别计算其包含的订单点数量， 标记右 下扇区每一簇中离 簇中心最远的点； S38、 判断簇内点的个数是否满足预设值， 若判断结果为是， 则将该簇的点从数据点中 删去， 并转入S39， 若判断结果 为否， 则将标记点移入离其 最近的簇中， 并转入S37； S39、 计算优化后所有簇的总路径， 输出订单聚类的结果。 5.根据权利要求4所述的面向订单聚合的拣货路径动态优化方法， 其特征在于， 所述 S31中密度系数的计算公式为： 一个订单点On的密度 ξn表示为： 权　利　要　求　书 1/3 页 2 CN 115439064 A 2其中， ωm为概率系数， s为订单On到更高密度点的最小距离， 为订单点m与 订单点 n之间的密度关系 系数。 6.根据权利要求5所述的一种面向订单聚合的拣货路径动态优化方法， 其特征在于， 所 述S32中选取聚类中心的方法包括： 计算聚类中心概率， 根据所述聚类中心概率选取聚类中心， 其中聚类中心概率的计算 公式如下： pn＝ξn×sn 其中， ξn表示密度， sn表示订单n到更高密度点的最小距离 。 7.一种面向订单聚合的拣货路径动态优化系统， 其特 征在于， 包括： 拣货单生成模块， 根据库位布局生成仓储单， 所述拣货单生成模块用于基于仓储单货 物货架信息生成拣货单； 订单处理模块， 所述订单处理模块用于提取所述拣货单中每个订单的货架信息， 对每 个订单采取区间化操作， 根据提取到的订单货架信息生成一以最大货架编号为纵轴和最小 货架编号为横轴的二 维正交坐标轴， 将 每一个订单的最大货架编号和最小货架编号转换成 二维正交坐标轴上的点， 以将拣货单的批量订单聚合寻优问题转化为对正交坐标轴上点聚 类的问题； 订单聚类模块， 所述订单聚类模块用于选取初始点， 使用欧氏距离选择相邻点路径差 小的订单聚类形成簇， 并对全部簇的总路径进行优化， 确定最佳仓库拣货路径， 输出同一簇 订单号及相应的货架号。 8.根据权利要求7所述的一种面向订单聚合的拣货路径动态优化系统， 其特征在于， 所 述订单聚类模块选取初始点的方法包括： 使用改进的DBSCAN算法将二维正交坐标轴上所有订单点按密度大小划分， 得到需要分 成的扇区簇的个数和初始聚类中心。 9.根据权利要求8所述的一种面向订单聚合的拣货路径动态优化系统， 其特征在于， 所 述订单聚类模块聚类成簇以及对 全部簇的总路径进行优化的方法包括： S31、 计算 二维正交坐标轴上 所有订单点的密度系数； S32、 选取其中K个密度较大的订单点作为聚类中心； S33、 扩大以聚类中心为圆心的圆， 将包 含的点划归到圆形簇内； S34、 计算 新的簇中心， 再聚簇； S35、 判断新的聚类结果是否与上一次的聚类结果相同， 若相同则转入S36， 若不相同则 转入S33； S36、 舍去圆形簇的左上、 右上和左下扇区的点； S37、 对得到 的每个簇采用改进的K ‑Means算法分别计算其包含的订单点数量， 标记右 下扇区每一簇中离 簇中心最远的点； S38、 判断簇内点的个数是否满足预设值， 若判断结果为是， 则将该簇的点从数据点中权　利　要　求　书 2/3 页 3 CN 115439064 A 3