【OR-Tools実践②】荷下ろし時間と時間枠を考慮した「配送ルート最適化」(VRPTW)

はじめに

【OR-Tools実践①】仲が悪いペアも夜勤明けも考慮した「シフト自動作成」(CP-SAT) に続き、本記事では配送ルート最適化を扱います。こちらも教科書的な巡回セールスマン問題（TSP）ではなく、**「配送先での荷下ろしは最大30分」「この店は午前中しか受け取れない」**といった、物流現場ならではの制約を盛り込みます。

このクラスは VRPTW（Vehicle Routing Problem with Time Windows）と呼ばれ、物流で最頻出の最適化問題です。これも OR-Tools だけで解きます。

実行環境

ローカルでの環境構築（インタープリタやパッケージの取り違え）でつまずきやすいので、Google Colab で動かすのがおすすめです。ブラウザだけで完結します。Colab の標準ランタイム（2026年6月時点で Python 3.12 / Ubuntu 22.04）で動作確認しています。

ノートブックの最初のセルで OR-Tools を入れます（pandas・matplotlib は Colab に最初から入っています）。

!pip install ortools

図（シフト表・ルート図）で日本語を表示する場合は、日本語フォントも入れておきます（入れないと文字が □ に化けます）。

!apt-get -y install fonts-noto-cjk > /dev/null

ソフトウェア	バージョン
実行環境	Google Colab（Python 3.12 / Ubuntu 22.04、2026年6月時点）
OR-Tools	9.15.6755（`pip install` で導入）
pandas / matplotlib	Colab 同梱版

ローカル（VSCode等）で動かす場合は、pip install ortools pandas matplotlib をVSCodeが選択しているインタープリタに対して実行してください。Colabで動いてローカルで動かない原因は、ほぼ「pipした環境と実行している環境の取り違え」です。

1. 問題設定

1つの倉庫（デポ）から3台のトラックで12店舗へ配送します。盛り込む制約は次の通りです。

制約	内容
荷下ろし最大30分	配送先での作業時間（サービス時間）。大口ほど長く、上限30分で頭打ち
受取可能な時間帯	「午前のみ」「13時以降」など、店ごとの時間枠（タイムウィンドウ）
積載量上限	トラック1台あたり120箱まで
営業時間	8:00〜18:00（600分）以内に全車が帰庫

2. 設計のキモ：時間の「次元(Dimension)」に全部を乗せる

OR-Tools の Routing では、移動時間・荷下ろし・時間枠・帰庫時刻をすべて1本の「時間Dimension」に乗せて管理します。アークのコストを「移動時間＋その地点での荷下ろし時間」と定義するのがコツです。

def time_callback(from_index, to_index):
    i = manager.IndexToNode(from_index)
    j = manager.IndexToNode(to_index)
    # 地点iを出発する前に荷下ろし時間を消費 → 移動
    return travel_min(i, j) + SERVICE_TIME[i]

荷下ろし時間は「最大30分で頭打ち」を min(30, ...) で表現しています。これがご指定の"最大30分"制約です。

SERVICE_TIME = [0] + [min(30, 8 + d) for d in DEMANDS[1:]]  # 大口ほど長く、上限30分

時間枠は、各ノードの累積変数（CumulVar）に範囲を与えるだけです。

open_, close_ = TIME_WINDOWS[node]
time_dim.CumulVar(index).SetRange(open_, close_)   # この店はこの時間しか受け取れない

3. 全コード

3台版（基本のVRPTW）の全コードです。長いので折りたたみにしています。

vrp.py 全文（クリックで展開）

# -*- coding: utf-8 -*-
"""
現場特有の制約を盛り込んだ「配送ルート最適化」
==================================================
OR-Tools の Routing ソルバーで、複数台トラックの配送計画を立てる。
教科書の巡回セールスマン(TSP)ではなく、現実の制約を盛り込む:
  - 配送先ごとの「荷下ろし時間(サービス時間)は最大30分」
  - 配送先ごとの「受け取り可能な時間帯(時間枠)」
  - トラックの積載量上限
  - 営業時間(デポの稼働時間)内に全車が帰庫

required: ortools
"""
import math
import random
from ortools.constraint_solver import routing_enums_pb2, pywrapcp

