旅行最適化
旅行に関する最適化問題の例を考えます。
3つの都市を訪れる旅行者が、最短距離の経路でそれぞれの都市を訪れるようにルートを決めるのが目的です。
解法・ソースコード
PythonのPuLPライブラリを使用して問題を解決します。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| import pulp
problem = pulp.LpProblem('Traveling Problem', pulp.LpMinimize)
cities = { 'City 1': (20, 50), 'City 2': (40, 20), 'City 3': (60, 70) }
def distance(city1, city2): return ((city1[0] - city2[0]) ** 2 + (city1[1] - city2[1]) ** 2) ** 0.5
routes = pulp.LpVariable.dicts('Route', ((i, j) for i in cities for j in cities if i!=j), cat='Binary')
problem += pulp.lpSum([routes[(i, j)] * distance(cities[i], cities[j]) for i in cities for j in cities if i!=j])
for i in cities: problem += pulp.lpSum([routes[(i, j)] for j in cities if i!=j]) == 1
for j in cities: problem += pulp.lpSum([routes[(i, j)] for i in cities if i!=j]) == 1
problem.solve()
print("最短距離: ", pulp.value(problem.objective)) for v in problem.variables(): if v.varValue == 1: print(v.name)
|
各都市を訪れるルートをバイナリ変数で表現し、目的関数には各ルートの距離を加算します。
制約条件として、各都市を正確に1回訪れなければならず、同じ都市には戻れないことを設定します。
最後に、PuLPを使用して問題を解決し、最適なルートを表示します。
上記のコードを実行すると、以下のような結果が表示されます。
[実行結果]
最短距離: 134.6285203759807
Route_('City_1',_'City_3')
Route_('City_2',_'City_1')
Route_('City_3',_'City_2')
都市1、都市3、都市2の順で訪れると、最短距離が134.62であることを示しています。
また、この結果には、各都市を訪れるためのルートが表示されています。
例えば、’Route_(‘City_1’,_’City_3’)’は、都市1から都市3へのルートを示しています。