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

神州控股

龚志峰

神州金库作为科捷自有研发系统，为客户提供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是表现最好的算法。对表现不好的案例分析，算法本身的效率不低，差值存在于对物品的挤压状况。切割体积造成的问题。