作者：京東物流 李碩

一、背景

京東物流到倉(cāng)業(yè)務(wù)「對(duì)商家」為了減少商家按照京東采購(gòu)單分貨備貨過(guò)程，對(duì)齊行業(yè)直接按照流向交接，提升商家滿意度；「對(duì)京東」攬收操作APP提效；到倉(cāng)合單功能應(yīng)運(yùn)而生；

二、問(wèn)題

一次批量采購(gòu)單（一次50或者100個(gè)采購(gòu)單）需要根據(jù)不同的規(guī)則合并成多個(gè)訂單；

每一個(gè)采購(gòu)單可以是不同的來(lái)源類(lèi)型（自營(yíng)和非自營(yíng)）、不同的收貨類(lèi)型，每一個(gè)采購(gòu)單會(huì)有多個(gè)SKU，同一個(gè)SKU只有一個(gè)等級(jí)，一批采購(gòu)單會(huì)有多個(gè)SKU，同一個(gè)SKU會(huì)有多個(gè)等級(jí)；

合單規(guī)則：

1.自營(yíng)和非自營(yíng)不能合；

2.實(shí)物收貨和單據(jù)收貨的采購(gòu)單不能合并；

3.相同收獲倉(cāng)和配送中心的采購(gòu)單可以合并；

4.兩個(gè)采購(gòu)單如果合并之后同一個(gè)SKU擁有多個(gè)等級(jí)，則不可以合單；

三、打法

A、思路

1.首先認(rèn)為這一批單子可以合單，后續(xù)就是根據(jù)合單規(guī)則將不符合規(guī)則轉(zhuǎn)換成拆單的過(guò)程；

2.根據(jù)合單規(guī)則1、2、3可以將這一批單子拆成多個(gè)需要執(zhí)行規(guī)則4的待合單集合List；

3.舉個(gè)極端例子，規(guī)則1、2、3這些采購(gòu)單都是相同的，則該List數(shù)量為1，這100個(gè)單子進(jìn)行后續(xù)根據(jù)SKU+等級(jí)維度的合單；

4.由于相同SKU不同等級(jí)不可以合單，我們可以先找出這100個(gè)采購(gòu)單中包含最多等級(jí)的SKU，比如skuA 包含最多的7個(gè)等級(jí), 根據(jù)skuA進(jìn)行按等級(jí)進(jìn)行分堆，分成7堆之后，由于并不是所有的采購(gòu)單都包含skuA， 則這100個(gè)采購(gòu)單可能還會(huì)剩下一些單子不在這7堆之內(nèi)，也就是剩下的這些單子如果只是基于skuA維度進(jìn)行分堆，可以跟這7堆任何一堆進(jìn)行合單，這時(shí)候需要將這些剩下的單子分別加入到這7堆里面，得到第一次合單后的結(jié)果，這里很重要，也是納入遞歸算法的基礎(chǔ)；

5.得到的7堆再分別進(jìn)行第四步的操作，直到當(dāng)前這一堆的sku不包含不同等級(jí)為止（這里是遞歸結(jié)束的條件）；

6.由于分堆里面包含了重復(fù)的訂單，所以有些單子組合會(huì)被重復(fù)計(jì)算，這時(shí)候需要維護(hù)一個(gè)列表將計(jì)算過(guò)的單據(jù)進(jìn)行保存，這樣可以將重復(fù)的列表進(jìn)行剪枝，這樣可以保證整個(gè)算法的時(shí)間復(fù)雜度不是指數(shù)級(jí)增長(zhǎng)；

7.針對(duì)最終全部遞歸之后的結(jié)果將合單的列表進(jìn)行由多到少進(jìn)行排序，然后進(jìn)行排重，這里如果排重之后只有一個(gè)采購(gòu)單了可以先釋放，但不要加到排重列表里面，因?yàn)楹竺婵赡苓€會(huì)出現(xiàn)可合并的集合，很重要，不然得到的合單結(jié)果會(huì)變少，得到最終的合單后的結(jié)果；

B、算法

