配送ルート最適化をOR-ToolsとClaude Codeで作る — 積載量と時間枠の検算

id,name,x_km,y_km,demand_kg,tw_start,tw_end,service_min
0,depot,0,0,0,0,480,0
1,A,4,3,20,30,120,10
2,B,-3,6,35,60,180,10
3,C,7,-2,25,0,90,10
4,D,-5,-4,40,120,240,15
5,E,2,9,15,90,200,10
6,F,9,5,30,150,300,10
7,G,-8,2,20,0,150,10
8,H,5,-7,45,200,360,15
9,I,-2,-8,10,60,200,10
10,J,10,-6,30,240,420,10

# 配送ルート最適化
- 入力は stops.csv(列: id,name,x_km,y_km,demand_kg,tw_start,tw_end,service_min)
- 時間の単位は分。拠点(id=0)の出発可能時刻を0とする
- 制約は「積載上限」「時間枠」「全地点を1回ずつ訪問」の3つ
- ソルバーを変更したら、必ず `./venv/bin/python vrp.py` を実行し、
  末尾の「検算: OK / NG」を貼って報告する。NG のまま完了としない
- 検算は verify() が経路だけから再計算する。ソルバーの内部値は使わない

{
  "permissions": {
    "allow": ["Bash(./venv/bin/python vrp.py *)"]
  }
}

import csv, math, sys
from ortools.constraint_solver import pywrapcp, routing_enums_pb2
 
SPEED_KM_PER_MIN = 0.5      # 30 km/h
VEHICLES, CAPACITY = 3, 100  # 台数, 1台あたり積載上限(kg)
 
def load(path):
    with open(path, newline="") as f:
        return [{k: (v if k == "name" else int(float(v)) if k in
                 ("id","demand_kg","tw_start","tw_end","service_min") else float(v))
                 for k, v in r.items()} for r in csv.DictReader(f)]
 
def travel(a, b):
    return math.ceil(math.hypot(a["x_km"]-b["x_km"], a["y_km"]-b["y_km"]) / SPEED_KM_PER_MIN)
 
def solve(stops, use_capacity=True, use_windows=True):
    n = len(stops)
    mgr = pywrapcp.RoutingIndexManager(n, VEHICLES, 0)
    routing = pywrapcp.RoutingModel(mgr)
 
    def time_cb(i, j):
        a, b = stops[mgr.IndexToNode(i)], stops[mgr.IndexToNode(j)]
        return travel(a, b) + a["service_min"]      # 移動 + 出発地の荷降ろし
    t = routing.RegisterTransitCallback(time_cb)
    routing.SetArcCostEvaluatorOfAllVehicles(t)
 
    if use_capacity:
        d = routing.RegisterUnaryTransitCallback(
            lambda i: stops[mgr.IndexToNode(i)]["demand_kg"])
        routing.AddDimensionWithVehicleCapacity(d, 0, [CAPACITY]*VEHICLES, True, "Load")
 
    routing.AddDimension(t, 60, 480, False, "Time")   # 待機60分まで・1台480分まで
    td = routing.GetDimensionOrDie("Time")
    if use_windows:
        for s in stops[1:]:
            td.CumulVar(mgr.NodeToIndex(s["id"])).SetRange(s["tw_start"], s["tw_end"])
        for v in range(VEHICLES):
            td.CumulVar(routing.Start(v)).SetRange(stops[0]["tw_start"], stops[0]["tw_end"])
 
    p = pywrapcp.DefaultRoutingSearchParameters()
    p.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    p.local_search_metaheuristic = routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH
    p.time_limit.FromSeconds(2)
    sol = routing.SolveWithParameters(p)
    if not sol:
        return None
    routes = []
    for v in range(VEHICLES):
        i, r = routing.Start(v), []
        while not routing.IsEnd(i):
            r.append(mgr.IndexToNode(i)); i = sol.Value(routing.NextVar(i))
        r.append(0)
        routes.append(r)
    return routes
 
def verify(stops, routes):
    """ソルバーの内部値に頼らず、経路だけから積載量・到着時刻を再計算する"""
    errors, seen = [], []
    for v, r in enumerate(routes):
        if len(r) == 2: continue
        clock, load = stops[0]["tw_start"], 0
        for a, b in zip(r, r[1:]):
            clock += travel(stops[a], stops[b]) + stops[a]["service_min"]
            if b == 0: break
            clock = max(clock, stops[b]["tw_start"])      # 早着は窓の開始まで待つ
            load += stops[b]["demand_kg"]; seen.append(b)
            if clock > stops[b]["tw_end"]:
                errors.append(f"車両{v}: 地点{b}に{clock}分着(窓 {stops[b]['tw_start']}-{stops[b]['tw_end']})")
        if load > CAPACITY:
            errors.append(f"車両{v}: 積載{load}kg > 上限{CAPACITY}kg")
    miss = sorted(set(range(1, len(stops))) - set(seen))
    dup = sorted({x for x in seen if seen.count(x) > 1})
    if miss: errors.append(f"未訪問: {miss}")
    if dup: errors.append(f"重複訪問: {dup}")
    return errors
 
if __name__ == "__main__":
    stops = load("stops.csv")
    flags = set(sys.argv[1:])
    routes = solve(stops, "--no-capacity" not in flags, "--no-windows" not in flags)
    if routes is None:
        print("解なし"); sys.exit(1)
    for v, r in enumerate(routes):
        print(f"車両{v}: " + " -> ".join(map(str, r)))
    errs = verify(stops, routes)
    print("検算: OK" if not errs else "検算: NG\n  " + "\n  ".join(errs))