vrplab 技術資料
このアプリが「何を決めて、何を最小化し、何を守っているか」と、 その解き方（アルゴリズム）をまとめます。
扱う問題
容量制約付き配送計画問題（CVRP）に時間枠（VRPTW）と、デポの開設判断を加えたものです。 デポは1つ以上置けますが、車両は所属デポから出て所属デポへ帰り、デポを跨いで移動しません。 車両とデポの組み合わせまで最適化する「真の複数デポVRP（MDVRP）」は扱いません。
一方でデポを開くか閉じるかはソルバが決めます。各デポに開設固定費があり、 「固定費を払ってこの拠点を開ける価値があるか」を輸送費と合わせて判断します。 車両の所属デポ自体は動かないので、上の MDVRP 除外と矛盾しません。
スコープ外: 車両種別ごとの仕様差、集荷と配送の混在（pickup & delivery）、 実道路の距離行列、CSV入出力、厳密解・最適性の保証。
決定変数（ソルバが決めるもの）
ソルバが探索するのは次の2つだけです。
| 変数 | 取りうる値 | 意味 |
|---|---|---|
| 割当 | 各配送先 → 車両番号 0..V−1 のどれか、または「未訪問」 | どの車両が運ぶか。運ばない選択（未訪問）も正規の選択肢 |
| 訪問順 | 各車両に割り当てられた配送先の順列 | どの順に回るか。デポは両端に暗黙に入る |
V は全デポの車両台数の合計です。車両番号はデポを先頭から並べて 各デポの車両台数の分だけ連番を割ったもの（例: デポA が3台なら 0,1,2、続くデポB が2台なら 3,4）で、 車両番号の空間は常に全候補デポ分で固定します。
目的関数（最小化するもの）
すべて実額（円）で、1日あたりの運用コストとして足し合わせた総額を最小化します。
| 用語 | 定義 |
|---|---|
| 開設デポ | そのデポの車両が1台以上使われている、または強制開設が指定されている |
| 距離km(r) | デポ→訪問順→デポ の直線距離 × 迂回係数の総和 |
| 稼働分(r) | 帰着時刻 − 出発可能時刻。時間枠待ちの待機時間を含む |
| 遅延分 | サービス開始が時間枠の終了時刻を超えた分（早着は違反ではない） |
既定の単価は次の値です。いずれも設定パネルから変更できます。
| 項目 | 既定値 | 内訳の想定 |
|---|---|---|
| デポ開設固定費 | 40,000 円/拠点 | 賃料・常駐人員・設備の按分 |
| 車両固定費 | 8,000 円/台 | リース・保険・税 |
| 距離 | 60 円/km | 燃料・タイヤ・整備 |
| 稼働時間 | 50 円/分 | 人件費（時給3,000円相当） |
| 未訪問 | 20,000 円/件 | 機会損失・再配達 |
| 遅延 | 300 円/分 | 遅延ペナルティ |
稼働分に待機時間を含めるので、時間枠を厳しくすると待機が増えて人件費が上がるという トレードオフも金額で見えます。
制約条件
常に守るもの（ハード制約）
| 制約 | 式 | どこで守るか |
|---|---|---|
| 積載容量 | ルートの需要量合計 ≤ 積載容量の上限 | ルート単位の判定（違反があれば手を採用しない） |
| 稼働時間上限 | 稼働分 ≤ 稼働時間の上限 | 同上 |
| 帰着期限 | 帰着時刻 ≤ 帰着期限 | 同上 |
| 車両台数 | ルート本数 = 全デポの車両台数の合計（固定） | 構造で守る（ルート配列の長さそのもの） |
| 強制閉鎖デポ | そのデポの車両は使用不可 | 構造で守る（候補車両から除外して到達不能にする） |
| 配送先の車両固定 | 固定した車両からは移動できない | 各近傍が移動先を検査 |
| 開設デポ数の上下限 | 開設数の下限 ≤ 開設デポ数 ≤ 開設数の上限 | 解全体の判定（1ルートだけでは分からないため、候補解の採否で見る） |
| カバー範囲 | 担当デポから配送先までの距離 ≤ デポからの最大距離 | ルート単位の判定。範囲外の配送先は未訪問になる |
切り替えられるもの
| 制約 | 扱い |
|---|---|
| 時間枠（遅着） | 厳守: 間に合わない訪問は挿入しない（結果として未訪問になる）／ 遅刻可: 遅刻を許し遅延単価でコストに計上する |
| 時間枠（早着） | 違反ではなく待機。時間枠の開始時刻まで待ってからサービスを開始し、待機時間は稼働時間に算入する |
アルゴリズム
厳密解ではなくヒューリスティック（発見的解法）です。 「初期解を作る → 少しずつ改善する → 行き詰まったら一部を壊して作り直す」を 時間予算が尽きるまで繰り返します。
1. 距離行列の事前計算
全地点（デポ＋配送先）間の距離と所要時間を先に計算して表にします。 局所探索は同じ2点間の距離を何度も引くので、都度2点間の距離を計算し直すと無駄になります。 60地点なら 66×66 程度で、計算は瞬時です。
実道路距離ではなく直線距離の近似です。この近似は画面上にも明記しています。
2. 初期解：並列挿入法（Solomon I1 の簡略版）
- 空のルートを車両台数分だけ用意する
- まだ割り当てていない配送先すべてについて、「どの車両のどの位置に挿し込むか」の 目的関数の増分を全通り計算する
- 増分が最小の（配送先, 車両, 位置）を1つ確定して挿入する
- 2〜3 を繰り返し、実行可能な挿入が無くなったら残りを未訪問にして終了
増分は距離だけでなく、その車両を新しく使い始める費用と、そのデポを新しく開く固定費を含めます。 距離だけで選ぶと、空いている車両（＝未開設デポ）へ気軽に配ってしまい、 せっかく閉じたデポをすぐ開け直してしまいます。
最近傍法から始めないのは、最後に遠い地点だけが残って極端に悪い解になりやすく、 時間枠との相性も悪いためです。挿入法は最初からそれなりの解を出すので、 改善過程の再生が「ぐちゃぐちゃからきれいへ」ではなく「それなりから良いへ」になり、 実務の感覚に近くなります。
3. 局所探索：4種の近傍を「改善即採用」方式で回す
| 近傍 | 操作 | 効く場面 |
|---|---|---|
| relocate（移動） | 1地点を別の位置（別ルート含む）へ移す | 車両間の偏りの是正 |
| swap（交換） | 2地点を入れ替える | 容量が詰まっていて移動できないとき |
| 2-opt | 1ルート内で辺を2本切って区間を反転する | 経路の交差の解消 |
| 2-opt* | 2ルート間で後半をまるごと交換する | ルート同士が絡んでいるとき |
改善が見つかったら即座に採用し、どの近傍でも改善が見つからなく なるまで繰り返します。あわせて、未訪問からの挿入試行も毎周行います （これが無いと「台数を増やしたのに未訪問が減らない」という説明しづらい挙動が出ます）。
速度のため、各近傍は触った1〜2ルートだけの部分和でコストを比較します（解全体を 毎回再計算しません）。ただしデポ開設固定費は「そのデポの全車両が空か」で決まるため、 1ルートだけ見ても判定できません。そこで降下の開始時にデポごとの「空でないルート数」を 数えておき、触るルートを除いた数と突き合わせることで、 他の車両がまだそのデポを使っているかを厳密に判定しています。
4. 摂動：ruin & recreate（壊して作り直す）
局所探索が行き詰まったら、解の一部を壊して作り直し、改善していれば乗り換えます。壊し方は3種類です。
| 壊し方 | 内容 | 選ばれる確率 |
|---|---|---|
| 一様ランダム破壊 | 割当済みの配送先から 10〜30% をランダムに取り除く | 50% |
| デポを閉じる方向 | 開いているデポを1つ選び、そのデポの車両のルートを全部空にする | 30%（デポが2つ以上あるとき） |
| デポを開く方向 | 閉じているデポを1つ選び、そのデポから近い順に5件の配送先を引き剥がす | 20%（デポが2つ以上あるとき） |
5. 時間予算と中断
打ち切りは反復回数ではなく実際に経過した時間で判定します。 既定の予算は500msで、画面から変更できます。局所探索の側も外側ループごとに 期限を見ます（60地点規模では1回の降下に200ms以上かかるため、ここを見ないと予算を超過します）。 各近傍は手を採用した時点で処理を終えるので、どこで打ち切っても解は壊れません。
画面側では世代番号を持ち、計算中に新しい要求が来たら Worker を作り直して古い結果は捨てます。 「中断は常に効く」ことを要件にしています。
6. 再現性
乱数は、シード値（種になる数）を固定した専用の生成器（xorshift32）だけを使い、 実行ごとに結果が変わる標準の乱数機能は使いません。 同じシナリオ・同じ設定・同じシード値なら、開設するデポの選択まで含めて常に同じ結果になります。 シード値は画面から変更できるので、「同じ問題でも初期条件が違えば違う解に落ちる」という ヒューリスティックの性質も見せられます。
7. デポの開け方を全比較する（任意）
通常の計算は「見つけた中で一番良かった1案」しか見せません。しかし 「拠点を1つ増やすと固定費はいくら増えて輸送費はいくら減るのか」を読むには、 採用されなかった開け方も並んでいる必要があります。 そこで、開け方（空の組み合わせを除く 2のデポ数乗 − 1 通り）をすべて数え上げて 表にするビューを、任意で開けるようにしています。
これは既定の解き方ではありません。既定はデポ単位の破壊近傍のままです。 また、全部を数え上げているのは開け方だけで、 それぞれの開け方の中の配送は近似のままなので、「これが最適」とは言えません。
| 段 | やること | 理由 |
|---|---|---|
| 1段目 | すべての開け方を、局所探索1回だけで粗くふるいにかける | 1つの開け方でも1降下に25〜241msかかるため、全部に本予算を配ると候補6拠点で数十秒になる |
| 2段目 | 上位5件だけを、画面で設定した計算時間で解き直す | 粗い見積りは絶対額がずれるので、少なくとも表の上位は確定値にしないと金額として読めない |
また打ち切りが時間制なので、金額は1円単位では再現しません （同じ設定でもパソコンの混み具合で反復回数が変わります）。表の金額は目安として読んでください。
表に並ぶのは、いまの設定の下で成立する開け方だけです。強制開設・強制閉鎖に反するもの、 開設数の上下限に反するもの、車両を固定した配送先のデポが閉じてしまうものは除き、 除いた件数と理由も画面に出します（黙って減らすと「全部見た」が嘘になります）。 候補が7拠点以上のときは、一部だけ見せるのではなくエラーにします。
各行の「この開け方にする」を押すと、その組み合わせを強制開設・強制閉鎖として設定し、 解き直します。このとき出る金額は表に出ていた金額と一致します （開け方ごとにシード値をずらさないようにしているためです。 ずらす実装にしていた時期があり、表の数字が再現しないという問題になりました）。
計算時間の目安
初期解の構築＋局所探索を1回通したときの実測値です（摂動を含まない、1回の降下）。
| 配送先 | デポ | 車両 | 初期解 | 局所探索 | 合計 |
|---|---|---|---|---|---|
| 25 | 1 | 5 | 15ms | 20ms | 35ms |
| 40 | 3 | 9 | 35ms | 68ms | 103ms |
| 60 | 3 | 9 | 61ms | 139ms | 200ms |
| 60 | 6 | 18 | 74ms | 158ms | 232ms |
想定規模は10〜60地点です。既定の500msでも、25地点なら100回以上摂動を回せますが、 60地点・6デポでは1〜2回しか回りません。規模が大きいときは予算を増やしてください。
最適性について（厳密解ではありません）
得られる解は良い解ですが、最適であることの保証はありません。下界も出しません。 これは意図した割り切りです。
配送計画とデポの開設判断を同時に厳密に解く問題（Location-Routing Problem）は、 経路の変数が地点数の2乗のオーダーで増え、部分巡回路を除去する追加の仕組みも必要になるため、 想定規模の上限（60地点・複数デポ）では現実的な時間で最適性を示せません。 加えて厳密解ソルバは「一発で答えを出す」性質上、 改善過程の再生ができなくなります。「最適化が何をしているのか」を動きで見せることを 重視しているため、ヒューリスティックを選んでいます。
経路を無視してよい（施設から需要地点への距離だけで評価してよい）問題であれば、 姉妹アプリ flplab が厳密解を出します。経路まで見た近似が vrplab、 経路を無視した厳密解が flplab、という住み分けです。
正しさの守り方
最も危険なのは評価関数（到着時刻の累積・待ち時間・時間枠違反・積載の累積・ デポの所属解決）です。ここを1箇所間違えても、ソルバはエラーを出さず 「一貫して間違った解」を返すため、地図はきれいに描かれ数字も出てしまい、 見た目では気づけません。次の4つで守っています。
- 手計算した期待値テスト — 3地点の例を手で解き、距離・到着時刻・待ち時間・ コストの期待値をテストに直書きする
- 総当たりとの突き合わせ — 5地点以下なら全割当・全順列を列挙して最良解を求め、 ソルバの解がそれより悪くないことを確認する
- 差分と全再計算の一致 — 局所探索が使う「部分和のデルタ」と、 解全体を再計算したときのコスト差が一致することを、ランダムな手で何通りも確認する。 ここがずれると、探索は嘘の改善を採用し続ける
- コスト内訳の合計一致 — 画面に出す内訳の合計が総コストと一致することを確認する