Un approccio di classe per risolvere efficacemente i problemi dei venditori ambulanti con Python | di Carlos J.Uribe | Intelligenza-Artificiale

Qui non inizieremo da zero. Come affermato in precedenza, abbiamo già sviluppato il codice che costruisce un modello Pyomo del TSP e lo risolve sprint 3. E credimi, quella è stata la parte più difficile. Ora abbiamo il compito più semplice di organizzare ciò che abbiamo fatto in modo da renderlo generale, nascondendo i dettagli mantenendo il essenziale elementi visibili. In un certo senso, vogliamo che l’ottimizzatore assomigli ad una “scatola magica” che anche gli utenti che non hanno familiarità con la modellazione matematica possano utilizzare per risolvere i loro problemi TSP in modo intuitivo.

4.1. TravelingSalesmanOptimizer progetto

La nostra classe di ottimizzazione avrà metodi “principali”, che svolgono la maggior parte del lavoro, e metodi “superficiali”, che fungono da interfaccia di alto livello della classe, che invocano i metodi principali sottostanti.

Questi sono i passaggi che saranno al centro della logica dell’ottimizzatore:

1. Crea un modello Pyomo da una matrice delle distanze. Questo viene fatto da _create_model metodo, che sostanzialmente avvolge il codice del proof-of-concept l’abbiamo già fatto. Accetta un dataframe di una matrice di distanza e ne costruisce un modello Pyomo. L’unica differenza importante tra ciò che abbiamo fatto e ciò che stiamo facendo è che, ora, il sito iniziale non è più codificato, ma semplicemente "hotel"ma è presunto per essere il sito della prima fila df_distances. Nel caso generale, quindi, il sito iniziale viene considerato il primo nel dataframe delle coordinate⁴ df_sites. Questa generalizzazione consente all’ottimizzatore di risolvere qualsiasi istanza.
2. (Tentativo di) Risolvere il modello. Questa operazione viene eseguita nel _optimize metodo ereditato da BaseOptimizerche ritorna True solo se si trova una soluzione.
3. Estrai la soluzione dal modello e analizzala in un modo che sia facile da interpretare e utilizzare. Questo avviene all’interno _store_solution_from_modelche è un metodo che ispeziona il modello risolto ed estrae i valori delle variabili decisionali e il valore della funzione obiettivo, per creare gli attributi tour_ E tour_distance_rispettivamente. Questo metodo viene invocato solo se esiste una soluzionequindi se non viene trovata alcuna soluzione, gli “attributi della soluzione” tour_ E tour_distance_ non essere mai creato. Il vantaggio di ciò è che la presenza di questi due “attributi della soluzione”, dopo l’adattamento, informerà l’utente dell’esistenza di una soluzione. Inoltre, i valori ottimali sia delle variabili che dell’obiettivo possono essere comodamente recuperati in qualsiasi momento, non necessariamente al momento dell’adattamento.

Gli ultimi 2 passaggi, ovvero trovare ed estrarre la soluzione, sono racchiusi nell’ultimo metodo “core”, _fit_to_distances.

“Ma aspetta” – potresti pensare – “Come suggerisce il nome, _fit_to_distances richiede le distanze come input; il nostro obiettivo non è risolvere i problemi TSP utilizzando solo coordinatenon distanze?”. Sì, è lì che fit metodo si adatta dentro. Passiamo coordinate ad esso e ne approfittiamo GeoAnalyzer per costruire la matrice delle distanze, che viene poi elaborata normalmente da _fit_to_distances. In questo modo, se l’utente non vuole raccogliere personalmente le distanze, può delegare il compito utilizzando fit. Se, tuttavia, preferisce utilizzare dati personalizzati, può assemblarli in un file df_distances e passarlo a _fit_to_distances Invece.

4.2. TravelingSalesmanOptimizer implementazione

Seguiamo la progettazione delineata sopra per creare in modo incrementale l’ottimizzatore. Innanzitutto, una versione minimalista che si limita a creare un modello e a risolverlo, senza ancora alcuna analisi della soluzione. Nota come __repr__ Il metodo ci consente di conoscere il nome e il numero di siti contenuti nell’ottimizzatore ogni volta che lo stampiamo.

