20261002_Jagu'e'r_街づくり分科会_地形データ×数理最適化

© 2026 NTT West, Inc. All Rights Reserved. 地形データ×数理最適化 Jagu’e’r 街づくり分科会 #06 2026/10/2 高須賀 将秀

© 2026 NTT West, Inc. All Rights Reserved. 2 /79 自己紹介 たかすか まさひで 高須賀 将秀 博士（情報学）（2023/3） 研究分野：組合せ最適化，数理最適化，オペレーションズ・リサーチ（OR），グラフ理論 高須賀将秀のホームページ 所属：NTT西日本 デジタル改革推進部（2021/8～）， 法政大学 デザイン工学部 兼任講師（2024/4～），個人事業（Udemy講師等）（2024/6～） 業務：データドリブン経営を牽引する立場 ・データ活用基盤のシステム開発 ・データ分析手法の研究 ・データ分析活用事例の提案 ・デジタル人材育成 New! 資格：クラウド資格（AWS全冠，Azure/AppliedSkills全冠，GCP全冠， Snowflake全冠）， 受賞：AWS Top Engineers（’26） ，AWS Community Builders（’26），AWS All Certifications Engineers（’24/’25/’26）， Microsoft Top Partner Engineer Award（’24, ‘26），Microsoft Innovative Educator Experts 2025-2026， Google Cloud Partner Top Engineer（’26），Google Cloud Partner All Certification Holders（‘25）， Jagu‘e’r Award 優秀賞（’25），Snowflake Squad（’24, ‘25）， Microsoft Certified Trainer（MCT）

© 2026 NTT West, Inc. All Rights Reserved. 本日の流れ • 数理最適化とは？ • 万博を例に • LLMとの違い，使い分け • Google Map APIについて • Google Map×数理最適化 • 旅行プランアプリ • 自然文から1日旅行プランを作る ── 巡回順を決める（TSP） • インフラ保全業務アプリ • インフラ保全の工事立会者手配 ── 人と工事を割り当てる • 避難所配置計画アプリ • 避難所配置の最適化 ── 施設をどこに置くか（MCLP） 3 /79

© 2026 NTT West, Inc. All Rights Reserved. 本日の流れ • 数理最適化とは？ • 万博を例に • LLMとの違い，使い分け • Google Map APIについて • Google Map×数理最適化 • 旅行プランアプリ • 自然文から1日旅行プランを作る ── 巡回順を決める（TSP） • インフラ保全業務アプリ • インフラ保全の工事立会者手配 ── 人と工事を割り当てる • 避難所配置計画アプリ • 避難所配置の最適化 ── 施設をどこに置くか（MCLP） 4 /79

© 2026 NTT West, Inc. All Rights Reserved. 5 /79 数理最適化とは？ 数理最適化の詳細はこちら↑ ↑ • 数理最適化とは，与えられた制約条件の下で，目的関数を最大化ま たは最小化する解を求める数学的手法である． • 目的関数: 最大化/最小化したい対象（コスト，時間，利益など） • 制約条件: 守るべきルールや条件 • 決定変数: 最適化によって決定する変数 𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑒 𝑓 𝑥 = −𝑥 + 6 1 14 𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜 𝑔 𝑥 = 𝑥 + ≤ 0 5 5 𝑥∈𝑅 8 1 14 𝑔 𝑥 = 𝑥+ 5 5 10 3 10 𝑥 = 3 のとき 𝑓 𝑥 は最大値 3 𝑓 𝑥 = −𝑥 + 6 8 𝑥

© 2026 NTT West, Inc. All Rights Reserved. 数理最適化について知ってますか？ • 万博で以下訪問したい場所があったとき，あなたはどのような順番で訪問 しますか？ 6 /79

© 2026 NTT West, Inc. All Rights Reserved. 万博の訪問ルートの最適解 • 最適解は以下ルートで，総移動距離は1.34km 7 /79

© 2026 NTT West, Inc. All Rights Reserved. 8 /79 万博の訪問ルートの実行可能解の一例 全部で 362,880 通り

© 2026 NTT West, Inc. All Rights Reserved. 9 /79 訪問したい場所を増やした場合 訪問場所52ヵ所の総数 訪問場所40ヵ所の総数 訪問場所10ヵ所の総数 https://homepage45.net/unit/sub.htm

• https://homepage45.net/unit/sub.htm

© 2026 NTT West, Inc. All Rights Reserved. LLM（gpt4o）を用いた訪問ルートの提示 10 /79

© 2026 NTT West, Inc. All Rights Reserved. 11 /79 訪問したい場所を増やした場合 • 訪問場所を増やしても探索方法を工夫すれば短時間で最適解が得られる LLM版

© 2026 NTT West, Inc. All Rights Reserved. 12 /79 万博訪問ルート最適化サービスについて 2 1 3 使い方 ①地図上に訪問したい場所をクリック ②探索方法を選択（Gurobiがお勧め） ③最適化ルートを探索ボタンをクリック 万博訪問ルート最適化サービス

• https://st-app-expo-504242909255.asia-northeast1.run.app/

© 2026 NTT West, Inc. All Rights Reserved. 13 /79 BI：Business Intelligence ML：Machine Learning AI：Artificial Intelligence MO：Mathmatical Optimization BI・ML・AIとMOとの違い BI・ML・AI MO データから ・可視化 ・学習、予測 ・推論 データドリブン 条件から ・データを生成し、探索 ルールドリブン 生産されたデータを厳密に探索 ここでクラウドが活躍 データ量 データ量 データからそれらしい解を生成 入力 出力 プロセス 生成 入力 出力 プロセス

© 2026 NTT West, Inc. All Rights Reserved. 14 /79 クラウドと数理最適化の相性 • クラウドと数理最適化は互いの強み・弱みを補完しあう関係にあり • 現在のBI・ML・AIの次世代技術として，データの生成のよるさらなるデータ量増とそのデータから得 られるインサイトの厳密性の保証を行える数理最適化 クラウドの特徴 数理最適化の特徴 強み ・無制限のデータ保存領域 ・コンピューティングの拡張性 弱み ・計算過程の解の保持が困難 ・一部の解のみ保持 ・メモリ使用量が大きくなる場合あり ・数理モデルやアルゴリズムによっては変化 弱み ・データを起点にした価値創造 ・データがあることが前提 ・データの信頼性が求められる ・厳密性の保証はできない 強み ・データ有無に関係なく価値創出 ・推論ではなく探索よる厳密性の保証

© 2026 NTT West, Inc. All Rights Reserved. 15 /79 Google Maps API の全体像 Google Maps Platform のAPIは「地図（表示）」「経路」「場所」「環境」の4カテゴリに整理できる（従量課金・APIキーで利用） Maps ── 地図（表示） Routes ── 経路 Places ── 場所 Environment ── 環境 ★ Maps JavaScript API ★ Routes API ★ Places API (New) Air Quality API Web地図の描画・操作【全事例】 経路・渋滞・Route Matrix【例①】 施設検索・評価・口コミ【例①③】 大気質データ Maps SDK（Android / iOS） ★ Distance Matrix API ★ Geocoding API Solar API モバイルアプリ向け地図 多地点間の時間・距離【例②③案】 住所 ⇔ 緯度経度の変換【例②案】 日照・太陽光ポテンシャル Static Maps・Maps Embed Directions API Address Validation API Pollen API 画像・埋め込みの簡易表示 経路案内（従来版） 住所の検証・正規化 花粉情報 Street View・Aerial View Roads API Time Zone API Weather API 実写パノラマ・航空映像 走行点列を道路へスナップ 地点のタイムゾーン 気象データ Map Tiles API Navigation SDK Place Autocomplete 2D・実写3Dタイルの配信 ターンバイターン案内 施設名・住所の入力補完 ★ Elevation API Route Optimization API 地点の標高を取得【例①】 配車・巡回のマネージド最適化 防災・環境など、街づくり分析への応用が広 がる領域 ★＝本発表で利用・言及するAPI．地図の「表示」だけでなく，現実世界を「数値データとして取得」するAPI群が最適化の材料になる

© 2026 NTT West, Inc. All Rights Reserved. 本日の流れ • 数理最適化とは？ • 万博を例に • LLMとの違い，使い分け • Google Map APIについて • Google Map×数理最適化 • 旅行プランアプリ • 自然文から1日旅行プランを作る ── 巡回順を決める（TSP） • インフラ保全業務アプリ • インフラ保全の工事立会者手配 ── 人と工事を割り当てる • 避難所配置計画アプリ • 避難所配置の最適化 ── 施設をどこに置くか（MCLP） 16 /79

© 2026 NTT West, Inc. All Rights Reserved. 17 /79 旅行プランアプリ Michi アプリ https://michi-trip-plannerhdjsogf5hq-an.a.run.app/ ソース https://github.com/mshdtksk /google-map-tsp/tree/main

• https://michi-trip-planner-hdjsogf5hq-an.a.run.app/
• https://github.com/mshdtksk/google-map-tsp/tree/main

© 2026 NTT West, Inc. All Rights Reserved. 18 /79 アーキテクチャ ユーザーの自然文 Gemini API Places API (New) 候補の事前絞り込み 日付・時間・出発地点 エリア・テーマ・検索語・移動手段 候補地点（実在施設） 評価×口コミ数スコア Gemini＝意図の変換 Routes API Elevation API 待ち時間推定 移動時間・距離・渋滞遅延の行列 標高 → 上り高低差の行列 カテゴリ×口コミ数（独自推定） Gurobi ── Selective TSP Maps JavaScript API 訪問地点の選択＋訪問順の最適化 地図・マーカー・順路・時刻表 Google Maps＝現実の数値化 Gurobi＝最適化 Streamlit＝入力・比較・表示

© 2026 NTT West, Inc. All Rights Reserved. 19 /79 Places API (New)：「どこへ行くか」の候補集合を作る 使用機能：Text Search 候補の事前スコア（絞り込み用） Gemini が生成した検索語から実在施設を検索し，以下を取得する scoreⱼ ＝ ratingⱼ × log₁₀( reviewCountⱼ ＋ 10 ) Place ID 施設名 住所 緯度・経度 評価 口コミ数 カテゴリ Maps URI システム内での用途 評価が高く，口コミが多い施設を優先して候補に残す 注意 候補地点の生成／Place ID による重複排除 評価×口コミ数による候補の事前順位付け このスコアは最終的な訪問順ではない．最適化へ投入する候補を絞る ための前処理である．順番を決めるのはあくまで数理最適化． 待ち時間推定／結果画面から施設ページへリンク https://developers.google.com/maps/documentation/places/web-service/overview?hl=ja

• https://developers.google.com/maps/documentation/places/web-service/overview?hl=ja

© 2026 NTT West, Inc. All Rights Reserved. 20 /79 Routes API：全地点間の移動コストを行列化する computeRouteMatrix 渋滞の反映（車移動） 予測移動時間・通常時移動時間・距離・経路の有無 travelMode = DRIVE ／ routingPreference = TRAFFIC_AWARE 候補 n 地点 → 必要な要素数はほぼ n² 旅行日時を departureTime に指定 → その時刻の交通予測 この行列が目的関数の辺コストと時間制約になる 渋滞遅延 cᵢⱼ ＝ max( 0, tᵢⱼ(交通あり) − tᵢⱼ(通常時) ) 公共交通（TRANSIT）の制限への対応 到達不能経路の扱い Route Matrix は 1リクエスト 100要素まで ROUTE_NOT_FOUND を「0分」として扱わない 16地点 → 256要素 なので出発地点側を分割 高いコストのまま保持し、選ばれないようにする 6×16 ＋ 6×16 ＋ 4×16 ＝ 256 → 応答を元の行列へ統合 公共交通で取れない区間は徒歩経路で補完 https://developers.google.com/maps/documentation/routes?hl=ja

