“Traversing the City of Dreams: Mapping the Perfect Tour using Python and Folium”
6 min readMar 2, 2023
Traveling Salesman Problem:
The Travelling Salesman Problem (TSP) is a classic optimization problem in computer science and operations research. It is an NP-hard problem that seeks to find the shortest possible route that visits a set of cities exactly once and returns to the starting city. The problem is commonly used to model a wide range of real-world applications, including logistics, transportation, and routing problems.
The TSP has been extensively studied in the literature, and numerous algorithms have been proposed to solve it. The most straightforward approach is to use a brute force algorithm that generates all possible permutations of the cities and calculates the length of each route. However, this approach becomes computationally intractable for large numbers of cities.
To solve the TSP for large numbers of cities, several heuristic algorithms have been developed. These algorithms are designed to quickly find a near-optimal solution that is close to the global optimum. One of the most popular heuristic algorithms for the TSP is the nearest neighbor algorithm, which constructs a tour by starting at a random city and repeatedly visiting the closest unvisited city until all cities have been visited.
Would you like to test the given code with cities of your own choosing?
Example code:
Import required libraries:
import pandas as pd
import numpy as np
import folium
from sklearn.neighbors import NearestNeighbors
import requests
import matplotlib.pyplot as plt
import imageio
import datetime
from geopy import distance
from folium import plugins
Get the locations:
# Function to get the longitude and latitude of a given city
def get_lat_lng(city):
url = "https://nominatim.openstreetmap.org/search"
params = {
"q": city,
"format": "jsonv2"
}
response = requests.get(url, params=params)
response_json = response.json()
if response_json:
return (response_json[0]['lat'], response_json[0]['lon'])
else:
return None
# Example usage
print("Enter the number of cities : ")
number_of_cities = int(input())
# Create an empty DataFrame
city_df = pd.DataFrame(columns=['City', 'Latitude', 'Longitude'])
# Loop through the cities and add them to the DataFrame
for i in range(number_of_cities):
print("Enter the name of the city : ")
city = input()
lat, lng = get_lat_lng(city)
print("Latitude of {} is {}".format(city, lat))
print("Longitude of {} is {}".format(city, lng))
city_df = city_df.append({'City': city, 'Latitude': lat, 'Longitude': lng}, ignore_index=True)
# Save the DataFrame as a CSV file
city_df.to_csv('city_coordinates.csv', index=False)
Find the shortest tour:
# Step 1: Load the data
df = pd.read_csv('city_coordinates.csv')
# Step 2: Calculate pairwise distances
X = np.array(df[['Latitude', 'Longitude']])
city_names = df['City']
nbrs = NearestNeighbors(n_neighbors=len(X), algorithm='ball_tree').fit(X)
distances, indices = nbrs.kneighbors(X)
# Step 3: Find the shortest tour
visited = np.zeros(len(X), dtype=bool)
visited[0] = True
tour = [0]
current = 0
for i in range(len(X)-1):
unvisited_mask = np.logical_not(visited[indices[current]])
if np.any(unvisited_mask):
nearest = indices[current][unvisited_mask][0].item()
else:
nearest = None
tour.append(nearest)
visited[nearest] = True
current = nearestPlot the cities:
fig, ax = plt.subplots(figsize=(20, 15))
ax.plot(df['Longitude'], df['Latitude'], '*', markersize=18, color='blue')
for i, name in enumerate(df['City']):
ax.annotate(name, (df['Longitude'][i], df['Latitude'][i]), fontsize=20)
Plot the tour and save it as gif:
# Step 4: Plot the tour
fig, ax = plt.subplots(figsize=(20, 15))
ax.plot(df['Longitude'], df['Latitude'], '*', markersize=28, color='blue')
for i, name in enumerate(df['City']):
ax.annotate(name, (df['Longitude'][i], df['Latitude'][i]), fontsize=20)
for i in range(len(tour)-1):
ax.plot([df['Longitude'][tour[i]], df['Longitude'][tour[i+1]]],
[df['Latitude'][tour[i]], df['Latitude'][tour[i+1]]], 'r-',linewidth = 4)
# Save the figure as an image
plt.savefig('tour_frame{:03d}.png'.format(i))
ax.plot([df['Longitude'][tour[-1]], df['Longitude'][tour[0]]],
[df['Latitude'][tour[-1]], df['Latitude'][tour[0]]], 'r-',linewidth = 4)
# Save the figure as an image
plt.savefig('tour_frame{:03d}.png'.format(len(tour)-1))
ax.set_xlabel('Longitude')
ax.set_ylabel('Latitude')
# Create an animated GIF from the images
images = []
for i in range(len(tour)):
images.append(imageio.imread('tour_frame{:03d}.png'.format(i)))
imageio.mimsave('tour_tsp.gif', images, fps=0.5)
plt.show()
Watch the animation GIF:
Plot the cities on a geographical map:
# Step 5: Plot the cities on a map
m = folium.Map(location=[df.Latitude[0],df.Longitude[0]], zoom_start=7)
for i in range(len(tour)-1):
coords1 = (df.iloc[tour[i]]['Latitude'], df.iloc[tour[i]]['Longitude'])
coords2 = (df.iloc[tour[i+1]]['Latitude'], df.iloc[tour[i+1]]['Longitude'])
folium.Marker(location=coords1).add_to(m)
coords1 = (df.iloc[tour[0]]['Latitude'], df.iloc[tour[0]]['Longitude'])
coords2 = (df.iloc[tour[-1]]['Latitude'], df.iloc[tour[-1]]['Longitude'])
folium.Marker(location=coords1).add_to(m)
folium.Marker(location=coords2).add_to(m)
m
Watch the end result:
# Step 4: Animate the tour on a map
m = folium.Map(location=[df.Latitude[0],df.Longitude[0]], zoom_start = 5)
for i in range(len(tour)-1):
coords1 = (df.iloc[tour[i]]['Latitude'], df.iloc[tour[i]]['Longitude'])
coords2 = (df.iloc[tour[i+1]]['Latitude'], df.iloc[tour[i+1]]['Longitude'])
folium.Marker(location=coords1).add_to(m)
coords1 = (df.iloc[tour[0]]['Latitude'], df.iloc[tour[0]]['Longitude'])
coords2 = (df.iloc[tour[-1]]['Latitude'], df.iloc[tour[-1]]['Longitude'])
folium.Marker(location=coords1).add_to(m)
folium.Marker(location=coords2).add_to(m)
for i in range(len(tour)-1):
coords1 = (df.iloc[tour[i]]['Latitude'], df.iloc[tour[i]]['Longitude'])
coords2 = (df.iloc[tour[i+1]]['Latitude'], df.iloc[tour[i+1]]['Longitude'])
folium.Marker(location=coords1, icon=folium.Icon(color='red')).add_to(m)
folium.PolyLine(locations=[coords1, coords2], color='blue').add_to(m)
coords1 = (df.iloc[tour[0]]['Latitude'], df.iloc[tour[0]]['Longitude'])
coords2 = (df.iloc[tour[-1]]['Latitude'], df.iloc[tour[-1]]['Longitude'])
folium.Marker(location=coords1, icon=folium.Icon(color='red')).add_to(m)
folium.Marker(location=coords2, icon=folium.Icon(color='red')).add_to(m)
folium.PolyLine(locations=[coords1, coords2], color='blue').add_to(m)
# Open the last frame of the animation or the end result
m
Watch the animation step by step:
# Step 1: Create the features list
features = []
# Set the start time
start_time = datetime.datetime.now()
# Loop through the tour
for i in range(len(tour)-1):
# Get the travel time to the next location
# time_minutes = df.iloc[i]['TravelTimeMinutes']
# Get the coordinates of the start and end points
start_coord = (df.iloc[tour[i]]['Latitude'], df.iloc[tour[i]]['Longitude'])
end_coord = (df.iloc[tour[i+1]]['Latitude'], df.iloc[tour[i+1]]['Longitude'])
# Calculate the distance and time to travel between the points
dist = distance.distance(start_coord, end_coord).km
time_hours = dist/60 # Assuming an average speed of 60 km/h
time_minutes = int(round(time_hours*60))
# Calculate the end time
end_time = start_time + datetime.timedelta(minutes=time_minutes)
# Create the feature with the actual travel time
feature = {
"type": "Feature",
"geometry": {
"type": "LineString",
"coordinates": [
[df.iloc[tour[i]]['Longitude'], df.iloc[tour[i]]['Latitude']],
[df.iloc[tour[i+1]]['Longitude'], df.iloc[tour[i+1]]['Latitude']]
],
},
"properties": {
'style': {'color': 'red'},
'icon': 'circle',
'iconstyle': {
'fillColor': '#0000FF',
'fillOpacity': 0.8,
'stroke': 'true',
'radius': 10
},
"times": [
start_time.strftime('%Y-%m-%dT%H:%M:%S'),
end_time.strftime('%Y-%m-%dT%H:%M:%S')
]
},
}
# Add the feature to the list of features
features.append(feature)
# Update the start time
start_time = end_time
# Get the coordinates of the start and end points
start_coord = (df.iloc[tour[-1]]['Latitude'], df.iloc[tour[-1]]['Longitude'])
end_coord = (df.iloc[tour[0]]['Latitude'], df.iloc[tour[0]]['Longitude'])
# Calculate the distance and time to travel between the points
dist = distance.distance(start_coord, end_coord).km
time_hours = dist/60 # Assuming an average speed of 60 km/h
time_minutes = int(round(time_hours*60))
# Calculate the end time
end_time = start_time + datetime.timedelta(minutes=time_minutes)
# Create the feature with the actual travel time
feature = {
"type": "Feature",
"geometry": {
"type": "LineString",
"coordinates": [
[df.iloc[tour[-1]]['Longitude'], df.iloc[tour[-1]]['Latitude']],
[df.iloc[tour[0]]['Longitude'], df.iloc[tour[0]]['Latitude']]
],
},
"properties": {
'style': {'color': 'red'},
'icon': 'circle',
'iconstyle': {
'fillColor': '#0000FF',
'fillOpacity': 0.8,
'stroke': 'true',
'radius': 10
},
"times": [
start_time.strftime('%Y-%m-%dT%H:%M:%S'),
end_time.strftime('%Y-%m-%dT%H:%M:%S')
]
},
}
# Add the feature to the list of features
features.append(feature)
# Step 2: Create the map and add the GeoJSON object
m = folium.Map(location=[df.iloc[tour[0]]['Latitude'], df.iloc[tour[0]]['Longitude']], zoom_start=12)
for i in range(len(tour)-1):
coords1 = (df.iloc[tour[i]]['Latitude'], df.iloc[tour[i]]['Longitude'])
coords2 = (df.iloc[tour[i+1]]['Latitude'], df.iloc[tour[i+1]]['Longitude'])
folium.Marker(location=coords1,icon=folium.Icon(color='black',icon_color='#FFFF00')).add_to(m)
coords1 = (df.iloc[tour[0]]['Latitude'], df.iloc[tour[0]]['Longitude'])
coords2 = (df.iloc[tour[-1]]['Latitude'], df.iloc[tour[-1]]['Longitude'])
folium.Marker(location=coords2,icon=folium.Icon(color='black',icon_color='#FFFF00')).add_to(m)
plugins.TimestampedGeoJson(
{
"type": "FeatureCollection",
"features": features,
},
period="PT1H",
add_last_point=True,
loop = False
).add_to(m)
# Step 3: Save the map as an HTML file
m
Conclusion:
In summary, the code presented here is a valuable resource for individuals seeking to organize a journey encompassing several cities. It is a remarkable illustration of how technology can enhance travel planning and maximize the benefits of every excursion. Through the application of advanced algorithms and graphical representations, the code has generated an impressive map displaying the optimal route for visiting multiple destinations.