from typing import Tuple, List
class TravelingSalesmanOptimizer(BaseOptimizer):
"""Implements the Miller–Tucker–Zemlin formulation (1) of the 
Traveling Salesman Problem (TSP) as a linear integer program. 
The TSP can be stated like: "Given a set of locations (and usually 
their pair-wise distances), find the tour of minimal distance that 
traverses all of them exactly once and ends at the same location 
it started from. For a derivation of the mathematical model, see (2).
Parameters
----------
name : str
Optional name to give to a particular TSP instance
Attributes
----------
tour_ : list
List of locations sorted in visit order, obtained after fitting.
To avoid duplicity, the last site in the list is not the initial 
one, but the last one before closing the tour.
tour_distance_ : float
Total distance of the optimal tour, obtained after fitting.
Example
--------
>>> tsp = TravelingSalesmanOptimizer()
>>> tsp.fit(df_sites)  # fit to a dataframe of geo-coordinates
>>> tsp.tour_  # list ofsites sorted by visit order
References
----------
(1) https://en.wikipedia.org/wiki/Travelling_salesman_problem
(2) https://towardsdatascience.com/plan-optimal-trips-automatically-with-python-and-operations-research-models-part-2-fc7ee8198b6c
"""
def __init__(self, name=""):
super().__init__()
self.name = name
def _create_model(self, df_distances: pd.DataFrame) -> pyo.ConcreteModel:
""" Given a pandas dataframe of a distance matrix, create a Pyomo model 
of the TSP and populate it with that distance data """
model = pyo.ConcreteModel(self.name)
# a site has to be picked as the "initial" one, doesn't matter which 
# really; by lack of better criteria, take first site in dataframe 
# as the initial one
model.initial_site = df_distances.iloc(0).name
#===========  sets declaration  ===========#
list_of_sites = df_distances.index.tolist()
model.sites = pyo.Set(initialize=list_of_sites, 
domain=pyo.Any, 
doc="set of all sites to be visited (𝕊)")
def _rule_domain_arcs(model, i, j):
""" All possible arcs connecting the sites (𝔸) """
# only create pair (i, j) if site i and site j are different
return (i, j) if i != j else None 
rule = _rule_domain_arcs
model.valid_arcs = pyo.Set(
initialize=model.sites * model.sites,  # 𝕊 × 𝕊
filter=rule, doc=rule.__doc__)
model.sites_except_initial = pyo.Set(
initialize=model.sites - {model.initial_site}, 
domain=model.sites,
doc="All sites except the initial site"
)
#===========  parameters declaration  ===========#
def _rule_distance_between_sites(model, i, j):
""" Distance between site i and site j (𝐷𝑖𝑗) """
return df_distances.at(i, j)  # fetch the distance from dataframe
rule = _rule_distance_between_sites
model.distance_ij = pyo.Param(model.valid_arcs, 
initialize=rule, 
doc=rule.__doc__)
model.M = pyo.Param(initialize=1 - len(model.sites_except_initial),
doc="big M to make some constraints redundant")
#===========  variables declaration  ===========#
model.delta_ij = pyo.Var(model.valid_arcs, within=pyo.Binary, 
doc="Whether to go from site i to site j (𝛿𝑖𝑗)")
model.rank_i = pyo.Var(model.sites_except_initial, 
within=pyo.NonNegativeReals, 
bounds=(1, len(model.sites_except_initial)), 
doc=("Rank of each site to track visit order"))
#===========  objective declaration  ===========#
def _rule_total_distance_traveled(model):
""" total distance traveled """
return pyo.summation(model.distance_ij, model.delta_ij)
rule = _rule_total_distance_traveled
model.objective = pyo.Objective(rule=rule, 
sense=pyo.minimize, 
doc=rule.__doc__)
#===========  constraints declaration  ===========#
def _rule_site_is_entered_once(model, j):
""" each site j must be visited from exactly one other site """
return sum(model.delta_ij(i, j) 
for i in model.sites if i != j) == 1
rule = _rule_site_is_entered_once
model.constr_each_site_is_entered_once = pyo.Constraint(
model.sites, 
rule=rule, 
doc=rule.__doc__)
def _rule_site_is_exited_once(model, i):
""" each site i must departure to exactly one other site """
return sum(model.delta_ij(i, j) 
for j in model.sites if j != i) == 1
rule = _rule_site_is_exited_once
model.constr_each_site_is_exited_once = pyo.Constraint(
model.sites, 
rule=rule, 
doc=rule.__doc__)
def _rule_path_is_single_tour(model, i, j):
""" For each pair of non-initial sites (i, j), 
if site j is visited from site i, the rank of j must be 
strictly greater than the rank of i.
"""
if i == j:  # if sites coincide, skip creating a constraint
return pyo.Constraint.Skip
r_i = model.rank_i(i)
r_j = model.rank_i(j)
delta_ij = model.delta_ij(i, j)
return r_j >= r_i + delta_ij + (1 - delta_ij) * model.M
# cross product of non-initial sites, to index the constraint
non_initial_site_pairs = (
model.sites_except_initial * model.sites_except_initial)
rule = _rule_path_is_single_tour
model.constr_path_is_single_tour = pyo.Constraint(
non_initial_site_pairs,
rule=rule, 
doc=rule.__doc__)
self._store_model(model)  # method inherited from BaseOptimizer
return model
def _fit_to_distances(self, df_distances: pd.DataFrame) -> None:
self._name_index = df_distances.index.name
model = self._create_model(df_distances)
solution_exists = self._optimize(model)
return self
@property
def sites(self) -> Tuple(str):
""" Return tuple of site names the optimizer considers """
return self.model.sites.data() if self.is_model_created else ()
@property
def num_sites(self) -> int:
""" Number of locations to visit """
return len(self.sites)
@property
def initial_site(self):
return self.model.initial_site if self.is_fitted else None
def __repr__(self) -> str:
name = f"{self.name}, " if self.name else ''
return f"{self.__class__.__name__}({name}n={self.num_sites})"

