OR-Toolsで巡回セールスマン問題を解く

これなに

「Watsonで巡回セールスマン問題を解く」をOR-Toolsを使って解いてみました。

OR-Toolsとは

Googleが作成した無料のOperations Research関連のライブラリーです。
OR-Toolsを使うと、配送最適化問題や巡回セールスマン問題を解くことができます。

参考：https://developers.google.com/optimization/routing

解いてみる

そのままだと、ちょっと面倒なので、ortoolpyのラッパーを使います。

import pandas as pd
import matplotlib.pyplot as plt
from scipy.spatial import distance
from ortoolpy import ortools_vrp

url = 'https://raw.githubusercontent.com/makaishi2/sample-data/master/data/att48.csv'
df = pd.read_csv(url)[:30]  # 元記事に揃えて30都市にする
dist = distance.cdist(df.values, df.values).astype(int)
route = ortools_vrp(len(df), dist, limit_time=1)[0]
plt.figure(figsize=(6, 6))
plt.plot(df.x[route], df.y[route], 'bo-');

計算時間1秒で、元記事と同じ結果が出ました（元記事の計算時間は、226秒）。

補足

OR-Toolsのアルゴリズムは近似解法です。limit_time=1をつけないと一瞬で解がでますが、若干精度が悪いです。
そこで、計算時間を1秒にすることで、元記事と同じ厳密解が得られています。

※ distを整数にしていますが、OR-Toolsは距離を整数にしないといけません。