• https://developers.google.com/maps/documentation/routes?hl=ja

© 2026 NTT West, Inc. All Rights Reserved. 21 /79 Elevation API：「坂の負担」をコストに変える 上り標高差（片方向のみ） h⁺ᵢⱼ ＝ max( 0, elevationⱼ − elevationᵢ ) 地点 j 上り 重み：上り100mを10分相当として評価 追加コスト ＝ 0.1 × h⁺ᵢⱼ （標高差50mなら5分相当） 地点 i i → j は上り（ペナルティあり）／ j → i は下り（ペナルティなし）→ コスト行列は 非対称になる α＝0.1 は調整可能な重みパラメーター 単に距離が短い経路ではなく「坂の負担が小さい」経路を選びやすくする 取得方法：各候補地点の緯度・経度から標高を取得（現状は地点間の標高差．経路上の細かなアップダウンの累積は今後の改善） https://developers.google.com/maps/documentation/elevation/overview?hl=ja

• https://developers.google.com/maps/documentation/elevation/overview?hl=ja

© 2026 NTT West, Inc. All Rights Reserved. 22 /79 Maps JavaScript API：最適化の結果の可視化 Places API との連携 表示内容 各訪問地点の番号付きマーカー 到着予定時刻の表示 旅程内の施設名を googleMapsUri へリンク → ワンクリックで施設ペ ージを確認できる 訪問順を結ぶポリライン 現在の制約と今後の改善 全地点が収まる自動ズーム 数理最適化案とGemini案に独立した地図 地図上の線は訪問順を示す直線（道路形状ではない）．今後は Routes API のルートポリラインで実道路に沿って描画する 「なぜこの順番か」を地図で見せられることが、最適化結果への納得感につながる 移動時間の計算自体は Routes API の道路ネットワークに基づいている（表示だけが概略直線） https://developers.google.com/maps/documentation/javascript/overview?hl=ja

• https://developers.google.com/maps/documentation/javascript/overview?hl=ja

© 2026 NTT West, Inc. All Rights Reserved. 23 /79 Google Maps API の役割まとめ API 入力 出力 最適化での用途 Places API (New) 検索語 実在施設・評価・カテゴリ・座標 候補地点集合を作る Routes API 地点・日時・移動手段 移動時間・距離・渋滞 辺コストと時間制約 Elevation API 緯度・経度 標高 上り高低差ペナルティ Maps JavaScript API 地点と訪問順 地図・マーカー・線 最適化結果の可視化 Google Maps Platform は地図表示ツールではなく，最適化モデルのパラメーターを供給するデータ基盤

© 2026 NTT West, Inc. All Rights Reserved. 24 /79 数理最適化の位置づけ：選択型TSP（Selective TSP） 通常のTSP すべての都市を1回ずつ訪問して出発地へ戻る，総移動コスト最小 の巡回路を求める 本システムでの拡張 候補15地点すべてが時間内に入るとは限らない 15地点から順に試し、時間内に入る最大の地点数を選ぶ ＝ 万博の例と同じ構造 最低でも10地点は訪問する 決定変数 xᵢⱼ ∈ {0,1}：地点 i から j へ移動するか 移動時間だけでなく渋滞・待ち時間・高低差も評価 出発地点と帰着地点は同じ yᵢ ∈ {0,1}：地点 i を訪問するか uᵢ：訪問順序の補助変数（MTZ用・連続） → 訪問地点の「選択」を含む 選択型TSP として、混合整数線形計画 問題（MILP）で定式化

© 2026 NTT West, Inc. All Rights Reserved. 25 /79 目的関数：4つの現実コストの加重和を最小化 min Σᵢ≠ⱼ ( tᵢⱼ ＋ λ·cᵢⱼ ＋ wⱼ ＋ α·h⁺ᵢⱼ ) xᵢⱼ tᵢⱼ wⱼ 予測移動時間 λ·cᵢⱼ λ＝1 α＝0.1 渋滞遅延 実際に必要と予測される移動時間（交通状況を反映） 渋滞依存度が高い辺をさらに避ける追加ペナルティ 推定待ち時間 上り高低差 混雑しやすい施設を避ける（カテゴリ×口コミ数で推定 ） α·h⁺ᵢⱼ 急な上りを避ける負担ペナルティ（100m＝10分相当） tᵢⱼ 自体が交通予測込み．さらに cᵢⱼ を加え，同じ所要時間でも渋滞依存度が高い経路をより強く避ける

© 2026 NTT West, Inc. All Rights Reserved. 26 /79 制約式：「実行可能な旅程」であることを保証する 出発・帰着（出発地点0から出て，戻る） Σⱼ x₀ⱼ ＝ 1 ／ Σᵢ xᵢ₀ ＝ 1 流量保存（訪問と辺の連動） Σⱼ xᵢⱼ ＝ yᵢ ／ Σⱼ xⱼᵢ ＝ yᵢ 旅程は出発地点から1本だけ出発し，1本だけ帰着する 訪問する地点では1回入り1回出る．訪問しない地点では辺を使わない 訪問地点数 時間予算（旅行可能時間 B 以内） Σᵢ yᵢ ＝ K （K＝15 → 10） 15地点から試し，実行不可能なら14，13…と減らす．最低10地点 そのほか：自己ループ禁止 xᵢᵢ＝0 Σ ( tᵢⱼ ＋ sⱼ ＋ wⱼ ) xᵢⱼ ≤ B 移動＋滞在＋待ち時間を旅行枠内に収める．高低差は快適性評価のみで，時計 上の時間には加えない

© 2026 NTT West, Inc. All Rights Reserved. 27 /79 部分巡回路の除去 MTZ制約（Miller–Tucker–Zemlin） 流量保存だけで起きる不正な解 uᵢ − uⱼ ＋ n·xᵢⱼ ≤ n − 1 （i ≠ j, i, j ∈ V′） 直観的な意味 本体：出発地→A→B→出発地 不正な別ループ：C→D→C uᵢ は訪問順序を表す補助変数．辺 i→j を選ぶと「順序が前へ進む」こ とを強制するため，出発地点を含まない独立した小ループは作れなくな る 巡回路の一体性を保証する定番の制約．TSPを整数計画で解く際の核心部分

© 2026 NTT West, Inc. All Rights Reserved. 28 /79 LLMとの違いを実験で示す：Gemini案との公平な比較 数理最適化が選んだ訪問地点集合を Gemini にも使わせ，比較対象を「訪問順だけ」にする Gemini へ渡す情報 Gemini へ渡さない情報 地点名 移動時間行列・渋滞・推定待ち時間・高低差 施設カテゴリ 住所・座標・口コミ数・旅行時間帯 評価 最適化された訪問順 → 人間が旅行雑誌を見て順番を考えるのに近い条件 公平性の担保 → 「現実の移動コストを知っているのは最適化側だけ」という状況を作る 両案とも，表示時には同じ Routes API 行列で移動時間・渋滞・待ち時間・高低差を事後評価する．Google Maps データ×数理 最適化の効果だけを比較できる

© 2026 NTT West, Inc. All Rights Reserved. 本日の流れ • 数理最適化とは？ • 万博を例に • LLMとの違い，使い分け • Google Map APIについて • Google Map×数理最適化 • 旅行プランアプリ • 自然文から1日旅行プランを作る ── 巡回順を決める（TSP） • インフラ保全業務アプリ • インフラ保全の工事立会者手配 ── 人と工事を割り当てる • 避難所配置計画アプリ • 避難所配置の最適化 ── 施設をどこに置くか（MCLP） 29 /79

© 2026 NTT West, Inc. All Rights Reserved. 30 /79 本日お話すること • 数理最適化を用いた実務でのデータ分析事例について紹介する • その中で実施する数値実験やその成果を現場の方に提示する際のPoC としてStreamlitを活用した話について紹介する • 数理最適化における学術的な価値（実用的な数理モデル，解の探索アルゴリ ズム（時間，精度））だけではなく，現場目線のUIを意識する • クラウドを活用してPoCの共有のしやすさを高める，現場の人との意思疎通をより 容易にすることで，数理最適化における学術的な価値をより高める Changed value of parameter MIPGap to 0.0 Prev: 0.0001 Min: 0.0 Max: 1e+100 Default: 0.0001 Changed value of parameter MIPGap to 0.0 Prev: 0.0001 Min: 0.0 Max: 1e+100 Default: 0.0001 Changed value of parameter threads to 1 Prev: 0 Min: 0 Max: 1024 Default: 0 model.objval 7230.0 model.runtime 0.7993485927581787 下界: 7164.50 dist: 0, cycle: (6,) dist: 0, cycle: (20,) dist: 1847, cycle: (1, 4, 2) dist: 1686, cycle: (7, 3, 8) dist: 790, cycle: (5, 10, 9) dist: 1240, cycle: (16, 11, 18) dist: 943, cycle: (13, 15, 12) dist: 665, cycle: (14, 19, 17) 現場目線でないUI 現場目線のI

© 2026 NTT West, Inc. All Rights Reserved. 31 /79 背景 ◼ 近年道路等のインフラの老朽化が深刻な社会問題となっている ◼ インフラを補修する工事等の件数が増加している 100 道路橋[約73万橋] 90 トンネル[約1万1千本] 河川管理施設（水門等）[約1万施設] 80 下水道管渠[総延長約47万km] 70 港湾岸壁[約5千施設] 割合[%] 60 50 40 30 20 10 0 2018 2019 2020 2021 2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 年 建設後５０年以上経過する社会資本の割合 (国土交通省) 2032 2033

© 2026 NTT West, Inc. All Rights Reserved. 32 /79 背景 ◼ インフラの補修工事には各設備に関する知識を有する監督者が必要である ◼ 電話等の通信設備への影響を防ぐためにNTTの社員が立会を行っている NTT管路系設備 道路の工事（掘削）の様子

© 2026 NTT West, Inc. All Rights Reserved. 33 /79 背景 ◼ 与えられた全ての工事に対して立会者の割当を決定する問題である ◼ 移動距離や立会者のスキル等の様々な条件を考慮し割当を決定している ◼ 条件は万人共通の条件もあれば手配者の思考や嗜好によって異なるものもある 入力 出力 工事4 工事1 1 工事2 4 手配者 工事5 2 1 工事6 3 工事7 工事8 8 工事9 6 工事5 数理モデル 5 工事6 工事3 手配者 の思考/嗜好 = 7 工事2 4 2 5 工事3 立会者1～4 工事4 工事1 立会者4 3 工事7 立会者1 7 立会者2 工事8 ブラックボックス 化 8 工事9 9 9 立会者3 6

© 2026 NTT West, Inc. All Rights Reserved. 34 /79 投影限り 背景 補足 • 事前準備 • • • 国から道路等の舗装依頼に関する工事情報が1 回100件近く FAX やメールにて送信される． 立会者の人員リソース状況から60 件より多くの工事全てに立ち 会うことは困難であるため，真に立会が必要な工事を精査し， 60 件以下，できれば40 件近くまで工事数を削減する． 地図を印刷した紙の上に透明なアクリル板を載せ，水性ペンを 用いて住所情報を元に立会すべき工事を地図上に点をつけて 記す． • 工事手配の決定 • • • 地図上に記された点が1 つから3 つになるようにグループ分けを 行う． 分けられたグループをいずれの立会者が担当するかを決定する． 工事に関する知識やスキル不足などの理由から，あるグループ の工事に対して適当な(すなわちそのグループの全ての工事を担 当可能な) 立会者がいない場合，グループ分けを再度やり直す． • 事後作業 • • 工事の手配結果を描写した地図を工事立会者に見てもらい， 各立会者は担当工事を記憶し，工事現場に向かう． 工事の手配結果を描写した地図の写真を撮り，データ化する． 次の工事手配業務を行うために，アクリル板上に書かれた情報 を消去する． 投影限り