Controlliamo rapidamente come si comporta l’ottimizzatore. Al momento dell’istanziazione, l’ottimizzatore non contiene alcun numero di siti, come mostra la stringa di rappresentazione, o un modello interno, e ovviamente non è montato:

tsp = TravelingSalesmanOptimizer("trial 1")
print(tsp)
#(Out): TravelingSalesmanOptimizer(trial 1, n=0)
print(tsp.is_model_created, tsp.is_fitted)
#(Out): (False, False)

Ora lo adattiamo ai dati di distanza e se non riceviamo un avviso significa che è andato tutto bene. Possiamo vedere che ora la stringa di rappresentazione ci dice che abbiamo fornito 9 siti, che esiste un modello interno e che l’ottimizzatore è stato adattato ai dati di distanza:

tsp._fit_to_distances(df_distances)
print(tsp)
#(Out): TravelingSalesmanOptimizer(trial 1, n=9)
print(tsp.is_model_created, tsp.is_fitted)
#(Out): (True, True)

Il fatto che sia stata trovata la soluzione ottimale è corroborato dalla presenza di valori definiti nelle variabili decisionali del rango del modello:

tsp.model.rank_i.get_values()

{'Sacre Coeur': 8.0,
'Louvre': 2.0,
'Montmartre': 7.0,
'Port de Suffren': 4.0,
'Arc de Triomphe': 5.0,
'Av. Champs Élysées': 6.0,
'Notre Dame': 1.0,
'Tour Eiffel': 3.0}

Queste variabili di rango rappresentano l’ordine cronologico delle fermate nel tour ottimale. Se ricordi da la loro definizionesono definiti su tutti i siti tranne quello iniziale⁵, ed è per questo che l’hotel non compare in essi. Facile, potremmo aggiungere l’hotel con posizione 0 e l’avremmo ottenuto la risposta al nostro problema. Non abbiamo bisogno di estrarre 𝛿ᵢⱼ, le variabili decisionali per il individuale archi del percorso, per sapere in quale ordine visitare i siti. Sebbene ciò sia vero, utilizzeremo comunque le variabili dell’arco 𝛿ᵢⱼ per estrarre l’esatta sequenza di fermate dal modello risolto.

💡 Agile non è necessario che lo sia fragile

