一、背景

極光藍包裝盒成潮流標識，得物App成年輕潮人精神歸屬，特殊的包裝材料已經(jīng)在消費者之間形成了強大的心智，極光藍等于得物。

但是由于早期箱型尺寸數(shù)據(jù)由人工經(jīng)驗設(shè)計，出現(xiàn)包裝箱尺寸和商品尺寸匹配度不高的問題，一般會造成以下影響：

不合理的紙箱尺寸導(dǎo)致部分商品使用了較大的紙箱，造成了紙箱采購成本的浪費。

較大紙箱會造成運輸成本的增加。

商品和紙箱之間的空隙過大，可能在運輸過程中造成商品的損壞。

二、確定方案

考慮到紙箱招標節(jié)奏以及還需要留給倉內(nèi)打樣試裝，試發(fā)貨的時間，所以需要用比較快的速度完成建模和計算。

在這件事上，業(yè)務(wù)方也無法給出一些特別明確的準則，例如具體要算的綜合目標中是包含運輸成本的，這之中包含承運商的分配算法規(guī)則和他們的運費模板，將這些因素直接納入到箱型建模之中基本是不可能的，再如箱子的數(shù)量是影響采購招標談判的成本以及倉內(nèi)的人效的，這里很難量化，也無法直接定義箱型數(shù)量值的評判標準。因此首先要和業(yè)務(wù)方產(chǎn)品分析現(xiàn)狀定義目標，將問題全部量化，同時去簡化問題。

2.1 問題分析

sku數(shù)據(jù)：過去一年的發(fā)貨sku主數(shù)據(jù)及其對應(yīng)的銷量，再排除規(guī)則之外（只考慮用紙箱包裝發(fā)貨的商品、排除異性箱包裝商品）和異常值（如sku尺寸異常）。

紙箱尺寸參數(shù)約束：考慮面單尺寸（紙箱尺寸下限定義）和便于倉內(nèi)人員打包等合理性（紙箱尺寸上限定義），我們確定了紙箱上下限，形成數(shù)百萬組合的空間。

箱型數(shù)約束：排除異型箱，需綜合考慮裝箱率、采購成本和倉內(nèi)效率，一般來說單倉的箱型數(shù)量不宜超過15個。

覆蓋率約束：在已經(jīng)篩選出紙盒外包裝打包的sku的前提下，接受部分異形、大件物品不可被箱型組覆蓋，要求覆蓋發(fā)貨訂單率>=99%。

基于以上對問題的分析可以看出，如果有了一組解K個箱型，去計算裝箱率，這個問題的復(fù)雜度還好。但是如果正面去計算，則需對符合條件的sku去遍歷箱型組合，這個基本上是無法在有效時間內(nèi)算出結(jié)果的。

2.2 問題簡化

2.2.1 箱型數(shù)約束

排除異型箱，基于得物當前的倉內(nèi)實際情況，本次預(yù)計新設(shè)計的箱子數(shù)在8~15個，需綜合考慮裝箱率、采購成本和倉內(nèi)效率，當箱型數(shù)量增加時，裝箱率會提高，采購成本也會提高，倉內(nèi)效率會降低。

由于這里并不能量化它，例如給出具體綜合指數(shù)，因此此處決定給出多個版本，供業(yè)務(wù)方抉擇，而不作為建模的約束或目標，這里相當于直接簡化為把M組箱型的M * 固定一種箱型的復(fù)雜度，在實際中開發(fā)中，只需要用M個容器同時執(zhí)行一次計算即可。

2.2.2 覆蓋率約束

覆蓋率約束是個不等式約束，且當前問題，不可覆蓋的sku部分的分布是非常顯而易見的，集中在長寬高中一個或多個值超過倉內(nèi)操控方便程度上限值，因此，這里將箱型上限值和接受不覆蓋的部分，再建模之前先確定下來。

2.2.3 目標函數(shù)定義

