An aesthetic method to fixing Touring Salesman Issues successfully with Python | by Carlos J. Uribe

Right here we received’t begin from scratch. As acknowledged earlier, we already developed the code that builds a Pyomo mannequin of the TSP and solves it in sprint 3. And belief me, that was the toughest half. Now, we now have the simpler job of organizing what we did in a manner that makes it basic, hiding the main points whereas protecting the important parts seen. In a way, we wish the optimizer to seem like a “magic field” that even customers not conversant in math modeling are in a position to make use of to unravel their TSP issues intuitively.

4.1. TravelingSalesmanOptimizer design

Our optimizer class may have “core” strategies, doing the majority of the work, and “superficial” strategies, serving because the high-level interface of the category, which invoke the core strategies beneath.

These are the steps that can lie on the core of the optimizer’s logic:

1. Create a Pyomo mannequin out of a distance matrix. That is finished by the _create_model technique, which principally wraps the code of the proof-of-concept we already did. It accepts a dataframe of a distance matrix and builds a Pyomo mannequin out of it. The one essential distinction between what we did and what we’re doing is that, now, the preliminary website is just not hard-coded as merely "lodge", however is assumed to be the positioning of the primary row in df_distances. Within the basic case, thus, the preliminary website is taken to be the primary one within the coordinates dataframe⁴ df_sites. This generalization permits the optimizer to unravel any occasion.
2. (Try and) Resolve the mannequin. That is carried out within the _optimize technique inherited from BaseOptimizer, which returns True provided that an answer is discovered.
3. Extract the answer from the mannequin and parse it in a manner that’s straightforward to interpret and use. This occurs inside _store_solution_from_model, which is a technique that inspects the solved mannequin and extracts the values of the choice variables, and the worth of the target operate, to create the attributes tour_ and tour_distance_, respectively. This technique will get invoked provided that an answer exists, so if no resolution is discovered, the “resolution attributes” tour_ and tour_distance_ by no means get created. The advantage of that is that the presence of those two “resolution attributes”, after becoming, will inform the person of the existence of an answer. As a plus, the optimum values of each the variables and goal could be conveniently retrieved at any level, not essentially in the meanwhile of becoming.

The final 2 steps — discovering and extracting the answer — are wrapped contained in the final “core” technique, _fit_to_distances.

“However wait” — you would possibly suppose — “Because the identify implies, _fit_to_distances requires distances as enter; is not our purpose to unravel TSP issues utilizing solely coordinates, not distances?”. Sure, that is the place the match technique matches in. We move coordinates to it, and we reap the benefits of GeoAnalyzer to assemble the gap matrix, which is then processed usually by _fit_to_distances. On this manner, if the person doesn’t wish to accumulate the distances himself, he can delegate the duty by utilizing match. If, nevertheless, he prefers to make use of customized information, he can assemble it in a df_distances and move it to _fit_to_distances as an alternative.

4.2. TravelingSalesmanOptimizer implementation

Let’s comply with the design outlined above to incrementally construct the optimizer. First, a minimalist model that simply builds a mannequin and solves it — with none resolution parsing but. Discover how the __repr__ technique permits us to know the identify and variety of websites the optimizer accommodates at any time when we print it.