Se il nostro unico obiettivo fosse risolvere il TSP, senza pensarci estendere Per consentire al modello di comprendere più dettagli del nostro problema nella vita reale, sarebbe sufficiente utilizzare le variabili di rango per estrarre il tour ottimale. Tuttavia, poiché il TSP è giusto il prototipo iniziale di quello che diventerà un modello più sofisticatoè meglio estrarre la soluzione dalle variabili decisionali dell’arco 𝛿ᵢⱼ, poiché saranno presenti in qualsiasi modello che implichi decisioni di routing. Tutte le altre variabili decisionali sono ausiliarie e, quando necessario, il loro compito è rappresentare stati o indicare condizioni dipendenti da VERO variabili decisionali, 𝛿ᵢⱼ. Come vedrai nei prossimi articoli, la scelta delle variabili di rango per estrarre il tour funziona per un modello TSP puro, ma non funzionerà per le sue estensioni che lo rendono opzionale per visitare alcuni siti. Quindi, se estraiamo la soluzione da 𝛿ᵢⱼ, il nostro approccio sarà generale e riutilizzabile, non importa quanto sia complesso il modello che stiamo utilizzando.

I vantaggi di questo approccio diventeranno evidenti negli articoli seguenti, in cui verranno aggiunti nuovi requisiti e quindi saranno necessarie ulteriori variabili all’interno del modello. Con il Perché coperto, passiamo al Come.

4.2.1 Estrazione del percorso ottimo dal modello

• Abbiamo la variabile 𝛿ᵢⱼ, indicizzata per possibili archi (i, j), dove 𝛿ᵢⱼ=0 significa che l’arco non è selezionato e 𝛿ᵢⱼ=1 significa che l’arco è selezionato.
• Vogliamo un dataframe in cui i siti sono nell’indice (come nel nostro input df_sites), e dove nella colonna è indicato il numero della fermata "visit_order".
• Noi scriviamo un metodo per estrarre tale dataframe dall’ottimizzatore montato. Questi sono i passaggi che seguiremo, con ogni passaggio incapsulato nei propri metodi di supporto:

1. Estrai gli archi selezionati da 𝛿ᵢⱼ, che rappresenta il tour. Fatto _get_selected_arcs_from_model.
2. Converti l’elenco degli archi (bordi) in un elenco di fermate (nodi). Fatto _get_stops_order_list.
3. Converti l’elenco delle fermate in un dataframe con una struttura coerente. Fatto _get_tour_stops_dataframe.

Poiché gli archi selezionati vengono mescolati (cioènon in “ordine di attraversamento”), ottenere un elenco di fermate ordinate non è così semplice. Per evitare codice contorto, sfruttiamo il fatto che gli archi rappresentano a graficoe usiamo l’oggetto grafico G_tour per percorrere in ordine i nodi del tour, arrivando facilmente alla lista.

import networkx as nx
# class TravelingSalesmanOptimizer(BaseOptimizer):
# def __init__()
# def _create_model()
# def _fit_to_distances()
# def sites()
# def num_sites()
# def initial_site()
_Arc = Tuple(str, str)
def _get_selected_arcs_from_model(self, model: pyo.ConcreteModel) -> List(_Arc):
"""Return the optimal arcs from the decision variable delta_{ij}
as an unordered list of arcs. Assumes the model has been solved"""
selected_arcs = (arc 
for arc, selected in model.delta_ij.get_values().items()
if selected)
return selected_arcs
def _extract_solution_as_graph(self, model: pyo.ConcreteModel) -> nx.Graph:
"""Extracts the selected arcs from the decision variables of the model, stores 
them in a networkX graph and returns such a graph"""
selected_arcs = self._get_selected_arcs_from_model(model)
self._G_tour = nx.DiGraph(name=model.name)
self._G_tour.add_edges_from(selected_arcs)
return self._G_tour
def _get_stops_order_list(self) -> List(str):
"""Return the stops of the tour in a list **ordered** by visit order"""
visit_order = ()
next_stop = self.initial_site  # by convention...
visit_order.append(next_stop)  # ...tour starts at initial site
G_tour = self._extract_solution_as_graph(self.model)
# starting at first stop, traverse the directed graph one arc at a time
for _ in G_tour.nodes:
# get consecutive stop and store it
next_stop = list(G_tour(next_stop))(0)
visit_order.append(next_stop)
# discard last stop in list, as it's repeated (the initial site) 
return visit_order(:-1)
def get_tour_stops_dataframe(self) -> pd.DataFrame:
"""Return a dataframe of the stops along the optimal tour"""
if self.is_fitted:
ordered_stops = self._get_stops_order_list()
df_stops = (pd.DataFrame(ordered_stops, columns=(self._name_index))
.reset_index(names='visit_order')  # from 0 to N
.set_index(self._name_index)  # keep index consistent
)
return df_stops
print("No solution found. Fit me to some data and try again")

