2次割当問題
対象物$P=\{P_1,P_2,\dots,P_n\}$の割当先$L=\{L_1,L_2,\dots,L_n\}$を考える。対象物$P_i$と$P_j$の間の輸送量$q_{ij}$と割当先$L_k$と$L_l$の間の距離$d_{kl}$が与えられているとき、輸送量と距離の積の総和を最小にする割当を求めよ。
実行方法
usage
Signature: quad_assign(quant, dist)
Docstring:
2次割当問題
全探索
入力
quant: 対象間の輸送量
dist: 割当先間の距離
出力
対象ごとの割当先番号リスト
python
from ortoolpy import quad_assign
quad_assign([[0, 2, 0], [0, 0, 1], [0, 0, 0]], [[0, 2, 4], [2, 0, 3], [4, 3, 0]])
結果
(0, 1, 2)
python
# pandas.DataFrame
from ortoolpy.optimization import QuadAssign
QuadAssign('data/quad_assign_quant.csv', 'data/quad_assign_dist.csv')[1]
| target | pos | |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 1 | 1 |
| 2 | 2 | 2 |
データ
補足
巡回セールスマン問題(TSP)など、様々な問題を 2次割当問題と捉えることができます。
2次割当問題は、抽象度の高い問題といえます。しかし、非常に解きずらい問題です。
問題の構造を理解するために、2次割当問題に帰着することは有益ですが、そのまま解くのはお薦めしません。より具体的な問題に捉えなおして解くべきでしょう。例えば、TSPは、TSP専用の解法を使った方が効率がよいでしょう。