flplab 内部構造解説

1. flplabは何を解いているのか

施設配置問題（Facility Location Problem, FLP）は、「需要が存在する地点に対して、どこに施設を 配置すれば、所定の制約を満たしながらコストを最小化／サービスを最大化できるか」を求める数理最適化 問題です。倉庫・工場・店舗・病院・消防署・データセンター・EV充電ステーションなど、対象は幅広く 共通しています。

基本的には次の2つを同時に決めます。

1. どの候補地点に施設を開設するか
2. 各需要地点をどの施設に割り当てるか

flplab は、需要地点と施設候補を地図上に置き、目的関数と制約を選んで 最適化実行 を押すと、HiGHS というソルバ（数理最適化の計算エンジン、 ブラウザの中だけで動くよう変換されたもの）がこの2つを厳密解として求める、 ブラウザ内だけで完結するデモ・学習用ツールです。

2. 対応する6モデルの数理的な意味

flplab は UFLP・CFLP・p-Median・p-Center・Set Covering・Maximal Covering（MCLP）の 6モデルに対応します。ただしこれらは「6本の別プログラム」ではなく、 目的関数の選択と制約のON/OFFという組合せの中の代表点です（詳しい理由は 7章）。まず、それぞれが何を計算しているかを確認します。

p-Median と UFLP の違いは「施設数を最適化するか、指定するか」「固定費を持つか」「主目的が コストか距離か」に集約されます。p-Center は p-Median の「総距離最小」を「最悪地点の距離最小」に 置き換えたものです。Set Covering と MCLP は「どの施設が担当するか」ではなく「カバーできているか」 だけを問う、構造的に別のファミリーです（この違いが計算の組み立てにどう表れるかは 7章）。

各モデルの目的関数と主な制約

以下、需要地点を添字 i、施設候補を添字 j で表します。 f_j は施設 j の固定費、 c_ij は需要 i を施設 j が担当するコスト、d_ij は両者の距離、 y_j は施設 j を開設するかどうか、 x_ij は需要 i を施設 j に割り当てるかどうかを表します。

予算・容量・最大距離・需要分割は横断的に効く

予算制約・容量制約・最大距離制約・需要分割可否は、UFLP/CFLP/p-Median/p-Center の4モデルに対して 個別にON/OFFできる横断的な設定です。6モデルはこの組合せの中の代表点であり、ユーザーは6モデルから 選ぶだけでなく、制約を個別に足し引きして「6モデルのどれとも一致しないカスタムな設定」を作れます。 たとえば予算制約は次のように追加します。

3. 意図的に扱わないこと

FLPは非常に大きな問題ファミリーで、複数施設タイプ・多階層・複数期間・不確実性・競合施設配置・ Location-Routing・実道路距離・準最適解の列挙など、拡張の方向は数十通りあります。 flplab はデモ・啓蒙用途にスコープを絞るため、これらを明示的に対象外としています。

• 複数施設タイプ（大/中/小）、多段階施設（工場→倉庫→店舗）
• 複数期間（Multi-Period）、動的需要、不確実性（Robust/Stochastic）
• 競合施設配置、迷惑施設配置（Obnoxious）
• Location-Routing（配置＋配送ルートの同時最適化）
• 実道路の距離行列（ルーティングAPI連携）。直線距離×迂回係数の近似に留める
• 準最適解の列挙・パレート解表示
• 数百規模の施設候補・数千規模の需要地点（想定は候補20〜50、需要50〜300程度）

4. データの正本は「シナリオ」ひとつ

flplab が扱う状態はすべて「シナリオ」という1つのまとまりに集約されます。計算結果（解）は シナリオを書き換えたものではなく、シナリオから毎回作り直される派生物です。

保存・比較・再現はすべて、このシナリオだけを見れば足ります。シナリオが持つ情報は次の通りです。

需要量と重みを分ける理由

容量制約が消費する「量」（需要量）と、目的関数が重視する「重要度」（重み）は概念上別物です。 既定値は同じにしておき、必要なら編集で分離できるようにすることで、どちらの意味の「需要」も 表現できるようにしています。

距離は直線距離の近似

強制開設・強制閉鎖はシナリオへの記録として持つ

