問題
特大、大、中、小のつぼが3つずつ、合計12本あります。
それぞれの高さは100cm、80cm、60cm、40cmです。
つぼを縦に重ねると上のつぼが下のつぼに20cmだけ入って低くなります。
たとえば、小の上に大を重ねると40 + 80 - 20で100cmになります。
ただし、下のつぼが大きいときは、上のつぼがほぼ入りますが、10cmだけ入り切りません。
たとえば、大の上に小を重ねると80 + 10で90cmになります。
3つのつぼをおける場所があります。つぼを重ねて高さを130cmに収めるにはどうすればよいでしょうか？
考え方
各つぼを頂点とし、重ねることを辺とすると、運搬経路(配送最適化)問題（VRP）として解くことができます。
デポを1つ用意し、デポからすべてのつぼに距離0でつなげます。つぼ間は、重ねたことで高くなる分が距離になります。
Pythonで解いてみる
VRPを解くためのPyVRPを使って解いてみましょう。PyVRPは、pip install pyvrpでインストールできます。
デポは、add_depot()で1つ用意します。
置く場所は車両になります。ここではadd_vehicle_type()で3台用意します。
つぼに相当する拠点は、add_client()で追加します。
辺は、add_edge()で追加します。
from pyvrp import Model
from pyvrp.stop import MaxIterations
size = [40, 60, 80, 100] # 小、中、大、特大の高さ
over = [ # 行の上に列を積んだときの増える高さ
[20, 40, 60, 80],
[10, 20, 40, 60],
[10, 10, 20, 40],
[10, 10, 10, 20],
]
# 12個のつぼの種類
vases = [0] * 3 + [1] * 3 + [2] * 3 + [3] * 3
m = Model()
depot = m.add_depot(0, 0)
m.add_vehicle_type(3, depot=depot, max_distance=130)
for index in vases:
nd = m.add_client(0, 0)
m.add_edge(depot, nd, size[index])
m.add_edge(nd, depot, 0)
for ifr, fr in zip(vases, m.locations[1:]):
for ito, to in zip(vases, m.locations[1:]):
d = 0 if fr == to else over[ifr][ito]
m.add_edge(fr, to, d)
result = m.solve(MaxIterations(100), display=False)
print(result)
出力
Solution results
================
# routes: 3
# clients: 12
objective: 390.00
# iterations: 100
run-time: 0.18 seconds
Routes
------
Route #1: 12 8 5 3
Route #2: 10 9 6 2
Route #3: 11 7 4 1
出力のRouteは重ねたつぼを意味し、左が下で右が上です。Routeの番号は各つぼで、数字の小さい方から、小、中、大、特大です。数字を見ると下から、特大、大、中、小になっています。
補足
高さを最小化したい場合は、高さを二分探索で求めるとよいでしょう。
以上