ラグビーワールドカップ会場 - 巡回セールスマン問題

nAG Library for Python Example集

このページは、nAGライブラリのJupyterノートブックExampleの日本語翻訳版です。オリジナルのノートブックはインタラクティブに操作することができます。

ラグビーワールドカップ会場 - 巡回セールスマン問題

イギリスにある様々なスタジアム間の距離(メートル単位)と自転車での移動時間(秒単位)が記載されたファイルがあります。これらのスタジアムはすべてラグビーワールドカップの試合会場として使用されたものです。ファイルは「タブ区切り値」(tsv)形式で保存されています。リストにあるすべてのスタジアムを巡る最適な方法を見つけたいと思います。ここでの「最適」とは、最短距離または最短時間のいずれかを意味します。

謝辞: このノートブックはRandy Olsonの作業にインスピレーションを受けています。アメリカ横断のロードトリップの最短経路を見つけるための彼のコードは、彼のGithubページこちらで見つけることができます。このnAGノートブックの最初のバージョンはJohn Muddleによって作成されました。

まず最初に、様々なスタジアムを定義します:

all_stadiums = ["Brighton community stadium, UK", 
                "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
stadium_data = pn.read_csv("my-rugby-bike-stadiums-dist-dur.tsv", sep="\t")

ファイルの内容を見てみましょう。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
distance_matrix = np.zeros((len(all_stadiums), len(all_stadiums)))
duration_matrix = np.zeros((len(all_stadiums), len(all_stadiums)))
for index, row in stadium_data.iterrows():
    distance_matrix[all_stadiums.index(row['stadium1'])][all_stadiums.index(row['stadium2'])] = row['distance_m']
    distance_matrix[all_stadiums.index(row['stadium2'])][all_stadiums.index(row['stadium1'])] = row['distance_m']
    duration_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']

nAGソルバー mip.tsp_simannのセットアップ

関数tsp_simannは、初期化のためにランダムに生成された状態を必要とします。この状態を定義するためにrand.init_repeatを使用します。

from naginterfaces.library import rand
statecomm = rand.init_repeat(genid=2, seed=[304950, 889934, 209094, 23423990], subid=53)

最適な経路をmip.tsp_simannを使用して見つけます。この関数を2回呼び出します。1回目は最適な距離を見つけるため、2回目は最適な時間を見つけるためです。

from naginterfaces.library import mip
soln_distance = mip.tsp_simann(dm=distance_matrix, bound=-1.0, targc=-1.0, statecomm=statecomm)
soln_duration = mip.tsp_simann(dm=duration_matrix, bound=-1.0, targc=-1.0, statecomm=statecomm)
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:
    optimal_path_distance.append(all_stadiums[i-1])
for i in soln_duration.path:
    optimal_path_duration.append(all_stadiums[i-1])

そして結果を表示する

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']
関連情報
MENU
© 譌・譛ャ繝九Η繝シ繝。繝ェ繧ォ繝ォ繧「繝ォ繧エ繝ェ繧コ繝�繧コ繧ー繝ォ繝シ繝玲�ェ蠑丈シ夂、セ 2024
Privacy Policy  /  Trademarks