Construction of Plat-form Models for the Problemof Packing Geometrical Objects

几何对象填充问题的平台模型构建

• 批准号: 20500012
• 负责人: NAGAMOCHI Hiroshi
• 金额: $ 2.91万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2010
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20500012/
• 关键词: 可視化; 詰め込み問題; パッキング; アルゴリズム; 最適化; 機械学習; グラフ描; 準ニュートン法; 離散最適化; 配置問題; グラフ描画; ルーティング問題; 近似解法; 計算幾何学; 組合せ最適; 図形配置; データ構造; 非線形最適化; 情報可視化

In this study, we proposed "Multi-sphere Scheme" to efficiently pack given two- or three-dimensional objects in a compact space, designed all the components of the scheme, and investigated fundamental theory on geometrical packings and graph drawings. We designed an algorithm that can directly transform given triangle-mesh data into data for Multi-sphere Scheme based on a graph-theoretical analysis. We developed a 3D visual interface for Multi-sphere Scheme, by which we can easily check computational results in a visualized form. We greatly improved our solver for packing rectangles so that a long-standing open benchmark instance is solved for the first time by our new solver. As for the theory part, we found a 2D representation of triconnected graphs so that a useful triconnected decomposition can be easily obtained, and a characterization of the graphs of non-convex polytopes in a certain class.In particular, the latter result is the first such result since Steinitz' theorem, a characterization of the graphs of convex polytopes is found 80 years ago.

在本研究中，我们提出了在紧凑空间中对给定的二维或三维物体进行高效包装的多球体方案，设计了该方案的所有组成部分，并研究了几何包装和图形绘制的基本理论。在图论分析的基础上，设计了一种将给定的三角网格数据直接转换为多球体数据的算法。我们为多球体格式开发了一个三维可视化界面，可以方便地以可视化的形式查看计算结果。我们极大地改进了用于填充矩形的求解器，因此我们的新求解器首次解决了一个长期存在的开放基准实例。在理论部分，我们得到了三连通图的二维表示，从而可以很容易地得到一个有用的三连通分解，并刻画了某类非凸多面体的图，特别是后者是自80年前Steinitz定理发现凸多面体的图的刻画以来的第一个结果。

项目成果

Visualization can improve multiple decision table classifiers

可视化可以改进多个决策表分类器

• 发表时间: 2009
• 作者: 上田祐華;他;K.Haraguchi
• 通讯作者: K.Haraguchi

Efficient branch-and-bound algorithms for one-dimensional contiguous bin packing problem and two-dimensional strip packing problem

一维连续装箱问题和二维带状装箱问题的高效分支定界算法

• 发表时间: 2009
• 作者: T.Imamichi;Y.Arahori;H.Nagamochi
• 通讯作者: H.Nagamochi

Optimization problems and algorithms in double-layered food packing systems, Journal of Advanced Mechanical Design

双层食品包装系统的优化问题和算法，《先进机械设计杂志》

• 发表时间: 2010
• 期刊: Systems, and Manufacturing Vol.4, No.3
• 作者: Y.Karuno;H.Nagamochi;X.Wang
• 通讯作者: X.Wang

Exact algorithms for the 2-dimensional strip packing problem with and without rotations

带旋转和不带旋转的二维条带堆积问题的精确算法

• 发表时间: 2009
• 期刊: European Journal of Operational Research 198(1)
• 作者: M.Kenmochi;T.Imamichi;K.Nonobe;M.Yagiura;H.Nagamochi
• 通讯作者: H.Nagamochi

Minimum Degree Orderings

• DOI: 10.1007/s00453-008-9239-2
• 发表时间: 2007-12
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: H. Nagamochi