random.seed(42)

# ----------------------------------------------------------------------
# 1. 問題データ（現場設定）
# ----------------------------------------------------------------------
# ノード0 = デポ(倉庫)。以降が配送先。座標は km。
NAMES = ["倉庫"] + [f"店{i}" for i in range(1, 13)]
random.seed(42)
COORDS = [(25, 25)]                              # デポは中心
for _ in range(12):
    COORDS.append((random.randint(0, 50), random.randint(0, 50)))

N = len(COORDS)
NUM_VEHICLES = 3
DEPOT = 0
VEHICLE_CAPACITY = 120                            # 1台あたり積載上限(箱数)

# 各配送先の需要(箱数)。デポは0。
DEMANDS = [0] + [random.randint(10, 30) for _ in range(N - 1)]

# 荷下ろし(サービス)時間[分]: 最大30分。大口ほど長く、上限30分で頭打ち。
SERVICE_TIME = [0] + [min(30, 8 + d) for d in DEMANDS[1:]]

# 受け取り可能な時間枠[分]（8:00を0分、18:00を600分とする）
# 一部の店は「午前のみ」「午後のみ」など受取可能な時間帯が限られる。
TIME_WINDOWS = [(0, 600)]                         # デポ: 終日
tw_presets = [(0, 600), (0, 300), (300, 600), (0, 600), (60, 360),
              (300, 540), (0, 600), (120, 420), (300, 600), (0, 600),
              (0, 300), (240, 600)]
TIME_WINDOWS += tw_presets

SPEED_KMH = 30                                    # 市街地平均速度
HORIZON = 600                                     # 営業時間 8:00-18:00 = 600分


def travel_min(i, j):
    """ノード間の移動時間[分]（ユークリッド距離 ÷ 速度）"""
    (xi, yi), (xj, yj) = COORDS[i], COORDS[j]
    dist = math.hypot(xi - xj, yi - yj)
    return int(round(dist / SPEED_KMH * 60))


# ----------------------------------------------------------------------
# 2. モデル構築（OR-Tools Routing）
# ----------------------------------------------------------------------
manager = pywrapcp.RoutingIndexManager(N, NUM_VEHICLES, DEPOT)
routing = pywrapcp.RoutingModel(manager)

# --- アーク費用 = 移動時間（総移動時間を最小化） ---
def time_callback(from_index, to_index):
    i = manager.IndexToNode(from_index)
    j = manager.IndexToNode(to_index)
    # その地点を出発するときに「荷下ろし時間」を消費してから移動する
    return travel_min(i, j) + SERVICE_TIME[i]

transit_idx = routing.RegisterTransitCallback(time_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_idx)

# --- 制約: 積載量 ---
def demand_callback(from_index):
    return DEMANDS[manager.IndexToNode(from_index)]

demand_idx = routing.RegisterUnaryTransitCallback(demand_callback)
routing.AddDimensionWithVehicleCapacity(
    demand_idx, 0, [VEHICLE_CAPACITY] * NUM_VEHICLES, True, "Capacity")

# --- 制約: 時間（時間枠 + 荷下ろし + 営業時間内に帰庫）---
routing.AddDimension(
    transit_idx,
    60,        # 待ち時間(slack)は最大60分まで許容
    HORIZON,   # 各車の総時間の上限 = 営業時間
    False,     # 出発時刻を0に固定しない
    "Time")
time_dim = routing.GetDimensionOrDie("Time")
# （補足）各車の稼働時間を平準化したい場合は次の1行を有効化する。
# ただし「稼働幅を縮めるため全車の出発が遅くなる」副作用があるため、
# 本記事のデフォルトは総時間最小化（＝早く動けるトラックは早く出発）とする。
# time_dim.SetGlobalSpanCostCoefficient(100)

# 各配送先に時間枠を設定
for node in range(N):
    if node == DEPOT:
        continue
    index = manager.NodeToIndex(node)
    open_, close_ = TIME_WINDOWS[node]
    time_dim.CumulVar(index).SetRange(open_, close_)

