神州金库系统中的装箱算法

神州控股

龚志峰

神州金库作为科捷自有研发系统
，，，为客户提供B2B/B2C全供应链提供一体化服务，，，
，可前端订单接入、、、中端订单数据处理（OMS、
、、、BMS、、、、WMS
、、、、TMS等）、、、、大数据处理等，，亦可对接智能化设备。。通过全国仓包材使用情况统计，，发现B2C业务装箱问题比较突出
，，，一是
：包材选用不合理，，
，人工装箱时没有逻辑规则概念，，，，导致每年该部分损耗严重；二是：箱材的选用影响效率，
，，
，且准确率低。。。。装箱问题在仓储物流行业也是普遍存在的难题，
，纷纷进行装箱算法研究
。。
。据网上的公开信息，，
，，阿里对装箱问题进行的研究，，，其物流算法统计，
，，，平均可以减少5%的包装，，
，，2017年双十一发货量超过10亿件，
，，，可节省4500多万个箱子。。。推行菜鸟电子面单替代传统三联面单，，阿里电商平台上商家使用率已经达到80%，，，，每一年节约纸张费用达12亿元。。科捷依托神州金库对该方面的问题进行了不断的研究和探索
。。

01

关于三维装箱问题主要从以下几个方面进行探讨

三维装箱问题算法：

装箱工人在装箱过程中需要对订单的商品选择箱型
，，评估商品体积和箱子容积的正确比例，，这一过程极其耗费资源，，，给仓库作业带来困难的同时还降低了作业效率。。
。其次，，
，，所送商品会出现装箱不合理的情况
，，如，，顾客只是买一款体积很小的商品，，，，收到的确是一个很大很空的箱子，，，，浪费资源的同时，，
，，也给用户带来困惑，
，，同时零售商的专业性也遭到了质疑。
。

三维装箱规则：

1) 所有箱子均视为标准的长方体或者正方体
。。长宽高为内围长宽高。
。。。

2) 所有商品均描述为矩形，，，，长宽高为外围长宽高。。。

3) 装箱时
，，，优先放置大件商品。。
。。如果大件商品放不满的情况下，，，考虑次小商品，，，直到放满为止。。

4) 装箱时，
，优先选择容积小的箱子
。。容积更小的箱子如果能够装下商品
，，则剩余容积会更小，，说明箱子更适合商品
。
。其次优先选择常规指数最大的箱子（值越大越常规
，，，值越小表示是非常规箱型甚至是特型箱）。
。

5) 如果订单中的商品恰好已经装完，，，，箱子未满，，，，尝试更换容积更小的箱子
。。。如果爆箱则换回原来的箱型
。。。。

6) 如果订单中的商品恰好已经装完
，
，出现爆箱，，，，尝试更换小一号箱子，，，后继续装箱剩余商品。。。。如果此时箱子已经是最小，
，则更换成多个箱子装箱
。。。

7) 将箱型按照容积从小到大的顺序排列。
。
。如果箱子装不满优先尝试小的箱型。。

8) 箱子优先放置大件商品，
，
，然后放置次大商品，，，
，最后放订单中最小的商品。。。

9) 如果所有的箱子都不能一个箱子装下单个订单内的全部商品，，
，，才会启用多个箱子来装商品
。。。。

对一次装箱过程进行了分解，，，每次需要一个商品和一个空箱子，，，同时会产生三块新的更小的剩余空间。。这三块剩余空间又可以看作是新的箱子
。。和新的合适自己的空间大小的商品去匹配
。
。。。

那么
，，，，这就是一个递归算法，，，方法输入一款商品和一个箱子，，每一次递归都会产生三个新的箱子
，
，新的箱子又可以装入其它更小的商品。。
。

如此循环往复
，，直到每一个新的箱子连最小的商品都装不下了，，或者没有任何商品可以装进箱子里了，，这个过程就会自动结束
。。这是递归的出口条件。。
。。

02

目前使用较多的算法

1) Heuristic Algorithm启发式演算法
：工业应用，，
，，时间短。。。
。用于在合理时间内找到可接受的摆放方式（结果）。。
。。

2) Exact Methods精准算法：学术应用
，，，，用于研究Global Optimality，，，Solution Error Bound。。最早的数学编程模型，，，混合整数线性规划模型，
，，，但是，，，，利用整数规划解决问题不太现实
，，计算量太大不好实现
，，，，很难用线性的求解器去精准解决非线性的问题

3) Three-dimensional open-dimension rectangular packing probloems(3D-ODRPP)。。。

3D-ODRPP算法详解：

a) box_selection：选出所有箱子中最小体积的那个；输入：所有箱子体积；输出：输出已打包物品清单，
，找到的最小箱型；pack_boxes：判断单个箱子打包所有物品；输入：单个箱子体积；输出：输出已打包物品清单。。。

b) pack_boxes：判断单个箱子打包所有物品；输入：单个箱子体积；输出：输出已打包物品清单
；insert_items_into_dimensions：将需要打包的物体塞进给定体积；输入：剩余长方体体积，
，需要打包物品，，，，已打包物品；输出
：剩余长方体体积（更新），，，，需要打包物品（更新），
，，已打包物品（更新）
。。。。

c) insert_items_into_dimensions：将需要打包的所有物体塞进给定体积
；输入：剩余长方体体积，，需要打包物品，，，已打包物品；输出：剩余长方体体积（更新）
，，，
，需要打包物品（更新），，
，已打包物品（更新）。
。。best_fit：将需要打包单个物体放进给定体积并给出最好切割方法；输入：给定长方体体积，，
，，物品体积
；输出：剩余长方体体积，
，三个长方体。
。
。

03

针对以上算法进行算法测试设计

对比1：和仅考虑总体积的情况比较。。。。仅考虑体积筛选会选出一些箱型会摆放不开的小箱子，，，进行筛选和比较
。。。。例：物体体积小但特别长
。。。。

对比2：和仅考虑总体积+能容纳所有物体三边的情况比较。
。此种筛选会筛选掉因为物体过长而放不进去的小箱子
，，
，依然会选出些摆放不下所有物体的小箱子。。。例：物体形状平均但因为位置关系摆放不下。。

对比3：先和Ortools的结果对比。
。因为Ortools跑出来的结果不够理想，，，，起码要比Ortools的表现好。。。。从良品铺子物品清单和沈阳良品-包材维护中抽取随机订单，，，
，订单长度（0-6个）。。。（因为一般的订单大小都在这个范围内）看看生成的箱型是否比Ortools的小一些
。。
。
。

04

真实数据测试

选用200个出库运单，，
，，每个运单对应一个箱子，，箱子中物体从1到21不等
。。。。数据来源沈阳良品库，
，9个箱型。。
。已删除0体积物品（赠品海报一类）。
。。无拆单，，拆单率不足1%。。

结论：200个出库运单中，，
，表现最好的是3DFFD先放长物体的策略，，和之前随机订单生成的测试结果一致。。。

05

算法表现分析

算法进行的是切割。。
。再拼凑的问题
，，，，会直接抛弃掉一些放不进东西的体积（优化）。。切割是演变式算法的弊端，，不好规避。。订单的物品越少，，，切割次数越少，，效率会越高。。
。和之前随机订单生成的测试结果一致，，，3DFFD是表现最好的算法。。。
。对表现不好的案例分析，，，
，算法本身的效率不低，，，，差值存在于对物品的挤压状况。。切割体积造成的问题。。