はじめに
トラックへの積み付け効率を上げることは、運行台数や燃料・人件費の削減につながる、物流における重要なテーマです。現場では Excel で試行錯誤しながら最適化しているケースが多いものの、制約が増えると人手では限界が見えてきます。
本記事では OR-Tools（CP-SAT）を使って、まずは Excel ベースの計算を置き換え、そこから積載率をさらに高めるまでの試行錯誤を整理します。
OR-Toolsとは
組み合わせ最適化のための高速で移植可能なソフトウェアです。
なぜ「Excel最適化」では限界が出るのか
Excel のロジックは現場にフィットしている一方で、制約値の変更に弱いのが実情です。現状はトラックの種類を固定し、1つのパレットに商品ケースを積み上げた時の最大高さ・重量を固定することでトラックの制約を満たす運用になっています。
ただし、トラックの高さや最大積載重量が変わると、既存のExcelでは制約を満たせなくなってしまうため、制約を満たせるように1つのパレットに商品ケースを積み上げた時の最大高さ・重量を変更する運用が必要になります。
OR-Tools で置き換えると、トラックの最大積載容積・最大積載重量の条件が変わってもパラメータ変更だけで対応でき、最適化の土台を共通化できます。
パレットと商品ケースのイメージ
まずは現場の前提を“制約”に落とす
現状の顧客業務を分析すると、以下のような前提があることがわかりました。前提はプロダクトチームのメンバーが顧客からヒアリングしたことを聞いたり、業務に使用しているExcelからロジックを読み解いたりすることで明らかにすることができました。
積み付けにおけるゴールは、転送したい各商品ケース数量を最も少ないトラックの台数に詰め込むことです。これは OR-Tools でいう「ビンパッキング問題」に近く、今回はその考え方をトラック積載に応用できることを示します。
- 転送対象の「商品ケース数リスト」が入力として与えられる。
- すべてのケースはパレットに載せてトラックに積載する。
- 1つのパレットには1種類の商品のみを載せる。
- パレットに載せるケース数には上限がある。
- 2段積みしてもトラック高さに収まることが条件。
- 上限まで積むと天面が平らになり、上に別パレットを置ける。
- 車両には寸法・重量の制約がある。
- 商品ケースごとに体積・重量・数量が定義されている。
- 商品には段積み可否の設定があり、段積み不可のパレットの上にはパレットを置けない。
- 最大ケース数に満たないパレットは段積み不可とする。
- トラック内のパレット積みは最大2段までとする。
上記の制約を満たしたときのトラック積みつけのイメージは以下のような形です。ここでは、水色のケースが段積み不可の商品と仮定しています。（水色のケースの商品の上にパレットをさらに置くことはできない）
まずは「解が出る」モデルを作る
最初の目的は、Excel ベースのロジックを置き換えられるモデルを作ることでした。
以下のような計算の流れ、制約条件と目的関数を設定することで既存の業務を再現しつつOR-Toolsに最適解を出させるプログラムが書けました。
計算の流れ
- 商品ケースを前提に従ってパレット単位にまとめる
- トラックの幅・奥行きの寸法とパレットの幅・奥行きから床に敷き詰められる最大パレット数を算出する
- 補足: 以降、床面の1枠を「パレット位置」と呼び、その真上に伸びる縦方向の積載スペースを「スタック」と呼ぶ
- まずは全て1段でトラックに順番に敷き詰める
- 制約条件・目的関数を設定してOR-Toolsを実行
- 解を得る
制約条件
- 各パレットはスタック内の「下段 or 上段」のいずれか1回だけ割り当てる
- 各スタック位置の下段・上段はそれぞれ1枚まで
- トラック未使用の場合は下段配置できない／パレットを積載できない
- 高さ制約: 下段+上段の合計高さが荷台高さ以下
- 段積み不可パレットの上には別パレットを置けない
- トラック耐荷重: 積載重量が最大積載重量以下
目的関数
- 使用するトラック台数を最小化する
この段階で、トラックの最大積載容積・最大積載重量の条件が変わっても対応できる土台ができました。
サンプルコード
サンプルコード
from ortools.linear_solver import pywraplp
from packing_utils import build_packing_context
def main():
sku_case_counts = {
"SKUA01": 800,
"SKUA02": 800,
"SKUA03": 800,
"SKUA04": 800,
"SKUA05": 800,
}
context = build_packing_context(
vehicle_type="10t",
pallet_type="1100x1100",
pallet_material="resin",
sku_case_counts=sku_case_counts,
)
print(f"トラック1台あたり床に敷ける最大パレット数: {context.max_positions}")
print(f"全パレット数: {len(context.pallets)}")
# Create the mip solver with the SCIP backend.
solver = pywraplp.Solver.CreateSolver("SCIP")
if not solver:
return
pallets = context.pallets
num_pallets = len(pallets)
vehicle = context.vehicle
num_trucks = context.max_trucks
max_positions = context.max_positions
if num_pallets == 0:
print("No pallets to plan.")
return
items = range(num_pallets)
trucks = range(num_trucks)
# 敷き詰めで得られた「1台あたりのパレット枠」をスタック数とみなす
stacks = range(max_positions)
lower = {}
upper = {}
# i: パレット（items）の添字
# j: トラック（trucks）の添字
# s: 1台あたりのスタック位置（stacks）の添字
for i in items:
for j in trucks:
for s in stacks:
lower[(i, j, s)] = solver.IntVar(0, 1, f"lower_{i}_{j}_{s}")
upper[(i, j, s)] = solver.IntVar(0, 1, f"upper_{i}_{j}_{s}")
y = {}
for j in trucks:
y[j] = solver.IntVar(0, 1, f"truck_used_{j}")
# 各パレットは下段もしくは上段のいずれか1回だけ使用する
for i in items:
solver.Add(
sum(lower[(i, j, s)] + upper[(i, j, s)] for j in trucks for s in stacks)
== 1
)
# 各スタック位置に置ける下段・上段はそれぞれ1枚まで
for j in trucks:
for s in stacks:
solver.Add(sum(lower[(i, j, s)] for i in items) <= 1)
solver.Add(sum(upper[(i, j, s)] for i in items) <= 1)
# トラックを使用しない場合は下段配置できない
solver.Add(sum(lower[(i, j, s)] for i in items) <= y[j])
# 高さ制約: 下段+上段の高さ合計を荷台高さ以下に抑える
solver.Add(
sum(
lower[(i, j, s)] * pallets[i].height_mm
+ upper[(i, j, s)] * pallets[i].height_mm
for i in items
)
<= vehicle.effective_height_mm
)
# 段積み不可パレットの上には別パレットを置けない
solver.Add(
sum(upper[(i, j, s)] for i in items)
<= sum(
lower[(i, j, s)] * (1 if pallets[i].is_stackable else 0)
for i in items
)
)
# トラック耐荷重制約
for j in trucks:
solver.Add(
sum(
(lower[(i, j, s)] + upper[(i, j, s)]) * pallets[i].weight_kg
for i in items
for s in stacks
)
<= vehicle.max_load_weight_kg
)
# トラック未使用の場合はパレットを積載できない
for j in trucks:
solver.Add(
sum((lower[(i, j, s)] + upper[(i, j, s)]) for i in items for s in stacks)
<= 2 * max_positions * y[j]
)
# 目的: 使用するトラック台数を最小化
solver.Minimize(solver.Sum(y[j] for j in trucks))
print(f"Solving with {solver.SolverVersion()}")
status = solver.Solve()
if status == pywraplp.Solver.OPTIMAL:
used_trucks = 0
for j in trucks:
# 使用していないトラックはスキップ
if y[j].solution_value() < 0.5:
continue
used_trucks += 1
print(f"トラック {j} を使用")
truck_weight = 0.0
max_stack_height = 0
stack_infos = []
for s in stacks:
lower_items = [
i for i in items if lower[(i, j, s)].solution_value() > 0.5
]
upper_items = [
i for i in items if upper[(i, j, s)].solution_value() > 0.5
]
if not lower_items and not upper_items:
continue
stack_height = sum(
pallets[i].height_mm for i in lower_items + upper_items
)
stack_weight = sum(
pallets[i].weight_kg for i in lower_items + upper_items
)
truck_weight += stack_weight
max_stack_height = max(max_stack_height, stack_height)
stack_infos.append(
{
"index": s,
"lower": lower_items,
"upper": upper_items,
"height": stack_height,
"weight": stack_weight,
}
)
weight_ratio = truck_weight / vehicle.max_load_weight_kg * 100
height_ratio = (
(max_stack_height / vehicle.effective_height_mm * 100)
if vehicle.effective_height_mm > 0
else 0
)
print(
f" ▶ 重量合計 {truck_weight:.1f}kg / 上限 {vehicle.max_load_weight_kg}kg"
f" (積載率 {weight_ratio:.1f}%)"
)
print(
f" ▶ 最大スタック高 {max_stack_height}mm / 上限 {vehicle.effective_height_mm}mm"
f" (高さ積載率 {height_ratio:.1f}%)"
)
for info in stack_infos:
def describe(idx):
pallet = pallets[idx]
return (
f"{pallet.sku_id} (h={pallet.height_mm}mm, w={pallet.weight_kg:.1f}kg)"
)
print(
f" スタック {info['index']}: 高さ {info['height']}mm 重量 {info['weight']:.1f}kg"
)
if info["lower"]:
print(" 下段:", ", ".join(describe(i) for i in info["lower"]))
if info["upper"]:
print(" 上段:", ", ".join(describe(i) for i in info["upper"]))
print()
print(f"使用トラック台数: {used_trucks}")
print("Time = ", solver.WallTime(), " milliseconds")
else:
print("The problem does not have an optimal solution.")
if __name__ == "__main__":
main()
実行結果
トラックの台数とそれぞれのトラックの積み付け状況まで出力されます。
❯ python3 truck.py
トラック1台あたり床に敷ける最大パレット数: 16
全パレット数: 110
Solving with SCIP 9.2.2 [LP solver: SoPlex 7.1.3]
トラック 0 を使用
▶ 重量合計 7166.2kg / 上限 10000kg (積載率 71.7%)
▶ 最大スタック高 2550mm / 上限 2600mm (高さ積載率 98.1%)
スタック 0: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
スタック 1: 高さ 1240mm 重量 269.0kg
下段: SKUA02 (h=1240mm, w=269.0kg)
スタック 2: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 3: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 4: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 5: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
スタック 6: 高さ 1550mm 重量 489.4kg
下段: SKUA05 (h=1550mm, w=489.4kg)
スタック 7: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
スタック 8: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 9: 高さ 2550mm 重量 836.4kg
下段: SKUA05 (h=1550mm, w=489.4kg)
上段: SKUA01 (h=1000mm, w=347.0kg)
スタック 10: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
スタック 11: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 12: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
スタック 13: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
スタック 14: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 15: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
トラック 1 を使用
▶ 重量合計 8800.4kg / 上限 10000kg (積載率 88.0%)
▶ 最大スタック高 2600mm / 上限 2600mm (高さ積載率 100.0%)
スタック 0: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 1: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
スタック 2: 高さ 2500mm 重量 741.0kg
下段: SKUA01 (h=1000mm, w=347.0kg)
上段: SKUA02 (h=1500mm, w=394.0kg)
スタック 3: 高さ 2600mm 重量 754.8kg
下段: SKUA01 (h=1000mm, w=347.0kg)
上段: SKUA03 (h=1600mm, w=407.8kg)
スタック 4: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
スタック 5: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 6: 高さ 2550mm 重量 836.4kg
下段: SKUA01 (h=1000mm, w=347.0kg)
上段: SKUA05 (h=1550mm, w=489.4kg)
スタック 7: 高さ 1550mm 重量 489.4kg
下段: SKUA05 (h=1550mm, w=489.4kg)
スタック 8: 高さ 1550mm 重量 489.4kg
下段: SKUA05 (h=1550mm, w=489.4kg)
スタック 9: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
スタック 10: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 11: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 12: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
スタック 13: 高さ 2600mm 重量 754.8kg
下段: SKUA01 (h=1000mm, w=347.0kg)
上段: SKUA03 (h=1600mm, w=407.8kg)
スタック 14: 高さ 1550mm 重量 489.4kg
下段: SKUA05 (h=1550mm, w=489.4kg)
スタック 15: 高さ 2550mm 重量 836.4kg
下段: SKUA05 (h=1550mm, w=489.4kg)
上段: SKUA01 (h=1000mm, w=347.0kg)
トラック 2 を使用
▶ 重量合計 7096.4kg / 上限 10000kg (積載率 71.0%)
▶ 最大スタック高 2600mm / 上限 2600mm (高さ積載率 100.0%)
スタック 0: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 1: 高さ 1550mm 重量 489.4kg
下段: SKUA05 (h=1550mm, w=489.4kg)
スタック 2: 高さ 2600mm 重量 754.8kg
下段: SKUA01 (h=1000mm, w=347.0kg)
上段: SKUA03 (h=1600mm, w=407.8kg)
スタック 3: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 4: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
スタック 5: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
スタック 6: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
スタック 7: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 8: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 9: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
スタック 11: 高さ 2450mm 重量 805.2kg
下段: SKUA01 (h=1000mm, w=347.0kg)
上段: SKUA04 (h=1450mm, w=458.2kg)
スタック 12: 高さ 1600mm 重量 407.8kg
下段: SKUA03 (h=1600mm, w=407.8kg)
スタック 13: 高さ 1000mm 重量 347.0kg
下段: SKUA01 (h=1000mm, w=347.0kg)
スタック 14: 高さ 1550mm 重量 489.4kg
下段: SKUA05 (h=1550mm, w=489.4kg)
スタック 15: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
トラック 3 を使用
▶ 重量合計 7036.4kg / 上限 10000kg (積載率 70.4%)
▶ 最大スタック高 2600mm / 上限 2600mm (高さ積載率 100.0%)
スタック 0: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 1: 高さ 2600mm 重量 754.8kg
下段: SKUA03 (h=1600mm, w=407.8kg)
上段: SKUA01 (h=1000mm, w=347.0kg)
スタック 3: 高さ 2550mm 重量 836.4kg
下段: SKUA05 (h=1550mm, w=489.4kg)
上段: SKUA01 (h=1000mm, w=347.0kg)
スタック 4: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 5: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
スタック 7: 高さ 1550mm 重量 489.4kg
下段: SKUA05 (h=1550mm, w=489.4kg)
スタック 8: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 9: 高さ 550mm 重量 62.2kg
下段: SKUA03 (h=550mm, w=62.2kg)
スタック 10: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 11: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
スタック 12: 高さ 2500mm 重量 741.0kg
下段: SKUA01 (h=1000mm, w=347.0kg)
上段: SKUA02 (h=1500mm, w=394.0kg)
スタック 13: 高さ 2050mm 重量 679.6kg
下段: SKUA01 (h=1000mm, w=347.0kg)
上段: SKUA05 (h=1050mm, w=332.6kg)
スタック 14: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 15: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
トラック 5 を使用
▶ 重量合計 6456.6kg / 上限 10000kg (積載率 64.6%)
▶ 最大スタック高 2600mm / 上限 2600mm (高さ積載率 100.0%)
スタック 0: 高さ 2600mm 重量 754.8kg
下段: SKUA01 (h=1000mm, w=347.0kg)
上段: SKUA03 (h=1600mm, w=407.8kg)
スタック 1: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
スタック 2: 高さ 2550mm 重量 836.4kg
下段: SKUA01 (h=1000mm, w=347.0kg)
上段: SKUA05 (h=1550mm, w=489.4kg)
スタック 3: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
スタック 4: 高さ 1600mm 重量 407.8kg
下段: SKUA03 (h=1600mm, w=407.8kg)
スタック 5: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 6: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
スタック 7: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 8: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 9: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 10: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
スタック 12: 高さ 620mm 重量 165.4kg
下段: SKUA04 (h=620mm, w=165.4kg)
スタック 13: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
スタック 14: 高さ 1550mm 重量 489.4kg
下段: SKUA05 (h=1550mm, w=489.4kg)
トラック 6 を使用
▶ 重量合計 8894.0kg / 上限 10000kg (積載率 88.9%)
▶ 最大スタック高 2600mm / 上限 2600mm (高さ積載率 100.0%)
スタック 0: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 1: 高さ 1550mm 重量 489.4kg
下段: SKUA05 (h=1550mm, w=489.4kg)
スタック 2: 高さ 1550mm 重量 489.4kg
下段: SKUA05 (h=1550mm, w=489.4kg)
スタック 3: 高さ 1500mm 重量 394.0kg
下段: SKUA02 (h=1500mm, w=394.0kg)
スタック 4: 高さ 1600mm 重量 407.8kg
下段: SKUA03 (h=1600mm, w=407.8kg)
スタック 5: 高さ 2450mm 重量 805.2kg
下段: SKUA01 (h=1000mm, w=347.0kg)
上段: SKUA04 (h=1450mm, w=458.2kg)
スタック 6: 高さ 1600mm 重量 407.8kg
下段: SKUA03 (h=1600mm, w=407.8kg)
スタック 7: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 8: 高さ 2450mm 重量 805.2kg
下段: SKUA01 (h=1000mm, w=347.0kg)
上段: SKUA04 (h=1450mm, w=458.2kg)
スタック 9: 高さ 2450mm 重量 805.2kg
下段: SKUA01 (h=1000mm, w=347.0kg)
上段: SKUA04 (h=1450mm, w=458.2kg)
スタック 10: 高さ 1550mm 重量 489.4kg
下段: SKUA05 (h=1550mm, w=489.4kg)
スタック 11: 高さ 2600mm 重量 754.8kg
下段: SKUA03 (h=1600mm, w=407.8kg)
上段: SKUA01 (h=1000mm, w=347.0kg)
スタック 12: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 13: 高さ 1450mm 重量 458.2kg
下段: SKUA04 (h=1450mm, w=458.2kg)
スタック 14: 高さ 2450mm 重量 805.2kg
下段: SKUA01 (h=1000mm, w=347.0kg)
上段: SKUA04 (h=1450mm, w=458.2kg)
スタック 15: 高さ 1600mm 重量 407.8kg
下段: SKUA03 (h=1600mm, w=407.8kg)
使用トラック台数: 6
Time = 21751 milliseconds
最大段数を変更して積載率を向上させる
2段に固定すると扱いやすい一方で、高さに余裕があるのにそのスペースを使えず、積載率をあげられないという問題があります。
そこで最大段数を変更できるようにし、積載率向上の余地を広げました。
これにより、以下のように3段目以上を置けるようになることを目指しました。
制約条件
- 最大段数（MAX_LEVELS_PER_STACK）を導入し、段数を可変にする
- 各スタック位置は段番号ごとに1枚まで、上の段を使う場合は下の段から順に埋まる（飛び段を禁止）
- スタックの総高さは荷台高さ以下（各段の高さ合計で判定）
- 段積み不可パレットの上には何も置けない
- トラック耐荷重: 積載重量が最大積載重量以下
- トラック未使用の場合はパレットを積載しない（上限は最大段数に合わせて調整）
目的関数
- 使用するトラック台数を最小化する
サンプルコード
from ortools.linear_solver import pywraplp
from packing_utils import build_packing_context
MAX_LEVELS_PER_STACK = 3
def main():
sku_case_counts = {
"SKUA01": 800,
"SKUA02": 800,
"SKUA03": 800,
"SKUA04": 800,
"SKUA05": 800,
}
context = build_packing_context(
vehicle_type="10t",
pallet_type="1100x1100",
pallet_material="resin",
sku_case_counts=sku_case_counts,
)
print(f"トラック1台あたり床に敷ける最大パレット数: {context.max_positions}")
solver = pywraplp.Solver.CreateSolver("SCIP")
if not solver:
return
pallets = context.pallets
num_pallets = len(pallets)
vehicle = context.vehicle
num_trucks = context.max_trucks
max_positions = context.max_positions
if num_pallets == 0:
print("No pallets to plan.")
return
items = range(num_pallets)
trucks = range(num_trucks)
stacks = range(max_positions)
levels = range(MAX_LEVELS_PER_STACK)
assign = {}
occ = {}
level_height = {}
for i in items:
for j in trucks:
for s in stacks:
for l in levels:
assign[(i, j, s, l)] = solver.IntVar(
0, 1, f"assign_{i}_{j}_{s}_{l}"
)
for j in trucks:
for s in stacks:
for l in levels:
occ[(j, s, l)] = solver.IntVar(0, 1, f"occ_{j}_{s}_{l}")
level_height[(j, s, l)] = solver.NumVar(
0, vehicle.effective_height_mm, f"height_{j}_{s}_{l}"
)
y = {j: solver.IntVar(0, 1, f"truck_used_{j}") for j in trucks}
# 各パレットは1つのスタックのいずれかの段に必ず配置する
for i in items:
solver.Add(
sum(assign[(i, j, s, l)] for j in trucks for s in stacks for l in levels)
== 1
)
# スタックの各段には最大1枚、段の使用は下から詰める
for j in trucks:
for s in stacks:
for idx, l in enumerate(levels):
expr = solver.Sum(assign[(i, j, s, l)] for i in items)
solver.Add(expr == occ[(j, s, l)])
solver.Add(
level_height[(j, s, l)]
== solver.Sum(
assign[(i, j, s, l)] * pallets[i].height_mm for i in items
)
)
if idx > 0:
solver.Add(occ[(j, s, l)] <= occ[(j, s, l - 1)])
solver.Add(level_height[(j, s, l - 1)] >= level_height[(j, s, l)])
else:
solver.Add(occ[(j, s, l)] <= y[j])
# 各スタックの総高さは荷台高さ以下
for j in trucks:
for s in stacks:
solver.Add(
sum(level_height[(j, s, l)] for l in levels)
<= vehicle.effective_height_mm
)
# 非スタッカブルパレットが置かれた段の上には何も置かない
for j in trucks:
for s in stacks:
for idx, l in enumerate(levels):
upper_levels = solver.Sum(
assign[(i, j, s, higher)]
for i in items
for higher in levels
if higher > l
)
max_above = MAX_LEVELS_PER_STACK - (idx + 1)
if max_above == 0:
continue
non_stack_expr = solver.Sum(
assign[(i, j, s, l)] for i in items if not pallets[i].is_stackable
)
solver.Add(upper_levels <= max_above * (1 - non_stack_expr))
# トラックの耐荷重制約
for j in trucks:
solver.Add(
sum(
assign[(i, j, s, l)] * pallets[i].weight_kg
for i in items
for s in stacks
for l in levels
)
<= vehicle.max_load_weight_kg * y[j]
)
# トラック未使用の場合はパレットを積載しない
for j in trucks:
solver.Add(
sum(assign[(i, j, s, l)] for i in items for s in stacks for l in levels)
<= max_positions * MAX_LEVELS_PER_STACK * y[j]
)
solver.Minimize(solver.Sum(y[j] for j in trucks))
print(f"Solving with {solver.SolverVersion()}")
status = solver.Solve()
if status != pywraplp.Solver.OPTIMAL:
print("The problem does not have an optimal solution.")
return
used_trucks = 0
for j in trucks:
if y[j].solution_value() <= 0.5:
continue
used_trucks += 1
truck_weight = 0.0
max_stack_height = 0
stack_infos = []
for s in stacks:
stack_levels = []
stack_height = 0
stack_weight = 0
for l in levels:
assigned = [
i for i in items if assign[(i, j, s, l)].solution_value() > 0.5
]
if not assigned:
continue
idx = assigned[0]
pallet = pallets[idx]
stack_levels.append((l, idx))
stack_height += pallet.height_mm
stack_weight += pallet.weight_kg
if stack_levels:
max_stack_height = max(max_stack_height, stack_height)
truck_weight += stack_weight
stack_infos.append((s, stack_height, stack_weight, stack_levels))
weight_ratio = truck_weight / vehicle.max_load_weight_kg * 100
height_ratio = (
max_stack_height / vehicle.effective_height_mm * 100
if vehicle.effective_height_mm > 0
else 0
)
print(f"トラック {j} を使用")
print(
f" ▶ 重量合計 {truck_weight:.1f}kg / 上限 {vehicle.max_load_weight_kg}kg"
f" (積載率 {weight_ratio:.1f}%)"
)
print(
f" ▶ 最大スタック高 {max_stack_height}mm / 上限 {vehicle.effective_height_mm}mm"
f" (高さ積載率 {height_ratio:.1f}%)"
)
for s, stack_height, stack_weight, levels_info in stack_infos:
print(f" スタック {s}: 高さ {stack_height}mm 重量 {stack_weight:.1f}kg")
for level_idx, pallet_idx in sorted(levels_info):
pallet = pallets[pallet_idx]
print(
f" 段{level_idx}: {pallet.sku_id} "
f"(h={pallet.height_mm}mm, w={pallet.weight_kg:.1f}kg, "
f"stackable={'OK' if pallet.is_stackable else 'NG'})"
)
print()
print(f"使用トラック台数: {used_trucks}")
print("Time = ", solver.WallTime(), " milliseconds")
if __name__ == "__main__":
main()
段数を増やすほど探索規模が急増して、計算結果が算出されるまでの時間が非常に長くなることがわかりました。現場で運用できる範囲に上限を置く必要があります。
まとめ
今回は OR-Tools を使って、トラックへの荷物積み付けの最適化に挑戦しました。パレットサイズ、ケースサイズ、トラックのサイズや最大積載重量が変わっても最適解が出せる形まで抽象化しつつ、余った高さに追加でパレットを置くようにできたことが、今回出せた価値だと感じています。
一方で、最適化を目指すほど転送量が多いケースでは組合せが膨大になり、実務に耐えうる時間内で解が出せなくなる課題があります。
実際のリリース時には OR-Tools に 1 分のタイムアウトを入れ、タイムアウトした場合は高速に近似解が出せるロジックへフォールバックする設計で対応しました。
今回は、全てパレットに載せるかつパレット内の商品は全て同じという条件があったため考えやすかったですが、今後は複数商品を同一パレットに載せたり、隙間にケースをバラで置いたりするケースへの対応なども考える必要がありそうです。
物流テックベンチャーの株式会社ギークプラスでは、「サプライチェーンマネジメント (SCM) の新しいあり方を、ソフトウェアで思い描く」をビジョンとして、オープン SCM ソリューション「skylaa」の開発をしています。本ブログでは、ギークプラスのソフトウェア開発チームが得た知見や技術情報を発信しています。
Discussion