對于采購成本來說，這不必說，一定和紙箱的用紙情況有關(guān)，紙箱用紙越?。埾湔归_面積越?。﹦t成本越低；

對于運輸成本來說，基本上3pl都是用MAX(拋重，實重)的方法來計算，那么這和紙箱展開面積的優(yōu)化方向也是正的；

如果把各3pl運費模板加入到建模中，同時也需要考慮承運商分配的算法設(shè)計，那么問題會過于復(fù)雜，計算量也是很大。現(xiàn)在很顯然，我們只要優(yōu)化單均用紙面積，如果某單優(yōu)化后的紙箱包裝未觸及運費模板的變動范圍，則運費不變，若觸及則運費成本必然會降低。

綜上，最終考慮用裝箱率這個間接指標作為目標，裝箱率指的是測試的（數(shù)據(jù)集sku總體積 / 數(shù)據(jù)集發(fā)貨箱子總體積），這個也是產(chǎn)品和業(yè)務(wù)方很熟悉且一直在關(guān)注的指標。

2.2.4 問題建模

經(jīng)過上述簡化，這里將目標函數(shù)定義成了裝箱率，并且發(fā)貨訂單覆蓋率、箱型數(shù)約束值放在了建模問題之外。

其中，S_i表示Sku_i的銷量，R_i表示Sku_i的推薦箱型結(jié)果裝箱率 推薦箱型應(yīng)滿足內(nèi)部間隙大于最低要求，在箱型組中選擇最小箱型，即

箱子的大小，應(yīng)滿足至少可以貼運單，也不能過大影響倉內(nèi)人員打包效率

同時我們對sku進行長>寬>高的排序清洗，同時定義紙箱長>寬>高

?

最后，我們要求箱子的長寬高數(shù)據(jù)均為整數(shù)，即

三、優(yōu)化算法

3.1 一般求解方法概述

對于這個優(yōu)化問題，通常主要包括精確解算法和啟發(fā)式算法：

精確方法主要是用單純形法（線性規(guī)劃）或者一些迭代的方法（非線性規(guī)劃）再結(jié)合分枝定界法找到我們要的整數(shù)解。精確方法如果是線性規(guī)劃問題能通過單純形法在可行域的頂點中找到全局最優(yōu)解，非線性規(guī)劃也是通過微分學(xué)方法或者有限次的迭代找到接近于最優(yōu)解的，由于不是多項式時間的求解方法，故而往往在大規(guī)模實例上不可行。

啟發(fā)算法如遺傳算法、蟻群算法、進化算法、智能算法針對普遍的問題。可以將它當作一個黑箱子對幾乎任何問題適用。啟發(fā)式算法，說白了就是有方向的窮舉法，在計算資源有限的情況下，需要根據(jù)問題場景和模型特點，選擇合理的鄰域結(jié)構(gòu)或操作機制，在全局搜索能力和局部搜索能力之間做權(quán)衡。啟發(fā)算法通常需要給定初始解；另外，算法不能保證在多項式時間收斂，但常?？梢钥刂扑惴ǖ螖?shù)。

3.2 精確解求法

線性規(guī)劃

對于線性規(guī)劃問題，它的可行解構(gòu)成的集合為凸集或者無界域，基可行解對應(yīng)凸集的頂點，通過凸集的性質(zhì)得出最優(yōu)解會在凸集的頂點上，然后通過遍歷再排序的方法可以得出最優(yōu)解，但是當頂點過多的時候，則需要用單純形法找到線性規(guī)劃的最優(yōu)解。

非線性規(guī)劃

如果目標函數(shù)或者約束條件中含有非線性函數(shù)，例如當前的問題中目標函數(shù)裝箱率中具有非線性因素，這種規(guī)劃問題為非線性規(guī)劃問題。一般來說，解非線性規(guī)劃問題要比解規(guī)劃問題困難的多，它不像求解線性規(guī)劃有單純形法這一種通用方法，非線性規(guī)劃目前還沒有適用于各種問題的一般算法，各個方法都有自己特定的適用范圍。