??遞歸算法是一種通過(guò)重復(fù)將問(wèn)題分解為同類(lèi)的子問(wèn)題來(lái)解決問(wèn)題的方法?; 特點(diǎn)是函數(shù)或子程序在運(yùn)行過(guò)程中直接或間接調(diào)用自身;常見(jiàn)的遞歸算法包括?Fibonacci函數(shù)、?Hanoi問(wèn)題和?階乘計(jì)算等；

C、解決方案

1. 遞歸代碼塊

/**
 * 指定不同等級(jí)不能合單
 *
 * @param poNoSet       采購(gòu)單號(hào)Set
 * @param poMainInfoMap 采購(gòu)單詳情
 * @param calculatedSet 計(jì)算過(guò)的采購(gòu)單據(jù)列表的集合
 * @return
 */
private List> doMergeClassDifferent(Set poNoSet, Map poMainInfoMap, Set calculatedSet) {
    // 如果該set已經(jīng)計(jì)算過(guò)則不重復(fù)計(jì)算
    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();
    // 存放同一個(gè)sku下有多少個(gè)不同等級(jí)的集合
    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);
        // 采購(gòu)單條目
        List poItemInfos = poMainInfo.getPoItemInfos();
        for (PoOrderFacadeResponse.PoItemInfo poItemInfo : poItemInfos) {

            String skuKey = poItemInfo.getGoodsNo();
            String skuLevelKey = buildSkuLevelKey(poItemInfo);
            skuSet.add(skuKey);
            setKeyMap(skuKey, skuMap, poNo);
            // 存放同一個(gè)sku下有多少個(gè)不同等級(jí)的集合
            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的數(shù)量和sku+level的數(shù)量相同，不需要再進(jìn)行遞歸運(yùn)算
        // 方法結(jié)束的出口
        resultList.add(poNoSet);
        return resultList;
    } else {
        // 同一個(gè)sku下最多等級(jí)個(gè)數(shù)
        int high = MagicCommonConstants.NUM_1;
        // 最多等級(jí)個(gè)數(shù)的對(duì)應(yīng)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);
                // 遞歸計(jì)算
                List> clist = doMergeClassDifferent(poNoTempSet, poMainInfoMap, calculatedSet);
                if (CollectionUtils.isNotEmpty(clist)) {
                    resultList.addAll(clist);
                }
            }
        }
    }

    return resultList;
}

2. 去重代碼塊

/**
 * 去重 合單之后的采購(gòu)單號(hào)
 *
 * @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;
}

四、價(jià)值

目前上線之后剛推廣，功能上線45天，已經(jīng)在浙江、 河南、上海、江蘇、安徽、天津、四川、北京22個(gè)客戶使用，增收500萬(wàn)整體運(yùn)營(yíng)平穩(wěn)，且在大促期間合單收貨功能優(yōu)勢(shì)更加凸顯：「對(duì)商家」減少商家按照京東采購(gòu)單分貨備貨過(guò)程，對(duì)齊行業(yè)直接按照流向交接，商家滿意度提升。「對(duì)京東」 攬收操作APP提效30%，分貨、入庫(kù)交倉(cāng)效率提升10％，整體TC轉(zhuǎn)運(yùn)效率更快；

五、總結(jié)

難點(diǎn)：將根據(jù)SKU分堆之后剩下的采購(gòu)單分別加到不同的分堆中，這個(gè)方案也是思考了好久之后想到的，然后構(gòu)造成遞歸進(jìn)行計(jì)算，最終進(jìn)行去重；

性能：遞歸算法中大部分計(jì)算都是重復(fù)的，但是經(jīng)過(guò)記錄中間計(jì)算結(jié)果，將計(jì)算過(guò)的采購(gòu)單集合直接剪枝，計(jì)算時(shí)間就不會(huì)隨著采購(gòu)單的數(shù)量增長(zhǎng)而指數(shù)增長(zhǎng)，真實(shí)情況也是隨著單據(jù)數(shù)量的增加、SKU和等級(jí)的種類(lèi)增多依然健壯；

審核編輯 黃宇