作者：京東物流 李碩

一、背景

京東物流到倉業務「對商家」為了減少商家按照京東采購單分貨備貨過程，對齊行業直接按照流向交接，提升商家滿意度；「對京東」攬收操作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> doMergeClassDifferent(Set poNoSet, Map poMainInfoMap, Set calculatedSet) {
    // 如果該set已經計算過則不重復計算
    List> resultList = new ArrayList();
    String calculatedPoNoKey = buildCalculatedPoNoKey(poNoSet);
    if (calculatedSet.contains(calculatedPoNoKey)) {
        return resultList;
    } else {
        calculatedSet.add(calculatedPoNoKey);
        resultValue.incrementAndGet();
    }

    // 以sku為key的集合
    Set skuSet = new HashSet();
    // 以sku 為key, 值為poNos
    Map> skuMap = new HashMap();
    // 存放同一個sku下有多少個不同等級的集合
    Map> skuToskuLevelMap = new HashMap();

    // 以sku+level 為key的集合
    Set skuLevelSet = new HashSet();
    // 以sku+level 為key, 值為poNos
    Map> skuLevelMap = new HashMap();

    for (String poNo : poNoSet) {
        PoOrderFacadeResponse.PoMainInfo poMainInfo = poMainInfoMap.get(poNo);
        // 采購單條目
        List 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 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 strings = skuToskuLevelMap.get(sku);
            if (strings.size() > high) {
                high = strings.size();
                maxLevelSku = sku;
            }
        }
        if (high > MagicCommonConstants.NUM_1) {
            // 獲取該sku下的poNos
            Set strings = skuMap.get(maxLevelSku);
            // 差集
            Set chaJiSet = poNoSet;
            chaJiSet.removeAll(strings);

            Set skuLevels = skuToskuLevelMap.get(maxLevelSku);
            for (String skuLevel : skuLevels) {
                Set poNoTempSet = skuLevelMap.get(skuLevel);
                poNoTempSet.addAll(chaJiSet);
                // 遞歸計算
                List> clist = doMergeClassDifferent(poNoTempSet, poMainInfoMap, calculatedSet);
                if (CollectionUtils.isNotEmpty(clist)) {
                    resultList.addAll(clist);
                }
            }
        }
    }

    return resultList;
}

2. 去重代碼塊

/**
 * 去重 合單之后的采購單號
 *
 * @param sets
 * @param dooModel
 */
private List> uniqueRepeatPoNo(List> sets, DooModel dooModel) {
    sets.sort(new Comparator>() {
        @Override
        public int compare(Set o1, Set o2) {
            return o2.size() - o1.size();
        }
    });

    List> resultList = new ArrayList();
    Set allMergedSet = new HashSet();

    Set allSet = new HashSet();
    for (Set set : sets) {
        Set 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和等級的種類增多依然健壯；

審核編輯 黃宇