2023年 11月 10日
テクノロジー
OR-Toolsで巡回セールスマン問題、配送経路問題を解く方法について、具体例をもとに紹介いたします。
© OpenStreetMap contributors
社歴約7年、クラウドエンジニア歴約5年の新人だと思っているエンジニア。
普段はAWSを利用したサービスのバックエンド開発などを担当。
元々は宗教における重要な場所(=聖地)を訪れることを指していたようですが、転じてドラマやアニメ、映画、漫画、小説などの舞台となった場所やキャラクターゆかりの場所などを訪れることを指すようになりました。
かくいう私もアニメや映画化もされた某作品の舞台となっている沼津を何度か聖地巡礼しています。
頻繁に沼津に行けるわけでもないので1回訪れた際にたくさんの場所を訪問したいわけですが、北は沼津駅の方から南は内浦の方まで広い範囲に訪問したい場所が点在しています。
(有名な場所にピンを立てていますが特に内浦周辺は行きたい所がたくさんありますよね。)
さらに沼津駅から内浦まではバスがあるものの本数は決して多くないため基本的には車を使って聖地巡礼をすることになります。
はるばる沼津まで来たのなら限られた時間でたくさんの聖地を訪問したいですよね？
さらに訪問先が飲食店なら食事時に訪問したいですし訪問先の営業時間外にたどり着いても意味がありません。
このような問題をどうすればいいのか？いい感じに最短で行きたい場所すべて訪問する順番は出せないだろうか？
このような問題は巡回セールスマン問題と呼ばれています。
wikipediaによると「都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める」とのことです。※
今回はなるべく効率的に行きたい場所すべてを訪問して聖地巡礼したいのでぴったりですね。
※出典：wikipedia「巡回セールスマン問題」
wikipedia
Google が開発しているオープンソースのソフトウェアで、無料で使えます。
無料なのにコンペで上位入賞したりしているすごいやつです。
公式サイトのドキュメントも充実しており、気軽に動作を試してみることができます。
今回紹介する内容も公式の内容を参考にしております。
今回pythonを使ってプログラムを作りますがインストールもpipでインストールするだけなので簡単です。
Python の OR ツール
まずは5地点で一番最適な訪問順番を出してみます。
GoogleMapで行きたい場所を選んで緯度経度情報を入力しました。
# 訪問したい地点の情報
locations = [ { 'latitude': 35.10266448367594, 'longitude': 138.85979846067406, 'name': '沼津駅' }, { 'latitude': 35.08349715336418, 'longitude': 138.85742281084683, 'name': '沼津 みなと新鮮館' }, { 'latitude': 35.01947137458642, 'longitude': 138.89606797052375, 'name': '伊豆・三津シーパラダイス' }, { 'latitude': 35.03300162141432, 'longitude': 138.89353619333394, 'name': 'あわしまマリンパーク チケット売り場' }, { 'latitude': 35.02220580110969, 'longitude': 138.8979907729162, 'name': '松月' } ]
あわしまマリンパークは船を使わないと行けないので手前のチケット売り場にしています。
地図にプロットすると以下のとおりです。
さて、最適な訪問順番の算出にはある地点から別の地点へ移動したときにどれくらいの移動コストがかかるのかが必要になります。
この移動コストをすべての地点を訪問する場合に一番小さくなるような移動の順番を求めるというわけですね。
今回この移動コストには地点間の直線距離を使用します。
本来であればルート探索をして移動時間や移動距離を求めてそれを使うことが望ましいですが、5地点の場合5×(5-1)=20回もルート探索する必要があり、
地点数が増えれば増えるほどルート探索の回数も非常に多くなるので計算が簡単な直線距離で妥協します。
2点間の直線距離を求める簡単な関数は以下のようになります。
# 2地点間の直線距離[m]を求める
def calc_distance(lat1, lon1, lat2, lon2): # 地球の半径[m] R = 6371 * 1000 # ラジアンに変換 lat1 = math.radians(lat1) lat2 = math.radians(lat2) lon1 = math.radians(lon1) lon2 = math.radians(lon2) # 2点の中心角 delta_sigma = math.acos(math.sin(lat1) * math.sin(lat2) + math.cos(lat1) * math.cos(lat2) * math.cos(lon1 - lon2)) # 大円距離 distance = R * delta_sigma return distance
2点間の直線距離を、関数を使って任意の2地点の直線距離が格納された行列を作成します。
# 直線距離のマトリクスを求める
def calc_distance_matrix(locations): distance_matrix = {} for from_counter, from_node in enumerate(locations): distance_matrix[from_counter] = {} for to_counter, to_node in enumerate(locations): if from_counter == to_counter: # 2地点は全く同じ場所なので距離は0 distance_matrix[from_counter][to_counter] = 0 else: # 2地点間の直線距離を求める distance_matrix[from_counter][to_counter] = int( calc_distance( from_node['latitude'], from_node['longitude'], to_node['latitude'], to_node['longitude'] ) ) return distance_matrix
次に、Routing Managerを作成します。
RoutingIndexManagerを作成する際に、訪問したい地点の数や使う車両の数、depotのindexについて記述します。
配達業務などでは複数台使うこともあると思いますが、今回使う車両の数は1台です。
またdepotとは配送基地のことでその場所からスタートしてその場所に戻ってくる場所のことです。
indexは指定した地点情報(このプログラムではlocations)に上から0,1,2…と振られる番号のことで、今回はlocationsの一番上にある沼津駅を出発して沼津駅に戻ってくるときの順番を求めてもらいます。
# Routing Managerを作成
manager = pywrapcp.RoutingIndexManager( len(locations), # 訪問したい地点の数 1, # 使う車両の数 0 # depotのindex ) routing = pywrapcp.RoutingModel(manager)
Routing Modelを作成します。
# Routing Modelを作成
routing = pywrapcp.RoutingModel(manager)
先程作成したRouting Modelに対して様々な制約や条件を追加していきます。
from_indexからto_indexに向かう際の移動コストを直線距離のマトリクスから見つけるコールバックを用意して、Arc Costを設定する関数に入れます。
# 直線距離のマトリクスを求める
distance_matrix = calc_distance_matrix(locations) def distance_callback(from_index, to_index): from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) return distance_matrix[from_node][to_node] transit_callback_index = routing.RegisterTransitCallback(distance_callback) # Arc Costの設定 routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
解を求める際に使うパラメータなどの設定をします。
初期解の求め方や、解を求める際の制限時間などを指定できますが、まずは公式サイトの条件を利用します。
# 解を求める際に使うパラメータなどの設定
search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC )
求まった解の結果を表示する関数も用意します。
こちらはOR-Toolsの公式サイトのものをそのまま使用しています。
# 結果を出力する
def print_solution(manager, routing, solution): print(f"Objective: {solution.ObjectiveValue()}") index = routing.Start(0) plan_output = "Route: n" route_distance = 0 while not routing.IsEnd(index): plan_output += f" {manager.IndexToNode(index)} ->" previous_index = index index = solution.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle(previous_index, index, 0) plan_output += f" {manager.IndexToNode(index)} n" print(plan_output) plan_output += f"Objective: {route_distance}m n"
最後に解を求めて結果を表示します。
制約や条件によっては、解は求まらないこともあるため求まった場合のみ結果を表示します。
# 解を求める
solution = routing.SolveWithParameters(search_parameters) # 解が見つかれば表示する if solution: print_solution(manager, routing, solution)
プログラム全体ではこのようになります。
simple_tsp.py
import math from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp # 2地点間の直線距離[m]を求める def calc_distance(lat1, lon1, lat2, lon2): # 地球の半径[m] R = 6371 * 1000 # ラジアンに変換 lat1 = math.radians(lat1) lat2 = math.radians(lat2) lon1 = math.radians(lon1) lon2 = math.radians(lon2) # 2点の中心角 delta_sigma = math.acos(math.sin(lat1) * math.sin(lat2) + math.cos(lat1) * math.cos(lat2) * math.cos(lon1 - lon2)) # 大円距離 distance = R * delta_sigma return distance # 直線距離のマトリクスを求める def calc_distance_matrix(locations): distance_matrix = {} for from_counter, from_node in enumerate(locations): distance_matrix[from_counter] = {} for to_counter, to_node in enumerate(locations): if from_counter == to_counter: # 2地点は全く同じ場所なので距離は0 distance_matrix[from_counter][to_counter] = 0 else: # 2地点間の直線距離を求める distance_matrix[from_counter][to_counter] = int( calc_distance( from_node['latitude'], from_node['longitude'], to_node['latitude'], to_node['longitude'] ) ) return distance_matrix # 結果を出力する def print_solution(manager, routing, solution): print(f"Objective: {solution.ObjectiveValue()}") index = routing.Start(0) plan_output = "Route: n" route_distance = 0 while not routing.IsEnd(index): plan_output += f" {manager.IndexToNode(index)} ->" previous_index = index index = solution.Value(routing.NextVar(index)) route_distance += routing.GetArcCostForVehicle(previous_index, index, 0) plan_output += f" {manager.IndexToNode(index)} n" print(plan_output) plan_output += f"Objective: {route_distance}m n" def main(): # 訪問したい地点の情報 locations = [ { 'latitude': 35.10266448367594, 'longitude': 138.85979846067406, 'name': '沼津駅' }, { 'latitude': 35.08349715336418, 'longitude': 138.85742281084683, 'name': '沼津 みなと新鮮館' }, { 'latitude': 35.01947137458642, 'longitude': 138.89606797052375, 'name': '伊豆・三津シーパラダイス' }, { 'latitude': 35.03300162141432, 'longitude': 138.89353619333394, 'name': 'あわしまマリンパーク チケット売り場' }, { 'latitude': 35.02220580110969, 'longitude': 138.8979907729162, 'name': '松月' } ] # Routing Managerを作成 manager = pywrapcp.RoutingIndexManager( len(locations), # 訪問したい地点の数 1, # 使う車両の数 0 # depotのindex ) # Routing Modelを作成 routing = pywrapcp.RoutingModel(manager) # 直線距離のマトリクスを求める distance_matrix = calc_distance_matrix(locations) def distance_callback(from_index, to_index): from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) return distance_matrix[from_node][to_node] transit_callback_index = routing.RegisterTransitCallback(distance_callback) # Arc Costの設定 routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # 解を求める際に使うパラメータなどの設定 search_parameters = pywrapcp.DefaultRoutingSearchParameters() search_parameters.first_solution_strategy = ( routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC ) # 解を求める solution = routing.SolveWithParameters(search_parameters) # 解が見つかれば表示する if solution: print_solution(manager, routing, solution) if __name__ == '__main__': main()
このプログラムを実行してみると以下のような結果が得られます。
Objective: 20032
Route:
0 -> 1 -> 2 -> 4 -> 3 -> 0
移動距離は約20kmでindexを元の名称に戻すと
沼津駅 -> 沼津 みなと新鮮館 -> 伊豆・三津シーパラダイス -> 松月 -> あわしまマリンパーク チケット売り場 -> 沼津駅
新鮮館からみとしーまで南下してから徐々に北上するのがいいみたいです。
しかしあくまで考慮しているのは直線距離であり、実際に車を走らせたときの距離とは異なってきます。
また各訪問先には営業時間がありますし、レストランであればお昼時に向かいたいですよね。
次はこういった時間の制約について考慮して最適なルートを求めていきたいと思います。
沼津駅から日帰りで聖地を巡ってみることにします。
以下の場所を用意しました。
"locations": [
{
"latitude": 35.10266448367594,
"longitude": 138.85979846067406,
"name": "沼津駅"
},
{
"latitude": 35.02135312342376,
"longitude": 138.88337230056888,
"name": "沼津市立長井崎小中一貫学校",
"service_time": "5m"
},
{
"latitude": 35.02415498831253,
"longitude": 138.89893140564527,
"name": "おさかな食堂 やまや",
"open": "11:30",
"close": "14:30",
"service_time": "45m"
},
{
"latitude": 35.08398178305709,
"longitude": 138.85730512626486,
"name": "沼津みなと新鮮館 駐車場",
"open": "7:30",
"close": "10:00",
"service_time": "30m"
},
{
"latitude": 35.01947137458642,
"longitude": 138.89606797052375,
"name": "伊豆・三津シーパラダイス",
"open": "9:00",
"close": "17:00",
"service_time": "1.5h"
},
{
"latitude": 35.017737822261495,
"longitude": 138.89333064220483,
"name": "三の浦総合案内所",
"open": "9:00",
"close": "17:00",
"service_time": "10m"
},
{
"latitude": 35.02046373505879,
"longitude": 138.89749166076285,
"name": "安田屋旅館",
"service_time": "5m"
},
{
"latitude": 35.08403714990312,
"longitude": 138.8583024589409,
"name": "沼津港深海水族館",
"open": "10:00",
"close": "18:00",
"service_time": "1.5h"
},
{
"latitude": 35.03283174332945,
"longitude": 138.8938840863703,
"name": "あわしまマリンパーク 駐車場",
"open": "9:30",
"close": "17:00",
"service_time": "1.5h"
}
]
ここでのservice_timeはその場所における滞在時間です。
あわしまやみとしーは長めにとっています。一方で日帰りなので安田屋はチラ見して終わりです。
長井崎は浦の星女学院のモデルとなった学校なのでぜひ行っておきたいですが今も使われているのであまり長居はしません。
新鮮館の中にある丸勘で朝食を、やまやで昼食を食べたいのでこのような時間の指定をしています。
さて、ここでlocationsからmatrixを求めたいのですが今回は時間について最適化を行うために2地点間の移動時間が知りたいです。
となるとlocationsから2地点を選んでルート探索を行い所要時間を求めることを全組み合わせに対して行う必要があります。
1回ずつルート探索するとかなり大変なので今回は1発で簡単にこのmatrixを求めるために弊社ルートマトリクスAPIを使うことにします。
ルートマトリクスAPIとは
複数地点間（最大25地点）の運行距離や所要時間をまとめて算出することができます。
POSTメソッドを使用し、データフォーマットはJSON形式のため、容易に関発可能です。
詳しくはこちら
求めた時間のmatrix結果など最適化に必要なパラメータを作る関数が以下になります。
def create_data_model():
data = {}
data['name'] = [
'沼津駅',
'沼津市立長井崎小中一貫学校',
'おさかな食堂 やまや',
'沼津みなと新鮮館 駐車場',
'伊豆・三津シーパラダイス',
'三の浦総合案内所',
'安田屋旅館',
'沼津港深海水族館',
'あわしまマリンパーク 駐車場'
]
data['time_matrix'] = [
[ 0, 2281, 1750, 371, 1869, 1904, 1827, 430, 1589],
[2183, 0, 471, 2020, 431, 346, 397, 2013, 629],
[1724, 468, 0, 1561, 106, 141, 64, 1554, 189],
[ 361, 2132, 1601, 0, 1720, 1755, 1678, 74, 1440],
[1804, 409, 112, 1641, 0, 82, 38, 1634, 270],
[1840, 342, 148, 1677, 108, 0, 74, 1670, 306],
[1765, 403, 73, 1602, 41, 76, 0, 1595, 231],
[ 431, 2168, 1637, 36, 1756, 1791, 1714, 0, 1476],
[1559, 636, 191, 1396, 274, 309, 232, 1389, 0]
]
data['time_windows'] = [
(0, 32400),
(0, 32400),
(12600, 21600),
(0, 7200),
(3600, 32400),
(3600, 32400),
(0, 32400),
(7200, 32400),
(3600, 32400)
]
data['service_time'] = [
0,
300,
2700,
1800,
5400,
600,
300,
5400,
5400
]
data['num_vehicles'] = 1
data['depot'] = 0
data['time_limit'] = 32400
data['start_time'] = 8
return data
沼津駅を8:00に出発して17:00に戻ってくるとします。
沼津駅周辺にも訪れたいスポットはたくさんありますが駅周辺は駐車場の問題があり、徒歩でも十分回れる距離なので駅に戻って駐車場に止めるなりレンタカーを返すなりしてから駅周辺を散策しようと思います。
駅周辺の施設は18:00くらいで閉まる事が多いので1時間で巡りましょう。
弊社ルートマトリクスAPIで得られる所要時間は秒なのでこのプログラム中で時間の単位は秒で統一しています。
8:00に出発して17:00が制限時間なので秒に直すと32400秒。nameやstart_timeは結果をprintするときに場所や時刻を見やすくするために用意しています。
time_windowsはその訪問先に訪問していい時間で指定した時間の範囲内で訪問するような制約を指定する際に使用します。
8:00が0秒、17:00が32400秒なのでいつでも訪問していい場所の場合は(0, 32400)となり、時間の制約がある場合はそれより範囲が小さくなります。
また、8:00より早くから営業していたり、17:00より遅くに営業終了するような場合はそれぞれ0、32400になります。
service_timeはその場所における滞在時間なので秒で滞在時間を指定します。
起終点である沼津駅は0を指定します。
create_data_model()を使って今回の最適化で使うパラメータを作り、Routing ManagerとRouting Modelを作ります。
data = create_data_model()
# Routing Managerを作成
manager = pywrapcp.RoutingIndexManager(
len(data['time_matrix']), # 訪問したい地点の数
data['num_vehicles'], # 使う車両の数
data['depot'] # depotのindex
)
# Routing Modelを作成
routing = pywrapcp.RoutingModel(manager)
このあたりはさっきとほぼ同じですね。
先程作成したRouting Modelに対して様々な制約や条件を追加していきます。
from_indexからto_indexに向かう際の移動コストを今回は時間のマトリクスから見つけるコールバックを用意します。
今回は訪問先での滞在時間があるので移動時間＋滞在時間を返すコールバックになります。
できたコールバックはArc Costを設定する関数に入れます。
# 移動時間のコールバックを用意する
def time_callback(from_index, to_index): from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) travel_time = data['time_matrix'][from_node][to_node] service_time = data['service_time'][from_node] # 移動時間と訪問先での滞在時間を足し合わせる return travel_time + service_time transit_callback_index = routing.RegisterTransitCallback(time_callback) # Arc Costの設定 routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
今回のプログラムで重要になってくる訪問先に訪れていい時間の制約についてです。
時間に関する次元をAddDimension()で用意し、各訪問先、車両毎に時間の制約を追加します。
# 訪問先の訪問時間の制約を追加する
time = 'Time' routing.AddDimension( transit_callback_index, data['time_limit'], # 訪問先での最大待機時間 data['time_limit'], # 車両ごとの最大移動時間 True, # 0からスタートを強制しない time) time_dimension = routing.GetDimensionOrDie(time) # depot以外の各訪問先について時間の制約を追加する for location_idx, time_window in enumerate(data['time_windows']): if location_idx == data['depot']: continue index = manager.NodeToIndex(location_idx) time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1]) if len(data['time_windows']) > 0: # 時間の制約を各車両に追加する depot_idx = data['depot'] for vehicle_id in range(data['num_vehicles']): index = routing.Start(vehicle_id) time_dimension.CumulVar(index).SetRange( data['time_windows'][depot_idx][0], data['time_windows'][depot_idx][1])
時間の次元はなるべく小さい方がいいのでなるべく最小化するような指定をします。
# ルートの開始時刻と終了時刻をインスタンス化し、実現可能な時刻を生成する
for i in range(data['num_vehicles']): routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.Start(i))) routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i)))
そして、解を求める際に使うパラメータなどの設定をします。
local_search_metaheuristicにはこういったルート最適化に向いているGUIDED_LOCAL_SEARCHを使用します。
GUIDED_LOCAL_SEARCHを用いると、よさげな解が見つかっても探索がなかなか終わらないため時間の上限を決めたほうがよいです。
# 解を求める際に使うパラメータなどの設定
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.seconds = 1
求まった解の結果を表示する関数も用意します。
こちらはOR-Toolsの公式サイトのものから結果が見やすいように少し改変しています。
def print_solution(data, manager, routing, solution):
print(f'Objective: {solution.ObjectiveValue()}')
time_dimension = routing.GetDimensionOrDie('Time')
total_time = 0
for vehicle_id in range(data['num_vehicles']):
index = routing.Start(vehicle_id)
plan_output = 'Route for vehicle {}: n'.format(vehicle_id)
while not routing.IsEnd(index):
time_var = time_dimension.CumulVar(index)
plan_output += '{0} (到着{1},出発{2}) -> '.format(
data['name'][manager.IndexToNode(index)],
datetime.timedelta(hours=data['start_time'], seconds=solution.Min(time_var)),
datetime.timedelta(hours=data['start_time'], seconds=solution.Max(time_var) + data['service_time'][manager.IndexToNode(index)])
)
index = solution.Value(routing.NextVar(index))
time_var = time_dimension.CumulVar(index)
plan_output += '{0} (到着{1},出発{2}) n'.format(
data['name'][manager.IndexToNode(index)],
datetime.timedelta(hours=data['start_time'], seconds=solution.Min(time_var)),
datetime.timedelta(hours=data['start_time'], seconds=solution.Max(time_var) + data['service_time'][manager.IndexToNode(index)])
)
plan_output += 'Time of the route: {} n'.format(
datetime.timedelta(seconds=solution.Min(time_var)))
print(plan_output)
total_time += solution.Min(time_var)
print('Total time of all routes: {}'.format(datetime.timedelta(seconds=total_time)))
最後に解を求めて結果を表示します。
制約や条件によっては解は求まらないこともあるので求まった場合のみ結果を表示します。
# 解を求める
solution = routing.SolveWithParameters(search_parameters) # 解が見つかれば表示する if solution: print_solution(data, manager, routing, solution) else: print('No solution found.')
プログラム全体ではこのようになります。
advanced_vrp.py
from ortools.constraint_solver import routing_enums_pb2 from ortools.constraint_solver import pywrapcp import datetime def create_data_model(): data = {} data['name'] = [ '沼津駅', '沼津市立長井崎小中一貫学校', 'おさかな食堂 やまや', '沼津みなと新鮮館 駐車場', '伊豆・三津シーパラダイス', '三の浦総合案内所', '安田屋旅館', '沼津港深海水族館', 'あわしまマリンパーク 駐車場' ] data['time_matrix'] = [ [ 0, 2281, 1750, 371, 1869, 1904, 1827, 430, 1589], [2183, 0, 471, 2020, 431, 346, 397, 2013, 629], [1724, 468, 0, 1561, 106, 141, 64, 1554, 189], [ 361, 2132, 1601, 0, 1720, 1755, 1678, 74, 1440], [1804, 409, 112, 1641, 0, 82, 38, 1634, 270], [1840, 342, 148, 1677, 108, 0, 74, 1670, 306], [1765, 403, 73, 1602, 41, 76, 0, 1595, 231], [ 431, 2168, 1637, 36, 1756, 1791, 1714, 0, 1476], [1559, 636, 191, 1396, 274, 309, 232, 1389, 0] ] data['time_windows'] = [ (0, 32400), (0, 32400), (12600, 21600), (0, 7200), (3600, 32400), (3600, 32400), (0, 32400), (7200, 32400), (3600, 32400) ] data['service_time'] = [ 0, 300, 2700, 1800, 5400, 600, 300, 5400, 5400 ] data['num_vehicles'] = 1 data['depot'] = 0 data['time_limit'] = 32400 data['start_time'] = 8 return data def print_solution(data, manager, routing, solution): print(f'Objective: {solution.ObjectiveValue()}') time_dimension = routing.GetDimensionOrDie('Time') total_time = 0 for vehicle_id in range(data['num_vehicles']): index = routing.Start(vehicle_id) plan_output = 'Route for vehicle {}: n'.format(vehicle_id) while not routing.IsEnd(index): time_var = time_dimension.CumulVar(index) plan_output += '{0} (到着{1},出発{2}) -> '.format( data['name'][manager.IndexToNode(index)], datetime.timedelta(hours=data['start_time'], seconds=solution.Min(time_var)), datetime.timedelta(hours=data['start_time'], seconds=solution.Max(time_var) + data['service_time'][manager.IndexToNode(index)]) ) index = solution.Value(routing.NextVar(index)) time_var = time_dimension.CumulVar(index) plan_output += '{0} (到着{1},出発{2}) n'.format( data['name'][manager.IndexToNode(index)], datetime.timedelta(hours=data['start_time'], seconds=solution.Min(time_var)), datetime.timedelta(hours=data['start_time'], seconds=solution.Max(time_var) + data['service_time'][manager.IndexToNode(index)]) ) plan_output += 'Time of the route: {} n'.format( datetime.timedelta(seconds=solution.Min(time_var))) print(plan_output) total_time += solution.Min(time_var) print('Total time of all routes: {}'.format(datetime.timedelta(seconds=total_time))) def main(): data = create_data_model() # Routing Managerを作成 manager = pywrapcp.RoutingIndexManager( len(data['time_matrix']), # 訪問したい地点の数 data['num_vehicles'], # 使う車両の数 data['depot'] # depotのindex ) # Routing Modelを作成 routing = pywrapcp.RoutingModel(manager) # 移動時間のコールバックを用意する def time_callback(from_index, to_index): from_node = manager.IndexToNode(from_index) to_node = manager.IndexToNode(to_index) travel_time = data['time_matrix'][from_node][to_node] service_time = data['service_time'][from_node] # 移動時間と訪問先での滞在時間を足し合わせる return travel_time + service_time transit_callback_index = routing.RegisterTransitCallback(time_callback) # Arc Costの設定 routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index) # 訪問先の訪問時間の制約を追加する time = 'Time' routing.AddDimension( transit_callback_index, data['time_limit'], # 訪問先での最大待機時間 data['time_limit'], # 車両ごとの最大移動時間 True, # 0からスタートを強制しない time) time_dimension = routing.GetDimensionOrDie(time) # depot以外の各訪問先について時間の制約を追加する for location_idx, time_window in enumerate(data['time_windows']): if location_idx == data['depot']: continue index = manager.NodeToIndex(location_idx) time_dimension.CumulVar(index).SetRange(time_window[0], time_window[1]) if len(data['time_windows']) > 0: # 時間の制約を各車両に追加する depot_idx = data['depot'] for vehicle_id in range(data['num_vehicles']): index = routing.Start(vehicle_id) time_dimension.CumulVar(index).SetRange( data['time_windows'][depot_idx][0], data['time_windows'][depot_idx][1]) # ルートの開始時刻と終了時刻をインスタンス化し、実現可能な時刻を生成する。 for i in range(data['num_vehicles']): routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.Start(i))) routing.AddVariableMinimizedByFinalizer(time_dimension.CumulVar(routing.End(i))) # 解を求める際に使うパラメータなどの設定 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.seconds = 1 # 解を求める solution = routing.SolveWithParameters(search_parameters) # 解が見つかれば表示する if solution: print_solution(data, manager, routing, solution) else: print('No solution found.') if __name__ == '__main__': main()
このプログラムを実行してみると以下のような結果が得られます。
Objective: 26699
Route for vehicle 0:
沼津駅 (到着8:00:00,出発8:00:00) -> 沼津みなと新鮮館 駐車場 (到着8:06:11,出発9:58:46) -> 沼津港深海水族館 (到着10:00:00,出発11:30:00) -> おさかな食堂 やまや (到着11:57:17,出発12:42:17) -> 安田屋旅館 (到着12:43:21,出発12:48:21) -> 伊豆・三津シーパラダイス (到着12:49:02, 出発14:19:02) -> 三の浦総合案内所 (到着14:20:24,出発14:30:24) -> 沼津市立長井崎小中一貫学校 (到着14:36:06,出発14:41:06) -> あわしまマリンパーク 駐車場 (到着14:51:35,出発16:21:35) -> 沼津駅 (到着16:47:34,出発16:47:34)
Time of the route: 8:47:34
Total time of all routes: 8:47:34
ギリギリ17時までにすべて訪問できるようです。
しかしよく見ると沼津みなと新鮮館について丸勘で朝食を取った後、沼津港深海水族館の営業まで待機しています。
これは効率的にたくさんの聖地を訪問したいのに時間がもったいないですよね。
こうなる理由は今回作ったプログラムは移動時間をなるべく小さくすることを目標としているからで、各訪問先の訪問時間の制約やそもそも全て回りきる制限時間といった制約の中でなるべく移動時間を小さくします。
つまり多少移動時間が多くなっても待ちの時間がなくなりすべて訪問して帰ってくる時間が小さくなることよりも、すべて訪問する制限時間の範囲内で多少の待ち時間が発生しても移動時間を小さくしようとします。
こういった条件の方が良いこともあると思いますが今回は「待ち」の時間は減らして短い時間ですべて訪問したいですよね。
というわけでプログラムにこれを追加します。
# 時間次元に対して係数をかけて重要度を高める
time_dimension.SetGlobalSpanCostCoefficient(1)
時間の次元に係数をかけてあげることで時間の次元の重要度をあげます。
1だと変わらないのでは？と思うかもしれませんが1でも効果があります。
複数の次元を用意してそれらを最小化もしくは最大化したいといったプログラムの場合、この関数を使って各次元の重要度を調整できます。
これを追加したときの結果が以下のとおりです。
Objective: 53728
Route for vehicle 0:
沼津駅 (到着8:00:00,出発8:00:00) -> 沼津みなと新鮮館 駐車場 (到着8:06:11,出発8:36:11) -> あわしまマリンパーク 駐車場 (到着9:00:11,出発10:30:11) -> 伊豆・三津シーパラダイス (到着10:34:45,出発12:04:45) -> 三の浦総合案内所 (到着12:06:07,出発12:16:07) -> 沼津市立長井崎小中 一貫学校 (到着12:21:49,出発12:26:49) -> 安田屋旅館 (到着12:33:26,出発12:38:26) -> おさかな食堂 やまや (到着12:39:39,出発13:24:39) -> 沼津港深海水族館 (到着13:50:33,出発15:20:33) -> 沼津駅 (到着15:27:44,出発15:27:44)
Time of the route: 7:27:44
場所と時刻以外を削除して改行してまとめてみました。
16時前には沼津駅に戻ってこられることがわかりました。
結構詰め込んだつもりでしたが意外と余裕がありそうですね。
渋滞やお店の混雑などもありますがこれだけ余裕があればもう少し訪問先を増やしてもいいかもしれません。
ちなみにここでの到着は最も早くついた場合の時刻、出発は最も遅く出発する場合の時刻です。
訪問時間の制約のために到着、出発時刻に幅ができることがあります。
さて、ここで弊社LBS APIの1つである巡回最適化APIを使って最適な順番を出してみようと思います。
リクエストに使う情報はjson形式で用意します。
request.json
{ "user_id": "numazu_seichi_junrei", "delivery_start_time": "2023-10-20T08:00:00.000+09:00", "delivery_end_time": "2023-10-20T17:00:00.000+09:00", "depot": { "address": { "latitude": 35.10266448367594, "longitude": 138.85979846067406 }, "unique_id": "depot" }, "locations": [ { "address": { "latitude": 35.02135312342376, "longitude": 138.88337230056888 }, "service_time": 5, "unique_id": "沼津市立長井崎小中一貫学校" }, { "address": { "latitude": 35.02415498831253, "longitude": 138.89893140564527 }, "service_time": 45, "scheduled_time": { "range_start": "2023-10-20T11:30:00+09:00", "range_end": "2023-10-20T14:30:00+09:00" }, "unique_id": "おさかな食堂 やまや" }, { "address": { "latitude": 35.08398178305709, "longitude": 138.85730512626486 }, "service_time": 30, "scheduled_time": { "range_start": "2023-10-20T08:00:00+09:00", "range_end": "2023-10-20T10:00:00+09:00" }, "unique_id": "沼津みなと新鮮館 駐車場" }, { "address": { "latitude": 35.01947137458642, "longitude": 138.89606797052375 }, "service_time": 90, "scheduled_time": { "range_start": "2023-10-20T09:00:00+09:00", "range_end": "2023-10-20T17:00:00+09:00" }, "unique_id": "伊豆・三津シーパラダイス" }, { "address": { "latitude": 35.017737822261495, "longitude": 138.89333064220483 }, "service_time": 10, "scheduled_time": { "range_start": "2023-10-20T09:00:00+09:00", "range_end": "2023-10-20T17:00:00+09:00" }, "unique_id": "三の浦総合案内所" }, { "address": { "latitude": 35.02046373505879, "longitude": 138.89749166076285 }, "service_time": 5, "unique_id": "安田屋旅館" }, { "address": { "latitude": 35.08403714990312, "longitude": 138.8583024589409 }, "service_time": 90, "scheduled_time": { "range_start": "2023-10-20T10:00:00+09:00", "range_end": "2023-10-20T17:00:00+09:00" }, "unique_id": "沼津港深海水族館" }, { "address": { "latitude": 35.03283174332945, "longitude": 138.8938840863703 }, "service_time": 90, "scheduled_time": { "range_start": "2023-10-20T09:30:00+09:00", "range_end": "2023-10-20T17:00:00+09:00" }, "unique_id": "あわしまマリンパーク 駐車場" } ], "map_region": "jp", "search_condition": { "use_toll": false, "use_hwy": false, "use_ferry": false, "use_smart_ic": false, "use_care_traffic": true, "use_care_regulation": false, "use_care_time_regulation": true }, "algorithm": { "travel_matrix_type": "time" }, "need_draw_data": true }
基本的には出発して戻ってくる場所の情報(depot)や言って戻ってくるまでの時間(delivery_start_timeとdelivery_end_time)行きたい場所の緯度経度(address)と滞在時間(service_time)、訪問したい時間の範囲(scheduled_time)を指定するだけです。
ルート探索の細かい条件を指定するsearch_conditionにて渋滞考慮(use_care_traffic)と時間規制(use_care_time_regulation)を有効化しています。
時間を秒に変換したり、時間についてのmatrixを求めたりする必要はないので簡単ですね。
また、順番を決めたあと1本のルートを出すのですがその形状を知りたいのでneed_draw_dataはtrueにしています。
APIを実行した後ルート形状点が返ってくるので、その結果のルートを地図画面で確認できるようになります。
APIを実行するとこのような結果が返ってきます。
result.json
{ "skipped": false, "skipped_location": [ ], "total_travel_cost": 52215, "require_time": 27532, "length": 37215, "break_time": [ ], "order": [ { "arrival_time": "2023-10-20T08:00:00+09:00", "departure_time": "2023-10-20T08:00:00+09:00", "service_time": 0, "unique_id": "depot" }, { "arrival_time": "2023-10-20T08:06:11+09:00", "departure_time": "2023-10-20T08:36:11+09:00", "service_time": 30, "unique_id": "沼津みなと新鮮館 駐車場" }, { "arrival_time": "2023-10-20T09:11:43+09:00", "departure_time": "2023-10-20T09:16:43+09:00", "service_time": 5, "unique_id": "沼津市立長井崎小中一貫学校" }, { "arrival_time": "2023-10-20T09:22:29+09:00", "departure_time": "2023-10-20T09:32:29+09:00", "service_time": 10, "unique_id": "三の浦総合案内所" }, { "arrival_time": "2023-10-20T09:33:52+09:00", "departure_time": "2023-10-20T11:03:52+09:00", "service_time": 90, "unique_id": "伊豆・三津シーパラダイス" }, { "arrival_time": "2023-10-20T11:04:30+09:00", "departure_time": "2023-10-20T11:09:30+09:00", "service_time": 5, "unique_id": "安田屋旅館" }, { "arrival_time": "2023-10-20T11:13:21+09:00", "departure_time": "2023-10-20T12:43:21+09:00", "service_time": 90, "unique_id": "あわしまマリンパーク 駐車場" }, { "arrival_time": "2023-10-20T12:46:32+09:00", "departure_time": "2023-10-20T13:31:32+09:00", "service_time": 45, "unique_id": "おさかな食堂 やまや" }, { "arrival_time": "2023-10-20T13:57:26+09:00", "departure_time": "2023-10-20T15:27:26+09:00", "service_time": 90, "unique_id": "沼津港深海水族館" }, { "arrival_time": "2023-10-20T15:34:37+09:00", "departure_time": "2023-10-20T15:34:37+09:00", "service_time": 0, "unique_id": "depot" } ], "path_point_num": 1004, "path_point_list": [ "<数が多いため省略>" ] }
(画像は開発用の動作確認ページAPIを実行した結果で、配達先の数字はindexと同じです。なので求まった順番は一緒ですね。)
今回プログラムで求めた場合、あくまでも2地点間の移動時間を足し合わせただけなので組み合わせによってはある地点から次の地点に行くときにUターンが発生してしまう可能性があります。
そんな問題も巡回最適化APIならなるべくUターンの無いような順番を選べますし、Uターンが発生してもそれを考慮したルートを引くことができます。
巡回最適化APIで求めたルートの総移動時間が今回のプログラムで求めた結果よりやや長くなっているのもUターンや移動のしやすさを考慮してルートを引いているため単純に足した移動時間よりも少し長くなりますが、それは正確に移動時間を出すことができるということです。
skippedには指定された時間内にどうしても訪問できない地点が発生した場合にtrueが入りますが、今回はすべて訪問できているのでfalseです。
require_timeには移動時間が秒で格納されており、orderの中に訪問先の順番と訪問する時刻が格納されています。
このように、訪問したい地点の緯度経度と時間などを指定するだけで簡単に最適な順番と訪問時刻を得ることができます。
本記事ではOR-Toolsで巡回セールスマン問題、配送経路問題を解く方法について、具体例をもとに紹介させていただきました。
ここで取り上げた機能以外にも様々な機能がOR-Toolsにはありルート最適化についてだけでも奥が深そうです。
一番難しい部分である順番を出す部分をOR-Toolsがやってくれるので意外と簡単に求めることができたのではないでしょうか？
ただ、移動時間のmatrixを求める部分については地点が増えるほど計算量が膨大になりますし、 他にも考慮したい項目がある場合はOR-Toolsを使って実装していくことになるので結構大変そうです。
ですが、弊社LBS APIの巡回最適化APIを使うことでいくつかのパラメータを設定するだけで簡単に最適な順番を求めることができます！
最大200地点まで対応していますし、最後に求めた順番を通る1本のルートも引いてくれます。
滞在時間や訪問時間の指定以外にも休憩時間を設定することもでき、また使う車両の大きさも指定できるので大きな車が通れない狭い道にルートが引かれることもありません。
もしそんなLBS APIに興味をお持ちいただけましたら、ページ下部のフォームよりお気軽にお問い合わせください。
2024年 4月 26日
カーボンニュートラル
2024年 4月 15日
カーボンニュートラル
2024年 4月 15日
カーボンニュートラル
2024年 4月 15日
カーボンニュートラル
2024年 4月 5日
カーボンニュートラル
2023年 12月 8日
テクノロジー
2023年 11月 10日
テクノロジー
2023年 10月 27日
ルート探索・配送
2023年 10月 27日
ルート探索・配送
2023年 10月 27日
ルート探索・配送
2023年 10月 20日
ルート探索・配送
2023年 10月 20日
ルート探索・配送
2023年 10月 20日
ルート探索・配送
2023年 10月 13日
ルート探索・配送
2023年 10月 13日
ルート探索・配送
2023年 9月 19日
テクノロジー
