An agent-based approach to the two-dimensional guillotine bin packing problem
An agent-based approach to the two-dimensional guillotine bin packing problem
复制标题
DOI：
10.1016/j.ejor.2007.10.020
复制
发表时间：
2009-02
期刊：
影响因子：
--
通讯作者：
S. Polyakovskiy;R. M’Hallah
中科院分区：
文献类型：
--
作者：
S. Polyakovskiy;R. M’Hallah
二维断头台装箱问题是将无重叠的小矩形物品装箱到最少数量的大矩形箱子中，通过断头台切割获得物品。使用一种新的断路器左下(GBL)构造性启发式算法及其基于代理(A-B)的实现来解决该问题。GBL是顺序的，它会将物品连续装入垃圾箱，并在每次无法再将任何未打包的物品放入当前垃圾箱时创建一个新的垃圾箱。A-B是伪平行的，它使用了最简单的人工生命系统。该系统由主动智能体组成，每个智能体由自己的参数、决策过程和适应度评估驱动，实时动态交互，共同填充垃圾箱。A-B算法速度特别快，可以产生接近最优的解。它的模块化使得它很容易适应背包相关的问题。
The two-dimensional guillotine bin packing problem consists of packing, without overlap, small rectangular items into the smallest number of large rectangular bins where items are obtained via guillotine cuts. This problem is solved using a new guillotine bottom left (GBL) constructive heuristic and its agent-based (A–B) implementation. GBL, which is sequential, successively packs items into a bin and creates a new bin every time it can no longer fit any unpacked item into the current one. A–B, which is pseudo-parallel, uses the simplest system of artificial life. This system consists of active agents dynamically interacting in real time to jointly fill the bins while each agent is driven by its own parameters, decision process, and fitness assessment. A–B is particularly fast and yields near-optimal solutions. Its modularity makes it easily adaptable to knapsack related problems.