Pynote

Python、機械学習、画像処理について

Python - Python で2次元箱詰め問題 (bin packing problem) を解いてみる。

概要

2次元箱詰め問題を rectpack を使って解いてみた。

2次元箱詰め問題 (bin packing problem)

容器 (bin) と箱 (box) が与えられたとき、箱を容器に効率よく詰める方法を探す問題である。

rectpack

rectpack は、2次元箱詰め問題 (in packing problem) のソルバーを提供しているライブラリである。

pip install rectpack

まず容器と箱を定義する。どちらも大きさ (幅, 高さ) であるタプルのリストで表す。

import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle
from rectpack import newPacker

# 容器
bins = [(500, 500)]
# 箱
rects = [(200, 200), (200, 200), (200, 400), (200, 100), (200, 100),
         (100, 100), (100, 100), (100, 100), (100, 100), (100, 100)]

ソルバーを作成し、newPacker.add_bin(width, height) で容器、newPacker.add_rect(width, height) で箱を登録する。
登録する際に求解したあとにどの箱であったかをわかるように bid で容器の ID、rid で箱の ID を設定する。
登録したら、newPacker.pack() で積付けを実行する。

packer = newPacker()

# 容器を設定する。
for i, b in enumerate(bins):
    packer.add_bin(*b, bid=i)

# 箱を設定する。
for i, r in enumerate(rects):
    packer.add_rect(*r, rid=i)

# 積付けを実行する。
packer.pack()

結果が出たので、matplotlib で可視化してみる。

def draw_result(packer):
    fig = plt.figure()
    for i, abin in enumerate(packer, 1):
        ax = fig.add_subplot(1, len(packer), i, aspect='equal')

        # 容器を描画する。
        ax.add_patch(Rectangle((0, 0), abin.width, abin.height,
                               fc='none', ec='g', lw=2, zorder=10))
        for r in abin:
            # 箱を描画する。
            ax.add_patch(Rectangle((r.x, r.y), r.width,
                                   r.height, fc='lightblue', ec='k'))
            cx, cy = r.x + r.width / 2, r.y + r.height / 2
            ax.text(cx, cy, r.rid, ha='center',
                    va='center', color='k', fontsize=16)

        ax.relim()
        ax.autoscale_view()


draw_result(packer)

きっちり詰められていることがわかる。

ランダムに生成した箱で試してみる。

# 容器
bins = [(500, 500), (500, 500), (500, 500)]
# 箱
rects = np.random.randint(50, 200, (30, 2))