© 2026 NTT West, Inc. All Rights Reserved. 35 /79 投影限り 背景 補足 • 事前準備 • • • 国から道路等の舗装依頼に関する工事情報が1 回100件近く FAX やメールにて送信される． 立会者の人員リソース状況から60 件より多くの工事全てに立ち 会うことは困難であるため，真に立会が必要な工事を精査し， 60 件以下，できれば40 件近くまで工事数を削減する． 地図を印刷した紙の上に透明なアクリル板を載せ，水性ペンを 用いて住所情報を元に立会すべき工事を地図上に点をつけて 記す． 34 • • 地図上に記された点が1 つから3 つになるようにグループ分けを 行う． 分けられたグループをいずれの立会者が担当するかを決定する． 工事に関する知識やスキル不足などの理由から，あるグループ の工事に対して適当な(すなわちそのグループの全ての工事を担 当可能な) 立会者がいない場合，グループ分けを再度やり直す． • 工事の手配結果を描写した地図を工事立会者に見てもらい， 各立会者は担当工事を記憶し，工事現場に向かう． 工事の手配結果を描写した地図の写真を撮り，データ化する． 次の工事手配業務を行うために，アクリル板上に書かれた情報 を消去する． 30 11 12 23 25 24 13 18 19 16 投影限り 26 27 17 10 22 15 1 14 7 9 2 31 3 4 • 事後作業 • 28 33 • 工事手配の決定 • 29 32 6 5 36 8 21 20 35

© 2026 NTT West, Inc. All Rights Reserved. 36 /79 投影限り 背景 補足 • 事前準備 • • • 国から道路等の舗装依頼に関する工事情報が1 回100件近く FAX やメールにて送信される． 立会者の人員リソース状況から60 件より多くの工事全てに立ち 会うことは困難であるため，真に立会が必要な工事を精査し， 60 件以下，できれば40 件近くまで工事数を削減する． 地図を印刷した紙の上に透明なアクリル板を載せ，水性ペンを 用いて住所情報を元に立会すべき工事を地図上に点をつけて 記す． 34 • • 地図上に記された点が1 つから3 つになるようにグループ分けを 行う． 分けられたグループをいずれの立会者が担当するかを決定する． 工事に関する知識やスキル不足などの理由から，あるグループ の工事に対して適当な(すなわちそのグループの全ての工事を担 当可能な) 立会者がいない場合，グループ分けを再度やり直す． • 工事の手配結果を描写した地図を工事立会者に見てもらい， 各立会者は担当工事を記憶し，工事現場に向かう． 工事の手配結果を描写した地図の写真を撮り，データ化する． 次の工事手配業務を行うために，アクリル板上に書かれた情報 を消去する． 30 11 12 23 25 24 13 18 19 16 投影限り 26 27 17 10 22 15 1 14 7 9 2 31 3 4 • 事後作業 • 28 33 • 工事手配の決定 • 29 32 6 5 36 8 21 20 35

© 2026 NTT West, Inc. All Rights Reserved. 37 /79 投影限り 背景 補足 • 事前準備 • • • 国から道路等の舗装依頼に関する工事情報が1 回100件近く FAX やメールにて送信される． 立会者の人員リソース状況から60 件より多くの工事全てに立ち 会うことは困難であるため，真に立会が必要な工事を精査し， 60 件以下，できれば40 件近くまで工事数を削減する． 地図を印刷した紙の上に透明なアクリル板を載せ，水性ペンを 用いて住所情報を元に立会すべき工事を地図上に点をつけて 記す． 34 • • 地図上に記された点が1 つから3 つになるようにグループ分けを 行う． 分けられたグループをいずれの立会者が担当するかを決定する． 工事に関する知識やスキル不足などの理由から，あるグループ の工事に対して適当な(すなわちそのグループの全ての工事を担 当可能な) 立会者がいない場合，グループ分けを再度やり直す． • 工事の手配結果を描写した地図を工事立会者に見てもらい， 各立会者は担当工事を記憶し，工事現場に向かう． 工事の手配結果を描写した地図の写真を撮り，データ化する． 次の工事手配業務を行うために，アクリル板上に書かれた情報 を消去する． 30 11 12 23 25 24 13 18 19 16 投影限り 26 27 17 10 22 15 1 14 7 9 2 31 3 4 • 事後作業 • 28 33 • 工事手配の決定 • 29 32 6 5 36 8 21 20 35

© 2026 NTT West, Inc. All Rights Reserved. 38 /79 投影限り 背景 補足 • 事前準備 • • • 国から道路等の舗装依頼に関する工事情報が1 回100件近く FAX やメールにて送信される． 立会者の人員リソース状況から60 件より多くの工事全てに立ち 会うことは困難であるため，真に立会が必要な工事を精査し， 60 件以下，できれば40 件近くまで工事数を削減する． 地図を印刷した紙の上に透明なアクリル板を載せ，水性ペンを 用いて住所情報を元に立会すべき工事を地図上に点をつけて 記す． 34 • • 地図上に記された点が1 つから3 つになるようにグループ分けを 行う． 分けられたグループをいずれの立会者が担当するかを決定する． 工事に関する知識やスキル不足などの理由から，あるグループ の工事に対して適当な(すなわちそのグループの全ての工事を担 当可能な) 立会者がいない場合，グループ分けを再度やり直す． • 工事の手配結果を描写した地図を工事立会者に見てもらい， 各立会者は担当工事を記憶し，工事現場に向かう． 工事の手配結果を描写した地図の写真を撮り，データ化する． 次の工事手配業務を行うために，アクリル板上に書かれた情報 を消去する． 30 11 12 23 25 24 13 18 19 16 投影限り 26 27 17 10 22 15 1 14 7 9 2 31 3 4 • 事後作業 • 28 33 • 工事手配の決定 • 29 32 6 5 36 8 21 20 35

© 2026 NTT West, Inc. All Rights Reserved. 39 /79 投影限り 背景 補足 • 事前準備 • • • 国から道路等の舗装依頼に関する工事情報が1 回100件近く FAX やメールにて送信される． 立会者の人員リソース状況から60 件より多くの工事全てに立ち 会うことは困難であるため，真に立会が必要な工事を精査し， 60 件以下，できれば40 件近くまで工事数を削減する． 地図を印刷した紙の上に透明なアクリル板を載せ，水性ペンを 用いて住所情報を元に立会すべき工事を地図上に点をつけて 記す． 34 • • 地図上に記された点が1 つから3 つになるようにグループ分けを 行う． 分けられたグループをいずれの立会者が担当するかを決定する． 工事に関する知識やスキル不足などの理由から，あるグループ の工事に対して適当な(すなわちそのグループの全ての工事を担 当可能な) 立会者がいない場合，グループ分けを再度やり直す． • 工事の手配結果を描写した地図を工事立会者に見てもらい， 各立会者は担当工事を記憶し，工事現場に向かう． 工事の手配結果を描写した地図の写真を撮り，データ化する． 次の工事手配業務を行うために，アクリル板上に書かれた情報 を消去する． 30 11 12 23 25 24 13 18 19 16 投影限り 26 27 17 10 22 15 1 14 7 9 2 31 3 4 • 事後作業 • 28 33 • 工事手配の決定 • 29 32 6 5 36 8 21 20 35

© 2026 NTT West, Inc. All Rights Reserved. 40 /79 やったこと ① 実用的な数理モデルの構築 ② 解の評価尺度の提案 ③ 組合せ爆発に対する実用的な解の探索手法の提案 料理で例えると・・・ 数理モデルの構築の際の現場ヒアリングで Streamlitを利用 ここでの計算実験を行う際にStreamlitを利用 ①実用的な数理モデルの構築 ②解の評価尺度の提案 ③組合せ爆発に対する実用的 な解の探索手法の提案 イメージしている料理の具体化 ・鍋？揚げ物？ ・辛いもの？甘いもの？ ・具材 ・調理道具 どの料理がイメージしているものに近いか という尺度 ・味 ・温かさ ・具材の大きさ あらゆる組合せの中から最適な調理 手順を見つけ出すやり方を考える ・具材，調味料の配分 ・加熱時間 ・調理の順序

© 2026 NTT West, Inc. All Rights Reserved. 41 /79 軽く紹介 ①現場の手配者による工事立会者の手配 ◼ 目的関数や制約条件は曖昧であり手配者によって手配結果が異なる ◼ 良い手配結果と悪い手配結果はベテランの手配者には判定可能である ◼ スキルの高い手配者の思考を再現可能な数理モデルを構築する Staff T1 T2 T3 合計移 合計割当 合計難易度 動時間 ペナルティ A 15 16 900 7 5 B C 1 4 2 5 3 6 638 518 13 16 8 8 D E 7 8 9 10 11 12 886 564 12 17 8 8 F G 13 14 17 18 19 586 825 12 18 4 8 H 20 21 - 1098 9 5 I J 22 23 24 25 26 27 604 1115 12 13 8 7 K 28 29 30 916 13 7 L M N 31 32 1276 33 34 796 35 36 702 総 11424 9 8 4 163 5 5 5 91 過去の現場の手配者が実際に割り当てた結果

© 2026 NTT West, Inc. All Rights Reserved. 42 /79 軽く紹介 ①工事立会者手配問題解決に向けた進め方 ◼ 数理モデル化には現場の意思決定者と数理モデルを構築可能な専門家の両者の 協力が必要である ◼ 一般的に1回のヒアリングで求められる解に到達することは難しい ◼ 現場ヒアリングと数理モデルの修正を繰り返し求められる解に近づける 汎用ソルバー（NUOPT/Gurobi） 現場ヒアリング 実社会問題 専門知識必須 定式化 専門知識必須 数理モデル 最適化計算 現場ヒアリング (近似)最適解 分析・検証 解 最適化モデルの修正 専門知識必須 入力 人の思考/嗜好 = 数理モデル 出力

© 2026 NTT West, Inc. All Rights Reserved. 43 /79 軽く紹介 ①数理モデル構築の結果まとめ ◼ 高度な技能を有している手配者により意思決定が行われている工事立会者手配 業務に対し実用的な手配結果を算出可能な数理モデルを構築した 長期効果 短期効果 付随効果 過去の工事立会者手配業務 デジタルデータ活用による工事立会者手配業務 人件費 年間1億（関東エリア：年間6万件） 年間0.1億（関東エリア：年間6万件）（想定） 品質 年間工事事故5件 年間工事事故0件（想定） 総移動時間 11,424 s（3.2 h） 11,593 s（3.2 h）※1 総割当ペナルティ 163 pt 81 pt※1 手配時間 3時間2回/1日 5分×2回/1日 やり方 アナログ（手書き） デジタル 手配結果 ※1：数理モデル4で総移動時間を重視すると, 総合移動時間10,697 s, 総品質146 ptとなる.

