Solve the traveling salesman problem with OR-Tools
what is this
I tried to solve "Solving the traveling salesman problem with Watson" using OR-Tools.
What is OR-Tools?
A free Operations Research-related library created by Google. With OR-Tools, Delivery Optimization Problem and Traveling Salesman Problem Can be solved.
Reference: https://developers.google.com/optimization/routing
Try to solve
If it is left as it is, it will be a little troublesome, so I will use the wrapper of ortoolpy.
import pandas as pd
import matplotlib.pyplot as plt
from scipy.spatial import distance
from more_itertools import pairwise
from ortoolpy import ortools_vrp
url = 'https://raw.githubusercontent.com/makaishi2/sample-data/master/data/att48.csv'
df = pd.read_csv(url)[:30] #Make 30 cities according to the original article
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-');
With a calculation time of 1 second, the same result as the original article was obtained (the calculation time of the original article is 226 seconds).
Supplement
The OR-Tools algorithm is an approximate solution. If you do not add limit_time = 1, you will get a solution in an instant, but the accuracy is a little poor.
Therefore, by setting the calculation time to 1 second, the same exact solution as the original article is obtained.
- OR-Tools must set the distance to an integer.
Recommended Posts