...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>INFORMS journal on computing >Combinatorial Benders Decomposition for the Two-Dimensional Bin Packing Problem
【24h】

Combinatorial Benders Decomposition for the Two-Dimensional Bin Packing Problem

机译：组合弯曲器对二维箱包装问题的分解

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The two-dimensional bin packing problem calls for packing a set of rectangular items into a minimal set of larger rectangular bins. Items must be packed with their edges parallel to the borders of the bins, cannot be rotated, and cannot overlap among them. The problem is of interest because it models many real-world applications, including production, warehouse management, and transportation. It is, unfortunately, very difficult, and instances with just 40 items are unsolved to proven optimality, despite many attempts, since the 1990s. In this paper, we solve the problem with a combinatorial Benders decomposition that is based on a simple model in which the two-dimensional items and bins are just represented by their areas, and infeasible packings are imposed by means of exponentially many no-good cuts. The basic decomposition scheme is quite naive, but we enrich it with a number of preprocessing techniques, valid inequalities, lower bounding methods, and enhanced algorithms to produce the strongest possible cuts. The resulting algorithm behaved very well on the benchmark sets of instances, improving on average on previous algorithms from the literature and solving for the first time a number of open instances.
机译：二维垃圾箱包装问题要求将一组矩形物品包装成最小的较大矩形箱。必须用与箱的边界平行的边缘包装项目，不能旋转，不能在它们之间重叠。问题是兴趣，因为它模拟了许多现实世界应用，包括生产，仓库管理和运输。遗憾的是，尽管许多尝试自20世纪90年代以来，它是非常困难的，但只有40件物品的实例是未解决的，以便证明最佳状态。在本文中，我们解决了基于一个简单模型的组合弯曲器分解的问题，其中二维物品和垃圾箱由它们的区域代表，并且通过指数呈许多不良切口施加不可行的包装。基本分解方案非常幼稚，但我们丰富了许多预处理技术，有效的不等式，下限方法和增强算法，以产生最强烈的削减。生成的算法在基准的实例组上表现得非常好，平均在文献中的前一算法上改善并解决了第一次开放实例。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号