© 2026 NTT West, Inc. All Rights Reserved. 44 /79 軽く紹介 ②提案した数理モデルから得られる解の評価 ◼ 数理モデル1から数理モデル4に改善するにあたり，各数理モデルから得られる解の 実用性について主観評価を行った ◼ 数理モデルにより算出される解と手配者が手作業で作成した手配結果との相違度 が減少することについて客観評価を行う 総移動時間 [秒] 総割当ペナルティ [point] 11424 163 10537 183 9595 172 9960 119 9877 97 11516 73 12580 53 13580 50 15007 45 17720 42 17268 41 18029 40 10697 146 10332 141 11006 101 11593 81 11309 73 11210 71 11103 67 13526 53 13831 50 14829 46 17652 42 18352 41 200 悪 現場の手配者 数理モデル1 数理モデル2 数理モデル3 数理モデル4 数理モデル1 180 数理モデル2 現場の手配者 160 総割当ペナルティ[point] 項番 モデル 1 現場の手配者 2 数理モデル1 3 数理モデル2 4 数理モデル3(α=20) 5 数理モデル3(α=40) 6 数理モデル3(α=60) 7 数理モデル3(α=170) 8 数理モデル3(α=190) 9 数理モデル3(α=330) 10 数理モデル3(α=610) 11 数理モデル3(α=770) 12 数理モデル3(α=1390) 13 数理モデル4(α=0) 14 数理モデル4(α=10) 15 数理モデル4(α=30) 16 数理モデル4(α=50) 17 数理モデル4(α=60) 18 数理モデル4(α=90) 19 数理モデル4(α=110) 20 数理モデル4(α=200) 21 数理モデル4(α=280) 22 数理モデル4(α=360) 23 数理モデル4(α=640) 24 数理モデル4(α=970) 数理モデル4(α=0) 数理モデル4(α=10) 140 数理モデル 120 3(α=20) 数理モデル数理モデル4(α=30) 100 3(α=40) 手配者の評価では現場の 結果と最も近い解は数理モ デル4（𝛼 = 50） 数理モデル4(α=50) 数理モデル4(α=60) 数理モデル4(α=90) 数理モデル 80 3(α=60) 数理モデル4(α=110) 数理モデル 60 3(α=170) 40 数理モデル4(α=200) 数理モデル4(α=280) 数理モデル 数理モデル 3(α=190) 3(α=330) 数理モデル4(α=360) 良 20 9000 良 10000 11000 12000 数理モデル 13000 14000 15000 総移動時間[秒] 16000 3(α=610) 数理モデル4(α=640) 数理モデル 3(α=1390) 数理モデル 3(α=770) 数理モデル4(α=970) 17000 18000 19000 悪

© 2026 NTT West, Inc. All Rights Reserved. 45 /79 軽く紹介 ②解の相違度について ◼ 工事立会者手配問題は各立会者にいずれの工事を割り当て各立会者が自分に 割り当てられた工事をどういう順序で巡回するかを決定する問題である ◼ 解の基本構造である工事間の移動ルート【観点1】と各工事への立会者の割当【観 点2】はそれぞれが目的関数に直接寄与している 1 2 3 1 0 0 0 21.73 12.42 27.93 2 0 0 0 21.73 12.42 27.93 3 0 0 0 21.73 12.42 27.93 4 21.73 21.73 21.73 4 5 6 Differ 0 12.42 12.42 5 12.42 12.42 12.42 12.42 0 21.73 6 27.93 27.93 27.93 12.42 21.73 0 Similar 【観点1】の相違度行列 1 2 1 0 0 21.82 14.55 7.274 21.82 2 0 0 21.82 14.55 7.274 21.82 3 21.82 21.82 3 4 6 Differ 0 18.18 14.55 21.82 4 14.55 14.55 18.18 0 7.274 25.46 5 7.274 7.274 14.55 7.274 工事立会者手配問題の解の例 5 0 29.1 6 21.82 21.82 21.82 25.46 29.1 0 Similar 【観点2】の相違度行列 相違度行列は正規化済

© 2026 NTT West, Inc. All Rights Reserved. 46 /79 軽く紹介 ②実データへの適用結果 ◼ 24 個の手配結果を相違度の尺度を用いて比較する ෡𝐴 と【観点2】の𝐻𝐵 の重み付き和 ◼ 行列内の数値は【観点1】の𝐻 ෡𝐶 = 1 − 𝛽 𝐻 ෡𝐴 + 𝛽𝐻 ෡𝐵 𝐻 ◼ 現場の手配者と最も相違度が低いのは数理モデル4 (𝛼 = 50)である ◼ 手配者の主観評価とも合致する結果となる 項番 モデル 1 現場の手配者 2 数理モデル1 3 数理モデル2 4 数理モデル3(α=20) 5 数理モデル3(α=40) 6 数理モデル3(α=60) 7 数理モデル3(α=170) 8 数理モデル3(α=190) 9 数理モデル3(α=330) 10 数理モデル3(α=610) 11 数理モデル3(α=770) 12 数理モデル3(α=1390) 13 数理モデル4(α=0) 14 数理モデル4(α=10) 15 数理モデル4(α=30) 16 数理モデル4(α=50) 17 数理モデル4(α=60) 18 数理モデル4(α=90) 19 数理モデル4(α=110) 20 数理モデル4(α=200) 21 数理モデル4(α=280) 22 数理モデル4(α=360) 23 数理モデル4(α=640) 24 数理モデル4(α=970) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 1 0 66.7 66.7 73.5 72.3 66.4 76.8 74.8 79.2 81.1 83.6 82 69.9 65.9 74.3 65 66.7 66.2 73.5 78.4 82.7 77 83.6 83.6 2 66.7 0 64.7 68.3 67.2 67.6 75.6 82.4 79.2 82.4 81.2 82.8 66.4 66.9 74 70.4 72 67.2 76.7 83.5 85.2 75.8 81.2 82.4 3 66.7 64.7 0 48 47.4 49.1 73.3 70.2 76.9 75.3 81.3 80.1 55.3 47.4 63.6 64.5 61.7 58.9 66.8 74.8 75.3 75.1 81.3 81.3 4 73.5 68.3 48 0 53.4 53.1 72.6 68.6 75.7 74.1 84.1 81.3 53.8 52 62.1 57 60.5 59.4 61.2 78.8 75.3 73.1 82.5 82.9 5 72.3 67.2 47.4 53.4 0 37.4 70.6 60.3 69.4 60.3 75.4 74.2 59.6 62.5 50.2 58.5 51.8 42.3 53.3 67.8 65.7 66 77 75.8 6 66.4 67.6 49.1 53.1 37.4 0 59.9 43.3 56.7 53.9 65.5 59.9 61.7 61.4 55.4 57.7 48 37.6 57 53.9 58.3 57.3 65.5 65.5 7 76.8 75.6 73.3 72.6 70.6 59.9 0 45.7 45.2 67.9 64 57.2 74 79.3 73.8 73.8 60.3 67 78.9 60.3 69.8 49.1 62.4 64 8 74.8 82.4 70.2 68.6 60.3 43.3 45.7 0 38.6 52 58 54.1 74.4 76.9 65.3 71.3 63.9 56.7 64.6 41.7 47.7 42 59.2 63.6 9 79.2 79.2 76.9 75.7 69.4 56.7 45.2 38.6 0 43 25.9 27.5 80 81.3 70.6 70.6 63.9 60.4 66.7 59.2 51.2 19.7 33 33 10 81.1 82.4 75.3 74.1 60.3 53.9 67.9 52 43 0 45.8 45.8 77.6 77.3 65.1 67.1 62.4 56 57.2 54.1 56.4 41.5 51.3 44.2 11 83.6 81.2 81.3 84.1 75.4 65.5 64 58 25.9 45.8 0 15.9 86 84.5 73.8 75 68.3 70.3 75.4 69.2 61.6 30.9 13.2 13.2 12 82 82.8 80.1 81.3 74.2 59.9 57.2 54.1 27.5 45.8 15.9 0 83.2 83.3 77 75 61.6 64.8 75.4 62.4 57.6 32.5 17.5 17.5 13 69.9 66.4 55.3 53.8 59.6 61.7 74 74.4 80 77.6 86 83.2 0 48.7 61.4 58.5 57.3 59.4 58 74.1 73.7 77.8 86 84.8 14 65.9 66.9 47.4 52 62.5 61.4 79.3 76.9 81.3 77.3 84.5 83.3 48.7 0 58.6 60.5 59.8 57.5 66.8 75.3 79.2 77.9 84.5 83.3 15 74.3 74 63.6 62.1 50.2 55.4 73.8 65.3 70.6 65.1 73.8 77 61.4 58.6 0 53.9 51.9 42 66.1 57.7 64.9 71.6 76.6 75.4 16 65 70.4 64.5 57 58.5 57.7 73.8 71.3 70.6 67.1 75 75 58.5 60.5 53.9 0 45.2 51.5 56.7 68.3 69 68.4 77.8 77.8 17 66.7 72 61.7 60.5 51.8 48 60.3 63.9 63.9 62.4 68.3 61.6 57.3 59.8 51.9 45.2 0 36.8 60.7 64.3 63.4 62.1 68.3 68.3 18 66.2 67.2 58.9 59.4 42.3 37.6 67 56.7 60.4 56 70.3 64.8 59.4 57.5 42 51.5 36.8 0 63.7 43.6 63.4 63.7 70.3 69.2 19 73.5 76.7 66.8 61.2 53.3 57 78.9 64.6 66.7 57.2 75.4 75.4 58 66.8 66.1 56.7 60.7 63.7 0 59.2 47.4 64 79.4 78.2 20 78.4 83.5 74.8 78.8 67.8 53.9 60.3 41.7 59.2 54.1 69.2 62.4 74.1 75.3 57.7 68.3 64.3 43.6 59.2 0 34.7 63.7 70.3 69.2 21 82.7 85.2 75.3 75.3 65.7 58.3 69.8 47.7 51.2 56.4 61.6 57.6 73.7 79.2 64.9 69 63.4 63.4 47.4 34.7 0 58.9 67.1 67.1 22 77 75.8 75.1 73.1 66 57.3 49.1 42 19.7 41.5 30.9 32.5 77.8 77.9 71.6 68.4 62.1 63.7 64 63.7 58.9 0 29.2 36.4 23 83.6 81.2 81.3 82.5 77 65.5 62.4 59.2 33 51.3 13.2 17.5 86 84.5 76.6 77.8 68.3 70.3 79.4 70.3 67.1 29.2 0 7.16 24 83.6 82.4 81.3 82.9 75.8 65.5 64 63.6 33 44.2 13.2 17.5 84.8 83.3 75.4 77.8 68.3 69.2 78.2 69.2 67.1 36.4 7.16 0 Differ Similar

© 2026 NTT West, Inc. All Rights Reserved. 47 /79 軽く紹介 ③工事立会者手配問題に対する種々の定式化に基づく求解法 ◼ 工事立会者手配問題に対して，以下4つの定式化に基づく求解法の比較を行う 1. 非線形の定式化（ TOM59Model） 2. 集合被覆アプローチによる定式化（Enum） 3. 制約生成法に基づく定式化（CG𝑥-(𝑦)） 4. 実行可能なルート候補を削減した集合被覆アプローチによる定式化（Enum+）

