一种基于包裹聚类和库位推荐的拣货波次规划方法与流程

1.本发明属于仓储拣货技术领域，具体涉及基于包裹聚类和库位推荐的拣货波次规划方法。


背景技术：

2.在电商仓储中实时会流入大量的订单信息，仓库系统会根据库存信息和订单需求拣货，电商仓库内存放商品多，订单相对较小，导致单个拣选订单非常困难，目前电商针对这种现状采用先分波聚合一个波次的订单需求，一个波次的商品分布在仓库的各个区域，每个区域会形成一个任务，在此区域的拣选工人会负责拣选这个任务所对应的商品，这些被不同区域拣选完的商品会最终合在一起并被整理成单个波次的商品集，单个波次的商品最后会被分成一个一个的包裹，最后打包贴面单通过物流手段最终流入客户手中，在所有仓储环节中，拣货是仓储物流中最占成本的工作，与拣货相关的人员约占整个仓储中心的50%，合理的优化拣选任务可以大大提高整个仓储物流的效率。目前上游分波和下游拣选大多分开处理，分波大多累计一定总量的订单或者一段时间窗口内的订单成为一个波次，下游的拣选直接遍历各个区域查询该区域能承担这个波次所需的商品的数量最大值然后进行分配，直到波次内所有的商品需求都被分配完成；为充分利用仓库面积，很多电商仓库开始使用随机库位而不是以往的指定库位，现有的分波方式只是纯粹对订单进行累积，并没有考虑对相似的订单进行聚类，而且目前的随机库存可以使得对于单个商品的拣选可以有多种选择，目前的拣选尚未利用这种可选择性，如果充分利用这两种特性，对订单同时进行分波和货位指派，可以大大减少拣选货物的工作量，因为现在的电商仓库内的拣货路线大多采用s形的行走路线，所以拣货人员的行走距离可以被拆解成巷道纵向行走距离和巷道横向行走距离，由于单个拣选任务已经被拆解到单个小区域，所以不再关注纵向行走距离，只集中在横向行走距离即巷道长度*巷道数，由于巷道长度是固定值，所以这里通过直接优化拣选完所有的货物所要经过的巷道数量来达到优化拣货行走距离的目的，显然，现有的方案中并没有解决拣选完所有的商品所需要经过的巷道最少，从而降低拣货所需要行走的距离的问题，需要研发一种新的规划方法来解决现有的技术方案。


技术实现要素：

