[PYTHON] Résolvez le problème du voyageur de commerce avec OR-Tools
Qu'est-ce que c'est
J'ai essayé de résoudre "Résoudre le problème du voyageur de commerce avec Watson" en utilisant OR-Tools.
Qu'est-ce que OR-Tools?
Une bibliothèque gratuite liée à la recherche opérationnelle créée par Google. Avec OR-Tools, Delivery Optimization Problem et Circuit Salesman Problem Peut être résolu.
Référence: https://developers.google.com/optimization/routing
Essayez de résoudre
S'il est laissé tel quel, ce sera un peu gênant, alors j'utiliserai le wrapper de 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] #Créez 30 villes selon l'article original
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-');
Avec un temps de calcul de 1 seconde, le même résultat que l'article d'origine a été obtenu (le temps de calcul de l'article d'origine était de 226 secondes).
Supplément
L'algorithme OR-Tools est une solution approximative. Si vous n'ajoutez pas limit_time = 1, vous obtiendrez une solution en un instant, mais la précision est un peu médiocre.
Par conséquent, en réglant le temps de calcul à 1 seconde, la même solution exacte que l'article d'origine est obtenue.
- OR-Tools doit définir la distance sur un entier.