LoginSignup
8

More than 3 years have passed since last update.

組合せ最適化 - 典型問題 - 巡回セールスマン問題

Last updated at Posted at 2015-07-10

典型問題と実行方法

巡回セールスマン問題

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])

データ

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
8