Vediamo cosa ci offre questo nuovo metodo:

tsp = TravelingSalesmanOptimizer("trial 2")
tsp._fit_to_distances(df_distances)
tsp.get_tour_stops_dataframe()

IL visit_order La colonna indica che dall’hotel dovremmo andare a Notre Dame, poi al Louvre e così via, fino all’ultima fermata prima di chiudere il tour, Sacre Coeur. Dopodiché è banale tornare in albergo. Bene, ora abbiamo la soluzione in un formato facile da interpretare e con cui lavorare. Ma la sequenza delle fermate non è l’unica cosa che ci interessa. Anche il valore della funzione obiettivo è una metrica importante di cui tenere tracciapoiché è il criterio che guida le nostre decisioni. Per il nostro caso particolare del TSP, ciò significa ottenere la distanza totale del tour ottimale.

4.2.2 Estrazione dell’obiettivo ottimo dal modello

Allo stesso modo in cui non abbiamo utilizzato le variabili di rango per estrarre la sequenza delle fermate perché in modelli più complessi i loro valori non coinciderebbero con le fermate del tour, non utilizzeremo la funzione obiettivo direttamente per ottenere la distanza totale del giro, anche se anche qui entrambe le misure sono equivalenti. Nei modelli più complessi, la funzione obiettivo incorporerà anche altri targetquindi questa equivalenza non sarà più valida.

Per ora, semplificheremo le cose e creeremo un metodo non pubblico, _get_tour_total_distanceche ne indica chiaramente l’intento. I dettagli da cui deriva questa distanza sono nascosti e dipenderanno dagli obiettivi particolari a cui tengono i modelli più avanzati. Per ora, i dettagli sono semplici: ottenere il valore oggettivo del modello risolto.

# class TravelingSalesmanOptimizer(BaseOptimizer):
# def __init__()
# def _create_model()
# def _fit_to_distances()
# def sites()
# def num_sites()
# def initial_site()
# def _get_selected_arcs_from_model()
# def _extract_solution_as_graph()
# def _get_stops_order_list()
# def get_tour_stops_dataframe()
def _get_tour_total_distance(self) -> float:
"""Return the total distance of the optimal tour"""
if self.is_fitted:
# as the objective is an expression for the total distance, 
distance_tour = self.model.objective()  # we just get its value
return distance_tour
print("Optimizer is not fitted to any data, no optimal objective exists.")
return None

Potrebbe sembrare superfluo adesso, ma servirà a ricordare a noi stessi futuri che esiste un disegno per acquisire valori oggettivi che faremmo meglio a seguire. Controlliamolo:

tsp = TravelingSalesmanOptimizer("trial 3")
tsp._fit_to_distances(df_distances)
print(f"Total distance: {tsp._get_tour_total_distance()} m")
# (Out): Total distance: 14931.0 m

Sono circa 14,9 km. Poiché sia ​​il tour ottimale che la sua distanza sono importanti, facciamo in modo che l’ottimizzatore li memorizzi insieme ogni volta che _fit_to_distances il metodo viene chiamato, e solo quando viene trovata una soluzione ottimale.

4.2.3 Memorizzazione della soluzione negli attributi

Nell’implementazione di _fit_to_distances sopra, abbiamo semplicemente creato un modello e lo abbiamo risolto, non abbiamo eseguito alcuna analisi della soluzione memorizzata all’interno del modello. Ora modificheremo _fit_to_distances affinché quando la soluzione del modello ha successo, vengono creati e resi disponibili due nuovi attributi con le due parti rilevanti della soluzione: il tour_ e il tour_distance_. Per renderlo semplice, il tour_ L’attributo non restituirà il dataframe che abbiamo fatto in precedenza, restituirà l’elenco con le fermate ordinate. Il nuovo metodo _store_solution_from_model si occupa di questo.

