著者：株式会社Gurobi Japan エキスパートチーム 杉田 宜之
EV充電ステーションはどこに置くべきでしょうか。コンビニは、駅ナカ店舗は、ロードサイドの看板は――。これらに共通するのは、顧客が「そこに住んでいるから」来るだけではなく、「そこを通りかかるから」立ち寄るという点です。ところが、施設配置の教科書で最初に習う定式化の多くは、需要を地図上の「点」として扱います。この前提のずれを正面から扱うのが、本稿で紹介するフロー捕捉型施設配置問題（Flow-Capturing Location Model, FCLM）です。
古典的な施設配置問題との違いを、代表的な定式化を並べながら見ていきます。
1. 古典的施設配置問題 ― 需要は「点」にある
まず出発点として、需要が点で与えられる代表的な2つのモデルを確認します。
1.1 p-メディアン問題
需要地点の集合を I、施設候補地点の集合を J とし、地点 i の需要量を a_i、地点 i から候補地 j までの距離を d_ij とします。開設する施設数を p に固定したとき、需要加重距離の総和を最小化する配置を求めるのが p-メディアン問題です。
ここで x_j は候補地 j に施設を置くか否か、y_ij は需要地点 i が施設 j に割り当てられるか否かを表します。倉庫や配送センターのように「施設側から需要へ届けに行く」タイプのサービスに適したモデルです。
1.2 最大被覆問題（MCLP）
一方、救急拠点や店舗のように「一定距離（時間）以内に施設があれば需要をカバーできる」と考える場合は、Church and ReVelle (1974) の最大被覆問題（Maximal Covering Location Problem）が代表的です。需要地点 i をカバーできる候補地の集合を N_i = { j ∈ J : d_ij ≤ D }（D はカバー半径）、地点 i の需要量を a_iとすると、
z_i は需要地点 i がカバーされるか否かです。限られた施設数 p でカバーできる需要量を最大化します。
p-median問題、最大被覆問題のどちらのモデルでも、需要は「地点 i に a_i だけ存在する」と表現されています。人口メッシュや町丁目の重心に需要を集約する、いわゆる点需要（point demand）の考え方です。
2. 需要が「流れ」であるとき
しかし冒頭の例のように、多くのサービスの需要は、居住地だけではなく移動そのものから生まれます。通勤経路の途中で給油する、帰宅途中にコンビニに寄る、長距離移動の途中でEVを充電する――。この種の需要を点に集約してしまうと、次のような不都合が起きます。
第一に、需要の発生場所を偽ってしまいます。自宅の最寄りにガソリンスタンドがなくても、通勤経路上にあれば困らない人は多いはずですが、点需要モデルでは「自宅がカバーされていない」と評価されてしまいます。第二に、二重計上の危険があります。同じドライバーの流れを、出発地側と目的地側の両方の需要として数えれば、実際より過大な需要を「カバーした」ことになります。
そこで Hodgson (1990) および Berman, Larson and Fouska (1992) は、需要をネットワーク上の交通流（フロー）として扱うモデルを提案しました。これがフロー捕捉型施設配置問題です（類似の問題に Flow Interception Problem もあります）。
3. フロー捕捉型施設配置問題（FCLM）の定式化
道路ネットワーク上の起点・終点（OD）ペアごとに、利用される経路と交通量が与えられているとします。
Q: 経路（ODペア）の集合
f_q: 経路 q を流れる交通量（例: 台/日）
N_q: 経路 q 上にある施設候補地点の集合
p: 開設する施設数
意思決定変数は、候補地 k に施設を置くか否かの x_k と、経路 q の流れが捕捉されるか否かの y_q です。
経路 q 上のどこか1箇所にでも施設があれば、その流れは「捕捉された」とみなされ、目的関数値に f_q が加算されます。制約が y_q ≤ Σ_k ∈ N_q x_k という不等式になっている点が重要で、同じ経路上に施設が2箇所以上あっても y_qの値は1、つまり同じ流れを二重に数えない構造が自然に入っています。
定式化を見比べると気づくと思いますが、FCLMのモデル は MCLP と数学的にはほぼ同じ形です。違いは被覆集合の定義だけで、MCLP の「需要点から半径 D 以内の候補地」N_i が、FCLM では「経路 q が通過する候補地」N_q に置き換わっています。しかしこの置き換えが意味するものは大きく、需要の単位が「地点」から「経路」へ、必要なデータが「人口分布」から「経路の交通量と経路上の施設」へと変わります。
なお、x が定まれば各 y_q の値は目的関数によって0か1に決まるため、y_q をバイナリ変数から 0 ≤ y_q ≤ 1 の連続変数に緩和することができます。
点需要モデルとの対比
古典的モデル（p-メディアン / MCLP） | フロー捕捉型モデル（FCLM） | |
|---|---|---|
需要の単位 | 地点（居住地・需要点） | 経路（ODペアの交通流） |
「カバー」の定義 | 需要点から一定距離以内に施設がある | 経路上のどこかに施設がある |
典型的な応用 | 倉庫、配送センター、救急拠点 | 給油所、EV充電、コンビニ、屋外広告、検問・検査所 |
主な入力データ | 需要点の位置と需要量、距離行列 | OD交通量、各ODの利用経路、経路上の候補地 |
注意すべき罠 | 需要集約による誤差 | 経路データの精度、流れの二重計上（定式化で回避） |
4. 代表的な拡張
FCLM は多くの拡張の土台になっています。実務でよく現れるものをいくつか挙げます。
フロー・リフューエリング問題（FRLM）: EVや水素自動車のように航続距離に制約がある場合、「経路上に1箇所あればよい」では済まず、航続距離ごとに充電・充填できる施設の組合せが必要になります。Kuby and Lim (2005) が提案した FRLM は、各経路を走行可能にする施設の組合せを使う定式化で、その後 Capar らによる、経路を部分経路に分解して各部分経路が到達可能であることを制約とするコンパクトな定式化（arc-cover 型）など、求解性を高める定式化が発展しました。EV充電インフラ計画の分野では現在も標準的な枠組みです。
経路逸脱（deviation-flow）モデル: ドライバーは施設のために最短経路から多少の回り道を受け入れることがあります。許容逸脱量の範囲で代替経路集合を生成し、N_q を拡張する形でモデル化されます。
時間軸を考慮したモデル: 本稿では「需要を点で見るか流れで見るか」という議論を行いましたが、古典的モデルにはもう一つ、需要を静的に扱うという前提があります。実際には交通流は時間帯によって大きく変動し、施設側にはサービス提供時間帯が存在します。施設の配置とサービス開始時刻を同時に最適化するモデル（Tanaka & Furuta, 2011）や、より長期の時間軸で人口変動を考慮しながら将来の拠点配置戦略を検討する研究（嚴・長谷川, 2023）など、時間軸を導入した施設配置問題の一般化も活発に研究されており、「空間（フロー）×時間」は施設配置研究の現在のフロンティアの一つです。
そのほか、施設の処理能力に上限を置く容量付きモデル、競合他社の存在を考える競争的配置、交通量の不確実性を扱う確率モデルなど、点需要の施設配置で培われた拡張の多くがフロー需要の世界に持ち込まれています。
5. Gurobi で解いてみる
FCLM は整数計画問題としてそのまま Gurobi に渡せます。経路を「通過する候補地点の列」として持っておけば、プログラムはほぼ定式化のとおりに書けます。
この規模なら一瞬で解けますが、実務では経路数が数十万、候補地点が数千というスケールになります。それでも FCLM の被覆制約は疎で構造が良いため、現代の MIP ソルバーにとっては十分手の届く範囲です。むしろ難所はモデルの外側――経路の交通量の推定や経路情報の決定――にあることが多く、ここが点需要モデルとの実務上の最大の違いと言えるでしょう。
6. おわりに ― 定式化の先にあるGISとの連携
施設配置問題は「需要をどう表現するか」で姿を大きく変えます。需要が移動から生まれるサービスであれば、点需要モデルを当てはめる前に、フロー捕捉型の枠組みを検討する価値があります。定式化自体は MCLP とほぼ同じですが、その背後にある需要観の転換こそが、このモデルの本質です。
そして第5節で触れたとおり、実務での難所はモデルの外側にあります。FCLM の入力――OD交通量、経路、経路上の候補地点――は本質的に地理空間データであり、道路網や人流のオープンデータの取得、座標系の変換、経路と候補地点の対応付けといった前処理は、GIS の空間演算そのものです。また、最適化が返すのは 0/1 の変数値にすぎず、「どの流れが捕捉され、どの地域が取り残されるのか」を地図上で可視化して初めて、結果は意思決定に使える情報になります。数理最適化と GIS は、施設配置の実務を回すための両輪です。実際、路線網形状を考慮してバスとデマンド型交通の併用効果を分析した研究（長谷川・鈴木, 2019）のように、地理情報と最適化を組み合わせて地域公共交通や施設の計画に取り組む研究も活発に進んでいます。
この「定式化から GIS まで」を一日で、実際に手を動かしながら学べる機会があります。日本オペレーションズ・リサーチ学会 2026年度第2回ORセミナー「Pythonによる地理情報分析・数理最適化 ―オープンデータの取得から施設配置のモデル化・可視化まで―」（2026年10月10日（土）10:00–17:30・東京大学本郷キャンパス 小島ホール）です。
田中健一氏（慶應義塾大学）のセッションでは、数理モデルによる都市・地域の課題解決の考え方に続き、まさに本稿で紹介したフロー捕捉型配置問題を中心に、基本モデルの解説・定式化の演習・数理最適化ソルバーによる例題の求解と分析までを体験できます。長谷川大輔氏（東京大学）のセッションでは、座標系・空間演算・オープンデータといった地理情報の基礎から、避難距離の短縮効果を題材に施設配置問題の Python 実装と地図上での可視化までを扱います。さらに協賛セッションでは、Gurobi Japan による Burrito Optimization Game 等を使った数理最適化の体験、ESRI ジャパンによる最適化結果を GIS で可視化・分析し意思決定につなげる方法の紹介が予定されており、本稿の後半で述べた「数理最適化×GIS」の実践をまとめて学べる構成です。
定員は60名、申込締切は2026年9月30日（水）です（定員になり次第締切）。詳細・お申し込みは学会の開催案内ページをご覧ください。筆者もコーディネータとして参加します。各セッションのさらに詳しい中身は――当日のお楽しみに！ 本稿を読んで「自分の問題に適用してみたい」と感じた方のご参加を、会場でお待ちしています。
講師のご紹介
田中健一氏（慶應義塾大学理工学部管理工学科 教授）は、まさに本稿で紹介したフロー捕捉型施設配置問題の第一線の研究者です。鉄道旅客流に特化したフロー捕捉モデルを提案し首都圏鉄道網（約1,500駅・約10万フロー）で大規模な配置分析を行った Railway flow interception location model（Operations Research Perspectives, 2019, オープンアクセス） をはじめ、混雑や競合を考慮したフロー捕捉型配置問題など、本稿の枠組みの発展研究を数多く発表されています（研究室ページ）。日本語で読める適用研究としては、中京都市圏の通勤・通学フローを対象に立寄り型施設の最適な配置駅を分析した「中京都市圏における通勤・通学フローに着目した最適な立寄り型施設の配置駅」（都市計画論文集, 57(3), 2022, オープンアクセス）があり、本稿で紹介したフロー需要の考え方が実際の都市圏データでどう機能するかを具体的に知ることができます。施設配置問題全般を日本語でさらに学びたい方には、田中氏ご自身による解説記事「数理最適化入門（4）：施設配置の数理モデル」（応用数理, 23巻4号, 2013, フリーアクセス）にまとめられており、本稿の次の一歩としておすすめです。
長谷川大輔氏（東京大学不動産イノベーション研究センター 特任講師）は、地理情報科学・都市解析・地域公共交通計画がご専門です。代表的な研究に、日本都市計画学会 2024年 年間優秀論文賞を受賞した「大規模人流データを活用した駅徒歩圏の広がりと分布の計測」（都市計画論文集, 59(3), 2024, フリーアクセス）があります。近年は、高解像度の人流データによって個々の移動軌跡を捉えられるようになったことで、本稿で紹介したフロー捕捉型のモデルをキッチンカー・ベンチ・暑熱避難施設といったヒューマンスケールの施設配置に応用する展開についても発信されており（講演紹介記事・Google Scholar）、本稿の定式化と実データ・GIS の世界の間の橋渡しに関する内容を聞くことができます。
参考文献
Hakimi, S. L. (1964). Optimum locations of switching centers and the absolute centers and medians of a graph. Operations Research, 12(3), 450–459.
Church, R., & ReVelle, C. (1974). The maximal covering location problem. Papers of the Regional Science Association, 32, 101–118.
Hodgson, M. J. (1990). A flow-capturing location-allocation model. Geographical Analysis, 22(3), 270–279.
Berman, O., Larson, R. C., & Fouska, N. (1992). Optimal location of discretionary service facilities. Transportation Science, 26(3), 201–211.
Kuby, M., & Lim, S. (2005). The flow-refueling location problem for alternative-fuel vehicles. Socio-Economic Planning Sciences, 39(2), 125–145.
Capar, I., Kuby, M., Leon, V. J., & Tsai, Y.-J. (2013). An arc cover–path-cover formulation and strategic analysis of alternative-fuel station locations. European Journal of Operational Research, 227(1), 142–151.
田中健一 (2013). 数理最適化入門（4）：施設配置の数理モデル. 応用数理, 23(4). https://www.jstage.jst.go.jp/article/bjsiam/23/4/23_KJ00008992858/_pdf/-char/ja
Tanaka, K., & Furuta, T. (2011). Maximum flow-covering location and service start time problem and its application to Tokyo metropolitan railway network. Journal of the Operations Research Society of Japan, 54(4), 237–258. https://www.jstage.jst.go.jp/article/jorsj/54/4/54_KJ00007729008/_article
Tanaka, K., Furuta, T., & Toriumi, S. (2019). Railway flow interception location model: Model development and case study of Tokyo metropolitan railway network. Operations Research Perspectives, 6. https://www.sciencedirect.com/science/article/pii/S2214716018301714
田中健一 (2022). 中京都市圏における通勤・通学フローに着目した最適な立寄り型施設の配置駅. 都市計画論文集, 57(3), 1010–1017. https://www.jstage.jst.go.jp/article/journalcpij/57/3/57_1010/_article/-char/ja/
長谷川大輔・鈴木勉 (2019). 路線網形状を考慮したバス・デマンド型交通併用効果の分析. GIS-理論と応用, 27(1), 1–11. https://www.jstage.jst.go.jp/article/thagis/27/1/27_1/_article/-char/ja/
嚴先鏞・長谷川大輔 (2023). 人口変動を考慮した拠点計画手法に基づいた将来の拠点配置戦略の検討. 都市計画論文集, 58(3), 585–591. https://www.jstage.jst.go.jp/article/journalcpij/58/3/58_585/_article/-char/ja/
長谷川大輔・嚴先鏞 (2024). 大規模人流データを活用した駅徒歩圏の広がりと分布の計測. 都市計画論文集, 59(3), 1217–1223. https://www.jstage.jst.go.jp/article/journalcpij/59/3/59_11017/_article/-char/ja/