© 2026 NTT West, Inc. All Rights Reserved. 48 /79 軽く紹介 ③非線形の定式化（ TOM59Model） ■非線形の定式化（ TOM59Model）は以下である ◼ 工事立会者手配問題は，訪問すべき点集合𝐽と点𝑘, 𝑙 ∈ 𝐽間の移動コスト𝑑𝑘𝑙 が与 えられたとき，各立会者に割り当てられた全ての工事を1度ずつ訪問する巡回路の 中で，総移動コストが最小のものを求める問題である min σ𝑠∈𝑆 𝐷𝑠 + 𝛼 σ𝑠𝜖𝑆 𝑄𝑠 s.t. σ𝑘∈𝐽∪𝐽′ 𝑥𝑠𝑘𝑡 = 1 (∀𝑠 ∈ 𝑆, ∀𝑡 ∈ 𝑇) σ𝑡∈𝑇 σ𝑠∈𝑆 𝑥𝑠𝑘𝑡 = 1 (∀𝑘 ∈ 𝐽) σ𝑡∈𝑇 σ𝑘∈𝐽 𝑤𝑘 𝑥𝑠𝑘𝑡 < 9 (∀𝑠 ∈ 𝑆) 𝐷𝑠 = σ𝑡∈𝑇 σ𝑘,𝑙∈𝐽∪𝐽′ 𝑑𝑘,𝑙 𝑥𝑠𝑘𝑡 𝑥𝑠𝑙(𝑡+1) (∀𝑠 ∈ 𝑆) 𝑄𝑠 = σ𝑡∈𝑇 σ𝑘∈𝐽 𝑐𝑠𝑘 𝑥𝑠𝑘𝑡 (∀𝑠 ∈ 𝑆) 𝑥𝑠𝑘𝑡 ∈ 0, 1 (∀𝑠 ∈ 𝑆, ∀𝑘 ∈ 𝐽 ∪ 𝐽′, ∀𝑡 ∈ 𝑇) 𝑆： 立合者の集合 𝑆 = {1, 2, … , 𝑛} 𝐽： 工事の集合 𝐽 = {1, 2, … , 𝑚} 𝐽′： 各要素𝑘に対応するダミー𝑘’からなる ダミー工事の集合 𝐽′ = {1, 2, … , 𝑚} 𝑇： 工事の枠の集合 𝑇 = {1, 2, 3} 𝑑𝑘𝑙 : 工事𝑘から工事𝑙への移動時間 (𝑘, 𝑙 ∈ 𝐽) 𝑐𝑠𝑘 : 立合者𝑠に工事𝑘を割り当てたときの割当ペナルティ(𝑠 ∈ 𝑆, 𝑘 ∈ 𝐽) 𝑤𝑘 : 工事𝑘の難易度(𝑘 ∈ 𝐽)

© 2026 NTT West, Inc. All Rights Reserved. 49 /79 軽く紹介 ③集合被覆アプローチによる定式化 (Enum) ◼ 集合被覆アプローチによる定式化は以下である ◼ 以下を満たす実行可能なルートを列挙し全ての工事を被覆するルートを選ぶ A) |𝐽|件の工事に対し， |𝑆|人の立会者を割り当てる B) 各工事にちょうど1人の立会者を割り当てる C) 各立会者に割り当てられる工事数は𝜈件以下とする D) 各立会者に割り当てられる工事の総難易度は𝑊点以下とする E) すべての立会者の総移動時間と総割当ペナルティの重み付き和を最小化する 𝑆： 立合者の集合 𝐽： 工事の集合 min σ𝑟∈𝑅 σ𝑠∈𝑆 𝑑ሚ𝑟 + 𝛼 𝑐ǁ𝑟𝑠 𝑦𝑟𝑠 s.t. σ𝑟∈𝑅 σ𝑠∈𝑆 𝑎𝑘𝑟 𝑦𝑟𝑠 ≥ 1 (∀𝑘 ∈ 𝐽) 𝑅： 実行可能なルートの集合 σ𝑟∈𝑅 𝑦𝑟𝑠 ≤ 1 ∀𝑠 ∈ 𝑆 𝑑ሚ𝑟 : ルート𝑟の合計移動時間 𝑦𝑟𝑠 ∈ 0, 1 (∀𝑟 ∈ 𝑅, ∀𝑠 ∈ 𝑆) 𝑐ǁ𝑟𝑠 : 立会者𝑠がルート𝑟を担当したとき の合計割当ペナルティ 𝑎𝑘𝑟 : ルート𝑟が工事𝑘を含むとき𝑎𝑘𝑟 = 1, 含まないとき𝑎𝑘𝑟 = 0 𝛼：総移動時間と総割当ペナルティの重み係数 ❏ 集合被覆アプローチによる定式化 1 2 3 4 5 6 7 8 9

© 2026 NTT West, Inc. All Rights Reserved. 50 /79 軽く紹介 ③工事立会者手配問題のEnumに対する計算量 ◼ 数理モデルによる手配結果を実業務で運用したところ，立会者の担当する工事件 数は3件以下に制限せず，4件以上割り当てることを許容したいという新しい要望が あがった ◼ 4 件以上となる実行可能なルートを全て列挙すると列挙数が指数的に増加するため， 先行研究での集合被覆アプローチ による実行可能なルートを全列挙する方法 （Enum）は実用的でない 実行可能なルートの列挙数 1.E+12 Enum（|J|=10, |S|=4） Enum（|J|=15, |S|=6） Enum（|J|=20, |S|=8） Enum（|J|=40, |S|=15） 1.E+10 列挙数 1.E+08 1.E+06 1.E+04 1.E+02 1.E+00 1 2 3 4 5 担当工事上限数ν 6 7 8 σ𝜈𝑘=1 40 𝑘 𝑘−1 ! σ𝜈𝑘=1 20 𝑘 15 𝜈 σ𝑘=1 𝑘 𝑘−1 ! 𝑘−1 ! σ𝜈𝑘=1 10 𝑘 𝑘−1 !

© 2026 NTT West, Inc. All Rights Reserved. 51 /79 軽く紹介 ③制約生成法に基づく定式化 (CG𝑥-(𝑦))（1/4） ◼ 工事立会者手配問題は，訪問すべき点集合𝐽と点𝑘, 𝑙 ∈ 𝐽間の移動コスト𝑑𝑘𝑙 が与 えられたとき，各立会者に割り当てられた全ての工事を1度ずつ訪問する巡回路の 中で，総移動コストが最小のものを求める問題である ◼ 巡回セールスマン問題では全頂点に対する部分巡回路除去制約が必要であるが， 工事立会者手配問題では各立会者に割り与えられた全ての工事に対する部分巡 回路切除制約が必要である ◼ σ𝑘,𝑙∈𝐽′ 𝑥𝑠𝑘𝑙 ≤ 𝐽′ − σ𝑘 ′∈𝐽∖𝐽′ 𝑥𝑠𝑘 ′ 𝑙′ を部分巡回路除去制約と呼ぶ ❏制約生成法に基づく定式化 min σ𝑠∈𝑆 σ𝑘,𝑙∈𝐽(𝑑𝑘𝑙 + α𝑐𝑠𝑘 )𝑥𝑠𝑘𝑙 s.t. σ𝑠∈𝑆 σ𝑙∈𝐽 𝑥𝑠𝑘𝑙 = 1 (∀𝑘 ∈ 𝐽) σ𝑙∈𝐽 𝑥𝑠𝑘𝑙 = σ𝑙∈𝐽 𝑥𝑠𝑘𝑙 (∀𝑠 ∈ 𝑆, ∀𝑘 ∈ 𝐽) σ𝑘,𝑙∈𝐽 𝑤𝑘 𝑥𝑠𝑘𝑙 ≤ 𝑊 (∀𝑠 ∈ 𝑆) σ𝑘,𝑙∈𝐽 𝑥𝑠𝑘𝑙 ≤ ν (∀𝑠 ∈ 𝑆) σ𝑘,𝑙∈𝐽′ 𝑥𝑠𝑘𝑙 ≤ 𝐽′ − σ𝑘 ′ ∈𝐽∖𝐽′ 𝑥𝑠𝑘 ′𝑙′ (∀𝑠 ∈ 𝑆, ∀𝐽′ ⊊ 𝐽, 𝐽′ ≠ ∅, ∀𝑙 ′ ∈ 𝐽 ∖ 𝐽′ ) 𝑥𝑠𝑘𝑙 ∈ 0, 1 (∀𝑠 ∈ 𝑆, ∀𝑘, 𝑙 ∈ 𝐽) 𝐽： 工事の集合 𝑆： 立会者の集合 𝑑𝑘𝑙 : 工事𝑘から工事𝑙への移動時間 𝑐𝑠𝑘 ：立会者𝑠に工事𝑘を割り当てたときの割当ペナル ティ 𝑤𝑘 : 工事𝑘の難易度 𝑊：各立会者に割り当てられた工事の難易度の和に 対する上限 ν：各立会者に割り当てられる工事数の上限 𝛼：総移動時間と総割当ペナルティの重み係数

© 2026 NTT West, Inc. All Rights Reserved. 52 /79 軽く紹介 ③制約生成法に基づく定式化 (CG𝑥-(𝑦))（2/4） ◼ 工事立会者手配問題は，訪問すべき点集合𝐽と点𝑘, 𝑙 ∈ 𝐽間の移動コスト𝑑𝑘𝑙 が与 えられたとき，各立会者に割り当てられた全ての工事を1度ずつ訪問する巡回路の 中で，総移動コストが最小のものを求める問題である ◼ 巡回セールスマン問題では全頂点に対する部分巡回路除去制約が必要であるが， 工事立会者手配問題では各立会者に割り与えられた全ての工事に対する部分巡 回路切除制約が必要である ◼ σ𝑘,𝑙∈𝐽′ 𝑥𝑠𝑘𝑙 ≤ 𝐽′ − σ𝑘 ′∈𝐽∖𝐽′ 𝑥𝑠𝑘 ′ 𝑙′ を部分巡回路除去制約と呼ぶ ❏ 最適解の例 1 4 ❏ 部分巡回路を含む解の例 7 𝐽1 1 𝐽2 2 3 8 9 立会者A 5 10 7 𝐽1 𝐽2 2 立会者A3 立会者B 5 𝐽3 9 立会者B 𝐽10 4 立会者B 6 立会者B 4 8 6

© 2026 NTT West, Inc. All Rights Reserved. 53 /79 軽く紹介 ③制約生成法に基づく定式化 (CG𝑥-(𝑦))（3/4） ◼ 工事立会者手配問題に対する制約生成法に基づく解法（CG）について述べる ◼ 工事立会者手配問題は|𝑆|人の立会者で|𝐽|件の工事を訪問したときの総移動時 間と総割当ペナルティの重み付き和を最小化する問題である ◼ 部分巡回路除去制約を最初から全て与えるのではなく，逐次的に制約を生成して もとの定式化に追加し，部分巡回路が存在しなくなるまで，この操作を繰り返す求 解法である 最小構成の定式化 ❏ 制約生成法の処理フロー min σ𝑠∈𝑆 σ𝑘,𝑙∈𝐽(𝑑𝑘𝑙 + α𝑐𝑠𝑘 )𝑥𝑠𝑘𝑙 s.t. σ𝑠∈𝑆 σ𝑙∈𝐽 𝑥𝑠𝑘𝑙 = 1 (∀𝑘 ∈ 𝐽) σ𝑙∈𝐽 𝑥𝑠𝑘𝑙 = σ𝑙∈𝐽 𝑥𝑠𝑘𝑙 (∀𝑠 ∈ 𝑆, ∀𝑘 ∈ 𝐽) σ𝑘,𝑙∈𝐽 𝑤𝑘 𝑥𝑠𝑘𝑙 ≤ 𝑊 (∀𝑠 ∈ 𝑆) σ𝑘,𝑙∈𝐽 𝑥𝑠𝑘𝑙 ≤ ν (∀𝑠 ∈ 𝑆) 𝑥𝑠𝑘𝑙 ∈ 0, 1 (∀𝑠 ∈ 𝑆, ∀𝑘, 𝑙 ∈ 𝐽) 最小構成（部分巡回路除去制約なし）の定式化 を解く 得られた解の中である立会者のルー トが2つ以上の部分巡回路を含む Y 1人のルートが2つ以上に分かれている立会者全員の そのような部分巡回路全てに対し，各々に含まれる 工事集合を部分巡回路除去制約としてもとの定式 化に追加し，新たな定式化を解く N 得られた解を最適解として出力して終了 部分巡回路除去制約 σ𝑘,𝑙∈𝐽′ 𝑥𝑠𝑘𝑙 ≤ 𝐽′ − σ𝑘 ′∈𝐽∖𝐽′ 𝑥𝑠𝑘 ′𝑙′ (∀𝑠 ∈ 𝑆, ∀𝐽′ ⊊ 𝐽, 𝐽′ ≠ ∅, ∀𝑙 ′ ∈ 𝐽 ∖ 𝐽′ )

