Getting Started
Get a brief introduction to what we’ll learn in this course.
We'll cover the following
The Traveling Salesperson Problem (TSP) is a classic optimization task. It involves finding the shortest possible route between a set of locations, visiting each place only once, and returning to the starting point.
Why take this course?
TSP is a useful programming task because it’s a good example of a real-world problem with a wide range of applications. In addition to route optimization, it can also be used to solve problems in logistics and biology. This course uses Python to solve TSP because it’s one of the most popular programming languages in the field of data science. Learning how to solve TSP with Python can help us become more efficient problem solvers and develop our programming skills. We’ll enrich geospatial data through data mining techniques, such as clustering, and add real value through visualizations. In this TSP course, we’ll learn to solve complex optimization problems to fully and approximately minimize routes and costs, all this through the development of creative solutions.
Press + to interact
What makes this course special?
This course demonstrates the programmatic solution of TSP.
Programming is key to success.
It shows how to visually present data-enriched results.
Data visualization is key to understanding.
Finally, a TSP app is programmed and deployed.
Deployment is key to availability.
By taking a holistic approach, we’ll solve TSP, learn to visualize the results, and deploy the app. The course is designed to make it as easy as possible to apply the techniques we learn to our own data.
How is this course structured?
A general outline of this course is as follows:
2D and 3D geodiscovery
Calculating distances
Calculating shortest routes
Adding additional features and creating a dashboard (sales, margin, etc.)
Building an application
Deploying the application (PyInstaller, Docker, GCP)
We’ll approach the task of solving TSP with Python step by step, using a real-life example. That is all we need, and any additional Python packages used will be explained in detail. No prior experience is needed to take this course. However, already having some (Python) programming knowledge definitely helps. Because we’ll be working on TSP using a concrete example, we’ll learn a lot of basic Python tips and tricks. Among other things, we’ll create an interactive dashboard during this course similar to the one below, which will demonstrate various parameters of TSP.
# Import necessary libraries
from dash import Dash, html, dcc, Input, Output
import pandas as pd
import plotly.express as px
import numpy as np
# to draw route lines
import plotly.graph_objects as go
# read data from CSV file and perform data transformations
df = pd.read_csv('StoreClusterCwDashi.csv')
# group the data by specified columns and calculate the mean for each group
crossDf = df.groupby(['CW', 'Store', 'Segment', 'StoreName']).mean()
# stack the grouped data to create a Pandas Series 'sf'
sf = crossDf.stack()
# convert the Pandas Series 'sf' back into a DataFrame called 'crossDf'
crossDf = pd.DataFrame(sf)
# reset the index of the DataFrame and move index levels to columns
crossDf = crossDf.reset_index()
# rename specific columns in the DataFrame
crossDf.rename(columns={'level_4': 'Indicator Name', 0: 'Value', 'CW': 'CW', 'StoreName': 'Store Name'}, inplace=True)
# get shortest route
shortesRoute = pd.read_csv('ShortestRoute.csv', sep=';')
longitude = shortesRoute['lon']
latitude = shortesRoute['lat']
# initialize the Dash app
app = Dash(__name__, title='Educative TSP', update_title='Educative is updating..')
PAGE_SIZE = 5
image_path = 'assets/dashboard-educative-logo.png'
# define the layout of the app
app.layout = html.Div([
# Header with logo
html.Div([
html.H1('', style={'display': 'inline-block', 'height': '50px'}),
html.Img(src=image_path, style={'height': '50px'})
]),
html.Div([
dcc.Graph(
id='crossfilter-indicator-scatter', config={
"displaylogo": False,
'modeBarButtonsToRemove': ['pan2d']},
hoverData={'points': [{'customdata': 0}]}
),
dcc.Graph(
id='crossfilter-indicator-scatters', config={
"displaylogo": False,
'modeBarButtonsToRemove': []}
),
], style={'width': '49%', 'display': 'inline-block', 'padding': '0 20'}),
html.Div([
dcc.Graph(id='x-time-series', config={
"displaylogo": False,
'modeBarButtonsToRemove': ['pan2d']}, ),
dcc.Graph(id='y-time-series', config={
"displaylogo": False,
'modeBarButtonsToRemove': ['pan2d']}, ),
dcc.Graph(id='z-time-series', config={
"displaylogo": False,
'modeBarButtonsToRemove': ['pan2d']}, ),
dcc.Graph(id='y-time-series3', config={ # third graph
"displaylogo": False,
'modeBarButtonsToRemove': ['pan2d']}, ),
], style={'display': 'inline-block', 'width': '49%'}),
html.P("Please use the sliders below to select the KPI."),
html.Div([
html.Div([
html.Div([
dcc.Dropdown(
crossDf['Indicator Name'].unique(),
'NetSales',
id='crossfilter-xaxis-column',
)
,
dcc.RadioItems(
[],
'Linear',
id='crossfilter-xaxis-type',
labelStyle={'display': 'inline-block', 'marginTop': '5px'}
)
]),
],
style={'width': '49%', 'display': 'inline-block'}),
html.Div([
dcc.Dropdown(
crossDf['Indicator Name'].unique(),
'Recency',
id='crossfilter-yaxis-column'
)
,
dcc.Dropdown(
crossDf['Indicator Name'].unique(),
'Frequency',
id='crossfilter-zaxis-column'
)
,
dcc.Dropdown(
crossDf['Indicator Name'].unique(),
'OverallScore',
id='crossfilter-qaxis-column'
),
dcc.Dropdown(id='continent-dropdown',
options=[{'label': i, 'value': i} for i in np.append([0], crossDf['Store Name'].unique())],
multi=True, value=0
),
dcc.Dropdown(id='ClusterCat-dropdown',
options=[{'label': i, 'value': i} for i in np.append(['All'], crossDf['Segment'].unique())],
multi=True, value='All'
),
dcc.RadioItems(
[],
'Linear',
id='crossfilter-yaxis-type',
labelStyle={'display': 'inline-block', 'marginTop': '5px'}
)
], style={'width': '49%', 'float': 'right', 'display': 'inline-block'})
], style={
'padding': '10px 5px'
}),
html.Div(dcc.Slider(
crossDf['CW'].min(),
crossDf['CW'].max(),
step=None,
id='crossfilter-CW--slider',
value=crossDf['CW'].max(),
marks={str(int): str(int) for int in crossDf['CW'].unique()}
), style={'width': '49%', 'padding': '0px 20px 20px 20px'}),
])
@app.callback(
Output('crossfilter-indicator-scatter', 'figure'),
Output('crossfilter-indicator-scatters', 'figure'),
Input('crossfilter-xaxis-column', 'value'), # 1st input
Input('crossfilter-yaxis-column', 'value'), # 2nd input
Input('crossfilter-zaxis-column', 'value'), # 3rd input
Input('crossfilter-xaxis-type', 'value'), # 4th input
Input('crossfilter-yaxis-type', 'value'), # 5th input
Input('continent-dropdown', 'value'), # SpHA
Input('crossfilter-CW--slider', 'value'), # 6th input
Input('crossfilter-qaxis-column', 'value'),
Input('ClusterCat-dropdown', 'value'))
def update_graph(xaxis_column_name, yaxis_column_name, zaxis_column_name,
xaxis_type, yaxis_type, Cust_value,
CW_value, qaxis_column_name, CusterCat_value):
# # filtering based on the slide and dropdown selection
if Cust_value == 0:
crossDff = crossDf.loc[crossDf['CW'] == CW_value]
else:
crossDff = crossDf.loc[(crossDf['CW'] == CW_value) & (crossDf['Store Name'].isin(Cust_value))]
if CusterCat_value == 'All':
crossDff = crossDff.loc[crossDff['CW'] == CW_value]
else:
crossDff = crossDff.loc[(crossDff['CW'] == CW_value) & (crossDff['Segment'].isin(CusterCat_value))]
fig = px.scatter_geo(lat=crossDff[crossDff['Indicator Name'] == 'lat']['Value'],
lon=crossDff[crossDff['Indicator Name'] == 'lon']['Value'],
hover_name=crossDff.loc[crossDf['Indicator Name'] == yaxis_column_name]['Store Name'],
projection="natural earth",
size=crossDff[crossDff['Indicator Name'] == xaxis_column_name]['Value'],
color=crossDff[crossDff['Indicator Name'] == yaxis_column_name][
'Value']) # fitbounds="locations" for zoom
# added route between stores
for i in range(1, len(shortesRoute)):
start_lat = shortesRoute.loc[i - 1, 'lat']
start_lon = shortesRoute.loc[i - 1, 'lon']
end_lat = shortesRoute.loc[i, 'lat']
end_lon = shortesRoute.loc[i, 'lon']
line_trace = go.Scattergeo(
lat=[start_lat, end_lat, None],
lon=[start_lon, end_lon, None],
mode='lines',
line=dict(width=2, color='blue')
)
fig.add_trace(line_trace)
# removes the legend for the routes
fig.update_layout(
showlegend=False
)
# calculate the longitude and latitude ranges with padding
padding_factor = 0.01
min_lon = longitude.min() - padding_factor
max_lon = longitude.max() + padding_factor
min_lat = latitude.min() - padding_factor
max_lat = latitude.max() + padding_factor
# set the ranges to zoom to the area of store locations
fig.update_geos(lonaxis_range=[min_lon, max_lon], lataxis_range=[min_lat, max_lat])
fig.update_traces(customdata=crossDff[crossDff['Indicator Name'] == yaxis_column_name][
'Store Name']) # updating of selected cust above first time series chart
fig.update_xaxes(title=xaxis_column_name,
type='linear' if xaxis_type == 'Linear' else 'log') # updating of x in first scatter graph
fig.update_yaxes(title=yaxis_column_name,
type='linear' if yaxis_type == 'Linear' else 'log') # updating of y in first scatter graph
fig.update_layout(margin={'l': 40, 'b': 40, 't': 10, 'r': 0}, hovermode='closest', template="plotly_white")
fig2 = px.scatter_3d(x=crossDff[crossDff['Indicator Name'] == xaxis_column_name]['Value'],
y=crossDff[crossDff['Indicator Name'] == yaxis_column_name]['Value'],
z=crossDff[crossDff['Indicator Name'] == zaxis_column_name]['Value'],
color=crossDff[crossDff['Indicator Name'] == xaxis_column_name]['Segment'],
hover_name=crossDff[crossDff['Indicator Name'] == yaxis_column_name]['Store Name'],
labels=crossDff[crossDff['Indicator Name'] == xaxis_column_name]['Segment']
# ,labels={"color":zaxis_column_name}
)
fig2.update_traces(customdata=crossDff[crossDff['Indicator Name'] == yaxis_column_name]['Store Name'])
fig2.update_xaxes(title=xaxis_column_name, type='linear' if xaxis_type == 'Linear' else 'log')
fig2.update_yaxes(title=yaxis_column_name, type='linear' if yaxis_type == 'Linear' else 'log')
fig2.update_yaxes(title=zaxis_column_name, type='linear' if yaxis_type == 'Linear' else 'log')
fig2.update_layout(margin={'l': 40, 'b': 40, 't': 10, 'r': 0}, hovermode='closest', showlegend=True,
template="plotly_white")
return fig, fig2
def create_time_series(crossDff, axis_type, title):
fig = px.scatter(crossDff, x='CW', y='Value')
fig.update_traces(mode='lines+markers')
fig.update_xaxes(showgrid=False, type='category') # only display int for weeks on x axis
fig.update_yaxes(type='linear' if axis_type == 'Linear' else 'log')
fig.add_annotation(x=0, y=0.85, xanchor='left', yanchor='bottom',
xref='paper', yref='paper', showarrow=False, align='left',
text=title)
fig.update_layout(height=225, margin={'l': 20, 'b': 30, 'r': 10, 't': 10}, template="plotly_white")
return fig
def create_Sp_graph(crossDff, axis_type, title):
fig = px.scatter(crossDff, x='CW', y='Value')
fig.update_traces(mode='lines+markers')
fig.update_xaxes(showgrid=False, type='category') # only display int for weeks on x axis
fig.update_yaxes(type='linear' if axis_type == 'Linear' else 'log')
fig.add_annotation(x=0, y=0.85, xanchor='left', yanchor='bottom',
xref='paper', yref='paper', showarrow=False, align='left',
text=title)
fig.update_layout(height=225, margin={'l': 20, 'b': 30, 'r': 10, 't': 10}, template="plotly_white")
return fig
def create_time_seriesSp(crossDff, axis_type, title):
fig = px.scatter(crossDff, x='CW', y='Value')
fig.update_traces(mode='lines+markers')
fig.update_xaxes(showgrid=False, type='category') # only display int for weeks on x axis
fig.update_yaxes(type='linear' if axis_type == 'Linear' else 'log')
fig.add_annotation(x=0, y=0.85, xanchor='left', yanchor='bottom',
xref='paper', yref='paper', showarrow=False, align='left',
text=title)
fig.update_layout(height=225, margin={'l': 20, 'b': 30, 'r': 10, 't': 10}, template="plotly_white")
return fig
@app.callback(
Output('x-time-series', 'figure'),
Input('crossfilter-indicator-scatter', 'hoverData'),
Input('crossfilter-xaxis-column', 'value'),
Input('crossfilter-xaxis-type', 'value'))
def update_y_timeseries(hoverData, xaxis_column_name, axis_type):
country_name = hoverData['points'][0]['customdata']
crossDff = crossDf[crossDf['Store Name'] == country_name]
crossDff = crossDff[crossDff['Indicator Name'] == xaxis_column_name]
title = '<b>{}</b><br>{}'.format(country_name, xaxis_column_name)
return create_time_series(crossDff, axis_type, title)
@app.callback(
Output('y-time-series', 'figure'),
Input('crossfilter-indicator-scatter', 'hoverData'),
Input('crossfilter-yaxis-column', 'value'),
Input('crossfilter-yaxis-type', 'value'))
def update_x_timeseries(hoverData, yaxis_column_name, axis_type):
crossDff = crossDf[crossDf['Store Name'] == hoverData['points'][0]['customdata']]
crossDff = crossDff[crossDff['Indicator Name'] == yaxis_column_name]
return create_time_series(crossDff, axis_type, yaxis_column_name)
@app.callback( # third time series chart
Output('z-time-series', 'figure'),
Input('crossfilter-indicator-scatter', 'hoverData'),
Input('crossfilter-zaxis-column', 'value'),
Input('crossfilter-yaxis-type', 'value'))
def update_x_timeseries(hoverData, zaxis_column_name, axis_type):
crossDff = crossDf[crossDf['Store Name'] == hoverData['points'][0]['customdata']]
crossDff = crossDff[crossDff['Indicator Name'] == zaxis_column_name]
return create_Sp_graph(crossDff, axis_type, zaxis_column_name)
@app.callback( # fourth time series chart
Output('y-time-series3', 'figure'),
Input('crossfilter-indicator-scatter', 'hoverData'),
Input('crossfilter-qaxis-column', 'value'),
Input('crossfilter-yaxis-type', 'value'))
def update_x_timeseries(hoverData, zaxis_column_name, axis_type):
crossDff = crossDf[crossDf['Store Name'] == hoverData['points'][0]['customdata']]
crossDff = crossDff[crossDff['Indicator Name'] == zaxis_column_name]
return create_time_seriesSp(crossDff, axis_type, zaxis_column_name)
# run the app
if __name__ == '__main__':
app.run(debug=True, host = '0.0.0.0',port=8100) Interactive dashboard (please click the link to see it running)
With this expertise, we’ll be able to successfully tackle other optimization problems using Python, such as optimizing the sequence of tasks in a manufacturing process, etc.