スケジューリング・配送のモデル化

← 数理最適化一覧

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：定式化の技法・代表的な組合せ問題　|　関連：割当問題（ハンガリアン法）

要点（BLUF）

配送（TSP/VRP）やスケジューリング（ジョブショップ）は、0/1 変数と論理制約（定式化の技法）で整数計画に定式化できる。
TSP の肝は 部分巡回路除去（subtour elimination）：全都市を1つの巡回路に繋ぐ制約。
これらは NP 困難（計算複雑性とNP困難の地図）。実務は専用ソルバー（OR-Tools）やメタヒューリスティクス（メタヒューリスティクス章目次）。
手法の数理はここ、深い適用は operations（オペレーションズ） へ wikilink。

概念 ── 「順序」と「割付」を変数にする

スケジューリング・配送の共通構造は「誰が・何を・いつ・どの順で」を決めること。これを 0/1 変数で表す：

TSP： $x_{ij}=1$ なら都市 $i$ の次に $j$ を訪れる。
ジョブショップ： $y_{jk}=1$ なら仕事 $j$ を仕事 $k$ より先に処理。
VRP（配送）：車両ごとに訪問順を 0/1 変数で。

TSP の定式化

各都市を1度ずつ訪れて出発点に戻る最短巡回路。 $c_{ij}$ を距離として：

\min \sum_{i,j} c_{ij} x_{ij} \quad \text{s.t.}\quad \sum_j x_{ij}=1\ (\forall i),\ \sum_i x_{ij}=1\ (\forall j),\ x_{ij}\in\{0,1\}

これだけだと割当問題（割当問題（ハンガリアン法））と同じで、部分巡回路（小さなループに分裂）が出てしまう。全都市を1つの巡回に繋ぐため 部分巡回路除去制約を足す：

\sum_{i,j \in S} x_{ij} \le |S| - 1 \quad (\forall S \subsetneq V,\ 2\le|S|)

任意の部分集合 $S$ 内で閉じたループを禁じる。だが $S$ の数は指数的なので、必要になったものだけ足す（遅延制約生成）か、MTZ 制約（補助変数で順序を表す）を使う。

graph LR
  A["各都市 入次数=出次数=1 (割当)"] --> B["部分巡回路が発生しうる"]
  B --> C["部分巡回路除去制約を追加"]
  C --> D["全都市が1つの巡回路に"]

Pythonで最短巡回路を解く

5都市の TSP を OR-Tools（配送特化ソルバー）で解き、全列挙の最適と一致するか確認する。

from ortools.constraint_solver import routing_enums_pb2, pywrapcp
import itertools

dist = [[0, 29, 20, 21, 16],
        [29, 0, 15, 17, 28],
        [20, 15, 0, 28, 14],
        [21, 17, 28, 0, 25],
        [16, 28, 14, 25, 0]]

manager = pywrapcp.RoutingIndexManager(len(dist), 1, 0)   # 5都市, 1台, 出発0
routing = pywrapcp.RoutingModel(manager)
def d_cb(i, j):
    return dist[manager.IndexToNode(i)][manager.IndexToNode(j)]
transit = routing.RegisterTransitCallback(d_cb)
routing.SetArcCostEvaluatorOfAllVehicles(transit)
params = pywrapcp.DefaultRoutingSearchParameters()
params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
sol = routing.SolveWithParameters(params)

idx, route, total = routing.Start(0), [], 0
while not routing.IsEnd(idx):
    route.append(manager.IndexToNode(idx))
    nxt = sol.Value(routing.NextVar(idx))
    total += routing.GetArcCostForVehicle(idx, nxt, 0)
    idx = nxt
route.append(0)

# 全列挙で検算(5都市なので可能)
best = min(sum(dist[t[k]][t[k+1]] for k in range(5))
           for p in itertools.permutations(range(1, 5))
           for t in [[0] + list(p) + [0]])
print(f"OR-Tools 最短巡回路 = {route}, 総距離 = {total}")
print(f"全列挙の最短距離 = {best}")

実行結果：

OR-Tools 最短巡回路 = [0, 4, 2, 1, 3, 0], 総距離 = 83
全列挙の最短距離 = 83

OR-Tools が見つけた巡回路 $0\to4\to2\to1\to3\to0$ は総距離 83 で、全列挙の最適と一致。5都市なら全列挙（ $4!/2=12$ 通り）も可能だが、都市数が増えると全列挙は爆発する（計算複雑性とNP困難の地図の通り、25都市で約980万年）。OR-Tools は分枝＋メタヒューリスティクスで大規模でも実用的な解を返す。

数理はここ、適用は operations へ

スケジューリング・在庫・配送の 深い適用（生産計画の実務・在庫方策・サプライチェーン）は オペレーションズ（operations） の領域。ここで扱うのは「それらをどう最適化問題に定式化するか」という モデリングの数理：

順序・割付を 0/1 変数で表す技法（定式化の技法）。
部分巡回路除去・時間枠・容量などの制約の書き方。
問題の難しさ（NP 困難）と解法選択（厳密 vs ヒューリスティック）。

実務の最適化は operations の待ち行列・在庫モデルや生産スケジューリングと繋がる ── そちらは適用例として参照する。

数式の直観的意味

スケジューリング・配送の定式化が難しいのは、「順序」という本質的に 離散で組合せ的な構造を、線形制約で表さねばならないから。割当制約（入次数・出次数1）だけでは順序の「繋がり」が表せず部分巡回路が漏れる ── これを塞ぐ部分巡回路除去制約が指数的に多いことが、TSP の難しさ（計算複雑性とNP困難の地図）の表れ。MTZ 制約や遅延制約生成は、この指数的な制約集合を「必要な分だけ」扱う工夫。スケジューリングの順序制約（ $y_{jk}+y_{kj}=1$ とビッグMで開始時刻を結ぶ）も同じ発想で、論理（先後関係）を線形に翻訳する（定式化の技法）。これらが NP 困難である以上、厳密解（分枝カット、分枝限定法）とヒューリスティック（メタヒューリスティクス章目次）の使い分けが実務の判断になる。

⚠️ よくある誤解・落とし穴

割当制約だけでは TSP にならない：部分巡回路が漏れる。除去制約か MTZ が必須。
ビッグMの乱用（定式化の技法）：スケジューリングの順序制約で $M$ を大きく取りすぎると遅くなる。
NP 困難を直視する：大規模を厳密に解こうとして詰まる。近似・専用ソルバーを選ぶ。
時間枠・容量・複数車両など制約が増えるほど難化。OR-Tools 等の専用モデリングが効率的。