The Ultimate Route Planning Challenge - When Efficiency Meets Real World!
The Ultimate Route Challenge 🗺️
The Problem: A salesperson needs to visit every city exactly once and return home, using the shortest possible route.
Real-World Analogy: * Like a delivery driver planning the most efficient route * GPS apps finding the fastest path through multiple stops * Amazon trucks optimizing deliveries to save time and fuel * Tour guides planning the best sightseeing route
Why It Matters 🚚
The Challenge ⚡
Key Question: “How do we find the best route without checking every possibility?”
For n cities, there are (n-1)!/2 unique routes to check Why? We fix the starting city and divide by 2 since routes can go clockwise or counterclockwise.
Route Count Growth 📊
def calculate_routes(n_cities):
"""Calculate number of TSP routes"""
if n_cities <= 1:
return 0
# (n-1)! / 2 unique routes
factorial = 1
for i in range(1, n_cities):
factorial *= i
return factorial // 2
# Let's see the explosion!
for cities in range(2, 11):
routes = calculate_routes(cities)
print(f"{cities} cities: {routes:,} routes")Real Numbers:
The Pattern:
⚠️ The Scary Truth About Computation Time
Even with the world’s fastest computers, brute force TSP becomes impossible very quickly!
Time Complexity Analysis ⏱️
import time
import math
def time_estimate(n_cities):
"""Estimate computation time for brute force TSP"""
routes = math.factorial(n_cities - 1) // 2
# Assume 1 million routes per second
seconds = routes / 1_000_000
if seconds < 60:
return f"{seconds:.2f} seconds"
elif seconds < 3600:
return f"{seconds/60:.2f} minutes"
elif seconds < 86400:
return f"{seconds/3600:.2f} hours"
elif seconds < 31536000:
return f"{seconds/86400:.2f} days"
else:
return f"{seconds/31536000:.2f} years"
# The scary truth
print("Time to solve TSP by brute force:")
for n in [10, 15, 20, 25]:
print(f"{n} cities: {time_estimate(n)}")Reality Check 🤯
Why This Matters 💡
⚠️ Warning: This Gets Slow Fast!
Our brute force solution checks every possible route. It works great for small examples, but becomes impossible for real-world problems.
The Core Algorithm 🧠
def tsp_brute_force(cities, current_city=0,
visited=None, path=None):
"""
Solve TSP by checking ALL possible routes
Time Complexity: O(n!) - FACTORIAL!
"""
# Initialize first call
if visited is None:
visited = {current_city}
path = [current_city]
# Base case: visited all cities, return home
if len(visited) == len(cities):
complete_path = path + [0] # Return to start
total_distance = calculate_distance(complete_path)
return complete_path, total_distance
# Try every unvisited city next
best_path = None
best_distance = float('inf')
for next_city in range(len(cities)):
if next_city not in visited:
# Recursive magic: solve for remaining cities
new_path, distance = tsp_brute_force(
cities, next_city,
visited | {next_city},
path + [next_city]
)
# Keep the best route found so far
if distance < best_distance:
best_distance = distance
best_path = new_path
return best_path, best_distanceDistance Calculation 📐
def calculate_distance(path):
"""Calculate total route distance"""
# Example distance matrix for 4 cities
distances = {
(0, 1): 10, (1, 0): 10, # City 0 ↔ City 1
(0, 2): 15, (2, 0): 15, # City 0 ↔ City 2
(0, 3): 20, (3, 0): 20, # City 0 ↔ City 3
(1, 2): 25, (2, 1): 25, # City 1 ↔ City 2
(1, 3): 30, (3, 1): 30, # City 1 ↔ City 3
(2, 3): 35, (3, 2): 35, # City 2 ↔ City 3
# Distance to self is 0
(0, 0): 0, (1, 1): 0, (2, 2): 0, (3, 3): 0
}
total = 0
for i in range(len(path) - 1):
current = path[i]
next_city = path[i + 1]
total += distances.get((current, next_city), 999)
return total
# Real-world: use Euclidean distance
def euclidean_distance(city1, city2):
"""Calculate straight-line distance between cities"""
x1, y1 = city1
x2, y2 = city2
return ((x2 - x1)**2 + (y2 - y1)**2)**0.5Left to the reader…
Copy these blocks into two files (main.py, examples.py and tsp.py) to run this larger demo from the commmand line.
tsp.py
def tsp_brute_force(cities, current_city=0,
visited=None, path=None):
"""
Solve TSP by checking ALL possible routes
Time Complexity: O(n!) - FACTORIAL!
"""
# Initialize first call
if visited is None:
visited = {current_city}
path = [current_city]
# Base case: visited all cities, return home
if len(visited) == len(cities):
complete_path = path + [0] # Return to start
total_distance = calculate_distance(complete_path)
return complete_path, total_distance
# Try every unvisited city next
best_path = None
best_distance = float('inf')
for next_city in range(len(cities)):
if next_city not in visited:
# Recursive magic: solve for remaining cities
new_path, distance = tsp_brute_force(
cities, next_city,
visited | {next_city},
path + [next_city]
)
# Keep the best route found so far
if distance < best_distance:
best_distance = distance
best_path = new_path
return best_path, best_distance
def calculate_distance(path):
"""Calculate total route distance"""
# Example distance matrix for 4 cities
distances = {
(0, 1): 10, (1, 0): 10, # City 0 ↔ City 1
(0, 2): 15, (2, 0): 15, # City 0 ↔ City 2
(0, 3): 20, (3, 0): 20, # City 0 ↔ City 3
(1, 2): 25, (2, 1): 25, # City 1 ↔ City 2
(1, 3): 30, (3, 1): 30, # City 1 ↔ City 3
(2, 3): 35, (3, 2): 35, # City 2 ↔ City 3
# Distance to self is 0
(0, 0): 0, (1, 1): 0, (2, 2): 0, (3, 3): 0
}
total = 0
for i in range(len(path) - 1):
current = path[i]
next_city = path[i + 1]
total += distances.get((current, next_city), 999)
return total
# Real-world: use Euclidean distance
def euclidean_distance(city1, city2):
"""Calculate straight-line distance between cities"""
x1, y1 = city1
x2, y2 = city2
return ((x2 - x1)**2 + (y2 - y1)**2)**0.5examples.py
#!/usr/bin/env python3
"""
Simple usage example for the TSP solver
Shows how to use the TSP functions directly in your own code
"""
from tsp import tsp_brute_force, euclidean_distance
import time
def example_usage():
"""Demonstrate how to use the TSP solver in your own code"""
print("🔧 TSP Solver - Usage Example")
print("=" * 40)
# Example 1: Using the built-in distance matrix (4 cities)
print("\n1️⃣ Using built-in distance matrix:")
cities = [0, 1, 2, 3]
start = time.time()
path, distance = tsp_brute_force(cities)
end = time.time()
print(f" Input: {cities}")
print(f" Best path: {path}")
print(f" Distance: {distance}")
print(f" Time: {end-start:.4f}s")
# Example 2: Custom coordinates with euclidean distance
print("\n2️⃣ Using custom city coordinates:")
# Define your cities as (x, y) coordinates
city_positions = [(0, 0), (1, 3), (4, 1), (2, 4)]
# Create a custom distance function
def calculate_custom_distance(path):
total = 0
for i in range(len(path) - 1):
city1 = city_positions[path[i]]
city2 = city_positions[path[i + 1]]
total += euclidean_distance(city1, city2)
return total
# Temporarily replace the global function
import tsp
original_calc = tsp.calculate_distance
tsp.calculate_distance = calculate_custom_distance
try:
start = time.time()
path, distance = tsp_brute_force(list(range(len(city_positions))))
end = time.time()
print(f" Coordinates: {city_positions}")
print(f" Best path: {path}")
print(f" Distance: {distance:.2f}")
print(f" Time: {end-start:.4f}s")
finally:
# Restore original function
tsp.calculate_distance = original_calc
# Example 3: Timing comparison
print("\n3️⃣ Performance for different city counts:")
for n in [3, 4, 5, 6, 7]:
cities = list(range(n))
start = time.time()
path, distance = tsp_brute_force(cities)
end = time.time()
import math
routes = math.factorial(n-1) if n > 1 else 1
print(f" {n} cities: {routes:>6} routes, {end-start:.4f}s")
if end - start > 0.1: # Stop if getting slow
print(" (stopping - getting slow)")
break
def solve_custom_problem():
"""Example of solving a specific TSP problem"""
print("\n🎯 Solving a specific problem:")
print(" Visiting 5 offices in a city")
# Office locations (in km from city center)
offices = {
'HQ': (0, 0),
'Branch A': (2, 3),
'Branch B': (5, 1),
'Branch C': (1, 4),
'Branch D': (4, 4)
}
office_names = list(offices.keys())
coordinates = list(offices.values())
print(f" Offices: {office_names}")
# Create distance calculation function
def office_distance(path):
total = 0
for i in range(len(path) - 1):
pos1 = coordinates[path[i]]
pos2 = coordinates[path[i + 1]]
total += euclidean_distance(pos1, pos2)
return total
# Solve the problem
import tsp
original_calc = tsp.calculate_distance
tsp.calculate_distance = office_distance
try:
start = time.time()
path, distance = tsp_brute_force(list(range(len(offices))))
end = time.time()
# Convert indices back to office names
route_names = [office_names[i] for i in path]
print(f" Best route: {' → '.join(route_names)}")
print(f" Total distance: {distance:.2f} km")
print(f" Solve time: {end-start:.4f} seconds")
finally:
tsp.calculate_distance = original_calc
if __name__ == "__main__":
example_usage()
solve_custom_problem()
print("\n✨ Want more examples? Run 'python3 main.py' for interactive mode!")main.py
#!/usr/bin/env python3
"""
Main driver for the Travelling Salesman Problem (TSP) solver
Demonstrates brute force TSP algorithm with various test cases
"""
import time
from tsp import tsp_brute_force, calculate_distance, euclidean_distance
def print_header(title):
"""Print a formatted header for output sections"""
print("\n" + "="*60)
print(f" {title}")
print("="*60)
def print_result(path, distance, execution_time):
"""Print formatted TSP solution results"""
print(f"\nBest Path: {' → '.join(map(str, path))}")
print(f"Total Distance: {distance}")
print(f"Execution Time: {execution_time:.4f} seconds")
def example_1_simple():
"""Example 1: Simple 4-city TSP with predefined distance matrix"""
print_header("Example 1: Simple 4-City TSP")
print("Cities: 0, 1, 2, 3")
print("Using predefined distance matrix in tsp.py")
# Create city list (just indices for this example)
cities = list(range(4))
# Time the execution
start_time = time.time()
best_path, best_distance = tsp_brute_force(cities)
end_time = time.time()
print_result(best_path, best_distance, end_time - start_time)
def calculate_euclidean_distance_matrix(cities):
"""Calculate distance matrix using Euclidean distances"""
n = len(cities)
distances = {}
for i in range(n):
for j in range(n):
if i == j:
distances[(i, j)] = 0
else:
dist = euclidean_distance(cities[i], cities[j])
distances[(i, j)] = dist
return distances
def tsp_with_coordinates(cities):
"""
Modified TSP solver that uses coordinate-based distances
"""
def calculate_coord_distance(path):
"""Calculate total route distance using coordinates"""
distances = calculate_euclidean_distance_matrix(cities)
total = 0
for i in range(len(path) - 1):
current = path[i]
next_city = path[i + 1]
total += distances[(current, next_city)]
return total
# Temporarily replace the global calculate_distance function
global calculate_distance
original_calc = calculate_distance
calculate_distance = calculate_coord_distance
try:
result = tsp_brute_force(list(range(len(cities))))
return result
finally:
# Restore original function
calculate_distance = original_calc
def example_2_coordinates():
"""Example 2: TSP with actual city coordinates"""
print_header("Example 2: TSP with City Coordinates")
# Define cities with (x, y) coordinates
city_coords = {
0: (0, 0), # City A
1: (3, 4), # City B
2: (6, 1), # City C
3: (2, 6) # City D
}
cities = list(city_coords.values())
print("Cities with coordinates:")
for i, (x, y) in enumerate(cities):
print(f" City {i}: ({x}, {y})")
# Display distance matrix
print("\nDistance Matrix:")
distances = calculate_euclidean_distance_matrix(cities)
print(" ", end="")
for j in range(len(cities)):
print(f"{j:8}", end="")
print()
for i in range(len(cities)):
print(f"{i:3}: ", end="")
for j in range(len(cities)):
print(f"{distances[(i,j)]:8.2f}", end="")
print()
# Solve TSP
start_time = time.time()
best_path, best_distance = tsp_with_coordinates(cities)
end_time = time.time()
print_result(best_path, best_distance, end_time - start_time)
def example_3_performance():
"""Example 3: Performance comparison with different city counts"""
print_header("Example 3: Performance Analysis")
print("Analyzing TSP performance for different numbers of cities...")
print("Note: Time complexity is O(n!) - grows VERY quickly!")
for n_cities in [3, 4, 5, 6]:
print(f"\n--- {n_cities} Cities ---")
# Create simple city list
cities = list(range(n_cities))
# Time the execution
start_time = time.time()
best_path, best_distance = tsp_brute_force(cities)
end_time = time.time()
execution_time = end_time - start_time
# Calculate theoretical number of permutations
import math
permutations = math.factorial(n_cities - 1) # (n-1)! since we fix starting city
print(f"Possible routes: {permutations}")
print(f"Best path: {' → '.join(map(str, best_path))}")
print(f"Distance: {best_distance}")
print(f"Time: {execution_time:.4f} seconds")
if n_cities >= 6:
print("Warning: 7+ cities will take significantly longer!")
def interactive_mode():
"""Interactive mode for custom TSP problems"""
print_header("Interactive TSP Solver")
try:
n_cities = int(input("\nHow many cities? (recommended: 3-6): "))
if n_cities > 8:
response = input("Warning: This may take a very long time. Continue? (y/n): ")
if response.lower() != 'y':
return
print(f"\nEnter coordinates for {n_cities} cities:")
cities = []
for i in range(n_cities):
while True:
try:
coords = input(f"City {i} (x,y): ").split(',')
x, y = float(coords[0].strip()), float(coords[1].strip())
cities.append((x, y))
break
except (ValueError, IndexError):
print("Please enter coordinates as: x,y (e.g., 1.5,2.0)")
print(f"\nSolving TSP for {n_cities} cities...")
start_time = time.time()
best_path, best_distance = tsp_with_coordinates(cities)
end_time = time.time()
print_result(best_path, best_distance, end_time - start_time)
except ValueError:
print("Invalid input. Please enter a number.")
except KeyboardInterrupt:
print("\nOperation cancelled.")
def main():
"""Main driver function"""
print_header("Travelling Salesman Problem (TSP) Solver")
print("Demonstrating brute force algorithm")
print("Author: CS101 Course")
# Run examples
example_1_simple()
example_2_coordinates()
example_3_performance()
# Interactive mode
while True:
print("\n" + "-"*40)
print("Options:")
print("1. Run interactive TSP solver")
print("2. Exit")
try:
choice = input("\nEnter your choice (1-2): ").strip()
if choice == '1':
interactive_mode()
elif choice == '2':
print("\nThank you for using the TSP solver!")
break
else:
print("Please enter 1 or 2.")
except KeyboardInterrupt:
print("\n\nGoodbye!")
break
if __name__ == "__main__":
main()python3 examples.py
Note
🔧 TSP Solver - Usage Example
========================================
1️⃣ Using built-in distance matrix:
Input: [0, 1, 2, 3]
Best path: [0, 1, 2, 3, 0]
Distance: 90
Time: 0.0001s
2️⃣ Using custom city coordinates:
Coordinates: [(0, 0), (1, 3), (4, 1), (2, 4)]
Best path: [0, 1, 3, 2, 0]
Distance: 12.31
Time: 0.0001s
3️⃣ Performance for different city counts:
3 cities: 2 routes, 0.0000s
4 cities: 6 routes, 0.0000s
5 cities: 24 routes, 0.0001s
6 cities: 120 routes, 0.0007s
7 cities: 720 routes, 0.0041s
🎯 Solving a specific problem:
Visiting 5 offices in a city
Offices: ['HQ', 'Branch A', 'Branch B', 'Branch C', 'Branch D']
Best route: HQ → Branch B → Branch D → Branch A → Branch C → HQ
Total distance: 16.03 km
Solve time: 0.0001 seconds
✨ Want more examples? Run 'python3 main.py' for interactive mode!The Travelling Salesman Problem appears in countless real-world scenarios, often disguised as other optimization challenges.
Logistics & Transportation 🚛
# Delivery route optimization
delivery_stops = [
"Warehouse", # Start/end point
"123 Main St", # Customer 1
"456 Oak Ave", # Customer 2
"789 Pine Rd", # Customer 3
"321 Elm St" # Customer 4
]
# TSP finds shortest route visiting all stops
optimal_route = tsp_solver(delivery_stops)
print(f"Optimal delivery route: {optimal_route}")
# Real impact:
# - UPS saves $50M+ annually with route optimization
# - FedEx reduces fuel consumption by 10%
# - Amazon uses TSP for same-day deliverySchool Bus Routing 🚌 * Visit all bus stops efficiently * Minimize travel time for students * Reduce fuel costs and emissions
Manufacturing & Technology 🔧
# Circuit board drilling optimization
drill_points = [
(10, 20), # Hole 1 coordinates
(30, 15), # Hole 2 coordinates
(25, 35), # Hole 3 coordinates
(40, 25) # Hole 4 coordinates
]
# TSP minimizes drill head movement
optimal_drilling = tsp_solver(drill_points)
# Result: Faster manufacturing, less wear on equipmentDNA Sequencing 🧬 * Arrange genetic fragments in correct order * Minimize overlapping regions * Critical for medical research
Video Game AI 🎮 * NPCs planning efficient patrol routes * Resource gathering optimization * Strategy game unit movement
1. Positive Environmental Effects ✅ - TSP optimization reduces fuel consumption and lowers emissions - Decreases overall traffic congestion - Minimizes unnecessary vehicle miles traveled
2. The Consumption Paradox ⚠️ - Does efficient delivery encourage more online shopping? - Could TSP optimization actually increase total environmental impact? - Are we solving the right problem or enabling overconsumption?
3. Future Transportation Challenges 🔋 - How should TSP algorithms adapt for electric delivery vehicles? - What about charging station stops and battery range limits? - How do we optimize for renewable energy usage timing?
Think: What is an Eco-Friendly TSP Design
If you could design a TSP system, what factors besides distance would you optimize for?
Consider these green factors: - Carbon footprint per route segment - Real-time traffic patterns to reduce idling - Air quality levels in different neighborhoods - Time-of-day energy grid efficiency
Research Task: Find one company using TSP for environmental benefits. What measurable impact have they achieved?
The Travelling Salesman Problem teaches us about the beauty and challenges of computer science! 🎯
What We Now Know 🧠📚
What We Also Know! 🧠🌟
Important
Remember: 🤔
Note
Questions to Explore:🌟