[PYTHON] Lösen Sie das Problem des Handlungsreisenden mit OR-Tools
Was ist das
Ich habe versucht, "Lösen des Problems mit reisenden Verkäufern mit Watson" mit OR-Tools zu lösen.
Was ist OR-Tools?
Eine kostenlose Operations Research-bezogene Bibliothek, die von Google erstellt wurde. Mit OR-Tools, Problem bei der Lieferoptimierung und Circuit Salesman Problem Kann gelöst werden.
Referenz: https://developers.google.com/optimization/routing
Versuche es zu lösen
Wenn es so bleibt, wie es ist, wird es ein wenig mühsam sein, also werde ich den Wrapper von ortoolpy verwenden.
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] #Bilden Sie 30 Städte gemäß dem ursprünglichen Artikel
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-');
Mit einer Berechnungszeit von 1 Sekunde wurde das gleiche Ergebnis wie beim Originalartikel erzielt (die Berechnungszeit für den Originalartikel betrug 226 Sekunden).
Ergänzung
Der OR-Tools-Algorithmus ist eine ungefähre Lösung. Wenn Sie nicht limit_time = 1 hinzufügen, erhalten Sie sofort eine Lösung, aber die Genauigkeit ist etwas schlecht.
Durch Einstellen der Berechnungszeit auf 1 Sekunde wird daher dieselbe exakte Lösung wie beim Originalartikel erhalten.
- OR-Tools müssen den Abstand auf eine Ganzzahl einstellen.
Recommended Posts