巡回セールスマン問題
n個の点(都市)の集合$V$から構成されるグラフ$G=(V,E)$および各辺に対するコストが与えられているとき、全ての点を1回ずつ経由する巡回路で辺上の（距離などの）コストの和を最小にするものを求めよ。
実行方法
usage
Signature: tsp(nodes, dist=None, method=None)
Docstring:
巡回セールスマン問題
入力
nodes: 点(dist未指定時は、座標)のリスト
dist: (i,j)をキー、距離を値とした辞書
method: 計算方法(ex. 'ortools')
出力
距離と点番号リスト
python
from ortoolpy import tsp
tsp([(2, 0), (1, 2), (0, 1), (3, 1), (2, 2)])[1]
結果
[0, 2, 1, 4, 3]
python
# pandas.DataFrame
from ortoolpy.optimization import Tsp
Tsp('data/node1.csv')[1]
| id | x | y | demand | |
|---|---|---|---|---|
| 0 | 0 | 5 | 1 | 0 |
| 3 | 3 | 1 | 0 | 1 |
| 5 | 5 | 0 | 4 | 1 |
| 2 | 2 | 1 | 5 | 1 |
| 1 | 1 | 8 | 5 | 1 |
| 4 | 4 | 8 | 0 | 1 |
Google OR-Toolsのソルバーを使う方法
「method='ortools'」をつけると、 Google OR-Tools のソルバー（近似解法）を使います。
注意
-
pip install ortoolsで Google OR-Tools をインストールしてください。 - 距離行列（
dist）の要素は整数にしてください。
python
import numpy as np
from scipy.spatial import distance
from ortoolpy import tsp
np.random.seed(0)
nodes = np.random.rand(20, 2) * 1000 # 20都市
dist = distance.cdist(nodes, nodes).astype(int) # 距離行列
print(tsp(nodes, dist, method='ortools')) # 近似解法
print(tsp(nodes, dist)) # 厳密解法（参考）
コストの総和（4099）は、2行目の厳密解（4072.0）より大きくなっています。
結果（コストの和と点番号のリスト）
(4099, [0, 11, 3, 6, 9, 10, 19, 4, 5, 18, 1, 14, 7, 17, 12, 8, 13, 15, 2, 16])
(4072.0, [0, 2, 16, 14, 7, 17, 12, 8, 13, 15, 11, 3, 6, 9, 10, 19, 4, 5, 1, 18])