作者：京东物流 李硕
一、背景
京东物流到仓业务「对商家」为了减少商家按照京东采购单分货备货过程，对齐行业直接按照流向交接，提升商家满意度；「对京东」揽收操作 APP 提效；到仓合单功能应运而生；
二、问题
一次批量采购单（一次 50 或者 100 个采购单）需要根据不同的规则合并成多个订单；
每一个采购单可以是不同的来源类型（自营和非自营）、不同的收货类型，每一个采购单会有多个 SKU，同一个 SKU 只有一个等级，一批采购单会有多个 SKU，同一个 SKU 会有多个等级；
合单规则：
1.自营和非自营不能合；
2.实物收货和单据收货的采购单不能合并；
3.相同收获仓和配送中心的采购单可以合并；
4.两个采购单如果合并之后同一个 SKU 拥有多个等级，则不可以合单；
三、打法
A、思路
1.首先认为这一批单子可以合单，后续就是根据合单规则将不符合规则转换成拆单的过程；
2.根据合单规则 1、2、3 可以将这一批单子拆成多个需要执行规则 4 的待合单集合 List；
3.举个极端例子，规则 1、2、3 这些采购单都是相同的，则该 List 数量为 1，这 100 个单子进行后续根据 SKU+等级维度的合单；
4.由于相同 SKU 不同等级不可以合单，我们可以先找出这 100 个采购单中包含最多等级的 SKU，比如 skuA 包含最多的 7 个等级, 根据 skuA 进行按等级进行分堆，分成 7 堆之后，由于并不是所有的采购单都包含 skuA， 则这 100 个采购单可能还会剩下一些单子不在这 7 堆之内，也就是剩下的这些单子如果只是基于 skuA 维度进行分堆，可以跟这 7 堆任何一堆进行合单，这时候需要将这些剩下的单子分别加入到这 7 堆里面，得到第一次合单后的结果，这里很重要，也是纳入递归算法的基础；
5.得到的 7 堆再分别进行第四步的操作，直到当前这一堆的 sku 不包含不同等级为止（这里是递归结束的条件）；
6.由于分堆里面包含了重复的订单，所以有些单子组合会被重复计算，这时候需要维护一个列表将计算过的单据进行保存，这样可以将重复的列表进行剪枝，这样可以保证整个算法的时间复杂度不是指数级增长；
7.针对最终全部递归之后的结果将合单的列表进行由多到少进行排序，然后进行排重，这里如果排重之后只有一个采购单了可以先释放，但不要加到排重列表里面，因为后面可能还会出现可合并的集合，很重要，不然得到的合单结果会变少，得到最终的合单后的结果；
B、算法
递归算法是一种通过重复将问题分解为同类的子问题来解决问题的方法; 特点是函数或子程序在运行过程中直接或间接调用自身;常见的递归算法包括Fibonacci 函数、Hanoi 问题和阶乘计算等；
C、解决方案
1. 递归代码块
/** * 指定不同等级不能合单 * * @param poNoSet 采购单号Set * @param poMainInfoMap 采购单详情 * @param calculatedSet 计算过的采购单据列表的集合 * @return */private List<Set<String>> doMergeClassDifferent(Set<String> poNoSet, Map<String, PoOrderFacadeResponse.PoMainInfo> poMainInfoMap, Set<String> calculatedSet) { // 如果该set已经计算过则不重复计算 List<Set<String>> resultList = new ArrayList<>(); String calculatedPoNoKey = buildCalculatedPoNoKey(poNoSet); if (calculatedSet.contains(calculatedPoNoKey)) { return resultList; } else { calculatedSet.add(calculatedPoNoKey); resultValue.incrementAndGet(); }
// 以sku为key的集合 Set<String> skuSet = new HashSet<>(); // 以sku 为key, 值为poNos Map<String, Set<String>> skuMap = new HashMap<>(); // 存放同一个sku下有多少个不同等级的集合 Map<String, Set<String>> skuToskuLevelMap = new HashMap<>();
// 以sku+level 为key的集合 Set<String> skuLevelSet = new HashSet<>(); // 以sku+level 为key, 值为poNos Map<String, Set<String>> skuLevelMap = new HashMap<>();
for (String poNo : poNoSet) { PoOrderFacadeResponse.PoMainInfo poMainInfo = poMainInfoMap.get(poNo); // 采购单条目 List<PoOrderFacadeResponse.PoItemInfo> poItemInfos = poMainInfo.getPoItemInfos(); for (PoOrderFacadeResponse.PoItemInfo poItemInfo : poItemInfos) {
String skuKey = poItemInfo.getGoodsNo(); String skuLevelKey = buildSkuLevelKey(poItemInfo); skuSet.add(skuKey); setKeyMap(skuKey, skuMap, poNo); // 存放同一个sku下有多少个不同等级的集合 Set<String> stringSet = skuToskuLevelMap.get(skuKey); if (CollectionUtils.isEmpty(stringSet)) { stringSet = new HashSet<>(); skuToskuLevelMap.put(skuKey, stringSet); } stringSet.add(skuLevelKey); skuLevelSet.add(skuLevelKey); setKeyMap(skuLevelKey, skuLevelMap, poNo); } }
if (skuSet.size() == skuLevelSet.size()) { // 此处sku的数量和sku+level的数量相同，不需要再进行递归运算 // 方法结束的出口 resultList.add(poNoSet); return resultList; } else { // 同一个sku下最多等级个数 int high = MagicCommonConstants.NUM_1; // 最多等级个数的对应sku String maxLevelSku = ""; for (String sku : skuToskuLevelMap.keySet()) { Set<String> strings = skuToskuLevelMap.get(sku); if (strings.size() > high) { high = strings.size(); maxLevelSku = sku; } } if (high > MagicCommonConstants.NUM_1) { // 获取该sku下的poNos Set<String> strings = skuMap.get(maxLevelSku); // 差集 Set<String> chaJiSet = poNoSet; chaJiSet.removeAll(strings);
Set<String> skuLevels = skuToskuLevelMap.get(maxLevelSku); for (String skuLevel : skuLevels) { Set<String> poNoTempSet = skuLevelMap.get(skuLevel); poNoTempSet.addAll(chaJiSet); // 递归计算 List<Set<String>> clist = doMergeClassDifferent(poNoTempSet, poMainInfoMap, calculatedSet); if (CollectionUtils.isNotEmpty(clist)) { resultList.addAll(clist); } } } }
return resultList;}
复制代码
2. 去重代码块
/** * 去重 合单之后的采购单号 * * @param sets * @param dooModel */private List<Set<String>> uniqueRepeatPoNo(List<Set<String>> sets, DooModel dooModel) { sets.sort(new Comparator<Set<String>>() { @Override public int compare(Set<String> o1, Set<String> o2) { return o2.size() - o1.size(); } });
List<Set<String>> resultList = new ArrayList<>(); Set<String> allMergedSet = new HashSet<>();
Set<String> allSet = new HashSet<>(); for (Set<String> set : sets) { Set<String> tempSet = new HashSet<>(); for (String poNo : set) { if (!allSet.contains(poNo)) { tempSet.add(poNo); allMergedSet.add(poNo); } } if (!tempSet.isEmpty()) { if (tempSet.size() > 1) { allSet.addAll(tempSet); resultList.add(tempSet); } // 此处的单条后面不一定不能合单 } }
// 差集 allMergedSet.removeAll(allSet); if (allMergedSet.size() > 0) { for (String poNo: allMergedSet) { putPoNoToSet(dooModel, poNo); } } return resultList;}
复制代码
四、价值
目前上线之后刚推广，功能上线 45 天，已经在浙江、 河南、上海、江苏、安徽、天津、四川、北京 22 个客户使用，增收 500 万整体运营平稳，且在大促期间合单收货功能优势更加凸显：「对商家」减少商家按照京东采购单分货备货过程，对齐行业直接按照流向交接，商家满意度提升。「对京东」 揽收操作 APP 提效 30%，分货、入库交仓效率提升 10％，整体 TC 转运效率更快；
五、总结
难点：将根据 SKU 分堆之后剩下的采购单分别加到不同的分堆中，这个方案也是思考了好久之后想到的，然后构造成递归进行计算，最终进行去重；
性能：递归算法中大部分计算都是重复的，但是经过记录中间计算结果，将计算过的采购单集合直接剪枝，计算时间就不会随着采购单的数量增长而指数增长，真实情况也是随着单据数量的增加、SKU 和等级的种类增多依然健壮；
评论