# class TravelingSalesmanOptimizer(BaseOptimizer):
# def __init__()
# def _create_model()
# def sites()
# def num_sites()
# def initial_site()
# def _get_selected_arcs_from_model()
# def _extract_solution_as_graph()
# def _get_stops_order_list()
# def get_tour_stops_dataframe()
# def _get_tour_total_distance()
def _fit_to_distances(self, df_distances: pd.DataFrame):
"""Creates a model of the TSP using the distance matrix 
provided in `df_distances`, and then optimizes it. 
If the model has an optimal solution, it is extracted, parsed and 
stored internally so it can be retrieved.
Parameters
----------
df_distances : pd.DataFrame
Pandas dataframe where the indices and columns are the "cities" 
(or any site of interest) of the problem, and the cells of the 
dataframe contain the pair-wise distances between the cities, i.e.,
df_distances.at(i, j) contains the distance between i and j.
Returns
-------
self : object
Instance of the optimizer.
"""
model = self._create_model(df_distances)
solution_exists = self._optimize(model)
if solution_exists:
# if a solution wasn't found, the attributes won't exist
self._store_solution_from_model()
return self
#====================  solution handling  ====================
def _store_solution_from_model(self) -> None:
"""Extract the optimal solution from the model and create the "fitted 
attributes" `tour_` and `tour_distance_`"""
self.tour_ = self._get_stops_order_list()
self.tour_distance_ = self._get_tour_total_distance()

Adattiamo nuovamente l’ottimizzatore ai dati sulla distanza e vediamo quanto è facile ottenere subito la soluzione:

tsp = TravelingSalesmanOptimizer("trial 4")._fit_to_distances(df_distances)
print(f"Total distance: {tsp.tour_distance_} m")
print(f"Best tour:\n", tsp.tour_)
# (Out):
# Total distance: 14931.0 m
# Best tour:
# ('hotel', 'Notre Dame', 'Louvre', 'Tour Eiffel', 'Port de Suffren', 'Arc de Triomphe', 'Av. Champs Élysées', 'Montmartre', 'Sacre Coeur')

Carino. Ma possiamo fare ancora meglio. Per promuovere aumentare l’usabilità di questa classeconsentiamo all’utente di risolvere il problema fornendo solo il dataframe delle coordinate del sito. Poiché non tutti saranno in grado di raccogliere una matrice di distanza per i propri siti di interesse, la classe può occuparsene e fornire una matrice di distanza approssimativa. Ciò è stato fatto sopra nella sezione 3.2 con il file GeoAnalyzerqui lo inseriamo semplicemente sotto il nuovo fit metodo:

# class TravelingSalesmanOptimizer(BaseOptimizer):
# def __init__()
# def _create_model()
# def _fit_to_distances()
# def sites()
# def num_sites()
# def initial_site()
# def _get_selected_arcs_from_model()
# def _extract_solution_as_graph()
# def _get_stops_order_list()
# def get_tour_stops_dataframe()
# def _get_tour_total_distance()
# def _store_solution_from_model()
def fit(self, df_sites: pd.DataFrame):
"""Creates a model instance of the TSP problem using a 
distance matrix derived (see notes) from the coordinates provided 
in `df_sites`.
Parameters
----------
df_sites : pd.DataFrame
Dataframe of locations "the salesman" wants to visit, having the 
names of the locations in the index and at least one column 
named 'latitude' and one column named 'longitude'.
Returns
-------
self : object
Instance of the optimizer.
Notes
-----
The distance matrix used is derived from the coordinates of `df_sites`
using the ellipsoidal distance between any pair of coordinates, as 
provided by `geopy.distance.distance`."""
self._validate_data(df_sites)
self._name_index = df_sites.index.name
self._geo_analyzer = GeoAnalyzer()
self._geo_analyzer.add_locations(df_sites)
df_distances = self._geo_analyzer.get_distance_matrix(precision=0)
self._fit_to_distances(df_distances)
return self
def _validate_data(self, df_sites):
"""Raises error if the input dataframe does not have the expected columns"""
if not ('latitude' in df_sites and 'longitude' in df_sites):
raise ValueError("dataframe must have columns 'latitude' and 'longitude'")