整數(shù)規(guī)劃

因為要求輸出的結(jié)果是整數(shù)，所以需要用分支定界法來求解。

分支定界法的核心思想就是分枝和剪枝。當不考慮所求解必須是整數(shù)這個條件時，用單純形法可求出最優(yōu)解，但是這個解往往不全是整數(shù)，因此采用剪枝的方式一點一點縮小范圍，直到所求解為整數(shù)解。

從圖中可以看到，初始化階段，需要給定輸出的全局的上界和下界，如果能有一些啟發(fā)式的方法獲得稍微好點的上下界作為初始解導(dǎo)入那是最好的不過的了。如果沒有的話可以先設(shè)置為正負無窮大。

接著進入到主循環(huán)中，通過求解整數(shù)規(guī)劃的連續(xù)松弛問題（線性規(guī)劃）來得到該子問題的上界；分解問題可以幫助對整數(shù)規(guī)劃問題進行拆分，同時也可以幫助我們得到下界。

3.3 元啟發(fā)式方法

以遺傳算法為代表的這類算法，適合以下場景：

神經(jīng)網(wǎng)絡(luò)超參數(shù)優(yōu)化

一部分結(jié)構(gòu)和特性固定的組合優(yōu)化問題

一部分機理模型難以建立的黑箱優(yōu)化問題

多目標優(yōu)化問題

3.3.1 遺傳算法

基本概念

基因：可行解的元素 染色體：一條染色體為一個可行解 交叉：多條染色體切斷拼接成新的染色體 變異：將染色體的部分基因進行修改 復(fù)制：完全遺傳復(fù)制上一條染色體

執(zhí)行流程

1）在算法初始階段，它會隨機生成一組可行解，也就是第一代染色體。

2）然后采用適應(yīng)度函數(shù)分別計算每一條染色體的適應(yīng)程度，并根據(jù)適應(yīng)程度計算每一條染色體在下一次進化中被選中的概率。

3）通過“交叉”，生成N-M條染色體。

4）再對交叉后生成的N-M條染色體進行“變異”操作。

5）然后使用“復(fù)制”的方式生成M條染色體；

6）重復(fù)2~5。

四、具體建模

4.1 數(shù)據(jù)分析

首先粗略看下近一年得物發(fā)貨的sku的長、寬、高主數(shù)據(jù)及其銷量分布，這是我們設(shè)計箱型的依據(jù)數(shù)據(jù)。同時綜合考慮倉內(nèi)實際作業(yè)時候的效率以及采購的成本，因此箱子的種類數(shù)量也不可太多，否則會增加倉內(nèi)打包人員取箱子的難度，采購成本也會相應(yīng)提高。

在這一步，考慮到首先要準確和當前箱型 A/B ，同時8~15種這個數(shù)量加入到建模參數(shù)中也增加了計算復(fù)雜度，所以決定固定這個箱型數(shù)量的值，首先假設(shè)固定N種箱型，每個箱型長寬高三個數(shù)，即輸出3 * N個參數(shù)。 接下來我們定義一下商品sku和箱型的 長>寬>高，首先對近一年的數(shù)據(jù)進行長寬高排序、異常值等清洗，例如固定了12種箱型，我們就將sku和箱型在長寬高維度用k-means聚類成12組。

? ?

做這個聚類分析，一方面，根據(jù)實際情況，例如結(jié)合面單尺寸定義箱型下限，再結(jié)合箱型覆蓋率下限值，定義箱型上限尺寸；

另一方面，每個聚類的最大值可以作為箱型的初始化值（實際需要加上5mm作為縫隙）。

4.2 約束和目標

業(yè)務(wù)上約束來說，只需要將商品裝入箱子，留下縫隙即可，且由于確定箱子的種類數(shù)量，這里還需要確定的是每組箱子的長>寬>高，即