3.本发明的目的在于提供一种基于包裹聚类和库位推荐的拣货波次规划方法，以解决拣选完所有的商品所需要经过的巷道较多的问题。
4.为实现上述目的，本发明提供如下技术方案：本发明的一种基于包裹聚类和库位推荐的拣货波次规划方法，包括以下步骤：步骤1：从包裹池随机抽取一个包裹，初始化波次；步骤2：初始化候选包裹，添加k个包裹，计算分波浓度；步骤3：寻找k个侯选包裹融入波次：添加另一组k个包裹，再次计算分波浓度，若再
次计算的分波浓度值大于目前的侯选包裹的分波浓度值，则替换侯选包裹，则把添加的k个包裹保留作为侯选包裹，同时把之前的k个侯选包裹放回波次池，且在这一轮中不再添加退回波次池的侯选包裹；若再次计算的分波浓度值小于目前的侯选包裹分波浓度值，则保留目前的侯选包裹，其中，k为正整数；步骤4：如果有剩余包裹，返回步骤3，如果没有剩余包裹，则输出波次。
5.上述波次输出的步骤如下：步骤41：在波次中确认候选包裹的融进波次；步骤42：重设包裹池，在包裹池里移去已正式融进波次的候选包裹；步骤43：如果包裹池没有剩余包裹或波次的包裹数已达上限，则到下一步输出波次；如果包裹池还有剩余包裹以及波次的包裹数还没达到上限，返回步骤3；步骤44：输出波次。
6.上述分波浓度的计算方法如下：计算每一个商品经过每一个通道的概率值，把每个通道的概率值加和，再把概率值再加和，并除以商品数；包括以下步骤：步骤21:包裹的每个sku出现在aisle_set的权重；包裹在每个通道的权重；第一个包裹和第二个包裹的相似度为；分子为包裹1和包裹2在每一条巷道的权重选小的一个，然后把这些权重加和；分母为包裹1和包裹2在所有巷道的权重加和，再减去分子；其中，sku为商品号，package为包裹集；sum()为加和函数，把括号()中的项加和；min()为求最小函数，从括号()中输出最小的项；z[sku,aisle]为0/1变量，当sku在巷道aisle时，z[sku,aisle]的值为1，否则为0；b:所有包裹的集合；a：所有巷道的集合；s
b
:包裹b中sku的集合；a
b
:包裹b中巷道数的集合；aisle_set_all是所有巷道的集；aisle_set是包裹裡的巷道aisle的集;
wi[aisle]为巷道aisle在包裹i裡的权重；wi为wi[aisle]所有巷道的简写；步骤22:随机选择一个包裹作为种子包裹，加入到波次中，添加新包裹到波次中，覆盖通道最多的包裹或者是覆盖sku最多的包裹，计算其他包裹与种子包裹的相似度，排序并依次加入波次中，直至违反约束,然后重新选择种子包裹继续执行步骤2。
[0007]
上述种子包裹中所有商品都需要被波次覆盖，波次覆盖公式为：，b是b的成员；w是所有波次的集，w是w的成员；s是所有sku的集，s是s的成员；a是a的成员；p是所有优先级的集，p是p的成员；表示种子包裹b的s商品是否被安排在第个波次拣选，且在第个巷道，第个优先级拣选的库存的数量,所述数量等于种子包裹有没有被个波次拣选，乘种子包裹里面包含s商品的数量，每个包裹都必须被且只被一个波次覆盖的计算公式如下：拣选的货物小于现有的库存，表示 s商品在巷道第优先级的库存数量，，限制单个波次中包含的包裹或者订单数不超过m个，计算公式如下 ,m为正整数；表示商品是否取优先级的商品，判断公式如下：最小化经过的巷道数的模型目标函数为，，z
wa
为波次w是否经过巷道a的变量，1为经过，0为不经过。
[0008]
上述库存的优先级越高，仓库会优先出库，所有库存商品优先级,下述约束表示商品若在优先级的库存的数量大于0，p2优先级的库存不出库，约束公式为：优先级的库存的数量大于0，p2优先级的库存不出库，约束公式为：表示商品是否取优先级的商品；isap1为 商品s在巷道a的优先p1的总库存量；如果xbwsap1 < isap1，那么fsp2就会为0，亦即代表p1优先及的库存还沒取完，不会取p2优先级的库存；波次中已经在这个过道取过的商品，则此波次拣货经过此过道的计算公式为：
。
[0009]
将所述包裹分配到波次的方法：计算每个商品的通道概率，将多个商品的通道概率加和，得到包裹选择各个通道的包裹概率；商品分配时，给所有商品指定库位，使所有商品拣货完成时所经过的巷道数最小:使拣选的商品数等于需求的商品数量计算公式如下：其中，表示商品在第个巷道，第个优先级拣选的库存的数量；表示商品的需求量，拣选的商品数量小于库存数量的计算公式为：取过商品的过道，则此次波次拣货经过此过道的计算公式为最小化经过的巷道数的所有商品拣货完成时目标函数为；z
a
为是否经过巷道a的变量，1为经过，0为不经过。
[0010]
本发明的技术效果和优点：该基于包裹聚类和库位推荐的拣货波次规划方法, 相比于现有的方案的优点，本发明给定一个包裹作为一个种子，用贪婪的方式往里面增加包裹同时优化路径，使得一个波次的拣货路径最短，但是现有方案具有很强的局部优化，和最优解的差距比本文提出的要大很多，且解的质量不可控,另外本发明把空间较大的调度问题变成了一个指派问题来求解，并且把分波和货位指派两个任务放在一个问题里面来解决，从而提供了更大的优化空间，具有较好的实际应用效果。
附图说明
[0011]
图1为本发明的分波算法流程图；图2为本发明的添加包裹流程图。
具体实施方式
[0012]
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0013]
本发明提供了如图1和图2，中所示的一种基于基于包裹聚类和库位推荐的拣货波次规划方法,先进行包裹聚类，然后进行库位推荐的拣货波次规划方法，包裹聚类包括两个循环，次一级循环寻找k个包裹加入波次，上一级循环寻找多个k个包裹加入波次直到符合波次要求；包裹聚类波次方法包括以下步骤：
步骤1：从包裹池随机抽取一个包裹，初始化波次；步骤2：初始化候选包裹，添加k个包裹，计算浓度；其中，k是一个可以调节的参数，k值越大，包裹聚类计算速度更快，但聚类效果也更差；所述步骤2中，分波浓度计算方法：计算每一个商品经过每一个可能通道概率，把每个通道的概率值加和，再把概率值再加和，并除以商品数；具体步骤是：步骤21:包裹的每个sku可能出现在的aisle_set的权重为 z[sku,aisle]=1/len(aisle_set)；包裹在每个通道的权重为w[aisle]= sum(z[sku,aisle] for aisle_set_all for sku in package)；第一个包裹和第二个包裹的相似度为 sum( min(w1[aisle] ,w2[ailse ]) for aisle in aisle_set)/(sum(w1) sum(w2)
‑ꢀ
sum( min(w1[aisle] ,w2[ailse ]) for aisle in aisle_set))；其中，sku为商品号、package为包裹集；当sku在巷道aisle，z[sku,aisle]的值为1，不然为0；aisle_set_all是所有巷道的集；w[aisle]为巷道aisle在每个包裹裡的权重，本实施例中，w1[aisle]与w2[aisle]分別为两个包裹的巷道aisle的权重步骤22:选择种子包裹，覆盖通道最多的包裹或者是覆盖sku最多的包裹，计算其他包裹与种子包裹的相似度，排序并依次加入波次中直至违反约束,然后重新选择种子包裹继续执行步骤2；步骤3：寻找k个侯选包裹融入波次：尝试添加另一组k个包裹，再次计算浓度，若再次计算的浓度比目前的侯选包裹更高，替换侯选包裹，把添加另一组k个包裹保留作侯选包裹，同时把之前的k个侯选包裹放回波次池，且在这一轮中不再添加退回波次池的侯选包裹，若浓度没有比目前的侯选包裹高，则保留目前的侯选包裹；步骤4：如果包裹剩余，返回步骤3，如果没有剩余包裹，输出波次；波次输出的步骤包括：步骤41：把在波次中的候选包裹确认融进波次；步骤42：重设包裹池，在包裹池里移去已正式融进波次的候选包裹；步骤43：如果包裹池没有包裹剩余或波次的包裹数已达上限，到下一步；如果包裹池还有包裹剩余以及波次的包裹数还没达上限，返回步骤3；步骤44：输出波次；通过累积一批订单，系统需要将所有的订单分波，并将所有波次的商品指派好库存拣货，使得拣选完所有的商品所需要经过的巷道最少，从而降低拣货所需要行走的距离；本实施例中，仓库储存的商品,拣选波次,巷道集合,因为仓库会有自有的运营策略比如清掉库龄较高的商品,所有库存商品本身存在优先级，对于优先级较高的库存，仓库会优先出库，分波的时候，为方便后续分包，需要把同一个订单或者包裹的商品分到同一个波次；所以模型需要满足这个波次一旦拿了这个包裹，这个包裹里面所有商品都需要被这个波次覆盖，且需要拿到需求量。表示这个包裹的商品是否被安排在第个波次拣选，且在第个巷道，第个优先级拣选的库存的数量。这个数量等于这个包裹有没有被个波次拣选，乘上这个包裹里面包含商品的数量，波次覆盖公式
为：每个包裹都必须被且只被一个波次覆盖的计算公式如下：拣选的货物必须比现有的库存要小的计算公式为，表示商品在巷道第优先级的库存数量，为了方便下游分波限制单个波次里面包含的包裹或者订单数不超过m个的计算公式如下：式如下：表示商品有没有拿优先级的商品的计算公式如下，为了满足运营策略比如清掉库龄较高的商品,所有库存商品本身存在优先级对于优先级较高的库存，仓库会优先出库，下述约束表示商品在p1优先级的库存没拿完的话，p2优先级的库存一个也不会拿，约束公式为：该波次在这个过道拿了商品，那么这个波次拣货的人就必须经过这个过道的计算公式为，整个模型的目标函数为最小化需要经过的巷道数的模型目标函数为。
[0014]
由于问题规模，无法直接求解，因此在求解时把原来分波和库存位指派分为两个阶段，分别求解；分波主要的作用是将包裹分配到波次，假设包裹b有3种商品(s1,s2,s3), s1的可能通道是(t1,t2,t3)，则 s1 选择通道 ( t1, t2, t3 ) 的概率 ( 1/3, 1/3, 1/3 )(平均概率)，同理可以计算 s2 的通道 ( t3, t4 ) 概率 ( 1/2, 1/2 ), s3 的通道 ( t4, t5 ) 的概率是（1/2, 1/2）,将多种商品的通道概率加和，得到包裹p选择各个通道的概率：( t1, t2, t3, t4, t5 ) 为 ( 1/3, 1/3, 1/3 1/2, 1/2 1/2, 1/2 )，每个通道被选择的最大概率为1。随机选择一个包裹p作为种子包裹，加入到波次中，假设其通道概率为 ( 0.1, 0.2, 0.3, 0.5, 0.9 )，总需求数量为5，则波次的初始通道选择概率为 ( 0.1, 0.2, 0.3, 0.5, 0.9 )，波次的商品数量为5。有一个新的包裹p2，假设其通道概率为 ( 0.4, 0.1, 0.8, 0.4, 1 ) ，总需求量为10。将新包裹p2加入到波次中，波次的浓度计算公式为：分子 = max ( 波次的通道概率, 新包裹p2的通道概率) = （max( 0.1, 0.4 ), max
( 0.2, 0.1 ), max( 0.3, 0.8 ), max( 0.5, 0.4 ), max( 0.9, 1 )）= ( 0.4, 0.2, 0.8, 0.5, 1 )。分子 = 分子的各个通道的概率加和 = 0.4 0.2 0.8 0.5 1 = 2.9，分母 = 波次的商品数 新包裹p2的商品数 = 5 10 = 15，浓度 = 分子/分母 = 2.9/15 = 0.192，遍历所有包裹，选择浓度最大的一个包裹加入到波次中，假设将包裹p2加入到波次中，则更新后的波次的通道概率= ( 0.4, 0.2, 0.8, 0.5, 1 )，商品数量为15，重复上面的过程，直到满足分波条件为止，一般是包裹数达到波次约束的上限值，此方法和jaccard聚类在覆盖类问题命名为jaccard
‑
variant；库位推荐的主要作用是，将一个波次里面的所有商品指定库位，使得拿完所有商品，拣货所经过的巷道数最小,因为分波的时候已经把包裹指定到波次里了，所以本模型不再关注包裹维度，且优先级在该模型中可以通过预处理处理掉，比如s1在这个波次中的需求量为10件，其中优先级为9的5件，优先级为8的4件，优先级为7的6件。那么预处理会优先去拿并且拿完优先级为8和优先级为9的所有s1的库存，那么优先级为8和优先级为9的库存所在巷道为必定会经过的巷道，只有优先级为7的库存还需要模型决定去哪个巷道拿一件，表示商品在第个巷道，第个优先级拣选的库存的数量，表示商品的需求量，模型需要满足拣选的商品数必须等于需求的商品数量的计算公式如下，拣选的商品数量，必须小于库存数量的计算公式为，在这个过道拿了商品，那么这个波次拣货的人就必须经过此过道的计算公式为，最小化经过的巷道数的所有商品拣货完成时目标函数为，。
[0015]
本实施例中，随机库位指每一个物品被指派存储的位置都是经由随机的过程所产生的，而且经常改变，也就是说，任何品项可以被存放在任何可以利用的位置，若能运用电脑协助随机存储的记忆管理，将仓库中每项物品的位置通过电脑记录，则可借助电脑来调配进货存储的位置空间；本实施例中，指定库位指每一项储存物品都有其固定货位，物品之间不能混用货位，因此规划每一项物品的货位容量时，不应小于其可能的在库容量。
[0016]
最后应说明的是：以上所述仅为本发明的优选实施例而已，并不用于限制本发明，尽管参照前述实施例对本发明进行了详细的说明，对于本领域的技术人员来说，其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换,凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。