「この施設は必ず開ける／絶対に開けない」という条件は、計算結果を直接書き換えるのではなく、 シナリオ側に「この施設は開設固定／閉鎖固定」という記録として持ちます。計算するときにこの記録を 読み取り、対応する開設変数の値を1つに固定するという形で制約に反映します。こうすることで、 「本当の状態」がシナリオと計算結果の2か所に分かれてしまう事態を避けています。

5. 全体構造（層の分け方）

flplab の内部は、「画面（ブラウザの表示）に直接触れるかどうか」を境界にして、大きく2つの役割に 分かれています。

依存の向きは一方通行（状態管理 → 画面表示 → 計算ロジック）で、逆方向の呼び出しはありません。 この境界を厳密に引いているのは、画面を一切開かずに計算ロジックだけを自動テストできる ようにするためです。新しい計算ロジックを追加するときは、画面表示のコードに計算を 混ぜ込まず、計算ロジックの層に置くという原則を守っています。

6. なぜ「パラメータ変更で即時再計算」をしないのか

これは、姉妹ツールである別の配送計画用アプリからの最大の逸脱です。そちらのアプリは 「パラメータを動かすと一瞬で結果が変わる」体感を優先し、厳密解ではなく近似的な計算手法を 採用していました。flplab は厳密解を採用したため、この体感は成立しません。問題の規模次第で 計算に数百ミリ秒〜数十秒かかるためです。

• パラメータの編集（需要点の追加、施設候補の追加、制約チェックボックスの変更）は即座に反映され、 地図上のピンなども即時に動きます。しかし計算は自動では行いません。 直前の計算結果は「古くなった」という印がつくだけで、画面には 「パラメータが変更されました。再実行してください」という案内が出ます。
• 計算は 最適化実行 ボタンを押したときだけ実行します。
• 計算そのものは、画面を止めないようブラウザのバックグラウンドの仕組み（Web Worker）の中で 動く計算エンジンが担います。このエンジンは起動したまま使い続けます。 毎回終了して作り直すと、計算エンジン本体（数MB規模）を操作のたびに再読み込みすることになり、 小さい問題でも毎回1秒前後の遅延が乗ってしまうためです。中断したいときだけ、明示的な 中断 や、時間切れを検知する安全装置を通じて計算エンジンを 終了・再起動します。

7. パラメータから数理モデルを組み立てる仕組み

flplab の最も重要な設計思想は、「UFLP・CFLP・p-Medianという固定的な計算を個別に用意するのではなく、 パラメータの組合せから数理モデルを生成する」ことです。

どちらの数式グループを使うかの切り替え

Set Covering の目的関数は「固定費の総和の最小化」で、UFLP・CFLPと同じ形をしています。そのため 目的関数だけでは、どちらの数式グループ（割当を扱う4モデルか、カバーだけを扱う2モデルか）を 使うべきかを判別できません。この判定は目的関数ではなく、カバー制約（半径以内に施設が 1つ以上あることを要求するチェックボックス）がONになっているかどうかで行います。 ONならSet Covering/MCLPの数式グループ、OFFならUFLP/CFLP/p-Median/p-Centerの数式グループを 使う、という単純な切り替えです。

割当を扱う4モデル（UFLP・CFLP・p-Median・p-Center）共通の骨格

最大距離制約が「割当不能」を作る場合

最大距離制約を厳しく設定すると、ある需要地点にとって到達可能な施設が1つもなくなり、 「必ず1つの施設に割り当てる」を満たせなくなることがあります。flplab のこのバージョンでは、 これを何らかのペナルティで救済することはせず、解が存在しない（実行不可能） という結果をそのまま表示し、「制約を緩めてください」と案内するだけに留めています。 未対応の需要を許容する仕組みは複雑さが増すため、将来の拡張候補として意図的に見送っています。

カバーだけを扱う2モデル（Set Covering・MCLP）

この2モデルは「どの施設が担当するか」を決めません。決めるのは施設の開設 （y_j）と、カバーされているかどうか （MCLPの z_i）だけです。割当を決める変数を持たないため、 同じ規模の問題でも割当系より変数の数が少なく、計算が軽くなります。設定画面側では、目的関数が カバー系のときは容量・予算・需要分割の項目を非表示にします（割当を前提とする設定のため、 割当変数を持たないこの2モデルには意味を持たないため）。