© 2026 NTT West, Inc. All Rights Reserved. 54 /79 軽く紹介 ③制約生成法に基づく定式化 (CG𝑥-(𝑦))（4/4） ◼ 工事立会者手配問題に対する制約生成法に基づく解法（CG）について述べる ◼ 工事立会者手配問題は|𝑆|人の立会者で|𝐽|件の工事を訪問したときの総移動時 間と総割当ペナルティの重み付き和を最小化する問題である ◼ 部分巡回路除去制約を最初から全て与えるのではなく，逐次的に制約を生成して もとの定式化に追加し，部分巡回路が存在しなくなるまで，この操作を繰り返す求 解法である ❏ 制約生成法の処理フロー例 立会者A 1 立会者B 4 7 𝐽1 2 8 𝐽3 1 𝐽2 3 立会者A 立会者B σ𝑘,𝑙∈𝐽2 𝑥𝑠𝑘𝑙 ≤ 𝐽2 − σ𝑘 ′∈𝐽∖𝐽2 𝑥𝑠𝑘 ′𝑙′ σ𝑘,𝑙∈𝐽2 𝑥𝑠𝑘𝑙 ≤ 𝐽3 − σ𝑘 ′∈𝐽∖𝐽3 𝑥𝑠𝑘 ′𝑙′ σ𝑘,𝑙∈𝐽3 𝑥𝑠𝑘𝑙 ≤ 𝐽4 − σ𝑘 ′∈𝐽∖𝐽4 𝑥𝑠𝑘 ′𝑙′ 4 7 6 5 9 立会者B 𝐽410 立会者B 部分巡回路除去制約として もとの定式化に追加 6 ・・・ 2 8 𝐽1 3 9 5 𝐽2 10

© 2026 NTT West, Inc. All Rights Reserved. 55 /79 軽く紹介 ③制約生成法の計算結果 ◼ 制約生成法に基づく解法（CG）の最適値への収束状況について述べる ◼ 下界の収束には時間を要しているが上界は早い段階で最適値に近い値に到達した ◼ 多くの問題例において計算の初期段階で上界と下界の乖離は小さくなっていた ◼ 厳密な最適解よりも実用的な時間で良質な解が求められる実社会ではCGは有効 である 制約生成法での上界と下界（ 𝐽 = 18, 𝑆 = 7, 𝜈 = 8）

© 2026 NTT West, Inc. All Rights Reserved. 56 /79 軽く紹介 ③実行可能なルート候補を削減した集合被覆アプローチによる定式化 (Enum+) ◼ Enumでは立会者の担当する工事件数を増加すると実行可能なルートの列挙数が 指数的に増加する ◼ 集合被覆アプローチを用いた定式化に基づき，ルートを列挙するときに巡回セールス マン問題として定式化し，各立会者が担当する工事の部分集合の候補の各々に 対して最適な巡回路のみを選ぶことで，列挙数を削減する（Enum+） ❏ Enum ❏ Enum+ 実行可能なルートを全て列挙する σ𝜈𝑘=1 |𝐽| 𝑘 1 6 6 2 1 6 2 4 7 8 2 1 𝑘−1 ! 個 5 1 6 3 8 7 8 1 5 6 3 4 2 1 5 3 6 2 σ𝜈𝑘=1 |𝐽| 𝑘 個 4 7 8 2 4 7 最適な巡回路のみを列挙する 1 5 6 3 8 7 8 1 5 3 4 5 3 集合被覆アプローチを用いた定式化で解く 8 2 4 7 7 6 4 1 5 6 3 1 5 8 8 2 4 7 6 4 7 5 3 4 7 5 8 2 3 (1 ≤ 𝑘 ≤ 2𝜈) 個の工事を選ぶ 3 |𝐽|個の工事から𝑘 組合せの各々に対して，制約生成法を用いて最 1 4 1 4 7 7 5 5 小巡回路を選ぶ 6 6 2 8 3 2 8 3 集合被覆アプローチを用いた定式化で解く

© 2026 NTT West, Inc. All Rights Reserved. 57 /79 軽く紹介 ③工事立会者手配問題のEnum+に対する計算量 ◼ EnumとEnum+に対する実行可能なルートの列挙数を比較した結果を以下に示 す ◼ EnumよりEnum+のほうが実行可能なルートの列挙数が削減している 実行可能なルートの列挙数 1.E+12 Enum（|J|=10, |S|=4） Enum（|J|=15, |S|=6） Enum（|J|=20, |S|=8） Enum（|J|=40, |S|=15） Enum+（|J|=10, |S|=4） Enum+（|J|=15, |S|=6） Enum+（|J|=20, |S|=8） 1.E+10 列挙数 1.E+08 σ𝜈𝑘=1 40 𝑘 1.E+06 σ𝜈𝑘=1 20 𝑘 σ𝜈𝑘=1 15 𝑘 σ𝜈𝑘=1 10 𝑘 1.E+04 1.E+02 1.E+00 1 2 3 4 5 担当工事上限数ν 6 7 8

© 2026 NTT West, Inc. All Rights Reserved. 58 /79 軽く紹介 ③計算環境と問題例 ■計算環境 CPU：Intel Core i9-9900K CPU @ 3.60GHz Memory：48 GB Solver：Gurobi Optimizer V8.1 Python：Python 3.6.5 合計工事難易度上限𝑤 ：9, 18 重み係数𝛼：1 計算の制限時間：3,600秒 ■問題例 過去に手配者が割当を行った36件の工事と14人の立会者からなる実データ

© 2026 NTT West, Inc. All Rights Reserved. 59 /79 軽く紹介 ③CG𝑥-(𝑦)の計算結果（W=9） ◼ 𝑊 = 9に対する， 制約生成法CG𝑥-(𝑦) の計算結果を示す ◼ 制約追加方針については，制約追加方針1と制約追加方針2の間に大きな差は 見られない ◼ 部分巡回路除去制約については，(15) と(18) の間に大きな差は見られず， (19) に比べて(15) と(18) のほうが厳密な最適解を得られた問題例が多い |𝐽| |𝑆| 𝜈 18 7 3 18 7 4 18 7 5 18 7 6 18 7 7 18 7 8 20 8 3 20 8 4 20 8 5 20 8 6 20 8 7 20 8 8 36 14 3 36 14 4 36 14 5 36 14 6 36 14 7 36 14 8 CG1-(15) CG1-(18) CG1-(19) CG2-(15) CG2-(18) CG2-(19) Opt SolTime ArrTime UB SolTime ArrTime UB SolTime ArrTime UB SolTime ArrTime UB SolTime ArrTime UB SolTime ArrTime 7,363 117.02 15 *7,363 147.08 3 *7,363 630.98 41 *7,363 162.07 31 *7,363 132.21 10 *7,363 443.43 29 6,889 219 *6,889 265 *6,889 494 *6,889 203 *6,889 240 *6,889 591 TL TL TL TL TL TL 6,741 364 *6,741 226 *6,741 99 *6,741 45 *6,741 1,941 *6,741 132 TL TL TL TL TL TL 6,741 492 *6,741 58 *6,741 1,871 *6,741 150 *6,741 410 *6,741 231 TL TL TL TL TL TL 6,741 120 *6,741 1,006 *6,741 1,438 6,742 670 *6,741 333 *6,741 860 TL TL TL TL TL TL 6,741 796 *6,741 72 *6,741 1,229 *6,741 277 *6,741 320 *6,741 454 TL TL TL TL TL TL 7,230 93.95 15 *7,230 6 *7,230 379.22 48 *7,230 302.62 149 *7,230 219.55 49 *7,230 111 TL TL 6,856 3,488 *6,856 1,568 *6,856 3,090 *6,856 1,244 *6,856 771 *6,856 1,225 TL TL TL TL TL TL 6,626 85 6,627 2,174 *6,626 2,703 *6,626 1,509 6,627 809 *6,626 2,237 TL TL TL TL TL TL 6,626 823 *6,626 2,543 *6,626 473 6,627 1,038 *6,626 1,104 6,627 288 TL TL TL TL TL TL 6,626 785 *6,626 1,182 6,627 769 6,627 679 *6,626 2,333 *6,626 3,165 TL TL TL TL TL TL 6,626 892 6,629 1,599 6,627 1,408 6,723 2,051 *6,626 1,139 6,627 2,099 TL TL TL TL TL TL 14,251 1,078 *14,251 490 *14,251 947 *14,251 910 *14,251 909 *14,251 2,616 TL TL TL TL TL TL 13,727 3,341 13,844 2,032 13,803 293 17,706 3,068 13,771 3,411 13,779 3,579 TL TL TL TL TL TL 13,387 2,463 13,389 3,463 13,478 1,239 13,395 1,931 13,389 1,977 13,779 2,800 TL TL TL TL TL TL 13,387 2,978 13,782 2,554 13,813 3,175 13,392 2,284 13,403 2,641 13,390 3,574 TL TL TL TL TL TL 13,387 3,036 13,522 1,547 13,804 3,576 14,331 3,568 13,389 3,140 13,840 3,471 TL TL TL TL TL TL 13,387 2,229 13,389 1,786 13,532 3,010 13,393 2,797 13,388 2,333 13,397 3,367 TL TL TL TL TL TL UB *7,363 *6,889 6,742 *6,741 *6,741 6,742 *7,230 *6,856 *6,626 6,629 6,627 6,627 14,507 31,729 13,854 13,467 13,401 13,781