from typing import Tuple, Checklist
class TravelingSalesmanOptimizer(BaseOptimizer):
"""Implements the Miller–Tucker–Zemlin formulation [1] of the 
Touring Salesman Drawback (TSP) as a linear integer program. 
The TSP could be acknowledged like: "Given a set of areas (and often 
their pair-wise distances), discover the tour of minimal distance that 
traverses all of them precisely as soon as and ends on the similar location 
it began from. For a derivation of the mathematical mannequin, see [2].
Parameters
----------
identify : str
Non-compulsory identify to offer to a specific TSP occasion
Attributes
----------
tour_ : record
Checklist of areas sorted in go to order, obtained after becoming.
To keep away from duplicity, the final website within the record is just not the preliminary 
one, however the final one earlier than closing the tour.
tour_distance_ : float
Whole distance of the optimum tour, obtained after becoming.
Instance
--------
>>> tsp = TravelingSalesmanOptimizer()
>>> tsp.match(df_sites)  # match to a dataframe of geo-coordinates
>>> tsp.tour_  # record ofsites sorted by go to 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, identify=""):
tremendous().__init__()
self.identify = identify
def _create_model(self, df_distances: pd.DataFrame) -> pyo.ConcreteModel:
""" Given a pandas dataframe of a distance matrix, create a Pyomo mannequin 
of the TSP and populate it with that distance information """
mannequin = pyo.ConcreteModel(self.identify)
# a website must be picked because the "preliminary" one, does not matter which 
# actually; by lack of higher standards, take first website in dataframe 
# because the preliminary one
mannequin.initial_site = df_distances.iloc[0].identify
#===========  units declaration  ===========#
list_of_sites = df_distances.index.tolist()
mannequin.websites = pyo.Set(initialize=list_of_sites, 
area=pyo.Any, 
doc="set of all websites to be visited ()")
def _rule_domain_arcs(mannequin, i, j):
""" All potential arcs connecting the websites () """
# solely create pair (i, j) if website i and website j are completely different
return (i, j) if i != j else None 
rule = _rule_domain_arcs
mannequin.valid_arcs = pyo.Set(
initialize=mannequin.websites * mannequin.websites,  #  × 
filter=rule, doc=rule.__doc__)
mannequin.sites_except_initial = pyo.Set(
initialize=mannequin.websites - {mannequin.initial_site}, 
area=mannequin.websites,
doc="All websites besides the preliminary website"
)
#===========  parameters declaration  ===========#
def _rule_distance_between_sites(mannequin, i, j):
""" Distance between website i and website j () """
return df_distances.at[i, j]  # fetch the gap from dataframe
rule = _rule_distance_between_sites
mannequin.distance_ij = pyo.Param(mannequin.valid_arcs, 
initialize=rule, 
doc=rule.__doc__)
mannequin.M = pyo.Param(initialize=1 - len(mannequin.sites_except_initial),
doc="massive M to make some constraints redundant")
#===========  variables declaration  ===========#
mannequin.delta_ij = pyo.Var(mannequin.valid_arcs, inside=pyo.Binary, 
doc="Whether or not to go from website i to website j ()")
mannequin.rank_i = pyo.Var(mannequin.sites_except_initial, 
inside=pyo.NonNegativeReals, 
bounds=(1, len(mannequin.sites_except_initial)), 
doc=("Rank of every website to trace go to order"))
#===========  goal declaration  ===========#
def _rule_total_distance_traveled(mannequin):
""" whole distance traveled """
return pyo.summation(mannequin.distance_ij, mannequin.delta_ij)
rule = _rule_total_distance_traveled
mannequin.goal = pyo.Goal(rule=rule, 
sense=pyo.reduce, 
doc=rule.__doc__)
#===========  constraints declaration  ===========#
def _rule_site_is_entered_once(mannequin, j):
""" every website j should be visited from precisely one different website """
return sum(mannequin.delta_ij[i, j] 
for i in mannequin.websites if i != j) == 1
rule = _rule_site_is_entered_once
mannequin.constr_each_site_is_entered_once = pyo.Constraint(
mannequin.websites, 
rule=rule, 
doc=rule.__doc__)
def _rule_site_is_exited_once(mannequin, i):
""" every website i need to departure to precisely one different website """
return sum(mannequin.delta_ij[i, j] 
for j in mannequin.websites if j != i) == 1
rule = _rule_site_is_exited_once
mannequin.constr_each_site_is_exited_once = pyo.Constraint(
mannequin.websites, 
rule=rule, 
doc=rule.__doc__)
def _rule_path_is_single_tour(mannequin, i, j):
""" For every pair of non-initial websites (i, j), 
if website j is visited from website i, the rank of j should be 
strictly higher than the rank of i.
"""
if i == j:  # if websites coincide, skip making a constraint
return pyo.Constraint.Skip
r_i = mannequin.rank_i[i]
r_j = mannequin.rank_i[j]
delta_ij = mannequin.delta_ij[i, j]
return r_j >= r_i + delta_ij + (1 - delta_ij) * mannequin.M
# cross product of non-initial websites, to index the constraint
non_initial_site_pairs = (
mannequin.sites_except_initial * mannequin.sites_except_initial)
rule = _rule_path_is_single_tour
mannequin.constr_path_is_single_tour = pyo.Constraint(
non_initial_site_pairs,
rule=rule, 
doc=rule.__doc__)
self._store_model(mannequin)  # technique inherited from BaseOptimizer
return mannequin
def _fit_to_distances(self, df_distances: pd.DataFrame) -> None:
self._name_index = df_distances.index.identify
mannequin = self._create_model(df_distances)
solution_exists = self._optimize(mannequin)
return self
@property
def websites(self) -> Tuple[str]:
""" Return tuple of website names the optimizer considers """
return self.mannequin.websites.information() if self.is_model_created else ()
@property
def num_sites(self) -> int:
""" Variety of areas to go to """
return len(self.websites)
@property
def initial_site(self):
return self.mannequin.initial_site if self.is_fitted else None
def __repr__(self) -> str:
identify = f"{self.identify}, " if self.identify else ''
return f"{self.__class__.__name__}({identify}n={self.num_sites})"

Let’s rapidly test how the optimizer behaves. Upon instantiation, the optimizer doesn’t comprise any variety of websites, because the illustration string reveals, or an inside mannequin, and it’s in fact not fitted:

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

We now match it to the gap information, and if we don’t get a warning, it implies that all of it went nicely. We will see that now the illustration string tells us we offered 9 websites, there’s an inside mannequin, and that the optimizer was fitted to the gap information:

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)

That the optimum resolution was discovered is corroborated by the presence of particular values within the rank determination variables of the mannequin:

tsp.mannequin.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}

These rank variables signify the chronological order of the stops within the optimum tour. If you happen to recall from their definition, they’re outlined over all websites besides the preliminary one⁵, and that’s why the lodge doesn’t seem in them. Straightforward, we may add the lodge with rank 0, and there we might have the reply to our downside. We don’t must extract ᵢⱼ, the choice variables for the particular person arcs of the tour, to know through which order we must always go to the websites. Though that’s true, we’re nonetheless going to make use of the arc variables ᵢⱼ to extract the precise sequence of stops from the solved mannequin.

💡 Agile doesn’t must be fragile

If our solely purpose have been to unravel the TSP, with out seeking to prolong the mannequin to embody extra particulars of our real-life downside, it could be sufficient to make use of the rank variables to extract the optimum tour. Nonetheless, because the TSP is simply the preliminary prototype of what is going to change into a extra refined mannequin, we’re higher off extracting the answer from the arc determination variables ᵢⱼ, as they are going to be current in any mannequin that entails routing selections. All different determination variables are auxiliary, and, when wanted, their job is to signify states or point out situations dependant on the true determination variables, ᵢⱼ. As you’ll see within the subsequent articles, selecting the rank variables to extract the tour works for a pure TSP mannequin, however received’t work for extensions of it that make it optionally available to go to some websites. Therefore, if we extract the answer from ᵢⱼ, our method can be basic and re-usable, regardless of how complicated the mannequin we’re utilizing.

The advantages of this method will change into obvious within the following articles, the place new necessities are added, and thus further variables are wanted contained in the mannequin. With the why coated, let’s soar into the how.

4.2.1 Extracting the optimum tour from the mannequin

• Now we have the variable ᵢⱼ, listed by potential arcs (i, j), the place ᵢⱼ=0 means the arc is just not chosen and ᵢⱼ=1 means the arc is chosen.
• We wish a dataframe the place the websites are within the index (as in our enter df_sites), and the place the cease quantity is indicated within the column "visit_order".
• We write a technique to extract such dataframe from the fitted optimizer. These are the steps we’ll comply with, with every step encapsulated in its personal helper technique(s):

1. Extract the chosen arcs from ᵢⱼ, which represents the tour. Executed in _get_selected_arcs_from_model.
2. Convert the record of arcs (edges) into a listing of stops (nodes). Executed in _get_stops_order_list.
3. Convert the record of stops right into a dataframe with a constant construction. Executed in _get_tour_stops_dataframe.

As the chosen arcs are blended (i.e., not in “traversing order”), getting a listing of ordered stops is just not that straight-forward. To keep away from convoluted code, we exploit the truth that the arcs signify a graph, and we use the graph object G_tour to traverse the tour nodes so as, arriving on the record simply.

import networkx as nx
# class TravelingSalesmanOptimizer(BaseOptimizer):
# def __init__()
# def _create_model()
# def _fit_to_distances()
# def websites()
# def num_sites()
# def initial_site()
_Arc = Tuple[str, str]
def _get_selected_arcs_from_model(self, mannequin: pyo.ConcreteModel) -> Checklist[_Arc]:
"""Return the optimum arcs from the choice variable delta_{ij}
as an unordered record of arcs. Assumes the mannequin 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, mannequin: pyo.ConcreteModel) -> nx.Graph:
"""Extracts the chosen arcs from the choice variables of the mannequin, shops 
them in a networkX graph and returns such a graph"""
selected_arcs = self._get_selected_arcs_from_model(mannequin)
self._G_tour = nx.DiGraph(identify=mannequin.identify)
self._G_tour.add_edges_from(selected_arcs)
return self._G_tour
def _get_stops_order_list(self) -> Checklist[str]:
"""Return the stops of the tour in a listing **ordered** by go to order"""
visit_order = []
next_stop = self.initial_site  # by conference...
visit_order.append(next_stop)  # ...tour begins at preliminary website
G_tour = self._extract_solution_as_graph(self.mannequin)
# beginning at first cease, traverse the directed graph one arc at a time
for _ in G_tour.nodes:
# get consecutive cease and retailer it
next_stop = record(G_tour[next_stop])[0]
visit_order.append(next_stop)
# discard final cease in record, because it's repeated (the preliminary website) 
return visit_order[:-1]
def get_tour_stops_dataframe(self) -> pd.DataFrame:
"""Return a dataframe of the stops alongside the optimum 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)  # hold index constant
)
return df_stops
print("No resolution discovered. Match me to some information and take a look at once more")

Let’s see what this new technique offers us:

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

The visit_order column signifies we must always go from the lodge to Notre Dame, then to the Louvre, and so forth, till the final cease earlier than closing the tour, Sacre Coeur. After that, it is trivial that one should return to the lodge. Good, now we now have the answer in a format straightforward to interpret and work with. However the sequence of stops is just not all we care about. The worth of the target operate can be an essential metric to maintain monitor of, as it is the criterion guiding our selections. For our specific case of the TSP, this implies getting the entire distance of the optimum tour.

4.2.2 Extracting the optimum goal from the mannequin

In the identical method that we didn’t use the rank variables to extract the sequence of stops as a result of in additional complicated fashions their values wouldn’t coincide with the tour stops, we received’t use the target operate instantly to acquire the entire distance of the tour, despite the fact that, right here too, each measures are equal. In additional complicated fashions, the target operate may also incorporate different targets, so this equivalence will now not maintain.

For now, we’ll hold it easy and create a personal technique, _get_tour_total_distance, which clearly signifies the intent. The main points of the place this distance comes from are hidden, and can rely upon the actual targets that extra superior fashions care about. For now, the main points are easy: get the target worth of the solved mannequin.

# class TravelingSalesmanOptimizer(BaseOptimizer):
# def __init__()
# def _create_model()
# def _fit_to_distances()
# def websites()
# 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 entire distance of the optimum tour"""
if self.is_fitted:
# as the target is an expression for the entire distance, 
distance_tour = self.mannequin.goal()  # we simply get its worth
return distance_tour
print("Optimizer is just not fitted to any information, no optimum goal exists.")
return None