constraint_ueq = (


    # 單個箱子長>寬>高
    lambda x: x[1] - x[0],
    lambda x: x[2] - x[1],


    lambda x: x[4] - x[3],
    lambda x: x[5] - x[4],


    ...   
 ）

def cal_avg_r_cached(p):
    '''The objective function. input routine, return total distance.
    cal_total_distance(np.arange(num_points))
    '''
    total_r = 0
    for row in npd:
        r = [-1] * box_num
        for i in range(box_num):
            if (row[0] <= p[3 * i]) and (row[1] <= p[3 * i + 1]) and (row[2] <= p[3 * i + 2]):
                r[i] = row[4] / (p[3 * i] * p[3 * i + 1] * p[3 * i + 2])
        total_r += max(r) * row[3]
    print(total_r)
    return -total_r / sum_cnt

4.3 結(jié)論

最終并行跑了幾個版本，裝箱率均有不等的提升，單均用紙面積有顯著下降； 最終選擇的1203方案作為工程側(cè)的輸出，裝箱率提升5.49%，單均用紙面積節(jié)約7.6%，單均運費降低0.06元。

五、彩蛋 -- 使用遺傳算法繪制NONO

在寫這篇文章查相關(guān)資料發(fā)現(xiàn)的挺有腦洞的內(nèi)容，用數(shù)個帶有顏色的三角形，組裝成圖像。 這里試著用60個三角形繪制了下NONO。

效果大致如下：

?

在優(yōu)化算法中，介紹了遺傳算法的大致流程，那么繪制這個NONO和箱型設(shè)計有啥區(qū)別呢？

在箱型設(shè)計中，需要基于裝箱率指標去計算箱子尺寸，因此，在定義適應(yīng)度函數(shù)的時候，只要取Maximize裝箱率這個指標即可，那么到了此處，只要將目標函數(shù)定義為不同顏色尺寸的透明三角形組裝結(jié)果與目標圖片的相似度即可。

5.1 適應(yīng)度函數(shù)

首先需要找到能夠量化透明三角形組成的圖和目標NONO圖的差異或者相似度的方法，那么如何定義相似度呢？圖像的相似度即在某個顏色空間（例如RGB、HSV）下的值向量的相似度，每個點的差異值總和最小則越接近想要的目標圖案，常用的評估函數(shù)例如MSE、RMSE、PSNR、ERGAS、SAM等。

下圖是對于一些圖像噪聲方法，各種相似度評估方法對應(yīng)的相似度結(jié)果。其中“Original”一欄顯示的是原始圖像與自身比較后的分數(shù)。 這里選擇ERGAS來作為我們的適應(yīng)度函數(shù)的依據(jù)。

5.2 選擇

這里用不一定完全用輪盤賭方法來做選擇，95%概率選擇適應(yīng)度函數(shù)靠前的解，5%的概率從其他解里面隨機選擇。

if random.random() < 0.95:
    '''選擇基因的來源父母，95%幾率從最優(yōu)的祖先中隨機'''
    poly_a = random.choice(polygons[:1])
    poly_b = random.choice(polygons[1:5])
else:
    '''選擇基因的來源父母，5%從所有的祖先中隨機'''
    poly_a = random.choice(polygons)
    poly_b = random.choice(polygons)

5.3 交叉和變異

這里也一樣用隨機數(shù)，大概率隨機從父類中繼承賦值基因，小概率修改基因值，坐標交叉變異大致如下，顏色交叉變異同理。

temp = random.random()
    if temp < 1 / polygon_num:
        '''設(shè)定一定幾率坐標變異'''
        rnd_temp_coord = poly_a.coord_list[i][:]
        rnd_temp_coord[random.randint(0, vertices - 1)] = random.randint(0, img_width), random.randint(0, img_height)
        temp_coords.append(rnd_temp_coord)
    elif temp < 0.5:
        '''隨機繼承父母中的一個基因'''
        temp_coords.append(poly_b.coord_list[i])
    else:
        temp_coords.append(poly_a.coord_list[i])
    temp = random.random()

審核編輯：劉清