© 2026 NTT West, Inc. All Rights Reserved. 60 /79 軽く紹介 ③EnumとEnum+の計算結果（W=9） ◼ 𝑊 = 9に対する， 集合被覆アプローチのEnum，Enum+の計算結果を示す ◼ Enumはルート生成の時間は小さいが，ルート生成数が大きく，集合被覆の定式 化を解く時間が大きい ◼ Enum+はルート生成の時間は大きいが，ルート生成数が小さく，集合被覆の定 式化を解く時間が小さい |𝐽| 18 18 18 18 18 18 20 20 20 20 20 20 36 36 36 36 36 36 |𝑆| 7 7 7 7 7 7 8 8 8 8 8 8 14 14 14 14 14 14 𝜈 3 4 5 6 7 8 3 4 5 6 7 8 3 4 5 6 7 8 Opt 7,363 6,889 6,741 6,741 6,741 6,741 7,230 6,856 6,626 6,626 6,626 6,626 14,251 13,727 13,387 13,387 13,387 13,387 EnmNum 5,052 44,604 153,324 218,124 218,124 218,124 7,024 73,024 320,344 601,144 651,544 651,544 43,110 667,350 3,626,670 8,022,990 9,529,950 9,529,950 Enum EnmTime 0.01 0.08 0.29 0.37 0.38 0.41 0.02 0.15 0.66 1.26 1.61 1.23 0.13 1.52 7.09 16.97 25.42 44.92 MdlTime 0.36 1.19 4.97 6.53 6.63 6.60 0.23 2.31 7.55 24.59 35.32 35.93 2.73 36.95 MO MO MO MO SolTime 0.37 1.27 5.26 6.90 7.02 7.01 0.25 2.47 8.21 25.85 36.93 37.15 2.86 38.47 MO MO MO MO EnmNum 959 2,607 3,513 3,603 3,603 3,603 1,314 4,064 6,125 6,515 6,525 6,525 7,635 33,645 58,306 64,412 64,711 64,711 Enum+ EnmTime 0.73 2.17 3.20 3.24 3.25 3.32 1.02 3.36 5.59 6.22 6.39 6.38 5.50 29.70 55.77 66.37 73.27 94.79 MdlTime 0.13 0.17 0.25 0.24 0.24 0.24 0.09 0.29 0.45 0.47 0.50 0.50 0.90 11.94 14.53 14.92 9.25 10.26 SolTime 0.87 2.34 3.45 3.49 3.49 3.56 1.11 3.65 6.04 6.69 6.89 6.88 6.40 41.64 70.31 81.30 82.51 105.05

© 2026 NTT West, Inc. All Rights Reserved. 61 /79 軽く紹介 ③CG とEnum+の計算結果（1/3） ◼ 𝑊 = 9に対する，CG，Enum+，TOM59Modelの計算結果を示す ◼ Enum+は全ての問題例で厳密に解いて探索を終了した時間が小さい |𝐽| 18 18 18 18 18 18 20 20 20 20 20 20 36 36 36 36 36 36 |𝑆| 7 7 7 7 7 7 8 8 8 8 8 8 14 14 14 14 14 14 𝜈 3 4 5 6 7 8 3 4 5 6 7 8 3 4 5 6 7 8 Opt 7,363 6,889 6,741 6,741 6,741 6,741 7,230 6,856 6,626 6,626 6,626 6,626 14,251 13,727 13,387 13,387 13,387 13,387 SolTime 147.08 TL TL TL TL TL TL TL TL TL TL TL TL TL TL TL TL TL CG1-(18) ArrTime 3 265 226 58 1,006 72 6 1,568 2,174 2,543 1,182 1,599 490 2,032 3,463 2,554 1,547 1,786 UB *7,363 *6,889 *6,741 *6,741 *6,741 *6,741 *7,230 *6,856 *6,626 *6,626 6,627 6,627 *14,251 13,803 13,478 13,813 13,804 13,532 Enum+ SolTime 0.87 2.34 3.45 3.49 3.49 3.56 1.11 3.65 6.04 6.69 6.89 6.88 6.40 41.64 70.31 81.30 82.51 105.05 ArrTime 0 2 3 3 3 3 1 3 6 6 6 6 6 39 70 81 81 104 SolTime TL TL TL TL TL TL TL TL TL TL TL TL TL TL TL TL TL TL TOM59Model ArrTime 1,265 3,205 3,176 960 2,682 1,999 162 3,497 1,172 407 344 3,584 3,281 3,399 3,189 3,486 3,081 3,597 UB *7,363 6,981 6,750 6,977 6,898 6,747 *7,230 7,055 6,733 7,337 7,281 6,717 15,321 15,368 17,439 16,739 15,115 22,876

© 2026 NTT West, Inc. All Rights Reserved. 62 /79 軽く紹介 ③CG とEnum+の計算結果（2/3） ◼ 𝑊 = 18に対する，CG，Enum+，TOM59Modelの計算結果を示す ◼ Enum+は一部を除いた問題例で厳密に解いて探索を終了した時間が小さい ◼ その一部の問題例でEnum+は計算中にメモリ不足で実行可能解が得られなかった ◼ CGとTOM59Modelは，問題例を厳密に解くのに要する時間はEnum+よりも大き い場合が多く，制限時間内に計算が終了せずTLと記されているものが多いが，全 ての問題例に対して制限時間内に実行可能解を得た |𝐽| 18 18 18 18 18 18 20 20 20 20 20 20 36 36 36 36 36 36 |𝑆| 7 7 7 7 7 7 8 8 8 8 8 8 14 14 14 14 14 14 𝜈 3 4 5 6 7 8 3 4 5 6 7 8 3 4 5 6 7 8 Opt 7,363 6,755 6,297 5,652 5,652 5,652 7,230 6,507 5,966 5,823 5,630 5,630 14,251 12,915 11,940 UNK UNK 11,226 SolTime TL TL TL 1,347.61 936.06 1,275.87 90.92 TL TL TL TL TL TL TL TL TL TL TL CG1-(18) ArrTime 3 398 123 239 88 61 8 29 57 769 2,615 258 343 3,010 2,640 2,900 3,314 3,226 UB *7,363 *6,755 *6,297 *5,652 *5,652 *5,652 *7,230 *6,507 *5,966 5,827 *5,630 5,632 *14,251 13,046 11,944 11,755 11,760 11,299 Enum+ SolTime 1.39 6.34 23.67 71.01 159.08 241.95 1.78 9.34 39.17 136.72 335.80 596.03 11.17 109.03 800.57 MO MO MO ArrTime 1 5 23 69 158 239 0 8 38 132 335 595 10 104 799 MO MO MO SolTime TL TL TL TL TL TL TL TL TL TL TL TL TL TL TL TL TL TL TOM59Model ArrTime 119 3,476 2,421 1,721 1,794 2,391 1,897 1,036 1,948 3,424 3,000 2,385 1,533 22 1,949 2,980 3,496 3,103 UB *7,363 6,757 6,314 5,736 5,656 5,845 *7,230 6,511 6,083 5,966 6,171 5,870 14,540 26,666 14,329 16,316 14,711 17,550

© 2026 NTT West, Inc. All Rights Reserved. 63 /79 軽く紹介 ③CG とEnum+の計算結果（3/3） ◼ さきほどの問題例に比べて|𝑆|が小さい問題例に対する，計算結果を示す ◼ CG によって全て厳密に解けており，求解に要した時間はEnum+より小さい |𝐽| 15 15 15 15 15 18 18 18 20 20 |𝑆| 2 3 3 3 3 3 3 3 3 3 𝜈 8 5 6 7 8 6 7 8 7 8 Opt 7,686 7,690 7,611 7,117 7,093 9,428 9,367 8,978 9,761 9,761 SolTime 1.56 4.38 10.27 17.34 15.95 27.68 48.32 44.61 156.31 127.85 CG1-(18) ArrTime 1 2 7 9 9 10 11 22 103 36 UB *7,686 *7,690 *7,611 *7,117 *7,093 *9,428 *9,367 *8,978 *9,761 *9,761 Enum+ SolTime 33.35 5.78 13.50 23.16 29.02 45.23 101.11 152.31 216.04 372.46 ArrTime 33 5 13 23 29 45 101 152 216 372 SolTime TL 1,064.63 TL TL TL TL TL TL TL TL TOM59Model ArrTime 154 72 246 1,025 306 224 2,117 419 1,859 424 UB 7,688 *7,690 7,613 *7,117 7,289 *9,428 9,428 9,018 10,108 10,038

© 2026 NTT West, Inc. All Rights Reserved. 64 /79 Geocoding と Routes：実運用に向けた Maps 機能の拡張 Geocoding API（実運用案） Routes / Distance Matrix（拡張案） 工事情報は「住所」で届く（FAX・メール由来） 拠点→工事，工事→工事の道路上の移動時間を取得 住所 → 緯度・経度へ変換し，正確な位置を地図へ配置 直線距離ではなく実移動時間を割当・巡回のコストへ 現PoCは概略座標を生成して代用している 時間帯別の交通状況も反映可能 この例での Maps の役割 ＝ ①配置の可視化（現在）＋ ②移動時間の現実化（拡張） https://developers.google.com/maps/documentation/geocoding/guides-v3/overview?hl=ja https://developers.google.com/maps/documentation/distance-matrix/overview?hl=ja

• https://developers.google.com/maps/documentation/geocoding/guides-v3/overview?hl=ja
• https://developers.google.com/maps/documentation/distance-matrix/overview?hl=ja

© 2026 NTT West, Inc. All Rights Reserved. 65 /79 Maps JavaScript API：采配結果を地図上に可視化する 従来のアナログ運用 PoC（Cloud Run 上の Web アプリ） 地図を印刷した紙にアクリル板を重ねる 工事地点をマーカー表示 水性ペンで工事箇所に点を打つ 立会者の拠点を表示 1〜3件ずつグループ分けして担当を決める 担当者別ルートを色分けして描画 手配結果を写真に撮ってデータ化、板を消して次回へ 結果の全体俯瞰・ズームで詳細確認 → 1回の手配に約3時間。属人的で再現性がない → 最適化した采配結果を、現場がそのまま読める地図にする https://developers.google.com/maps/documentation/javascript/overview?hl=ja

• https://developers.google.com/maps/documentation/javascript/overview?hl=ja

© 2026 NTT West, Inc. All Rights Reserved. 66 /79 より実務で活用しやすいPoCをクラウドで提供 • 以下は，采配結果を地図上に可視化するPoCのGUI（ワンストップクラウド版） https://koujitachiai-504242909255.asianortheast1.run.app/

• https://koujitachiai-504242909255.asia-northeast1.run.app/

© 2026 NTT West, Inc. All Rights Reserved. まとめ ◼ まとめ • 数理最適化の実社会での活用事例として，工事立会者手配問題への適用を紹介した • 学術の寄与①（現場に寄り添う数理モデリング）：現場ヒアリングと修正を繰り返し，手配者 の思考・嗜好を再現する実用的な数理モデルと解の評価尺度を構築した．手配時間を1回3 時間から5分に短縮しつつ，ベテラン手配者と遜色ない手配結果を実現した • 学術の寄与②（アルゴリズム改善）：組合せ爆発に対し，制約生成法や集合被覆アプローチ 等の複数の定式化・求解法を比較し，実用的な時間で良質な解が得られることを確認した • 実務への接続（現場への展開方法・実行基盤・環境）：学術的な価値だけでなく現場目線 のUIを意識し，StreamlitによるPoCをクラウドで提供することで，現場との意思疎通と共有の しやすさを高めた • 数理最適化の学術的な価値は，現場に届く形で展開してはじめて社会実装につながる．この 基盤整備の先にあるのが，後半で述べる「数理最適化の民主化」である 67 /79

