0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@zhongtianzuobo

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

0
Last updated at Posted at 2026-06-24

【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箱以内

vrp_result.png

すべての時間枠と積載制約を守りつつ、総稼働時間を最小化した配送計画が約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つです。

  1. 各トラックに「便」を仮想車両として複数用意する（2台×2便＝4ルート）。積載量は便ごとにリセットされる。
  2. 同じトラックの2便目は「1便目が帰庫してから（積み直し時間を挟んで）」出発する、という順序制約を加える。
  3. 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までに帰庫

multitrip_result.png

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

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

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

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

  1. 車両を「物理トラック×便」に分ける。 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)

  2. 積載量は便ごとにリセット。 これは特別な実装は不要で、容量上限を仮想車両の数だけ並べるだけです。各便が別ルートなので、倉庫に戻るたびに積載が0に戻ります。

    # 上限を NUM_VEH 個ぶん並べる（便ごとに120箱）
routing.AddDimensionWithVehicleCapacity(
    didx, 0, [VEHICLE_CAPACITY] * NUM_VEH, True, "Cap")

  3. 積み直しの順序制約を追加（新規）。 同じ物理トラックの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)

  4. 両トラックを2便構成にする（任意）。 何も指定しないと「1台が大きく1便、もう1台だけ2便」という非対称解になりがちです。各便に最低1店を割り当てて、両車に午前・午後便を持たせます。

    for v in range(NUM_VEH):
    solver.Add(routing.NextVar(routing.Start(v)) != routing.End(v))

  5. 休息と配分の微調整（任意）。 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) をご覧ください。質問はコメントで歓迎します。

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?