6モデルは「初期値を一括設定するボタン」

6モデルの選択は、選んだ瞬間に目的関数と制約をその型の標準的な組合せへ一括で上書きする 操作です。排他的な「モード」ではないため、選択後も個々の制約チェックボックスで自由に調整でき、 その場合は表示が「（カスタム）」に切り替わります。これは仕様です。

8. 計算エンジン（ソルバ）の動かし方

厳密解を求める計算エンジン（HiGHS）は、ブラウザの中で直接動くようにコンパイルされたものを 使っています。重い計算で画面が固まらないよう、ブラウザのバックグラウンド実行の仕組み （Web Worker）の中でこのエンジンを動かします。

エンジンは起動したまま使い続ける

6章で触れたとおり、このエンジンは1度起動したら使い続けます。 最適化実行 を押すたびに、その時点のシナリオを数式に変換して エンジンに渡し、計算が終わると結果を受け取って画面に反映します。制限時間を超えても応答が なければ、安全装置がエンジンを強制終了して再起動し、「制限時間を超えたため打ち切りました」と 案内します。

感度分析は同じエンジンを使い回すバッチ処理

「施設数を変えたら総コストがどう変わるか」を調べる感度分析は、新しい仕組みを追加するのではなく、 施設数を1件から指定した最大数まで1件ずつ増やしたシナリオを順番に同じエンジンへ渡し、 1件計算が終わるたびにグラフへ1点ずつ追記する、という繰り返し処理です。エンジンを使い回すため、 エンジンの再読み込みは発生しません。途中で中断したいときは、次の計算に進まないよう内部の カウンタを進めるだけで止められます（エンジン自体は終了させません）。

9. 結果を検証する仕組み — 最も注意が必要な場所要注意

計算エンジンが返す生の結果（内部的な変数の値の一覧）から、「どの施設が開設されたか」 「どの需要地点がどの施設に割り当てられたか」を復元し、コスト・距離・カバー率・稼働率を 独立に再計算する処理があります。この部分が最も注意が必要な場所です。

「危険」でありながら「見つけやすくもできる」理由

flplab では計算エンジンが厳密解を返すため、「エンジンが最適化した目的関数の値」 と「結果から独立に再計算した値」は、数理モデルへの変換が正しければ必ず一致します （わずかな浮動小数点の誤差の範囲内で）。この一致を毎回確認することで、 「数理モデルへの変換」と「結果の復元・再計算」の両方の正しさを同時に守れます。

3段構えでの確認

1. 手計算した小さな例の期待値 — 需要2件・施設候補2件程度の単純な例を手で解き、 期待される開設施設・割当・コストをあらかじめ用意しておく
2. 計算エンジンの目的関数値と、独立に再計算した値の一致 — 実際に計算エンジンを 動かして確認する
3. 総当たりとの突き合わせ — 施設候補が5個以下の小さな例では、開設パターンを しらみつぶしに全部試し、制約を満たす中でコストが最小になる組合せを求め、計算エンジンの結果と 一致することを確認する

数理モデルへの変換や結果の復元処理に手を入れるときは、必ずこの一致を確認する自動テストが 通ることを運用の前提にしています。

10. ハマりやすい注意点

「必ず0か1に固定する」指示が黒く消えることがある

計算エンジンに渡す条件式を組み立てる際、「0または1しか取らない」という種類の変数は、 通常は上限・下限を明示せず「0/1しか取らない」という前提だけで扱われます。ところが、 強制開設・強制閉鎖のように、この種の変数を「必ず1つの値に固定したい」という指示を出したい場面 では、その前提のままだと固定の指示が反映されず、エンジンは通常どおり自由に0か1を選んでしまいます。

flplab では、値を固定したい変数だけ扱いを変えて、固定したい値が確実にエンジンへ伝わるようにする ことでこれを避けています。同様に「0/1の変数を特定の値に固定したい」という場面を新たに作るときは、 この落とし穴を思い出す必要があります。

