このページは、nAGライブラリのJupyterノートブックExampleの日本語翻訳版です。オリジナルのノートブックはインタラクティブに操作することができます。
ラグビーワールドカップ会場 - 巡回セールスマン問題
イギリスにある様々なスタジアム間の距離(メートル単位)と自転車での移動時間(秒単位)が記載されたファイルがあります。これらのスタジアムはすべてラグビーワールドカップの試合会場として使用されたものです。ファイルは「タブ区切り値」(tsv)形式で保存されています。リストにあるすべてのスタジアムを巡る最適な方法を見つけたいと思います。ここでの「最適」とは、最短距離または最短時間のいずれかを意味します。
謝辞: このノートブックはRandy Olsonの作業にインスピレーションを受けています。アメリカ横断のロードトリップの最短経路を見つけるための彼のコードは、彼のGithubページこちらで見つけることができます。このnAGノートブックの最初のバージョンはJohn Muddleによって作成されました。
まず最初に、様々なスタジアムを定義します:
= ["Brighton community stadium, UK",
all_stadiums "City of Manchester Stadium, Ashton New Road, Manchester",
"Elland Road, UK",
"King Power Stadium, Filbert Way, Leicester",
"Kingsholm Stadium, Kingsholm Road, Gloucester",
"Millennium Stadium, Westgate Street, Cardiff",
"Sandy Park Stadium, Exeter",
"St. James' Park, Barrack Road, Newcastle upon Tyne",
"Stadium MK, Grafton Street, Bletchley",
"The Stadium, Queen Elizabeth Olympic Park",
"Twickenham Stadium, Whitton Road, Twickenham",
"Villa Park, Trinity Road, Birmingham",
"Wembley Stadium, Wembley"]
その後、Pythonのデータ分析ライブラリであるpandasのルーチンを使用して、ファイルから距離と時間のデータを読み込みます。ファイルは「タブ区切り値」(tsv)形式で保存されています。ファイル内の距離と時間はGoogleマップを使用して計算されました。
import pandas as pn
= pn.read_csv("my-rugby-bike-stadiums-dist-dur.tsv", sep="\t") stadium_data
ファイルの内容を見てみましょう。n=13のスタジアムがあるため、ファイルにはすべてのスタジアムのペア間の距離が含まれる必要があります。そのため、ファイルには12+11+10+…+1 = n*(n-1)/2 = 78行が含まれています。
stadium_data
stadium1 | stadium2 | distance_m | duration_s | |
---|---|---|---|---|
0 | Brighton community stadium, UK | King Power Stadium, Filbert Way, Leicester | 280176 | 52420 |
1 | Brighton community stadium, UK | Sandy Park Stadium, Exeter | 313295 | 62141 |
2 | Brighton community stadium, UK | St. James’ Park, Barrack Road, Newcastle upon … | 622834 | 116360 |
3 | Brighton community stadium, UK | Stadium MK, Grafton Street, Bletchley | 184675 | 34481 |
4 | Brighton community stadium, UK | Twickenham Stadium, Whitton Road, Twickenham | 106895 | 20637 |
… | … | … | … | … |
73 | Wembley Stadium, Wembley | Sandy Park Stadium, Exeter | 327375 | 62045 |
74 | Wembley Stadium, Wembley | St. James’ Park, Barrack Road, Newcastle upon … | 512945 | 96107 |
75 | Wembley Stadium, Wembley | Stadium MK, Grafton Street, Bletchley | 75540 | 13953 |
76 | Wembley Stadium, Wembley | Twickenham Stadium, Whitton Road, Twickenham | 16002 | 3315 |
77 | Wembley Stadium, Wembley | Villa Park, Trinity Road, Birmingham | 205027 | 37293 |
78 rows × 4 columns
nAG関数への入力用の距離と時間を含む行列を作成する
import numpy as np
= np.zeros((len(all_stadiums), len(all_stadiums)))
distance_matrix = np.zeros((len(all_stadiums), len(all_stadiums)))
duration_matrix for index, row in stadium_data.iterrows():
'stadium1'])][all_stadiums.index(row['stadium2'])] = row['distance_m']
distance_matrix[all_stadiums.index(row['stadium2'])][all_stadiums.index(row['stadium1'])] = row['distance_m']
distance_matrix[all_stadiums.index(row['stadium1'])][all_stadiums.index(row['stadium2'])] = row['duration_s']
duration_matrix[all_stadiums.index(row['stadium2'])][all_stadiums.index(row['stadium1'])] = row['duration_s'] duration_matrix[all_stadiums.index(row[
nAGソルバー mip.tsp_simannのセットアップ
関数tsp_simannは、初期化のためにランダムに生成された状態を必要とします。この状態を定義するためにrand.init_repeatを使用します。
from naginterfaces.library import rand
= rand.init_repeat(genid=2, seed=[304950, 889934, 209094, 23423990], subid=53) statecomm
最適な経路をmip.tsp_simannを使用して見つけます。この関数を2回呼び出します。1回目は最適な距離を見つけるため、2回目は最適な時間を見つけるためです。
from naginterfaces.library import mip
= mip.tsp_simann(dm=distance_matrix, bound=-1.0, targc=-1.0, statecomm=statecomm)
soln_distance = mip.tsp_simann(dm=duration_matrix, bound=-1.0, targc=-1.0, statecomm=statecomm)
soln_duration print(soln_distance.path)
print(soln_duration.path)
[ 1 7 6 5 12 2 8 3 4 9 13 11 10]
[ 1 10 11 13 9 4 8 3 2 12 5 6 7]
望ましい経路は、mip.tsp_simannによって返されるタプルの整数リスト「path」に格納されています。返された経路から対応するスタジアムに変換します
= []
optimal_path_distance = []
optimal_path_duration for i in soln_distance.path:
-1])
optimal_path_distance.append(all_stadiums[ifor i in soln_duration.path:
-1]) optimal_path_duration.append(all_stadiums[i
そして結果を表示する
print('This is the shortest path by distance, of {:4.2f} kilometres:'.format(soln_distance.cost/1000))
print(optimal_path_distance)
This is the shortest path by distance, of 1793.38 kilometres:
['Brighton community stadium, UK', 'Sandy Park Stadium, Exeter', 'Millennium Stadium, Westgate Street, Cardiff', 'Kingsholm Stadium, Kingsholm Road, Gloucester', 'Villa Park, Trinity Road, Birmingham', 'City of Manchester Stadium, Ashton New Road, Manchester', "St. James' Park, Barrack Road, Newcastle upon Tyne", 'Elland Road, UK', 'King Power Stadium, Filbert Way, Leicester', 'Stadium MK, Grafton Street, Bletchley', 'Wembley Stadium, Wembley', 'Twickenham Stadium, Whitton Road, Twickenham', 'The Stadium, Queen Elizabeth Olympic Park']
print('This is the shortest path by time, of {:4.2f} hours:'.format(soln_duration.cost/3600))
print(optimal_path_duration)
This is the shortest path by time, of 96.06 hours:
['Brighton community stadium, UK', 'The Stadium, Queen Elizabeth Olympic Park', 'Twickenham Stadium, Whitton Road, Twickenham', 'Wembley Stadium, Wembley', 'Stadium MK, Grafton Street, Bletchley', 'King Power Stadium, Filbert Way, Leicester', "St. James' Park, Barrack Road, Newcastle upon Tyne", 'Elland Road, UK', 'City of Manchester Stadium, Ashton New Road, Manchester', 'Villa Park, Trinity Road, Birmingham', 'Kingsholm Stadium, Kingsholm Road, Gloucester', 'Millennium Stadium, Westgate Street, Cardiff', 'Sandy Park Stadium, Exeter']