---
title: 20250806_OptimizationNight_現場目線のUIを意識した数理最適化_投影用
tags: 
author: [mshdtksk](https://convert.docswell.com/user/3324212129)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/YJ6LYXPQEV.jpg?width=480
description: 20250806_OptimizationNight_現場目線のUIを意識した数理最適化_投影用 by mshdtksk
published: August 05, 25
canonical: https://convert.docswell.com/s/3324212129/5LVNX8-2025-08-05-191451
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/YJ6LYXPQEV.jpg)

© 2025 NTT West, Inc. All Rights Reserved
1 / 49
現場目線のUIを意識した数理最適化
Optimization Night #10
2025/8/6
高須賀 将秀


# Page. 2

![Page Image](https://bcdn.docswell.com/page/GJ51GXK274.jpg)

© 2025 NTT West, Inc. All Rights Reserved
2 / 49
自己紹介
たかすか
まさひで
高須賀 将秀
博士（情報学）（2023/3）
研究分野：組合せ最適化，数理最適化，オペレーションズ・リサーチ（OR），グラフ理論
所属：NTT西日本 デジタル改革推進部（2021/8～），
法政大学 デザイン工学部 兼任講師（2024/4～），個人事業（Udemy講師等）（2024/6～）
業務：データドリブン経営を牽引する立場
・データ活用基盤のシステム開発 ・データ分析手法の研究
・データ分析活用事例の提案 ・デジタル人材育成
資格：クラウド資格（AWS 15/15，MCP 39/48，GCP 12/12），
Microsoft Top Partner Engineer Award（2024），
AWS All Certifications Engineers（2024, 2025） ，
Snowflake Squad（2025）
高須賀将秀のホームページ


# Page. 3

![Page Image](https://bcdn.docswell.com/page/9E21YXW1JR.jpg)

© 2025 NTT West, Inc. All Rights Reserved
3 / 49
本日お話すること
• 数理最適化を用いた実務でのデータ分析事例について紹介する
• その中で実施する数値実験やその成果を現場の方に提示する際の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


# Page. 4

![Page Image](https://bcdn.docswell.com/page/D7YZG8L4JM.jpg)

© 2025 NTT West, Inc. All Rights Reserved
4 / 49
背景
◼ 近年道路等のインフラの老朽化が深刻な社会問題となっている
◼ インフラを補修する工事等の件数が増加している
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


# Page. 5

![Page Image](https://bcdn.docswell.com/page/VEN3GQ46E8.jpg)

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


# Page. 6

![Page Image](https://bcdn.docswell.com/page/Y799WDQR73.jpg)

© 2025 NTT West, Inc. All Rights Reserved
6 / 49
背景
◼ 与えられた全ての工事に対して立会者の割当を決定する問題である
◼ 移動距離や立会者のスキル等の様々な条件を考慮し割当を決定している
◼ 条件は万人共通の条件もあれば手配者の思考や嗜好によって異なるものもある
入力
出力
工事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


# Page. 7

![Page Image](https://bcdn.docswell.com/page/G789N3GGJD.jpg)

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


# Page. 8

![Page Image](https://bcdn.docswell.com/page/L7LWPVGXER.jpg)

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


# Page. 9

![Page Image](https://bcdn.docswell.com/page/4EM94GQ37W.jpg)

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


# Page. 10

![Page Image](https://bcdn.docswell.com/page/PERGWZ8R79.jpg)

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


# Page. 11

![Page Image](https://bcdn.docswell.com/page/P7XXP98Y7X.jpg)

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


# Page. 12

![Page Image](https://bcdn.docswell.com/page/37KWDPK47D.jpg)

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


# Page. 13

![Page Image](https://bcdn.docswell.com/page/LJ31RXZDE5.jpg)

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


# Page. 14

![Page Image](https://bcdn.docswell.com/page/8JDXY2R27G.jpg)

© 2025 NTT West, Inc. All Rights Reserved
14 / 49
軽く紹介
①現場の手配者による工事立会者の手配
◼ 目的関数や制約条件は曖昧であり手配者によって手配結果が異なる
◼ 良い手配結果と悪い手配結果はベテランの手配者には判定可能である
◼ スキルの高い手配者の思考を再現可能な数理モデルを構築する
合計難易度
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
過去の現場の手配者が実際に割り当てた結果


# Page. 15

![Page Image](https://bcdn.docswell.com/page/VEPP61WLE8.jpg)

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


# Page. 16

![Page Image](https://bcdn.docswell.com/page/27V23Y867Q.jpg)

© 2025 NTT West, Inc. All Rights Reserved
16 / 49
軽く紹介
①数理モデル構築の結果まとめ
◼ 高度な技能を有している手配者により意思決定が行われている工事立会者手配
業務に対し実用的な手配結果を算出可能な数理モデルを構築した
長期効果
短期効果
付随効果
過去の工事立会者手配業務
デジタルデータ活用による工事立会者手配業務
人件費
年間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となる.


# Page. 17

![Page Image](https://bcdn.docswell.com/page/5JGR39527L.jpg)

© 2025 NTT West, Inc. All Rights Reserved
17 / 49
軽く紹介
②提案した数理モデルから得られる解の評価
◼ 数理モデル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)
100
数理モデル3(α=40)
数理モデル4(α=30)
手配者の評価では現場の
結果と最も近い解は数理モ
デル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)
3(α=610)
数理モデル4(α=640)
数理モデル
3(α=1390)
数理モデル
数理モデル4(α=360)
良 20
9000
良
10000
11000
12000
13000
14000
15000
総移動時間[秒]
16000
3(α=770)
数理モデル4(α=970)
17000
18000
19000
悪


# Page. 18

![Page Image](https://bcdn.docswell.com/page/47QV5WZ9EP.jpg)

© 2025 NTT West, Inc. All Rights Reserved
18 / 49
軽く紹介
②解の相違度について
◼ 工事立会者手配問題は各立会者にいずれの工事を割り当て各立会者が自分に
割り当てられた工事をどういう順序で巡回するかを決定する問題である
◼ 解の基本構造である工事間の移動ルート【観点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】の相違度行列
相違度行列は正規化済


# Page. 19

![Page Image](https://bcdn.docswell.com/page/KE4M9KDR71.jpg)

© 2025 NTT West, Inc. All Rights Reserved
19 / 49
軽く紹介
②実データへの適用結果
◼ 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


# Page. 20

![Page Image](https://bcdn.docswell.com/page/L718KXZVJG.jpg)

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


# Page. 21

![Page Image](https://bcdn.docswell.com/page/G7WZDN9372.jpg)

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


# Page. 22

![Page Image](https://bcdn.docswell.com/page/4JZ1G39GE3.jpg)

© 2025 NTT West, Inc. All Rights Reserved
22 / 49
軽く紹介
③集合被覆アプローチによる定式化 (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


# Page. 23

![Page Image](https://bcdn.docswell.com/page/YE6LYXKQ7V.jpg)

© 2025 NTT West, Inc. All Rights Reserved
23 / 49
軽く紹介
③工事立会者手配問題の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 !


# Page. 24

![Page Image](https://bcdn.docswell.com/page/GE51GXP2J4.jpg)

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


# Page. 25

![Page Image](https://bcdn.docswell.com/page/9721YX61ER.jpg)

© 2025 NTT West, Inc. All Rights Reserved
25 / 49
軽く紹介
③制約生成法に基づく定式化 (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


# Page. 26

![Page Image](https://bcdn.docswell.com/page/DJYZG894EM.jpg)

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


# Page. 27

![Page Image](https://bcdn.docswell.com/page/V7N3GQL678.jpg)

© 2025 NTT West, Inc. All Rights Reserved
27 / 49
軽く紹介
③制約生成法に基づく定式化 (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


# Page. 28

![Page Image](https://bcdn.docswell.com/page/YJ99WD4RJ3.jpg)

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


# Page. 29

![Page Image](https://bcdn.docswell.com/page/GJ89N3QGED.jpg)

© 2025 NTT West, Inc. All Rights Reserved
29 / 49
軽く紹介
③実行可能なルート候補を削減した集合被覆アプローチによる定式化 (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
集合被覆アプローチを用いた定式化で解く


# Page. 30

![Page Image](https://bcdn.docswell.com/page/LJLWPVXX7R.jpg)

© 2025 NTT West, Inc. All Rights Reserved
30 / 49
軽く紹介
③工事立会者手配問題の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


# Page. 31

![Page Image](https://bcdn.docswell.com/page/47M94GL3JW.jpg)

© 2025 NTT West, Inc. All Rights Reserved
31 / 49
軽く紹介
③計算環境と問題例
■計算環境
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人の立会者からなる実データ


# Page. 32

![Page Image](https://bcdn.docswell.com/page/P7RGWZKRJ9.jpg)

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


# Page. 33

![Page Image](https://bcdn.docswell.com/page/PJXXP9LYJX.jpg)

© 2025 NTT West, Inc. All Rights Reserved
33 / 49
軽く紹介
③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


# Page. 34

![Page Image](https://bcdn.docswell.com/page/3JKWDPL4JD.jpg)

© 2025 NTT West, Inc. All Rights Reserved
34 / 49
軽く紹介
③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


# Page. 35

![Page Image](https://bcdn.docswell.com/page/LE31RX3D75.jpg)

© 2025 NTT West, Inc. All Rights Reserved
35 / 49
軽く紹介
③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


# Page. 36

![Page Image](https://bcdn.docswell.com/page/8EDXY242JG.jpg)

© 2025 NTT West, Inc. All Rights Reserved
36 / 49
軽く紹介
③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


# Page. 37

![Page Image](https://bcdn.docswell.com/page/V7PP61ML78.jpg)

© 2025 NTT West, Inc. All Rights Reserved
37 / 49
計算実験でStreamlitを利用
• 以下は，人のスキルを考慮した采配アルゴリズムが組込まれたPoCのGUI
数理モデルのパラメータ
入力データのアップロード


# Page. 38

![Page Image](https://bcdn.docswell.com/page/2JV23Y96JQ.jpg)

© 2025 NTT West, Inc. All Rights Reserved
38 / 49
計算実験でStreamlitを利用
• 以下は，人のスキルを考慮した采配アルゴリズムが組込まれたPoCのGUI
入力データを出力
入力データを出力
アルゴリズムの選択


# Page. 39

![Page Image](https://bcdn.docswell.com/page/5EGR39Z2JL.jpg)

© 2025 NTT West, Inc. All Rights Reserved
39 / 49
計算実験でStreamlitを利用
• 以下は，人のスキルを考慮した采配アルゴリズムが組込まれたPoCのGUI
アルゴリズムの選択
各アルゴリズムに
関するパラメータ
実行ボタン


# Page. 40

![Page Image](https://bcdn.docswell.com/page/4JQV5WL97P.jpg)

© 2025 NTT West, Inc. All Rights Reserved
計算実験でStreamlitを利用
• 以下は，人のスキルを考慮した采配アルゴリズムが組込まれたPoCのGUI
40 / 49


# Page. 41

![Page Image](https://bcdn.docswell.com/page/K74M9K5RJ1.jpg)

© 2025 NTT West, Inc. All Rights Reserved
41 / 49
計算実験でStreamlitを利用
• 以下は，人のスキルを考慮した采配アルゴリズムが組込まれたPoCのGUI
出力結果
（采配結果）
目的関数値
計算時間


# Page. 42

![Page Image](https://bcdn.docswell.com/page/LJ18KXWVEG.jpg)

© 2025 NTT West, Inc. All Rights Reserved
42 / 49
計算実験でStreamlitを利用
• 以下は，采配結果を地図上に可視化するPoCのGUI（not Streamlit）
データ入力タブ
データ出力タブ
投影のみ


# Page. 43

![Page Image](https://bcdn.docswell.com/page/GJWZDN63J2.jpg)

© 2025 NTT West, Inc. All Rights Reserved
43 / 49
計算実験でStreamlitを利用
• 以下は，采配結果を地図上に可視化するPoCのGUI（not Streamlit）
采配結果のcsvファイル
立会者データに関するcsvファイル
投影のみ
工事データに関するcsvファイル
工事間の距離データに
関するcsvファイル
工事難易度データに
関するcsvファイル


# Page. 44

![Page Image](https://bcdn.docswell.com/page/4EZ1G3YG73.jpg)

© 2025 NTT West, Inc. All Rights Reserved
44 / 49
計算実験でStreamlitを利用
• 以下は，采配結果を地図上に可視化するPoCのGUI（not Streamlit）
画像データに出力するボタン
数理モデルの重みに関するパラメータ
投影のみ
采配結果を地図上に可視化


# Page. 45

![Page Image](https://bcdn.docswell.com/page/Y76LYXDQJV.jpg)

© 2025 NTT West, Inc. All Rights Reserved
45 / 49
より実務で活用しやすいPoCをクラウドで提供
• 以下は，采配結果を地図上に可視化するPoCのGUI（ワンストップクラウド版）
投影のみ
https://st-app-setcoverproblem504242909255.asia-northeast1.run.app/


# Page. 46

![Page Image](https://bcdn.docswell.com/page/G751GX32E4.jpg)

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


# Page. 47

![Page Image](https://bcdn.docswell.com/page/9J21YXZ17R.jpg)

© 2023
2025 NTT West
West, Corporation.
Inc. All RightsAll
Reserved
Rights Reserved
まとめ
◼ まとめ
• 数理最適化を用いたより高度なデータ分析事例について紹介した
• その中で実施する数値実験やその成果を現場の方に提示する際のPoCとして
Streamlitを活用した
47 / 18
49


# Page. 48

![Page Image](https://bcdn.docswell.com/page/DEYZG8R47M.jpg)

© 2023
2025 NTT West
West, Corporation.
Inc. All RightsAll
Reserved
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.
48 / 18
49


# Page. 49

![Page Image](https://bcdn.docswell.com/page/VJN3GQD6J8.jpg)

© 2025 NTT West, Inc. All Rights Reserved
宣伝（Udemyコンテンツ）
• 簡単に数理最適化アプリが作れる！製造業における数理最適化の活用術
• 明日から役立つ「オペレーションズ・リサーチ概論」
49 / 49