It might look superfluous now, nevertheless it’ll function a reminder to our future selves that there’s a design for grabbing goal values we’d higher comply with. Let’s test it:

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

It’s round 14.9 km. As each the optimum tour and its distance are essential, let’s make the optimizer retailer them collectively at any time when the _fit_to_distances technique will get referred to as, and solely when an optimum resolution is discovered.

4.2.3 Storing the answer in attributes

Within the implementation of _fit_to_distances above, we simply created a mannequin and solved it, we did not do any parsing of the answer saved contained in the mannequin. Now, we’ll modify _fit_to_distances in order that when the mannequin resolution succeeds, two new attributes are created and made accessible with the 2 related elements of the answer: the tour_ and the tour_distance_. To make it easy, the tour_ attribute will not return the dataframe we did earlier, it’ll return the record with ordered stops. The brand new technique _store_solution_from_model takes care of this.

# class TravelingSalesmanOptimizer(BaseOptimizer):
# def __init__()
# def _create_model()
# def websites()
# 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 mannequin of the TSP utilizing the gap matrix 
offered in `df_distances`, after which optimizes it. 
If the mannequin has an optimum resolution, it's extracted, parsed and 
saved internally so it may be retrieved.
Parameters
----------
df_distances : pd.DataFrame
Pandas dataframe the place the indices and columns are the "cities" 
(or any website of curiosity) of the issue, and the cells of the 
dataframe comprise the pair-wise distances between the cities, i.e.,
df_distances.at[i, j] accommodates the gap between i and j.
Returns
-------
self : object
Occasion of the optimizer.
"""
mannequin = self._create_model(df_distances)
solution_exists = self._optimize(mannequin)
if solution_exists:
# if an answer wasn't discovered, the attributes will not exist
self._store_solution_from_model()
return self
#====================  resolution dealing with  ====================
def _store_solution_from_model(self) -> None:
"""Extract the optimum resolution from the mannequin and create the "fitted 
attributes" `tour_` and `tour_distance_`"""
self.tour_ = self._get_stops_order_list()
self.tour_distance_ = self._get_tour_total_distance()