# 各車のデポ出発時刻に営業時間枠を設定
for v in range(NUM_VEHICLES):
    index = routing.Start(v)
    time_dim.CumulVar(index).SetRange(0, HORIZON)
    routing.AddVariableMinimizedByFinalizer(time_dim.CumulVar(routing.Start(v)))
    routing.AddVariableMinimizedByFinalizer(time_dim.CumulVar(routing.End(v)))

# ----------------------------------------------------------------------
# 3. 求解
# ----------------------------------------------------------------------
params = pywrapcp.DefaultRoutingSearchParameters()
params.first_solution_strategy = (
    routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
params.local_search_metaheuristic = (
    routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
params.time_limit.FromSeconds(10)

solution = routing.SolveWithParameters(params)

# ----------------------------------------------------------------------
# 4. 結果の表示
# ----------------------------------------------------------------------
def hhmm(minutes):
    return f"{8 + minutes // 60:02d}:{minutes % 60:02d}"

if solution:
    print("=" * 60)
    print("配送ルート最適化 結果")
    print("=" * 60)
    total_time = 0
    total_load = 0
    routes = []
    for v in range(NUM_VEHICLES):
        index = routing.Start(v)
        route = []
        load = 0
        line = []
        while not routing.IsEnd(index):
            node = manager.IndexToNode(index)
            t = solution.Value(time_dim.CumulVar(index))
            load += DEMANDS[node]
            route.append(node)
            tag = "発" if node == DEPOT else "着"   # デポ起点は「出発時刻」
            line.append(f"{NAMES[node]}({tag}{hhmm(t)})")
            index = solution.Value(routing.NextVar(index))
        end_t = solution.Value(time_dim.CumulVar(index))
        route.append(DEPOT)
        line.append(f"倉庫(帰{hhmm(end_t)})")
        routes.append(route)
        total_time += end_t
        total_load += load
        print(f"\n[トラック{v+1}] 積載 {load}/{VEHICLE_CAPACITY}箱")
        print("  " + " → ".join(line))
    print("\n" + "-" * 60)
    print(f"全車の総稼働時間 : {total_time} 分")
    print(f"総配送箱数       : {total_load} 箱")
    print(f"求解時間         : 約10秒以内")

    # 検証: 時間枠と積載の遵守
    print("\n■ 制約チェック")
    ok = True
    for v in range(NUM_VEHICLES):
        index = routing.Start(v)
        while not routing.IsEnd(index):
            node = manager.IndexToNode(index)
            if node != DEPOT:
                t = solution.Value(time_dim.CumulVar(index))
                o, c = TIME_WINDOWS[node]
                if not (o <= t <= c):
                    ok = False
                    print(f"  時間枠違反: {NAMES[node]}")
            index = solution.Value(routing.NextVar(index))
    print(f"  時間枠: {'全て遵守' if ok else '違反あり'}")
    print(f"  積載量: 全車 {VEHICLE_CAPACITY}箱以内")
else:
    print("解が見つかりませんでした")

# ============================================================
# 【Colab用】3台版(vrp.py)のルート地図を「その場に」表示する描画セル
#   ※ 先に vrp.py のコードを実行しておくこと。
#     solution, routing, manager, COORDS, NAMES, DEMANDS,
#     TIME_WINDOWS, NUM_VEHICLES がそのまま使われます。
#     （注: 3台版は変数名が solution / manager です）
# ------------------------------------------------------------
# 日本語フォント（初回だけ）:  !apt-get -y install fonts-noto-cjk
# ============================================================
import matplotlib.pyplot as plt
import matplotlib.font_manager as fm
for p in ["/usr/share/fonts/opentype/noto/NotoSansCJK-Regular.ttc",
          "/usr/share/fonts/opentype/noto/NotoSansCJKjp-Regular.otf"]:
    try:
        fm.fontManager.addfont(p)
        plt.rcParams["font.family"] = fm.FontProperties(fname=p).get_name()
        break
    except Exception:
        pass
plt.rcParams["axes.unicode_minus"] = False

COLORS = ["#E63946", "#2A9D8F", "#264653"]   # トラック1,2,3
fig, ax = plt.subplots(figsize=(9, 8.5))

for i, (x, y) in enumerate(COORDS):
    if i == 0:
        ax.scatter(x, y, c="black", s=340, marker="*", zorder=6)
        ax.annotate("倉庫", (x, y), textcoords="offset points",
                    xytext=(10, 8), fontsize=11, fontweight="bold")
    else:
        ax.scatter(x, y, c="#cccccc", s=120, zorder=3, edgecolors="gray")
        o, c = TIME_WINDOWS[i]
        tw = "終日" if (o, c) == (0, 600) else f"{8+o//60}-{8+c//60}時"
        ax.annotate(f"{NAMES[i]}\n{DEMANDS[i]}箱/{tw}", (x, y),
                    textcoords="offset points", xytext=(8, 6), fontsize=8)

for v in range(NUM_VEHICLES):
    idx = routing.Start(v)
    path = []
    while not routing.IsEnd(idx):
        path.append(manager.IndexToNode(idx))
        idx = solution.Value(routing.NextVar(idx))
    path.append(0)
    ax.plot([COORDS[n][0] for n in path], [COORDS[n][1] for n in path],
            "-o", color=COLORS[v], lw=2, ms=5, zorder=2, alpha=0.85,
            label=f"トラック{v+1}（{len(path)-2}件）")

ax.set_title("3台のトラックの配送ルート\n（積載量・時間枠・荷下ろし最大30分を考慮）")
ax.set_xlabel("X [km]"); ax.set_ylabel("Y [km]")
ax.legend(fontsize=10); ax.grid(alpha=0.25); ax.set_aspect("equal")
plt.show()   # ← Colab/Jupyter ではこれで画像がその場に表示される

4. 実行結果

[トラック1] 積載 45/120箱
  倉庫(発11:03) → 店6(着13:00) → 店8(着14:07) → 倉庫(帰15:01)
[トラック2] 積載 116/120箱
  倉庫(発08:00) → 店11(08:26) → 店2(09:29) → 店10(11:17) → 店9(13:00) → 店4(13:54) → 店3(14:39) → 倉庫(帰15:35)
[トラック3] 積載 97/120箱
  倉庫(発08:35) → 店7(10:19) → 店12(12:00) → 店5(12:51) → 店1(13:35) → 倉庫(帰14:52)

全車の総稼働時間 : 1288 分
時間枠: 全て遵守 / 積載量: 全車 120箱以内

すべての時間枠と積載制約を守りつつ、総稼働時間を最小化した配送計画が約10秒で得られました。

各トラックが地理的に固まったエリアを担当し、ルートがほとんど交差していません。注目すべきはトラック1で、担当する店6（13〜17時）・店8（10〜15時）がいずれも午後しか受け取れないため、あえて11:03発・2件のみという配置になっています。これは「制約を守った結果としての合理的な偏り」です。

「最適解」ではなく「良質な解」：シフト編(CP-SAT)は最適性を証明できましたが、VRPは局所探索メタヒューリスティクス（Guided Local Search）で制限時間内の最良解を返します。規模が小さいので最適に近いですが、OPTIMAL を保証するものではない点は正直に押さえておきます。

5. 「均等に配る」と「早く帰る」はトレードオフ

トラック2が7件・116箱とやや重い一方、トラック1は2件と軽くなっています。台数を均したい場合は、コード内のコメントアウトを1行外すだけで最長ルートを縮める平準化が効きます。

time_dim.SetGlobalSpanCostCoefficient(100)   # 各車の稼働を平準化

ただしこれには**「稼働の幅を縮めるため全車の出発が遅くなる」という副作用**があります（早く動けるトラックまで待機する）。総稼働時間も増えます。「総時間を短く」「台数を均等に」「全車早く帰す」は同時には立てづらく、どれを優先するかを目的関数のさじ加減で決めるのがVRP設計の本質です。

6. 発展：2台に減らせるか？ ― 積み直し（マルチトリップ）

「3台必要」という結論は、実は時間ではなく積載量で決まっていました。総需要は258箱なので、1台120箱で「1台＝1便（積んだら戻らず一筆書き）」だと、2台×120＝240箱で18箱足りず不可能です。試しに2台で解くと INFEASIBLE（解なし）になります。

しかし現実のトラックは、倉庫に戻って積み直し、1日に複数回走ります。これを マルチトリップVRP と呼びます。これをモデルに入れると、120箱トラック2台のままで全部運べます。

モデル上の工夫は3つです。

各トラックに「便」を仮想車両として複数用意する（2台×2便＝4ルート）。積載量は便ごとにリセットされる。
同じトラックの2便目は「1便目が帰庫してから（積み直し時間を挟んで）」出発する、という順序制約を加える。
1便目はできるだけ早く帰庫・2便目はできるだけ遅く出発、として積み直し＋休息のバッファを確保する。

肝になるのは2の順序制約です。同じ物理トラックの2つの便の時刻を、車両をまたいでつなぎます。

solver = routing.solver()
for t in range(NUM_TRUCKS):
    v1, v2 = t * TRIPS, t * TRIPS + 1          # 1便目, 2便目（仮想車両）
    # 2便目は「1便目が帰庫 + 積み直し(RELOAD分)」以降に出発
    solver.Add(tdim.CumulVar(routing.Start(v2))
               >= tdim.CumulVar(routing.End(v1)) + RELOAD)

積載量は便ごとにリセットしたいので、容量は仮想車両ごとに与えます（AddDimensionWithVehicleCapacity の上限を便の数だけ並べる）。これで1台が1便120箱を超えて運べるようになります。

求解結果（積載120箱のまま・2台・各2便）は次の通りです。

■ トラック1（59箱→85箱）
  1便目: 08:00発 → 店11・店2・店8 → 12:09帰庫
  2便目: 13:55発 → 店10・店9・店4・店3 → 18:00帰庫   （積み直し＋休息 106分）
■ トラック2（50箱→64箱）
  1便目: 08:00発 → 店1・店5 → 10:59帰庫
  2便目: 13:10発 → 店6・店12・店7 → 18:00帰庫        （積み直し＋休息 131分）

2便合計の総移動時間: 637分 / 全時間枠遵守 / 全便18:00までに帰庫

実線が1便目、破線が2便目です。各トラックが午前便を終えて一度倉庫に戻り、積み直してから午後便を回しています。午前便と午後便の間には106〜131分の積み直し＋休息が入り、全車が18:00までに帰庫できています。

ここでの学びは「3台必要だったのは時間ではなく容量の問題だった」という点です。時間にはもともと余裕があったので、積み直しという発想で容量の壁を外せば2台で足ります。なお「両車きっちり120分以上の休息」までは18:00帰庫と競合して厳しく、ここでは総移動の最短（637分）を優先しています。休息・台数・総移動・帰庫時刻のどれを優先するかは、やはり目的関数と制約の置き方しだいです。

元コード（3台版）からの変更点

3台版 vrp.py を、どこをどう書き換えると2台マルチトリップ版になるかを整理します。データ部分（座標・需要・時間枠など）はそのままで、変えるのは主に「車両の定義」と「制約」です。

車両を「物理トラック×便」に分ける。 NUM_VEHICLES = 3 をやめ、2台×2便＝4つの仮想車両にします。RoutingIndexManager や容量配列、ループはこの NUM_VEH を使います。

# 変更前（3台・1台1便）
NUM_VEHICLES = 3
manager = pywrapcp.RoutingIndexManager(N, NUM_VEHICLES, DEPOT)

# 変更後（2台 × 2便 = 4仮想車両）
NUM_TRUCKS = 2
TRIPS = 2
NUM_VEH = NUM_TRUCKS * TRIPS          # = 4
mgr = pywrapcp.RoutingIndexManager(N, NUM_VEH, DEPOT)

積載量は便ごとにリセット。 これは特別な実装は不要で、容量上限を仮想車両の数だけ並べるだけです。各便が別ルートなので、倉庫に戻るたびに積載が0に戻ります。
```
# 上限を NUM_VEH 個ぶん並べる（便ごとに120箱）
routing.AddDimensionWithVehicleCapacity(
    didx, 0, [VEHICLE_CAPACITY] * NUM_VEH, True, "Cap")
```

積み直しの順序制約を追加（新規）。 同じ物理トラックの2便目を、1便目の帰庫＋積み直し後に出発させます。3台版には無かった、便どうしをつなぐ制約です。

solver = routing.solver()
for t in range(NUM_TRUCKS):
    v1, v2 = t * TRIPS, t * TRIPS + 1
    solver.Add(tdim.CumulVar(routing.Start(v2))
               >= tdim.CumulVar(routing.End(v1)) + RELOAD)

両トラックを2便構成にする（任意）。 何も指定しないと「1台が大きく1便、もう1台だけ2便」という非対称解になりがちです。各便に最低1店を割り当てて、両車に午前・午後便を持たせます。
```
for v in range(NUM_VEH):
    solver.Add(routing.NextVar(routing.Start(v)) != routing.End(v))
```
休息と配分の微調整（任意）。 1便目は早く帰庫・2便目は遅く出発というソフト制約で積み直し＋休息を伸ばし、各便に最低積載量を課して「ほぼ空荷の便」を防ぎます（本記事では各便40箱以上）。

残りの時間Dimensionや時間枠の設定は3台版と同じです。

vrp_multitrip.py 全文（クリックで展開）

# -*- coding: utf-8 -*-
"""2台のトラックが倉庫で積み直して複数便を走る（マルチトリップ）検証"""
import math, random
from ortools.constraint_solver import routing_enums_pb2, pywrapcp

random.seed(42)
NAMES = ["倉庫"] + [f"店{i}" for i in range(1, 13)]
COORDS = [(25, 25)]
for _ in range(12): COORDS.append((random.randint(0, 50), random.randint(0, 50)))
N = len(COORDS)
DEMANDS = [0] + [random.randint(10, 30) for _ in range(N - 1)]
SERVICE_TIME = [0] + [min(30, 8 + d) for d in DEMANDS[1:]]
TIME_WINDOWS = [(0, 600), (0, 600), (0, 300), (300, 600), (0, 600), (60, 360),
                (300, 540), (0, 600), (120, 420), (300, 600), (0, 600), (0, 300), (240, 600)]
SPEED_KMH, HORIZON = 30, 600
VEHICLE_CAPACITY = 120        # ← 現状と同じ120箱のまま
NUM_TRUCKS = 2                # 物理トラック2台
TRIPS = 2                     # 1台あたり最大2便（往復して積み直し）
RELOAD = 15                   # 倉庫での積み直し時間[分]
NUM_VEH = NUM_TRUCKS * TRIPS  # 仮想車両 = 2台 x 2便 = 4
DEPOT = 0

def travel_min(i, j):
    (xi, yi), (xj, yj) = COORDS[i], COORDS[j]
    return int(round(math.hypot(xi - xj, yi - yj) / SPEED_KMH * 60))

mgr = pywrapcp.RoutingIndexManager(N, NUM_VEH, DEPOT)
routing = pywrapcp.RoutingModel(mgr)

def time_cb(fi, ti):
    i, j = mgr.IndexToNode(fi), mgr.IndexToNode(ti)
    return travel_min(i, j) + SERVICE_TIME[i]
tidx = routing.RegisterTransitCallback(time_cb)
routing.SetArcCostEvaluatorOfAllVehicles(tidx)

def dem_cb(fi): return DEMANDS[mgr.IndexToNode(fi)]
didx = routing.RegisterUnaryTransitCallback(dem_cb)
# 各便（仮想車両）ごとに容量120 … 倉庫に戻るたびにリセットされる
routing.AddDimensionWithVehicleCapacity(didx, 0, [VEHICLE_CAPACITY]*NUM_VEH, True, "Cap")

routing.AddDimension(tidx, 60, HORIZON, False, "Time")
tdim = routing.GetDimensionOrDie("Time")
for node in range(N):
    if node == DEPOT: continue
    idx = mgr.NodeToIndex(node)
    o, c = TIME_WINDOWS[node]
    tdim.CumulVar(idx).SetRange(o, c)
for v in range(NUM_VEH):
    tdim.CumulVar(routing.Start(v)).SetRange(0, HORIZON)

# ★マルチトリップの肝: 同じ物理トラックの「2便目」は「1便目が倉庫に戻ってから(+積み直し)」出発
solver = routing.solver()
for t in range(NUM_TRUCKS):
    v1, v2 = t*TRIPS, t*TRIPS + 1     # 1便目, 2便目
    # 2便目は「1便目が帰庫 + 積み直しRELOAD分」以降に出発（順序制約）
    solver.Add(tdim.CumulVar(routing.Start(v2)) >= tdim.CumulVar(routing.End(v1)) + RELOAD)
    # 積み直し＋休息のバッファを伸ばす（1便目は早く帰庫・2便目は遅く出発）
    REST = 8
    tdim.SetCumulVarSoftUpperBound(routing.End(v1), 0, REST)
    tdim.SetCumulVarSoftLowerBound(routing.Start(v2), HORIZON, REST)

for v in range(NUM_VEH):
    solver.Add(routing.NextVar(routing.Start(v)) != routing.End(v))
cap_dim = routing.GetDimensionOrDie("Cap")
for v in range(NUM_VEH):
    cap_dim.CumulVar(routing.End(v)).SetMin(40)   # 各便40箱以上（極端な空荷便を禁止）
# 目的:
# → 全便合わせた総移動時間が最短になるよう最適化する。
#   休息は上のソフト制約でできる限り確保（このデータでは106〜131分）。

params = pywrapcp.DefaultRoutingSearchParameters()
params.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
params.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
params.time_limit.FromSeconds(20)
sol = routing.SolveWithParameters(params)

def hhmm(m): return f"{8 + m//60:02d}:{m%60:02d}"
if sol:
    print("=== 2台・各2便（積載120箱のまま, 両車2便・総移動最小・休息はできる限り確保）===")
    for t in range(NUM_TRUCKS):
        print(f"\n■ トラック{t+1}")
        end1 = start2 = None
        for trip in range(TRIPS):
            v = t*TRIPS + trip
            idx = routing.Start(v)
            if routing.IsEnd(sol.Value(routing.NextVar(idx))):
                continue  # 空便
            load, line = 0, []
            start_t = sol.Value(tdim.CumulVar(idx))
            while not routing.IsEnd(idx):
                node = mgr.IndexToNode(idx)
                tt = sol.Value(tdim.CumulVar(idx))
                load += DEMANDS[node]
                tag = "発" if node == DEPOT else "着"
                line.append(f"{NAMES[node]}({tag}{hhmm(tt)})")
                idx = sol.Value(routing.NextVar(idx))
            end_t = sol.Value(tdim.CumulVar(idx))
            line.append(f"倉庫(帰{hhmm(end_t)})")
            print(f"  {trip+1}便目 (積載{load}箱): " + " → ".join(line))
            if trip == 0:
                end1 = end_t
            else:
                start2 = start_t
        if end1 is not None and start2 is not None:
            print(f"  → 1便目帰庫 {hhmm(end1)} 〜 2便目出発 {hhmm(start2)}："
                  f"積み直し＋休息に {start2 - end1} 分確保")
    # 検証
    ok = True
    for v in range(NUM_VEH):
        idx = routing.Start(v)
        while not routing.IsEnd(idx):
            node = mgr.IndexToNode(idx)
            if node != DEPOT:
                tt = sol.Value(tdim.CumulVar(idx))
                o, c = TIME_WINDOWS[node]
                if not (o <= tt <= c): ok = False
            idx = sol.Value(routing.NextVar(idx))
    # 総移動時間（荷下ろし時間を除いた純粋な移動）を集計
    total_travel = 0
    for v in range(NUM_VEH):
        idx = routing.Start(v)
        while not routing.IsEnd(idx):
            nxt = sol.Value(routing.NextVar(idx))
            total_travel += travel_min(mgr.IndexToNode(idx), mgr.IndexToNode(nxt))
            idx = nxt
    print(f"\n2便合計の総移動時間: {total_travel} 分（4便ぶんの走行のみ・荷下ろし除く）")
    print(f"時間枠: {'全て遵守' if ok else '違反あり'} / 全便18:00までに帰庫")
else:
    print("解が見つかりませんでした（2台では不可）")

# ============================================================
# 【Colab用】ルート地図を「その場に」表示する描画セル
#   ※ 先に vrp_multitrip.py（または vrp.py）のコードを実行しておくこと。
#     sol, routing, mgr, COORDS, NAMES, DEMANDS, TIME_WINDOWS,
#     NUM_TRUCKS, TRIPS などの変数がそのまま使われます。
# ------------------------------------------------------------
# 日本語フォント（初回だけ）:  !apt-get -y install fonts-noto-cjk
# ============================================================
import matplotlib.pyplot as plt
import matplotlib.font_manager as fm
for p in ["/usr/share/fonts/opentype/noto/NotoSansCJK-Regular.ttc",
          "/usr/share/fonts/opentype/noto/NotoSansCJKjp-Regular.otf"]:
    try:
        fm.fontManager.addfont(p)
        plt.rcParams["font.family"] = fm.FontProperties(fname=p).get_name()
        break
    except Exception:
        pass
plt.rcParams["axes.unicode_minus"] = False

TRUCK_COLOR = ["#E63946", "#2A9D8F"]   # トラック1=赤, 2=緑
TRIP_STYLE  = ["-", "--"]              # 1便目=実線, 2便目=破線
fig, ax = plt.subplots(figsize=(9, 8.5))

for i, (x, y) in enumerate(COORDS):
    if i == 0:
        ax.scatter(x, y, c="black", s=340, marker="*", zorder=6)
        ax.annotate("倉庫", (x, y), textcoords="offset points",
                    xytext=(10, 8), fontsize=11, fontweight="bold")
    else:
        ax.scatter(x, y, c="#cccccc", s=120, zorder=3, edgecolors="gray")
        o, c = TIME_WINDOWS[i]
        tw = "終日" if (o, c) == (0, 600) else f"{8+o//60}-{8+c//60}時"
        ax.annotate(f"{NAMES[i]}\n{DEMANDS[i]}箱/{tw}", (x, y),
                    textcoords="offset points", xytext=(8, 6), fontsize=8)

for t in range(NUM_TRUCKS):
    for trip in range(TRIPS):
        v = t*TRIPS + trip
        idx = routing.Start(v)
        if routing.IsEnd(sol.Value(routing.NextVar(idx))):
            continue
        path = []
        while not routing.IsEnd(idx):
            path.append(mgr.IndexToNode(idx))
            idx = sol.Value(routing.NextVar(idx))
        path.append(0)
        load = sum(DEMANDS[n] for n in path)
        ax.plot([COORDS[n][0] for n in path], [COORDS[n][1] for n in path],
                TRIP_STYLE[trip], color=TRUCK_COLOR[t], lw=2.2, ms=5, marker="o",
                zorder=2, alpha=0.85, label=f"トラック{t+1} {trip+1}便目（{load}箱）")

ax.set_title("2台＋積み直し（マルチトリップ）の配送ルート\n実線=1便目 / 破線=2便目")
ax.set_xlabel("X [km]"); ax.set_ylabel("Y [km]")
ax.legend(fontsize=9); ax.grid(alpha=0.25); ax.set_aspect("equal")
plt.show()   # ← Colab/Jupyter ではこれで画像がその場に表示される

まとめ

VRPTW は「移動・荷下ろし・時間枠・帰庫」を1本の時間Dimensionに集約して表現する。
「荷下ろし最大30分」はサービス時間の min(30, ...)、時間枠は CumulVar の範囲指定で素直に書ける。
平準化・総時間・帰庫時刻はトレードオフ関係にあり、目的関数の重み付けが設計の肝になる。
「2台で足りるか」は時間ではなく容量で決まることもあり、**積み直し（マルチトリップ）**で台数を減らせる場合がある。

シフト自動作成編は【OR-Tools実践①】仲が悪いペアも夜勤明けも考慮した「シフト自動作成」(CP-SAT) をご覧ください。質問はコメントで歓迎します。