みなさん、こんにちは。 データ/AI部でデータサイエンティストをしております廣田と申します。今回は家庭訪問を題材とし、教育業界への数理最適化技術の応用について語ってみたいと思います。「データサイエンティストなのに数理最適化の話？」と疑問に思われた方もいらっしゃるかと思いますので、まずはこの点についての補足から話を始めさせていただければと思います。
なぜ数理最適化の話をするのか
データ/AI部ではこれまで、サービスの利用ログや学習コンテンツデータ・アンケートデータ等、多種多様なデータを駆使して教育業界に様々な価値を生み出してきました。
その一方で、データ活用ではなく数理最適化技術で解決できる見込みのある課題にも数多く遭遇してきました。例えば時間割の自動作成問題などが挙げられます。これまではチームのリソース不足などの事情もあり、このような課題についてはなかなか検討が進められておりませんでした。最近になって本格的に検討が進められる体制が整ってきたため、今後バリバリ数理最適化技術も活用して価値を生み出していこうという決意表明もかねて、こちらのブログで数理最適化の話題を扱おうと考えた次第です。
ここでは読者に教育現場の課題を数理最適化技術で解決するイメージを具体的に持っていただくため、具体的な問題を1つ取り上げてみたいと思います。前述の時間割の自動作成問題については既存研究が数多くあるため、ここでは（筆者調べで）あまり見かけないテーマとして「家庭訪問」を取り上げたいと思います。
家庭訪問について
家庭訪問で学校の先生が自宅に訪問してきた経験、皆様はございますでしょうか。訪問される側は経験していても、訪問する側の視点に立つことはなかなか無いと思います。そこでここでは訪問する側、つまり先生側の視点で家庭訪問を見てみたいと思います。
先生が家庭訪問を行う主な目的としては
保護者と1対1でコミュニケーションをとる機会
児童・生徒の家の位置や周辺の環境の確認
が挙げられます。そのため、1家庭の訪問でもそれなりに時間が必要となります。小中学校において1クラスあたりの生徒・児童数は30人前後であることが多い1
ここで、この訪問計画の案出しが問題になります。クラスによって生徒・児童の家の位置の分布は異なるため、クラスごとに検討が必要です。全家庭が学校から近い位置にあれば、どういう順序でも先生の負担はそれほど変わらないでしょう。しかし、学校から遠い家庭が複数あるような場合では、回り方を工夫しないと先生の移動がかなり大変なものとなります。どうすれば良い塩梅で決められるか・・・？そこで数理最適化技術の出番となるわけです。
家庭訪問の訪問計画問題
まず解きたい問題を整理します。ここで最適化問題に落とし込むのにあたり、本記事では総移動距離が短い回り方を求めることを目的とすることにします。
入力
2地点間の距離（学校及び生徒の自宅の全ペアについて事前計算しておく）
制約
家庭訪問期間の日数
1日で訪問できる最大の家庭の数（各家庭で話す時間から概算）
各日のルートは、学校から出て学校に戻ってくるものとする
出力
総移動距離が短くなるような、各日における家庭の回り方
このように整理すれば、解きたい問題は「容量制約付き配送計画問題（Capacitated Vehicle Routing Problem、CVRP）」であることが見えてきます。
CVRPについての説明はこちらの記事 がわかりやすいと思います。こちらの記事で扱っている問題は「1箇所の倉庫に集められた荷物を複数のトラックを使って各店舗に配送する際に、トラックの総移動距離を最小化したい」というものですが、それと今回の問題を下記のように対応付ければ、今回の問題がCVRPになることはイメージできるかと思います。
トラックを用いた配送計画
家庭訪問の訪問計画
1台のトラック
ある日の先生
トラックの台数
家庭訪問期間の日数
トラックの最大積載量
先生が1日で訪問できる家庭の数
各トラックは倉庫から出発し、要望のあった荷物を各店舗に配り、倉庫へ帰ってくる
先生は各日において学校から出発し、各家庭を1回訪問し、学校へ帰ってくる
全トラックの移動距離の合計を最小化
期間中の先生の移動距離の合計を最小化
それでは実際に解いてみます。今回の問題のようによく知られた問題に対しては、それを解くためのライブラリが整備されていることも多いです。ここではGoogleの数理最適化ライブラリ OR-Tools を使ってみることにしましょう。 OR-Tools を利用してCVRPを解くサンプルコードがこちら に載っていますので、参考にして python でコーディングしていきます。
下記のコードは「1日7家庭までの制約の下で31家庭を5日かけて訪問する計画を立てる」といったコードです。実行前に pip install ortools networkx matplotlib で、必要なライブラリをインストールしてください。コードの詳しい説明は省略しますが、前述のサンプルコードにほぼ準拠しています。サンプルコードとの主な差異は2点で、問題用のデータセット生成処理と、結果の画像出力処理が追加されています。2地点間の移動距離については簡易的に直線距離をベースに計算しています。
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
import matplotlib.pyplot as plt
import networkx as nx
import math
def create_data_model ():
nodes = [
{'name' : 'School' , 'coord' : (0 , 0 )},
{'name' : '1' , 'coord' : (-330 , 200 )},
{'name' : '2' , 'coord' : (-300 , 300 )},
{'name' : '3' , 'coord' : (-220 , 250 )},
{'name' : '4' , 'coord' : (-50 , 100 )},
{'name' : '5' , 'coord' : (20 , 100 )},
{'name' : '6' , 'coord' : (150 , 220 )},
{'name' : '7' , 'coord' : (260 , 170 )},
{'name' : '8' , 'coord' : (370 , 40 )},
{'name' : '9' , 'coord' : (420 , 20 )},
{'name' : '10' , 'coord' : (-390 , -60 )},
{'name' : '11' , 'coord' : (-370 , -200 )},
{'name' : '12' , 'coord' : (-300 , -110 )},
{'name' : '13' , 'coord' : (-250 , -150 )},
{'name' : '14' , 'coord' : (-50 , -150 )},
{'name' : '15' , 'coord' : (10 , -300 )},
{'name' : '16' , 'coord' : (-50 , -250 )},
{'name' : '17' , 'coord' : (80 , -180 )},
{'name' : '18' , 'coord' : (200 , -200 )},
{'name' : '19' , 'coord' : (300 , -120 )},
{'name' : '20' , 'coord' : (370 , -150 )},
{'name' : '21' , 'coord' : (450 , -100 )},
{'name' : '22' , 'coord' : (-300 , 120 )},
{'name' : '23' , 'coord' : (-150 , 60 )},
{'name' : '24' , 'coord' : (-100 , 20 )},
{'name' : '25' , 'coord' : (450 , 370 )},
{'name' : '26' , 'coord' : (250 , 50 )},
{'name' : '27' , 'coord' : (-250 , -20 )},
{'name' : '28' , 'coord' : (-50 , -60 )},
{'name' : '29' , 'coord' : (120 , -100 )},
{'name' : '30' , 'coord' : (140 , -10 )},
{'name' : '31' , 'coord' : (180 , -50 )}
]
n_nodes = len (nodes)
school = 0
n_days = 5
capacities = [7 for _ in range (n_days)]
colors = ["r" , "g" , "b" , "c" , "m" ]
distance_matrix = [[0 for _ in range (n_nodes)] for _ in range (n_nodes)]
for from_node in range (n_nodes):
from_coord = nodes[from_node]['coord' ]
for to_node in range (n_nodes):
to_coord = nodes[to_node]['coord' ]
distance_matrix[from_node][to_node] = \
math.sqrt((from_coord[0 ] - to_coord[0 ]) ** 2 + (from_coord[1 ] - to_coord[1 ]) ** 2 )
data = dict ()
data['distance_matrix' ] = distance_matrix
data['demands' ] = [1 if n != school else 0 for n in range (n_nodes)]
data['vehicle_capacities' ] = capacities
data['num_vehicles' ] = n_days
data['depot' ] = school
data['nodes' ] = nodes
data['colors' ] = colors
return data
def draw_solution (data, manager, routing, solution, fig_name='output.png' ):
G = nx.DiGraph()
nodes = data['nodes' ]
G.add_nodes_from([node['name' ] for node in nodes])
for vehicle_id in range (data['num_vehicles' ]):
index = routing.Start(vehicle_id)
while not routing.IsEnd(index):
previous_node_index = manager.IndexToNode(index)
index = solution.Value(routing.NextVar(index))
node_index = manager.IndexToNode(index)
G.add_edge(
nodes[previous_node_index]['name' ],
nodes[node_index]['name' ],
color=data['colors' ][vehicle_id])
pos = {
node['name' ]: node['coord' ] for node in data['nodes' ]
}
edge_color = [edge['color' ] for edge in G.edges.values()]
nx.draw_networkx(G, pos=pos, arrowsize=15 , edge_color=edge_color, node_color='c' )
plt.savefig(fig_name)
print (f'Result: {fig_name}' )
def main ():
data = create_data_model()
manager = pywrapcp.RoutingIndexManager(len (data['distance_matrix' ]),
data['num_vehicles' ], data['depot' ])
routing = pywrapcp.RoutingModel(manager)
def distance_callback (from_index, to_index):
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['distance_matrix' ][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
def demand_callback (from_index):
from_node = manager.IndexToNode(from_index)
return data['demands' ][from_node]
demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
routing.AddDimensionWithVehicleCapacity(
demand_callback_index,
0 ,
data['vehicle_capacities' ],
True ,
'Capacity' )
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)
search_parameters.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.FromSeconds(1 )
solution = routing.SolveWithParameters(search_parameters)
if solution:
draw_solution(data, manager, routing, solution)
if __name__ == '__main__' :
main()
実行してみると下記のような結果が得られます。各日に回るルートが同じ色の矢印で表現されています。見た目的にも納得感のある結果が得られたのではないでしょうか。
得られた結果
ひとまず解を得ることはできましたが、様々な課題が残っています。このような課題については、実際に現場の先生や専門家と意見を交えながら解決策を探っていくことになります。
目的関数や制約の設定の妥当性
移動時間が不正確
実際の移動時間は直線距離でなく道のりに基づいて計算するべき
また、学校から遠く徒歩・公共交通を併用する必要がある家庭の場合は、その移動手段の違いも考慮して移動時間を計算するべき
特定の日時でしか家庭訪問の対応ができない家庭があった場合、その事情をどう解に組み込んでいくか
最後に
ここまで家庭訪問を題材に数理最適化の話をしてきましたが、そもそも最近は家庭訪問を行う学校・先生の数は減少傾向にあると耳にします。両親共働き家庭の増加や新型コロナの影響など様々な要因により、平日の昼間に学校の先生と保護者がオフラインコミュニケーションを行うことは困難になりつつあります。ではなぜこのような下火になりつつある題材を取り上げたのかと言えば、これまであまり光が当たらなかった話題であり、かつ数理最適化技術の面白さが光る話題だと考えたためです。
今回取り上げた題材をはじめとして、教育業界にはまだまだ数理最適化技術の活躍の余地が広く残されていると考えております。学校関係者及び数理最適化の研究者の方、教育現場を進化させるために何ができるか、一緒に考えていきませんか？
また、弊社ではミッション「子供の無限の可能性を解き放ち、学びの形を進化させる」に共感し、様々な課題に前向きに取り組んでいただける仲間を募集しております。興味を持たれた方はぜひ採用ページ からご連絡ください！
id:aereal