Let’s match the optimizer once more to the gap information and see how straightforward it’s to get the answer now:

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

Good. However we are able to do even higher. To additional improve the usability of this class, let’s permit the person to unravel the issue by solely offering the dataframe of websites coordinates. As not everybody will be capable of accumulate a distance matrix for his or her websites of curiosity, the category can maintain it and supply an approximate distance matrix. This was finished above in part 3.2 with the GeoAnalyzer, right here we simply put it below the brand new match technique:

# class TravelingSalesmanOptimizer(BaseOptimizer):
# def __init__()
# def _create_model()
# def _fit_to_distances()
# def websites()
# 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 match(self, df_sites: pd.DataFrame):
"""Creates a mannequin occasion of the TSP downside utilizing a 
distance matrix derived (see notes) from the coordinates offered 
in `df_sites`.
Parameters
----------
df_sites : pd.DataFrame
Dataframe of areas "the salesperson" desires to go to, having the 
names of the areas within the index and not less than one column 
named 'latitude' and one column named 'longitude'.
Returns
-------
self : object
Occasion of the optimizer.
Notes
-----
The space matrix used is derived from the coordinates of `df_sites`
utilizing the ellipsoidal distance between any pair of coordinates, as 
offered by `geopy.distance.distance`."""
self._validate_data(df_sites)
self._name_index = df_sites.index.identify
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 enter dataframe doesn't have the anticipated columns"""
if not ('latitude' in df_sites and 'longitude' in df_sites):
elevate ValueError("dataframe will need to have columns 'latitude' and 'longitude'")

