Online 3-dimensional bin packing problem (O3D-BPP) is getting renewed prominence due to the industrial automation brought by Industry 4.0. However, due to limited attention in the past and its challenging nature, a good approximate algorithm is in scarcity as compared to 1D or 2D problems. This paper considers real-time O$3$D-BPP of cuboidal boxes with partial information (look-ahead) in an automated robotic sorting center. We present two rolling-horizon mixed-integer linear programming (MILP) cum-heuristic based algorithms: MPack (for bench-marking) and MPackLite (for real-time deployment). Additionally, we present a framework OPack that adapts and improves the performance of BP heuristics by utilizing information in an online setting with a look-ahead. We then perform a comparative analysis of BP heuristics (with and without OPack), MPack, and MPackLite on synthetic and industry provided data with increasing look-ahead. MPackLite and the baseline heuristics perform within bounds of robot operations and thus, can be used in real-time.
翻译:由于工业带来的工业自动化,在线3维垃圾包装问题(O3D-BPP)因工业自动化问题而重新得到重视。然而,由于过去关注有限,而且具有挑战性,与1D或2D问题相比,一种良好的近似算法仍然稀缺。本文考虑在自动机器人分类中心提供部分信息(视距)的幼虫箱实时O3$D-BPP(O3D-BPP),对自动机器人分类中心部分信息(视距)进行比较分析。我们提出了两种基于滚动和双向混合线性线性编程(MILP)和基于超重力的算法:MPack(用于台阶标记)和MPackLite(用于实时部署)。此外,我们提出了一个Opack框架,通过在有外观的在线环境中使用信息来调整和改进BPHeuristics的性能。我们随后对BPHeuristic(带和不带OPack)、MPack和关于合成和工业的MPackLite(MPackLite)进行了比较分析,提供越来越多的外观光头数据。MPackLite和在机器人操作范围内进行实际操作和使用的基线超时可以使用。