組合せ最適化 - 典型問題 - n次元パッキング問題

典型問題と実行方法

##n次元パッキング問題

n次元の直方体に、なるべく多くのn次元の直方体の詰込む。その方法を求めよ。
nは、1から3にあたる。nが1の場合、ナップサック問題で容量と価値が同じケースとなる。

##実行方法(ギロチンカットによる2次元パッキング問題)

usage

Init signature: TwoDimPackingClass(self, width, height, items=None)
Docstring:
2次元パッキング問題
    ギロチンカットで元板からアイテムを切り出す(近似解法)
入力
    width, height: 元板の大きさ
    items: アイテムの(横,縦)のリスト
出力
    容積率と入ったアイテムの(横,縦,x,y)のリスト

python

from ortoolpy import TwoDimPackingClass
TwoDimPackingClass(500, 300, [(240, 150), (260, 100), \
    (100, 200), (240, 150), (160, 200)]).solve()

結果

(1.0,
 [(240, 150, 0, 0),
  (260, 100, 240, 0),
  (160, 200, 240, 100),
  (100, 200, 400, 100),
  (240, 150, 0, 150)])

python

# pandas.DataFrame
from ortoolpy.optimization import TwoDimPacking
TwoDimPacking('data/tdpacking.csv', 500, 300)[1]

	width	height	x	y
0	240	150	0	0
1	260	100	240	0
4	160	200	240	100
2	100	200	400	100
3	240	150	0	150

##データ

• data/tdpacking.csv