And now we now have achieved our purpose: discover the optimum tour from simply the websites areas (and never from the distances as earlier than):

tsp = TravelingSalesmanOptimizer("trial 5")
tsp.match(df_sites)
print(f"Whole distance: {tsp.tour_distance_} m")
tsp.tour_
#[Out]:
# Whole 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 for dummies

Congratulations! We reached the purpose the place the optimizer could be very intuitive to make use of. For mere comfort, I’ll add one other technique that can be fairly useful afterward after we do [sensitivity analysis] and examine the outcomes of various fashions. The optimizer, as it’s now, tells me the optimum go to order in a listing, or in a separate dataframe returned by get_tour_stops_dataframe(), however I might prefer it to inform me the go to order by reworking the areas dataframe that I give it instantly—by returning the identical dataframe with a brand new column having the optimum sequence of stops. The tactic fit_prescribe can be in control of this:

# class TravelingSalesmanOptimizer(BaseOptimizer):
# def __init__()
# def _create_model()
# def websites()
# 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 match()
# def _validate_data()
def fit_prescribe(self, df_sites: pd.DataFrame, kind=True) -> pd.DataFrame:
"""In a single line, soak up a dataframe of areas and return 
a duplicate of it with a brand new column specifying the optimum go to order
that minimizes whole distance.
Parameters
----------
df_sites : pd.DataFrame
Dataframe with the websites within the index and the geolocation 
info in columns (first column latitude, second longitude).
kind : bool (default=True)
Whether or not to kind the areas by go to order.
Returns
-------
df_sites_ranked : pd.DataFrame 
Copy of enter dataframe `df_sites` with a brand new column, 'visit_order', 
containing the cease sequence of the optimum tour.
See Additionally
--------
match : Resolve a TSP from simply website areas.
Examples
--------
>>> tsp = TravelingSalesmanOptimizer()
>>> df_sites_tour = tsp.fit_prescribe(df_sites)  # resolution appended
"""
self.match(df_sites)  # discover optimum tour for the websites
if not self.is_fitted:  # unlikely to occur, however nonetheless
elevate Exception("An answer couldn't be discovered. "
"Evaluation information or examine attribute `_results` for particulars."
)
# be part of enter dataframe with column of resolution
df_sites_ranked = df_sites.copy().be part of(self.get_tour_stops_dataframe())    
if kind:
df_sites_ranked.sort_values(by="visit_order", inplace=True)
return df_sites_ranked

Now we are able to resolve any TSP in simply one line:

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

If we’d prefer to preserve the unique order of areas as they have been in df_sites, we are able to do it by specifying kind=False:

tsp.fit_prescribe(df_sites, kind=False)

And if we’re curious we are able to additionally test the variety of variables and constraints the inner mannequin wanted to unravel our specific occasion of the TSP. This can be helpful when doing debugging or efficiency evaluation.

tsp.print_model_info()
#[Out]:
# Identify: Paris
# - Num variables: 80
# - Num constraints: 74
# - Num goals: 1