J9集团

J9集团金库系统中的装箱算法

J9集团控股

龚志峰

J9集团金库作为科捷自有研发系统，为客户提供B2B/B2C全供给链提供一体化服务，可前端订单接入、中端订单数据处置（OMS、BMS、WMS、TMS等）、大数据处置等，亦可对接智能化设备。通过全国仓包材使用情况统计，发现B2C业务装箱问题比力凸起，一是：包材选用不合理，人为装箱时没有逻辑规定概想，导致每年该部门损耗严沉；二是：箱材的选用影响效能，且正确率低。装箱问题在仓储物盛行业也是普遍存在的难题，纷纷进行装箱算法钻研。据网上的公开信息，阿里对装箱问题进行的钻研，其物流算法统计，均匀能够削减5%的包装，2017年双十一发货量超过10亿件，可节俭4500多万个箱子。奉行菜鸟电子面单代替传统三联面单，阿里电商平台上商家使用率已经达到80%，每一年节约纸张用度达12亿元？平菀栏絁9集团金库对该方面的问题进行了不休的钻研和索求。

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是阐发最好的算法。对阐发不好的案例分析，算法自身的效能不低，差值存在于对物品的挤压情况。切割体积造成的问题。