Studies on heuristic algorithms for cutting and packing problems

切割包装问题的启发式算法研究

• 批准号: 18700005
• 负责人: IMAHORI Shinji
• 金额: $ 2.41万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Young Scientists (B)
• 财政年份: 2006
• 资助国家: 日本
• 起止时间: 2006 至 2008
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18700005/
• 关键词: 組合せ最適化; アルゴリズム; 配置問題; 近似解法; 長方形詰込み; 多角形詰込み

本研究では,代表的な組合せ最適化問題であり,実社会においてもさまざまな応用をもつ配置問題に対して,実用性の高い近似解法の設計手法について研究することを目的とした.本研究で具体的に取り扱った問題は,長方形配置問題,多角形配置問題,および配置問題と同時に現れるカッターパス計算問題であり,これらの問題に対し,発見的解法やメタ戦略アルゴリズムの設計を行い,その計算効率と近似精度に関する理論的解析と,計算機実験による実用性の評価を行った.その結果,本研究で提案した近似解法が,既存手法と比較してより高い実用性を有すること確認された

This study represents a combinatorial optimization problem, which is socially relevant, and a design technique for practical and highly approximate solutions to the problem. In this paper, the concrete problems are rectangular configuration problem, polygonal configuration problem, and simultaneous computation problem. The solutions are found in the design of rectangular configuration problem, the theoretical analysis of approximate accuracy of computation efficiency, and the practical evaluation of computer implementation. The results of this study suggest that the approximate solution of the proposed method can be compared with the existing method, and that the proposed method can be used to confirm the feasibility of the proposed method.

项目成果

長方形配置問題に対するbest-fit法の効率的な実現

矩形布局问题最佳拟合方法的高效实现

• 发表时间: 2007
• 作者: 今堀慎治;柳浦睦憲
• 通讯作者: 柳浦睦憲

資源の有効利用-パッキング技法の貢献-

资源的有效利用 - 包装技术的贡献 -

• 发表时间: 2007
• 作者: 今堀慎治;梅谷俊治;柳浦睦憲
• 通讯作者: 柳浦睦憲

大規模な長方形詰込み問題に対する実用的解法

大规模矩形包装问题的实用解决方案

• 发表时间: 2007
• 作者: 今堀慎治;柳浦睦憲
• 通讯作者: 柳浦睦憲

Practical Algorithms for Two-dimensional Packing(in: T.F. Gonzalez (ed.), Handbook of Approximation Algorithms and Metaheuristics)

二维包装的实用算法（来自：T.F. Gonzalez (ed.), Handbook of Approximation Algorithms and Metaheuristics）

• 发表时间: 2007
• 作者: S. Imahori;M. Yagiura;H. Nagamochi
• 通讯作者: H. Nagamochi

Solving the irregular strip packing problem via guided local search for overlap minimization

通过引导局部搜索重叠最小化解决不规则条带堆积问题

• 发表时间: 2009
• 期刊: International Transactions in Operational Research 16
• 作者: S.Umetani;M.Yagiura;S.Imahori;T.Imamichi;K.Nonobe;T.Ibaraki
• 通讯作者: T.Ibaraki