多集装箱装箱、背包和 覆盖问题

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

摘要翻译：
许多组合优化问题，如装箱问题和多背包问题，涉及到将一组离散对象分配给多个集装箱。这些问题可用于多Agent系统和分布式系统中的任务和资源分配问题的建模，也可作为调度问题的子问题。针对一维多集装箱装箱问题，我们提出了一种分枝定界策略&装箱完成策略。Bin补全将面向Bin的搜索空间与一个强大的优势准则相结合，使我们能够修剪大部分空间。基本bin完成框架的性能可以通过使用许多扩展来增强，包括基于nogood的剪枝技术，这些技术允许进一步利用优势标准。将装箱完成应用于四个问题：多背包问题、装箱覆盖问题、最小成本覆盖问题和装箱问题。我们证明了我们的bin补全算法对于多重背包问题、bin复盖问题和最小代价复盖问题产生了新的、最先进的结果，在一些困难的、随机的问题实例上，相对于运行时间，我们的bin补全算法比以前的算法性能高出几个数量级。对于装箱问题，我们证明了与大多数以前的结果相比有显著的改进，但表明装箱完成与当前最先进的基于切割库存的方法没有竞争力。
---
英文标题：
《Bin Completion Algorithms for Multicontainer Packing, Knapsack, and
  Covering Problems》
---
作者：
A. S. Fukunaga, R. E. Korf
---
最新提交年份：
2011
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--

---
英文摘要：
  Many combinatorial optimization problems such as the bin packing and multiple knapsack problems involve assigning a set of discrete objects to multiple containers. These problems can be used to model task and resource allocation problems in multi-agent systems and distributed systms, and can also be found as subproblems of scheduling problems. We propose bin completion, a branch-and-bound strategy for one-dimensional, multicontainer packing problems. Bin completion combines a bin-oriented search space with a powerful dominance criterion that enables us to prune much of the space. The performance of the basic bin completion framework can be enhanced by using a number of extensions, including nogood-based pruning techniques that allow further exploitation of the dominance criterion. Bin completion is applied to four problems: multiple knapsack, bin covering, min-cost covering, and bin packing. We show that our bin completion algorithms yield new, state-of-the-art results for the multiple knapsack, bin covering, and min-cost covering problems, outperforming previous algorithms by several orders of magnitude with respect to runtime on some classes of hard, random problem instances. For the bin packing problem, we demonstrate significant improvements compared to most previous results, but show that bin completion is not competitive with current state-of-the-art cutting-stock based approaches.
---
PDF链接：
https://arxiv.org/pdf/1110.2209

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖

关键词：集装箱 Presentation Optimization Intelligence exploitation knapsack 策略 库存 Bin 集装箱