11. 画面設計と状態管理の考え方

フォーカスガードの罠

画面の再構築は、パネル内で編集中の入力欄があるとスキップされる仕組みになっています （編集中の値が再描画で消えてしまう事故を防ぐため）。ただし 最適化実行/中断 はボタン です。ボタンをクリックすると、クリックしたボタン自身にフォーカスが移るため、「パネル内に フォーカスがあるかどうか」だけで判定すると、クリックした瞬間からパネル全体 （ボタンが押せない状態の見た目を含む）が固まって見える事故になります。このため、 再構築をスキップする判定は「入力欄・選択欄・テキストエリアにフォーカスがあるかどうか」に 絞ってあります。新しい編集用の部品を追加するときは、この判定に注意が必要です。

画面が保持している状態

保存・比較・感度分析

• シナリオはブラウザ内に自動保存され、名前を付けて複数保存することもできる
• ファイルとしての書き出し・読み込みでPC間の受け渡しが可能
• 案A/B比較ビューは、2つの計算結果を保存して差分と2枚の地図を並べる
• 感度分析は施設数×コストの折れ線グラフを1点ずつ描き、途中で中断できる

12. テストの守り方

画面に触れない計算ロジックはすべて自動テストで確認し、画面表示そのものは自動テストの対象にしません （手動確認、または画面操作を自動化するツールでの確認に委ねます）。テストが確認する内容は次の カテゴリに分かれます。

• 距離計算（直線距離×迂回係数）の値が正しいか
• 需要地点×施設候補の距離の対応関係が正しいか
• 計算エンジン向けの内部的な変数の名前と、結果から元の需要地点・施設への逆引きが正しく対応するか
• UFLP/CFLP/p-Median/p-Centerそれぞれで、期待した形の制約が組み立てられ、強制開設・強制閉鎖が 正しく反映されるか
• Set Covering/MCLPで、期待した形の制約が組み立てられるか
• ★最重要：計算エンジンが返す目的関数の値と、結果から独立に再計算した値が 一致するか（手計算した例・総当たりとの一致も含む、9章）
• シナリオの検証（負の需要、IDの重複、強制設定の整合性など）が正しく働くか
• 用意されたプリセットシナリオが、いずれも矛盾のない内容になっているか

13. 実装中に見つかった問題と教訓

設計時点では想定していなかったものの、実際にブラウザで動かして初めて見つかった問題が いくつかありました。いずれも修正済みで、再発を防ぐ確認も追加しています。

1. 連続クリックによる計算要求の取りこぼし — ボタンを押せない状態にする仕組みは 通常の操作では二重クリックを防ぐが、想定外の連続クリックがあると、後から出した計算要求が 先に出した要求を上書きしてしまい、先発の要求がいつまでも応答を受け取れなくなることがあった。 「いま計算中かどうか」を画面の状態としてきちんと管理することで防いだ。
2. 計算中のパラメータ変更による結果の食い違い — 計算が終わるまでの間にパネルで パラメータを変更すると、計算が完了した時点で「新しい設定」と「古い計算結果」を組み合わせてしまい、 意味を持たない結果を作ってしまうことがあった。計算を開始した時点の設定を保存しておき、それを 使って結果を組み立てることで防いだ（計算完了時に設定が変わっていれば、結果は古いものとして 印を付ける）。
3. フォーカスガードがボタン自身を固まらせる — 11章で説明した 問題。判定の対象を絞ることで解決した。
4. 「必ず0か1に固定する」指示が黒く消える — 10章で説明した 問題。値を固定したい変数だけ扱いを変えることで解決した。

これらのうち②③④は、自動テストだけでは検出できない種類の不整合でした。実際に画面を操作して 初めて見つかったため、以後は計算エンジンを実際に動かして結果まで確認する統合的なテストも 追加し、再発を防いでいます。

14. 姉妹ツールとの関係

flplab は、配送計画を扱う姉妹アプリの画面設計・状態管理・地図描画の流儀を引き継ぎつつ、 計算エンジンだけは、別の汎用最適化アプリの資産（ブラウザで動く厳密解ソルバ）を移植して 厳密解に置き換えた構成です。