在电商仓储中,对于不规则物品打包作业属于特殊的三维装箱问题(three dimensional bin packing problem,3D-BPP),需要选择箱子的种类和数量,确定物品的装箱位置和方向,以期最大化利用装载空间.本文采用点云刻画不规则物品的形状,通过颗粒化的思想,将稀疏不均匀的点云转化为不规则物品的空间颗粒凸包,构建了不规则物品三维装箱问题的空间颗粒模型;通过提炼装箱活动实践操作的专家规则,设计了基于经验模拟的启发式算法,并结合DQN(deep q-network)算法框架设计了针对不规则物品三维装箱问题的H-DQN(heuristic deep q-network)算法.此外,本文基于现有行业数据,开发了一个实例生成器用于算例测试.数值测试结果表明,相较于遗传算法等已有算法,H-DQN算法的空间利用率平均提高到45.92％;同时计算速度明显加快,平均降低了 97％的计算时间,验证了 H-DQN算法处理3D-BPP的有效性.
Intelligent Three-dimensional Bin Packing Decision Research for E-commerce Based on Spatial Granular Model
In e-commerce warehouses,the packaging of irregular items is a special type of three-dimensional bin packing problem(3D-BPP),which requires the selection of box types and quantities,and the determination of the packing positions and orientations of items,in order to maximize the utilization of loading space.This paper uses point clouds to characterize the shape of irregular items.By the idea of granulation,the sparse and uneven point clouds are transformed into the spatial granular convex hull of irregular items,and the spatial granular model of the three-dimensional packing problem of irregular items is constructed.By extracting the expert rules of the practical operation of packing activities,a heuristic algorithm based on experience simulation is designed.Combined with the DQN(deep q-network)algorithm framework,an H-DQN(heuristic deep q-network)algorithm for the three-dimensional packing problem of irregular items is designed.In addition,this paper develops an instance generator based on existing industry data for case testing.The numerical test results show that the H-DQN algorithm improves the average space utilization rate to 45.92％compared with existing algorithms such as the genetic algorithm.At the same time,the calculation speed is significantly accelerated,reducing the average calculation time by 97％,which verifies the effectiveness of the H-DQN algorithm in handling 3D-BPP.
万方数据
维普
