The three-dimensional bin packing problem (3D-BPP) plays an important role in city logistics and manufacturing environments, due to its direct relevance to operational cost. Most existing literature have investigated the conventional 3D-BPP, in which the shape of items are typically considered as regular shapes, e.g., rectangular-shaped rigid boxes or cylindrical-shaped containers. However, 3D-BPP for non-rectangular shaped items are quite common in varies delivery schemes, especially in fresh food delivery, and few published studies focusing on these issues. In this paper, we address a novel 3D-BPP variant in which the shape changing factor of non-rectangular and deformable items is incorporated to further enhance the loading efficiency and reduce the operational cost of related companies. Motivated by the compression process of item-loading, we propose a constructive heuristic (i.e., an improved dynamic-volume-based packing algorithm) to solve the studied problem. Experimental results over a set of randomly generated instances reveal that considering shape changing factor is indeed able to achieve higher space utilization than that of conventional schemes, thereby has potential to save packaging and delivering cost, as well as enhance operation efficiency.
翻译:在城市物流和制造环境中,三维垃圾包装问题(3D-BPP)在城市物流和制造环境中起着重要作用,因为它与业务费用直接相关,大多数现有文献都对常规的3D-BPP进行了调查,在常规的3D-BPP中,物品的形状通常被视为正常形状,例如矩形硬体箱或圆柱体形容器;然而,用于非矩形物品的3D-BPP在不同的交付计划中非常常见,特别是在新鲜食品的交付方面,而且针对这些问题的公布的研究很少。在本文件中,我们讨论了一个新的3D-BPP变异物,其中纳入了非矩形和变形物品的形状变异因,以进一步提高装载效率,降低相关公司的业务费用。受重装物品压缩过程的驱动,我们提议了一种建设性的超常(即改进的动态容量包装算法)来解决所研究的问题。一组随机生成的事例表明,变形因素确实能够实现比常规计划更高的空间利用率,从而可以节省和交付成本。