Problème typique et méthode d'exécution
Un graphe composé d'un ensemble de n points (ville) $ V $ $ G = (V, E) $ et d'un circuit qui parcourt tous les points une fois lorsque le coût pour chaque côté est donné. Trouvez celui qui minimise la somme des coûts (comme la distance) sur les côtés.
usage
Signature: tsp(nodes, dist=None, method=None)
Docstring:
Problème de vendeur de patrouille
contribution
nodes:point(Lorsque dist n'est pas spécifié, les coordonnées)Liste de
dist: (i,j)Un dictionnaire avec la clé et la distance comme valeur
method:Méthode de calcul(ex. 'ortools')
production
Liste des distances et des numéros de points
python
from ortoolpy import tsp
tsp([(2, 0), (1, 2), (0, 1), (3, 1), (2, 2)])[1]
résultat
[0, 2, 1, 4, 3]
python
# pandas.DataFrame
from ortoolpy.optimization import Tsp
Tsp('data/node1.csv')[1]
| id | x | y | demand | |
|---|---|---|---|---|
| 0 | 0 | 5 | 1 | 0 |
| 3 | 3 | 1 | 0 | 1 |
| 5 | 5 | 0 | 4 | 1 |
| 2 | 2 | 1 | 5 | 1 |
| 1 | 1 | 8 | 5 | 1 |
| 4 | 4 | 8 | 0 | 1 |
Si " method = 'ortools' "est ajouté, le solveur (solution approximative) de Google OR-Tools est utilisé.
--Installez Google OR-Tools avec pip install or tools.
dist) doit être un entier.python
import numpy as np
from scipy.spatial import distance
from ortoolpy import tsp
np.random.seed(0)
nodes = np.random.rand(20, 2) * 1000 #20 villes
dist = distance.cdist(nodes, nodes).astype(int) #Matrice de distance
print(tsp(nodes, dist, method='ortools')) #Solution approximative
print(tsp(nodes, dist)) #Solution exacte (référence)
Le coût total (4099) est supérieur à la solution exacte (4072,0) sur la deuxième ligne.
Résultat (somme des coûts et liste des numéros de points)
(4099, [0, 11, 3, 6, 9, 10, 19, 4, 5, 18, 1, 14, 7, 17, 12, 8, 13, 15, 2, 16])
(4072.0, [0, 2, 16, 14, 7, 17, 12, 8, 13, 15, 11, 3, 6, 9, 10, 19, 4, 5, 1, 18])
Recommended Posts