继续创作，加快成长！这是我参加「日新计划 10 月更文应战」的第5天，点击查看活动详情
一、布景
极光蓝包装盒成潮流标识，得物App成年轻潮人精神归属，特别的包装材料现已在消费者之间形成了强壮的心智，极光蓝等于得物。
可是因为早期箱型尺度数据由人工经历规划，出现包装箱尺度和产品尺度匹配度不高的问题，一般会形成以下影响：
- 不合理的纸箱尺度导致部分产品运用了较大的纸箱，形成了纸箱收购本钱的浪费。
- 较大纸箱会形成运送本钱的添加。
- 产品和纸箱之间的空隙过大，可能在运送过程中形成产品的损坏。
二、确认计划
考虑到纸箱投标节奏以及还需求留给仓内打样试装，试发货的时间，所以需求用比较快的速度完结建模和核算。
在这件事上，事务方也无法给出一些特别清晰的准则，例如详细要算的归纳方针中是包含运送本钱的，这之中包含承运商的分配算法规矩和他们的运费模板，将这些要素直接纳入到箱型建模之中基本是不行能的，再如箱子的数量是影响收购投标谈判的本钱以及仓内的人效的，这儿很难量化，也无法直接界说箱型数量值的评判标准。因而首要要和事务方产品剖析现状界说方针，将问题全部量化，一起去简化问题。
2.1 问题剖析
sku数据：过去一年的发货sku主数据及其对应的销量，再扫除规矩之外（只考虑用纸箱包装发货的产品、扫除异性箱包装产品）和异常值（如sku尺度异常）。
纸箱尺度参数束缚：考虑面单尺度（纸箱尺度下限界说）和便于仓内人员打包等合理性（纸箱尺度上限界说），咱们确认了纸箱上下限，形成数百万组合的空间。
箱型数束缚：扫除异型箱，需归纳考虑装箱率、收购本钱和仓内功率，一般来说单仓的箱型数量不宜超过15个。
掩盖率束缚：在现已筛选出纸盒外包装打包的sku的前提下，承受部分异形、大件物品不行被箱型组掩盖，要求掩盖发货订单率>=99%。
根据以上对问题的剖析可以看出，假如有了一组解K个箱型，去核算装箱率，这个问题的复杂度还好。可是假如正面去核算，则需对契合条件的sku去遍历箱型组合，这个基本上是无法在有用时间内算出成果的。
2.2 问题简化
2.2.1 箱型数束缚
扫除异型箱，根据得物当时的仓内实际情况，本次估计新规划的箱子数在8~15个，需归纳考虑装箱率、收购本钱和仓内功率，当箱型数量添加时，装箱率会提高，收购本钱也会提高，仓内功率会下降。因为这儿并不能量化它，例如给出详细归纳指数，因而此处决定给出多个版别，供事务方抉择，而不作为建模的束缚或方针，这儿相当于直接简化为把M组箱型的M * 固定一种箱型的复杂度，在实际中开发中，只需求用M个容器一起执行一次核算即可。
2.2.2 掩盖率束缚
掩盖率束缚是个不等式束缚，且当时问题，不行掩盖的sku部分的散布是非常显而易见的，会集在长宽高中一个或多个值超过仓内操控方便程度上限值，因而，这儿将箱型上限值和承受不掩盖的部分，再建模之前先确认下来。
2.2.3 方针函数界说
关于收购本钱来说，这不用说，必定和纸箱的用纸情况有关，纸箱用纸越小（纸箱打开面积越小）则本钱越低；
关于运送本钱来说，基本上3pl都是用MAX(抛重，实重)的办法来核算，那么这和纸箱打开面积的优化方向也是正的；
假如把各3pl运费模板加入到建模中，一起也需求考虑承运商分配的算法规划，那么问题会过于复杂，核算量也是很大。现在很显然，咱们只需优化单均用纸面积，假如某单优化后的纸箱包装未触及运费模板的变化范围，则运费不变，若触及则运费本钱必然会下降。
综上，终究考虑用装箱率这个直接方针作为方针，装箱率指的是测试的（数据集sku总体积 / 数据集发货箱子总体积），这个也是产品和事务方很熟悉且一直在重视的方针。
2.2.4 问题建模
经过上述简化，这儿将方针函数界说成了装箱率，而且发货订单掩盖率、箱型数束缚值放在了建模问题之外。
其间，S_i表明Sku_i的销量，R_i表明Sku_i的引荐箱型成果装箱率
引荐箱型应满意内部空隙大于最低要求，在箱型组中挑选最小箱型，即
箱子的大小，应满意至少可以贴运单，也不能过大影响仓内人员打包功率
一起咱们对sku进行长>宽>高的排序清洗，一起界说纸箱长>宽>高
最后，咱们要求箱子的长宽高数据均为整数，即
三、优化算法
3.1 一般求解办法概述
关于这个优化问题，一般主要包含精确解算法和启发式算法：
精确办法主要是用单纯形法（线性规划）或许一些迭代的办法（非线性规划）再结合分枝定界法找到咱们要的整数解。精确办法假如是线性规划问题能经过单纯形法在可行域的极点中找到全局最优解，非线性规划也是经过微分学办法或许有限次的迭代找到挨近于最优解的，因为不是多项式时间的求解办法，故而往往在大规模实例上不行行。
启发算法如遗传算法、蚁群算法、进化算法、智能算法针对遍及的问题。可以将它当作一个黑箱子对几乎任何问题适用。启发式算法，说白了便是有方向的穷举法，在核算资源有限的情况下，需求根据问题场景和模型特色，挑选合理的邻域结构或操作机制，在全局搜索才能和局部搜索才能之间做权衡。启发算法一般需求给定初始解；别的，算法不能保证在多项式时间收敛，但常常可以控制算法迭代次数。
3.2 精确解求法
-
线性规划
关于线性规划问题，它的可行解构成的集合为凸集或许无界域，基可行解对应凸集的极点，经过凸集的性质得出最优解会在凸集的极点上，然后经过遍历再排序的办法可以得出最优解，可是当极点过多的时分，则需求用单纯形法找到线性规划的最优解。
-
非线性规划
假如方针函数或许束缚条件中含有非线性函数，例如当时的问题中方针函数装箱率中具有非线性要素，这种规划问题为非线性规划问题。一般来说，解非线性规划问题要比解规划问题困难的多，它不像求解线性规划有单纯形法这一种通用办法，非线性规划现在还没有适用于各种问题的一般算法，各个办法都有自己特定的适用范围。
-
整数规划
因为要求输出的成果是整数，所以需求用分支定界法来求解。
分支定界法的中心思维便是分枝和剪枝。当不考虑所求解有必要是整数这个条件时，用单纯形法可求出最优解，可是这个解往往不全是整数，因而采用剪枝的办法一点一点缩小范围，直到所求解为整数解。
从图中可以看到，初始化阶段，需求给定输出的全局的上界和下界，假如能有一些启发式的办法获得略微好点的上下界作为初始解导入那是最好的不过的了。假如没有的话可以先设置为正负无穷大。
接着进入到主循环中，经过求解整数规划的连续松懈问题（线性规划）来得到该子问题的上界；分化问题可以协助对整数规划问题进行拆分，一起也可以协助咱们得到下界。
3.3 元启发式办法
以遗传算法为代表的这类算法，合适以下场景：
- 神经网络超参数优化
- 一部分结构和特性固定的组合优化问题
- 一部分机理模型难以树立的黑箱优化问题
- 多方针优化问题
3.3.1 遗传算法
-
基本概念
- 基因：可行解的元素
- 染色体：一条染色体为一个可行解
- 穿插：多条染色体堵截拼接成新的染色体
- 变异：将染色体的部分基因进行修改
- 仿制：彻底遗传仿制上一条染色体
-
执行流程
- 在算法初始阶段，它会随机生成一组可行解，也便是第一代染色体。
- 然后采用习惯度函数别离核算每一条染色体的习惯程度，并根据习惯程度核算每一条染色体鄙人一次进化中被选中的概率。
- 经过“穿插”，生成N-M条染色体。
- 再对穿插后生成的N-M条染色体进行“变异”操作。
- 然后运用“仿制”的办法生成M条染色体；
- 重复2~5。
四、详细建模
4.1 数据剖析
首要大略看下近一年得物发货的sku的长、宽、高主数据及其销量散布，这是咱们规划箱型的根据数据。一起归纳考虑仓内实际作业时分的功率以及收购的本钱，因而箱子的种类数量也不行太多，否则会添加仓内打包人员取箱子的难度，收购本钱也会相应提高。
在这一步，考虑到首要要精确和当时箱型 A/B ，一起8~15种这个数量加入到建模参数中也添加了核算复杂度，所以决定固定这个箱型数量的值，首要假定固定N种箱型，每个箱型长宽高三个数，即输出3 * N个参数。
接下来咱们界说一下产品sku和箱型的 长>宽>高，首要对近一年的数据进行长宽高排序、异常值等清洗，例如固定了12种箱型，咱们就将sku和箱型在长宽高维度用k-means聚类成12组。
做这个聚类剖析，一方面，根据实际情况，例如结合面单尺度界说箱型下限，再结合箱型掩盖率下限值，界说箱型上限尺度；
另一方面，每个聚类的最大值可以作为箱型的初始化值（实际需求加上5mm作为缝隙）。
4.2 束缚和方针
事务上束缚来说，只需求将产品装入箱子，留下缝隙即可，且因为确认箱子的种类数量，这儿还需求确认的是每组箱子的长>宽>高，即
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],
...
）
方针则是max 装箱率，即
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 结论
终究并行跑了几个版别，装箱率均有不等的提高，单均用纸面积有显著下降；
终究挑选的1203计划作为工程侧的输出，装箱率提高5.49%，单均用纸面积节约7.6%，单均运费下降0.06元。
五、彩蛋 — 运用遗传算法制作NONO
在写这篇文章查相关资料发现的挺有脑洞的内容，用数个带有色彩的三角形，拼装成图画。
这儿试着用60个三角形制作了下NONO。
效果大致如下：
在优化算法中，介绍了遗传算法的大致流程，那么制作这个NONO和箱型规划有啥区别呢？
在箱型规划中，需求根据装箱率方针去核算箱子尺度，因而，在界说习惯度函数的时分，只需取Maximize装箱率这个方针即可，那么到了此处，只需将方针函数界说为不同色彩尺度的透明三角形拼装成果与方针图片的类似度即可。
5.1 习惯度函数
首要需求找到可以量化透明三角形组成的图和方针NONO图的差异或许类似度的办法，那么如何界说类似度呢？图画的类似度即在某个色彩空间（例如RGB、HSV）下的值向量的类似度，每个点的差异值总和最小则越挨近想要的方针图案，常用的评估函数例如MSE、RMSE、PSNR、ERGAS、SAM等。
下图是关于一些图画噪声办法，各种类似度评估办法对应的类似度成果。其间“Original”一栏显现的是原始图画与自身比较后的分数。
这儿挑选ERGAS来作为咱们的习惯度函数的根据。
5.2 挑选
这儿用不必定彻底用轮盘赌办法来做挑选，95%概率挑选习惯度函数靠前的解，5%的概率从其他解里面随机挑选。
if random.random() < 0.95:
'''挑选基因的来历父母，95%几率从最优的先人中随机'''
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 穿插和变异
这儿也相同用随机数，大概率随机从父类中承继赋值基因，小概率修改基因值，坐标穿插变异大致如下，色彩穿插变异同理。
temp = random.random()
if temp < 1 / polygon_num:
'''设定必定几率坐标变异'''
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()
*文 /酱油
重视得物技能，每周一三五晚18:30更新技能干货
要是觉得文章对你有协助的话，欢迎评论转发点赞～
