遞歸算法實踐--到倉合單助力京東物流提效增收详情 - 程序員京東雲開發者日志

一、背景

京東物流到倉業務「對商家」為了減少商家按照京東採購單分貨備貨過程，對齊行業直接按照流向交接，提升商家滿意度；「對京東」攬收操作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轉運效率更快；