import urllib.request
url = 'https://raw.githubusercontent.com/maskot1977/ipython_notebook/master/toydata/location.txt'
urllib.request.urlretrieve(url, 'location.txt') #Daten herunterladen

('location.txt', <http.client.HTTPMessage at 0x7f9f4e7685c0>)

import pandas as pd
japan = pd.read_csv('location.txt')
japan

Hier ist ein Diagramm der Positionsbeziehung zwischen Städten.

%matplotlib inline
import matplotlib.pyplot as plt
plt.figure(figsize=(10, 8))
plt.scatter(japan['Latitude'], japan['Longitude'])
for city, x, y in zip(japan['Town'], japan['Latitude'], japan['Longitude']):
    plt.text(x, y, city, alpha=0.5, size=12)
plt.grid()

simanneal Paket

Installieren Sie das Paket simanneal, um die Glühmethode zu lösen.

!pip install simanneal

In diesem Paket gibt es beispielsweise bereits eine Klasse zur Lösung des Problems des Handlungsreisenden, sodass Sie es so verwenden können, wie es ist.

from simanneal import Annealer
class TravellingSalesmanProblem(Annealer):

    """Test annealer with a travelling salesman problem.
    """

    # pass extra data (the distance matrix) into the constructor
    def __init__(self, state, distance_matrix):
        self.distance_matrix = distance_matrix
        super(TravellingSalesmanProblem, self).__init__(state)  # important!

    def move(self):
        """Swaps two cities in the route."""
        # no efficiency gain, just proof of concept
        # demonstrates returning the delta energy (optional)
        initial_energy = self.energy()

        a = random.randint(0, len(self.state) - 1)
        b = random.randint(0, len(self.state) - 1)
        self.state[a], self.state[b] = self.state[b], self.state[a]

        return self.energy() - initial_energy

    def energy(self):
        """Calculates the length of the route."""
        e = 0
        for i in range(len(self.state)):
            e += self.distance_matrix[self.state[i-1]][self.state[i]]
        return e

Distanzmatrix

Die Distanzmatrix kann auf diese Weise beispielsweise mit scipy berechnet werden

import numpy as np
from scipy.spatial import distance

mat = japan[['Latitude', 'Longitude']].values
dist_mat = distance.cdist(mat, mat, metric='euclidean') #Euklidische Entfernung

Um es mit simanneal verwenden zu können, muss es anscheinend so formatiert werden.

distance_matrix = {}
for i, town in enumerate(japan['Town']):
    if town not in distance_matrix.keys():
        distance_matrix[town] = {}
    for j, town2 in enumerate(japan['Town']):
        distance_matrix[town][town2] = dist_mat[i][j]

Erster Satz

Ordne die Städte in zufälliger Reihenfolge an und nenne sie den "Anfangskreislauf".

import random
init_state = list(japan['Town'])
random.shuffle(init_state)

Stellen Sie es in eine Klasse ein, die das Problem des reisenden Verkäufers löst.

tsp = TravellingSalesmanProblem(init_state, distance_matrix)

Berechnung starten

tsp.set_schedule(tsp.auto(minutes=0.2))
tsp.copy_strategy = "slice"
state, e = tsp.anneal()

Berechnungsergebnis

Die Schaltung wurde ausgegeben.

state

['Otsu',
 'Kyoto',
 'Nara',
 'Osaka',
 'Kobe',
 'Tottori',
 'Matsue',
 'Hiroshima',
 'Yamaguchi',
 'Fukuoka',
 'Saga',
 'Nagasaki',
 'Naha',
 'Kagoshima',
 'Miyazaki',
 'Kumamoto',
 'Oita',
 'Matsuyama',
 'Kochi',
 'Okayama',
 'Takamatsu',
 'Tokushima',
 'Wakayama',
 'Tsu',
 'Gifu',
 'Nagoya',
 'Shizuoka',
 'Kofu',
 'Maebashi',
 'Niigata',
 'Akita',
 'Aomori',
 'Sapporo',
 'Morioka',
 'Sendai',
 'Yamagata',
 'Fukushima',
 'Utsunomiya',
 'Mito',
 'Chiba',
 'Yokohama',
 'Tokyo',
 'Saitama',
 'Nagano',
 'Toyama',
 'Kanazawa',
 'Fukui']

Schaltung von der angegebenen Stadt

Machen Sie die erhaltene Schaltung zum Beispiel zu einer Schaltung ab Tokio.

while state[0] != 'Tokyo':
        state = state[1:] + state[:1]  # rotate NYC to start

print()
print("%i mile route:" % e)
print(" ➞  ".join(state))

56 mile route:
Tokyo ➞  Saitama ➞  Nagano ➞  Toyama ➞  Kanazawa ➞  Fukui ➞  Otsu ➞  Kyoto ➞  Nara ➞  Osaka ➞  Kobe ➞  Tottori ➞  Matsue ➞  Hiroshima ➞  Yamaguchi ➞  Fukuoka ➞  Saga ➞  Nagasaki ➞  Naha ➞  Kagoshima ➞  Miyazaki ➞  Kumamoto ➞  Oita ➞  Matsuyama ➞  Kochi ➞  Okayama ➞  Takamatsu ➞  Tokushima ➞  Wakayama ➞  Tsu ➞  Gifu ➞  Nagoya ➞  Shizuoka ➞  Kofu ➞  Maebashi ➞  Niigata ➞  Akita ➞  Aomori ➞  Sapporo ➞  Morioka ➞  Sendai ➞  Yamagata ➞  Fukushima ➞  Utsunomiya ➞  Mito ➞  Chiba ➞  Yokohama

Illustriert

plt.figure(figsize=(10, 10))
Xs = []
Ys = []
for i in range(len(state)):
    Xs.append(list(japan[japan['Town'] == state[i]].iloc[:, 2])[0])
    Ys.append(list(japan[japan['Town'] == state[i]].iloc[:, 1])[0])

plt.plot(Xs, Ys)
for city, x, y in zip(japan['Town'], japan['Latitude'], japan['Longitude']):
    plt.text(x, y, city, alpha=0.5, size=12)

Das war's. Es scheint nicht die optimale Lösung zu sein, aber es scheint, dass etwas in der Nähe davon erhalten wurde.