© 2026 NTT West, Inc. All Rights Reserved. 参考文献 [1] 国土交通省, インフラ老朽化対策 (平成27 年9 月11 日第2 回非社会保障ワーキング・グループ資料1-3 国土交通省資料). https://www5.cao.go.jp/keizaishimon/kaigi/special/reform/wg2/270911/agenda.html (Retrieved on October 13, 2019) [2] 国土交通省, 浅層埋設にあたっての安全対策について(2015 年7 月31 日第5 回無電柱化低コスト手法技術検討委員会資料3 浅層埋設にあたっての安全対策について). http://www.nilim.go.jp/lab/ucg/koho/k150731.html (Retrieved on October 13, 2019) [3] NTT 東日本, 電話ケーブル切ったら大へん (NTT 東日本東京事業部2018). http://kirenkyo.gr.jp/sites/default/files/doc/NTT higashi2018.pdf (Retrieved on October 13, 2019) [4] NTT 西日本, 管路・電柱等. https://www.ntt-west.co.jp/open/99guidebook/pdf/2-6syo.pdf (Retrieved on October 13, 2019) [5] 月刊ビジネスコミュニケーション, ワンストップサービスを提供するインフラネットのIT システム群. https://www.bcm.co.jp/magazine/00-02/html/052.html (Retrieved on October 13, 2019) [6] 一柳徳宏, 若松良彦, 能島裕介, 石渕久生, 多目的遺伝的局所探索アルゴリズムにおける局所探索適用個体の選択, システム制御情報学会論文誌, 23 (2010) 178–187. [7] 池上敦子, 問題把握の難しさ, 特集『21 世紀を最適化する女性たち』, オペレーションズ・リサーチ, 51 (2006) 388–391. [8] S. Umetani, M. Arakawa and M. Yagiura, Relaxation heuristics for the set multicover problem with generalized upper bound constraints, Computers and Operations Research, 93 (2018) 90–100. [9] H. Hashimoto, M. Yagiura and T. Ibaraki, An iterated localsearch algorithm for the time-dependent vehicle routingproblem with time windows, Discrete Optimization, 5 (2008) 434–456. [10] S. Lin and B. W. Kernighan, An effective heuristic algorithm for the travelingsalesman problem, Operations Research, 21 (1973) 498–516. [11] M. Yagiura and T. Ibaraki, Local Search, P.M. Pardalos and M.G.C. Resende (eds), Handbook of Applied Optimization, Oxford University Press (2002) 104–123. [12] G. Dantzig, R. Fulkerson, S. Johnson, Solution of a large-scale travelingsalesman problem, Journal of the Operations Research Society of America, 2 (1954), 393–410. [13] U. Pferschy, R. Stanek, Generating subtour elimination constraints for the TSP from pure integer solutions, Central European Jounal of Operations Research, 25 (2017), 231-260. [14] R. H. Pearce, Towards a General Fomulation of Lazy Constraints, Doctoral Dissertation, School of Mathematics and Physics, The University of Queensland, (2019). [15] P. Toth, D. Vigo, The Vihicle Routing Problem, SIAM, (2011). [16] D. L. Applegate, R. E. Bixby, V. Chvatal, W. J. Cook, The Traveling Salesman Problem, Promceton University Press, (2011). [17] H. Crowder, M. W. Padberg, Solving large-scale symmetric traveling salesman problems to optimality, Management Science, 26 (1980), 495-509. [18] 高須賀将秀, 柳浦睦憲, 工事手配業務に対する数理最適化の活用と意思決定の支援, 情報処理学会論文誌数理モデル化と応用, 14 (2021), 112–120. [19] 高須賀将秀, 呉偉, 柳浦睦憲, 工事立会者手配問題に対する制約生成法および集合被覆アプローチ, 情報処理学会論文誌数理モデル化と応用, 15 (2022), 1–10. 68 /79

• https://www5.cao.go.jp/keizaishimon/kaigi/special/reform/wg2/270911/agenda.html
• http://www.nilim.go.jp/lab/ucg/koho/k150731.html
• http://kirenkyo.gr.jp/sites/default/files/doc/NTT higashi2018.pdf
• https://www.ntt-west.co.jp/open/99guidebook/pdf/2-6syo.pdf
• https://www.bcm.co.jp/magazine/00-02/html/052.html

© 2026 NTT West, Inc. All Rights Reserved. 本日の流れ • 数理最適化とは？ • 万博を例に • LLMとの違い，使い分け • Google Map APIについて • Google Map×数理最適化 • 旅行プランアプリ • 自然文から1日旅行プランを作る ── 巡回順を決める（TSP） • インフラ保全業務アプリ • インフラ保全の工事立会者手配 ── 人と工事を割り当てる • 避難所配置計画アプリ • 避難所配置の最適化 ── 施設をどこに置くか（MCLP） 69 /79

© 2026 NTT West, Inc. All Rights Reserved. 70 /79 避難所配置計画 候補地 × 需要地点 × 距離 MCLP（最大被覆立地問題） 開設できる避難所の数に上限があるとき，避難可能距離 R 以内でカバーされる住民の 人口が最大になるように，避難所の開設場所を決める問題 施設配置問題の代表的な定式化のひとつ（Church & ReVelle, 1974） 同じ枠組みで扱える街づくりの課題 避難所・防災拠点 消防・救急 医療・保健施設 EV充電スタンド 物流・宅配拠点 公共施設・観光案内所 ● カバーされた住民 ● 未カバー

© 2026 NTT West, Inc. All Rights Reserved. 71 /79 避難所配置最適化アプリの全体像 人口データ（需要点） 東京23区＋多摩5市 484点の格子メッシュ 距離行列 dᵢⱼ Gurobi で MCLP 求解 Google Maps で可視化 緯度経度から直線距離 （本番は実移動時間へ） WLSライセンス／失敗時は PuLP＋CBC に自動フォールバック 選択避難所・カバー範囲 カバー／未カバー住民 候補避難所 56件 学校・区民会館・体育館 収容 500〜2500人 実装スタック バックエンド：FastAPI API ＋ バニラJS 最適化：Gurobi（優先）／ PuLP＋CBC（OSS フォールバック） フロント：Maps JavaScript レスポンスの solver フィールドでどちらのソルバーを使ったか判別可能 → 「商用ソルバーとOSSソルバーの両対応」 人口・候補データは発表用の疑似データ（e-Statの人口メッシュを模した合成）

© 2026 NTT West, Inc. All Rights Reserved. 72 /79 MCLP の定式化 記号 I：需要点（住民メッシュ）の集合 max Σᵢ pᵢ · xᵢ （カバー人口の最大化） J：候補避難所の集合 pᵢ：需要点 i の人口 dᵢⱼ：需要点 i と候補 j の距離 R：避難可能距離（カバー半径） P：開設可能な避難所数の上限 yⱼ ∈ {0,1}：避難所 j を開設するか xᵢ ∈ {0,1}：需要点 i がカバーされるか 開設数の上限 Σⱼ yⱼ ≤ P 開ける避難所は P ヵ所まで カバー条件 xᵢ ≤ Σⱼ∈Nᵢ yⱼ Nᵢ ＝ { j ∈ J : dᵢⱼ ≤ R } 半径 R 内に開設済み避難所があるときだけ「カバー」とみなす UIと対応：P＝「開設可能な避難所数」スライダー（1〜56）、R＝「避難可能距離」 スライダー（200〜5000m）

© 2026 NTT West, Inc. All Rights Reserved. 73 /79 収容人数制約 課題：近いというだけで割り当てると，特定の避難所に人口が集中してしまう（収容能力を超える） 追加する決定変数と目的関数 追加・変更される制約 zᵢⱼ ∈ {0,1}：需要点 i を避難所 j に割り当てるか Σⱼ∈Nᵢ zᵢⱼ ≤ 1 1つの需要点は高々1つの避難所へ max Σᵢ pᵢ · Σⱼ∈Nᵢ zᵢⱼ zᵢⱼ ≤ yⱼ 「カバーされるか」から「どこへ割り当てるか」へ解像度を上げる 開設した避難所にのみ割当できる Σᵢ pᵢ · zᵢⱼ ≤ capacityⱼ · yⱼ UIの「収容人数制約を有効化」チェックボックスで切替（use_capacity） 収容人数の上限を超えない デモではこの制約のON/OFFで，特定避難所への集中が解消される様子を見せる

© 2026 NTT West, Inc. All Rights Reserved. 74 /79 Google Maps の機能をどう使っているか Maps JavaScript API 地図表示・操作の土台。東京全域が収まる中心・ズームで初期化 Marker 候補避難所（グレー）／選択された避難所(緑・拡大)。ホバーで施設名・収容人数 Circle ── 3つの用途 ①カバー範囲（半径R の緑の輪）②人口密度の濃淡（コロプレス）③住民のカバー状態（青＝カバー／赤＝未カバー） レイヤートグル 「人口密度」「カバー範囲」「住民ポイント」を個別ON/OFF インタラクティブ再計算 P・R スライダー変更 → API再リクエスト → 地図を再描画 GeoJSON エクスポート 最適化結果をダウンロードし，GISツール連携や資料転記に利用 補足：HeatmapLayer は v3.65 で廃止 → 人口に応じ色分けした半透明円の「コロプレス方式」で代替（実務で直面する変化への対応）

© 2026 NTT West, Inc. All Rights Reserved. 75 /79 避難所配置最適化アプリ アプリ https://shelter-mclp504242909255.asianortheast1.run.app/ ソース https://github.com/mshdtksk /Facility-layoutproblem/tree/main

• https://shelter-mclp-504242909255.asia-northeast1.run.app/
• https://github.com/mshdtksk/Facility-layout-problem/tree/main

© 2026 NTT West, Inc. All Rights Reserved. 本日の流れ • 数理最適化とは？ • 万博を例に • LLMとの違い，使い分け • Google Map APIについて • Google Map×数理最適化 • 旅行プランアプリ • 自然文から1日旅行プランを作る ── 巡回順を決める（TSP） • インフラ保全業務アプリ • インフラ保全の工事立会者手配 ── 人と工事を割り当てる • 避難所配置計画アプリ • 避難所配置の最適化 ── 施設をどこに置くか（MCLP） • まとめ 76 /79

© 2026 NTT West, Inc. All Rights Reserved. 77 /79 街づくりにどう役立つか 1 2 3 4 5 見える化 比較可能 説明可能 合意形成 更新可能 サービス空白地域（未カバー住 民）を地図で共有できる 候補案を同じKPI（カバー率な ど）で比較できる 目的関数・制約・データが明示 され、結論の根拠を示せる 住民・行政・事業者が「同じ地 図」を見て議論できる 人口・道路・施設の変化に合わ せて再計算できる 最適化は政策を自動決定するものではない．前提（目的・制約・データ）を明示して，「より良い比較」を支える道具である

© 2026 NTT West, Inc. All Rights Reserved. 78 /79 3つの事例を同じフレームで見る ① 巡回順（旅行プラン） ② 割当（工事立会） ③ 配置（避難所） Mapsが供給 地点間の時間・渋滞・標高 工事・拠点の位置、移動（拡張） 需要・候補地・到達距離 決定変数 訪問地点と訪問順 担当者と訪問順 開設場所と需要割当 主な制約 時間枠・巡回・部分巡回路 スキル・勤務時間・重複 施設数・容量・カバー半径 最適化モデル Selective TSP（MILP） 割当＋ルーティング MCLP（＋容量制約） Google Maps ＝ 現実を数値化 ｜ 数理最適化 ＝ 選択を決める ｜ LLM ＝ 意図をつなぎ，説明する

© 2026 NTT West, Inc. All Rights Reserved. 79 /79 まとめ：街の課題を「測る → 選ぶ → 説明する」 MAPS OPTIMIZATION LLM 測る 選ぶ 説明する 現実世界を数値データへ 制約下で最良の選択へ 意図理解と対話・説明へ 実在施設・移動時間・渋滞・標高・人口をモ デルのパラメーターに変換する 巡回順・割当・配置を，目的関数と制約で説 明できる形で決定する 曖昧な要望を構造化し，結果を人に伝わる言 葉へ戻す Google Maps は「地図」ではなく，意思決定のデータ基盤になる．