E ora abbiamo raggiunto il nostro obiettivo: trova il tour ottimale solo dalle posizioni dei siti (e non dalle distanze come prima):

tsp = TravelingSalesmanOptimizer("trial 5")
tsp.fit(df_sites)
print(f"Total distance: {tsp.tour_distance_} m")
tsp.tour_
#(Out):
# Total distance: 14931.0 m
# ('hotel',
# 'Notre Dame',
# 'Louvre',
# 'Tour Eiffel',
# 'Port de Suffren',
# 'Arc de Triomphe',
# 'Av. Champs Élysées',
# 'Montmartre',
# 'Sacre Coeur')

4.3. TravelingSalesmanOptimizer per inesperti

Congratulazioni! Siamo arrivati ​​al punto in cui l’ottimizzatore è molto intuitivo da usare. Per mera comodità, aggiungerò un altro metodo che sarà molto utile in seguito quando lo faremo (analisi di sensibilità) e confronteremo i risultati di diversi modelli. L’ottimizzatore, così com’è adesso, mi dice l’ordine ottimale delle visite in un elenco o in un dataframe separato restituito da get_tour_stops_dataframe()ma mi piacerebbe che me lo dicesse l’ordine di visita entro trasformando il dataframe delle posizioni che lo do direttamente, restituendo lo stesso dataframe con una nuova colonna avente la sequenza ottimale di fermate. Il metodo fit_prescribe si occuperà di questo:

# class TravelingSalesmanOptimizer(BaseOptimizer):
# def __init__()
# def _create_model()
# def sites()
# def num_sites()
# def initial_site()
# def _get_selected_arcs_from_model()
# def _extract_solution_as_graph()
# def _get_stops_order_list()
# def get_tour_stops_dataframe()
# def _get_tour_total_distance()
# def _fit_to_distances()
# def _store_solution_from_model()
# def fit()
# def _validate_data()
def fit_prescribe(self, df_sites: pd.DataFrame, sort=True) -> pd.DataFrame:
"""In one line, take in a dataframe of locations and return 
a copy of it with a new column specifying the optimal visit order
that minimizes total distance.
Parameters
----------
df_sites : pd.DataFrame
Dataframe with the sites in the index and the geolocation 
information in columns (first column latitude, second longitude).
sort : bool (default=True)
Whether to sort the locations by visit order.
Returns
-------
df_sites_ranked : pd.DataFrame 
Copy of input dataframe `df_sites` with a new column, 'visit_order', 
containing the stop sequence of the optimal tour.
See Also
--------
fit : Solve a TSP from just site locations.
Examples
--------
>>> tsp = TravelingSalesmanOptimizer()
>>> df_sites_tour = tsp.fit_prescribe(df_sites)  # solution appended
"""
self.fit(df_sites)  # find optimal tour for the sites
if not self.is_fitted:  # unlikely to happen, but still
raise Exception("A solution could not be found. "
"Review data or inspect attribute `_results` for details."
)
# join input dataframe with column of solution
df_sites_ranked = df_sites.copy().join(self.get_tour_stops_dataframe())    
if sort:
df_sites_ranked.sort_values(by="visit_order", inplace=True)
return df_sites_ranked

Ora possiamo risolvere qualsiasi TSP in poco tempo una linea:

tsp = TravelingSalesmanOptimizer("Paris")
tsp.fit_prescribe(df_sites)

Se desideriamo conservare l’ordine originale delle posizioni così come erano in df_sitespossiamo farlo specificando sort=False:

tsp.fit_prescribe(df_sites, sort=False)

E se siamo curiosi possiamo anche verificare il numero di variabili e vincoli necessari al modello interno per risolvere la nostra particolare istanza del TSP. Ciò sarà utile durante il debug o l’analisi delle prestazioni.

tsp.print_model_info()
#(Out):
# Name: Paris
# - Num variables: 80
# - Num constraints: 74
# - Num objectives: 1