Optimisation de combinaison - Problème typique - Problème de vendeur circulaire

Problème typique et méthode d'exécution

Problème de vendeur de patrouille

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.

Méthode d'exécution

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

Comment utiliser le solveur Google OR-Tools

Si " method = 'ortools' "est ajouté, le solveur (solution approximative) de Google OR-Tools est utilisé.

Mise en garde

--Installez Google OR-Tools avec pip install or tools.

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])

Les données

Recommended Posts

Optimisation de combinaison - Problème typique - Problème de vendeur circulaire
Optimisation de combinaison - problème typique de problème de sac à dos
Optimisation de combinaison - problème typique de conditionnement n-dimensionnel
Optimisation de combinaison - problème typique - problème de couverture de vertex minimum
Problème de correspondance stable aux problèmes typique d'optimisation de combinaison
Optimisation de combinaison - problème typique d'allocation généralisé
Optimisation de combinaison - problème typique de correspondance de problème maximum
Optimisation des combinaisons - Problème typique - Problème d'allocation secondaire
Combinaison d'optimisation-problème typique-problème de chemin le plus court
Optimisation combinée - problème typique d'enchères combinées
Optimisation de la combinaison - problème typique - problème de débit maximal
Combinaison d'optimisation-problème typique de couverture d'agrégat
Problème de correspondance typique de problème-poids par optimisation de combinaison
Problème d'optimisation de combinaison-problème typique de placement des installations
Optimisation de la combinaison - problème typique de l'atelier de travail
Optimisation de la combinaison - problème typique - problème de coupe maximale
Problème d'ordonnancement de travail-problème typique d'optimisation de combinaison
Optimisation de combinaison - problème typique - problème d'arborescence de surface minimale
Combinaison optimisation-problème typique-problème d'ensemble stable maximum
Optimisation de la combinaison - problème typique - problème de flux de coût minimal
Optimisation de combinaison-problème typique-problème de livraison postale chinoise
Optimisation des combinaisons - Problème typique - Problème d'itinéraire de transport (optimisation de la livraison)
Problème d'optimisation de la combinaison - coupe minimale
Optimisation des combinaisons - Problème typique - Problème de placement des installations sans contrainte de capacité
À propos du problème du voyageur de commerce
Combinaison de problèmes typiques d'optimisation et comment le faire
Problème de méthode de gravure et de voyageur de commerce
À propos du problème du vendeur de patrouille commandé