旅行最適化 PuLP

旅行最適化

旅行に関する最適化問題の例を考えます。

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)

# 都市の座標 (x, y)
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へのルートを示しています。