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-');

image.png

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.

Recommended Posts

Solve the traveling salesman problem with OR-Tools
About the traveling salesman problem
Try to solve the traveling salesman problem with a genetic algorithm (Theory)
About the Ordered Traveling Salesman Problem
Try to solve the traveling salesman problem with a genetic algorithm (Python code)
Try to solve the traveling salesman problem with a genetic algorithm (execution result)
Solve the Python asymmetric traveling salesman problem with a branch and bound method
Python: I tried the traveling salesman problem
Try to solve the fizzbuzz problem with Keras
I tried to implement the traveling salesman problem
Solve a simple traveling salesman problem using a Boltzmann machine with simulated annealing
Solve the Monty Hall problem
Try to solve the internship assignment problem with Python
Solving the traveling salesman problem with the genetic algorithm (GA) and its library (vcopt)
I tried to solve the problem with Python Vol.1
Simulated Annealing and Traveling Salesman Problem
I wanted to solve the ABC164 A ~ D problem with Python
Solve the initial value problem of ordinary differential equations with JModelica
Solve the Python knapsack problem with a branch and bound method
Solve the subset sum problem with a full search in Python
I tried "Implementing a genetic algorithm (GA) in python to solve the traveling salesman problem (TSP)"
The story of the algorithm drawing a ridiculous conclusion when trying to solve the traveling salesman problem properly
Solving the paraboloid minimization problem with OpenMDAO
I tried paiza's campaign problem. (Traveling salesman problem)
Let's solve the portfolio with continuous optimization
How to solve the bin packing problem
[AtCoder] Solve ABC1 ~ 100 A problem with Python
Solve the maximum subarray problem in Python
The 16th offline real-time how to write reference problem to solve with Python
The 19th offline real-time how to write reference problem to solve with Python
[AtCoder] Solve A problem of ABC101 ~ 169 with Python
Try to solve the Python class inheritance problem
Solve the knapsack problem using pyomo and glpk
Try to solve the man-machine chart with Python
Solving the N Queen problem with combinatorial optimization
Solving the N Queens problem with combinatorial optimization
[At Coder] Solve the problem of binary search
Traveling salesman problem practice collection ③ ~ Non-random map edition ~
Solving the Python knapsack problem with the greedy algorithm
I tried to solve the virtual machine placement optimization problem (simple version) with blueqat
The 15th offline real-time I tried to solve the problem of how to write with python
Try to solve the programming challenge book with python3
The first algorithm to learn with Python: FizzBuzz problem
I tried to solve the soma cube with python
The 14th offline real-time writing reference problem with Python
Solving the iris problem with scikit-learn ver1.0 (logistic regression)
Solve AtCoder 167 with python
How to write offline real time I tried to solve the problem of F02 with Python
Solve Sudoku with Python
Solve Sudoku with PuLP
Examine the dual problem
Solve POJ 2386 with python
Solve the verbal arithmetic
I wanted to solve the Panasonic Programming Contest 2020 with Python
Finding a solution to the N-Queen problem with a genetic algorithm (2)
I tried to solve a combination optimization problem with Qiskit
Solve the spiral book (algorithm and data structure) with python!
Solve Mathematical Optimization Model Exercises with Google's OR-Tools (4) Solve Number Places
A story about how to deal with the CORS problem
Solve the Japanese problem when using the CSV module in Python.
The problem becomes easier to solve depending on the formulation method