Optimizing Travel Routes with Traffic Data using Python and OSMnx and LLM

30 Jun, 2024

routeimg

Introduction

In the fast-paced world we live in, optimizing travel routes to save time is essential, especially for delivery services, ride-sharing companies, and logistics firms. "Life is like a box of chocolates. You never know what you're gonna get," unless you have a perfect route optimizer! Today, we’ll walk through an exciting project where we developed a Python application to find the fastest travel route between multiple addresses, considering historical traffic data. Let's dive in and make sure we don't take any wrong turns!

Tools and Libraries

Our project leverages several powerful libraries and services:

OSMNx: Used for downloading OpenStreetMap data and creating distance matrices.
HERE API: Fetches travel times with traffic data.
Google OR-Tools: Solves the Traveling Salesman Problem (TSP) for optimal routing.
Geopy: Geocodes addresses into latitude and longitude.
Tkinter: Provides a simple graphical user interface (GUI).

Step-by-Step Guide

1. Setting Up the Environment

Before diving into the code, you need to install the necessary libraries. Here’s a quick guide to setting up your environment:

pip install osmnx networkx ortools geopy requests tkinter

geocoding

2. Geocoding Addresses

We start by converting street addresses into geographic coordinates (latitude and longitude) using the Geopy library. "To infinity and beyond!" Well, at least to the correct latitudes and longitudes.

from geopy.geocoders import Nominatim

def geocode_addresses(addresses):
    geolocator = Nominatim(user_agent="route_optimizer")
    locations = []
    for address in addresses:
        location = geolocator.geocode(address)
        if location:
            locations.append({'lat': location.latitude, 'lng': location.longitude})
        else:
            raise ValueError(f"Geocoding failed for address: {address}")
    return locations

3. Fetching Traffic Data

Next, we use the HERE API to fetch travel times between locations, considering traffic conditions. This is crucial for finding the fastest route. Remember, "With great power comes great responsibility" to avoid traffic jams.

import requests

HERE_API_KEY = 'YOUR_HERE_API_KEY'  # Replace with your HERE API key

def get_travel_time_with_traffic(origin, destination):
    api_url = "https://router.hereapi.com/v8/routes"
    params = {
        'transportMode': 'car',
        'origin': f"{origin['lat']},{origin['lng']}",
        'destination': f"{destination['lat']},{destination['lng']}",
        'return': 'summary',
        'apikey': HERE_API_KEY
    }
    response = requests.get(api_url, params=params)
    data = response.json()
    if 'routes' in data and len(data['routes']) > 0:
        travel_time = data['routes'][0]['sections'][0]['summary']['duration']
        return travel_time
    else:
        return float('inf')

4. Creating the Time Matrix

We create a matrix where each element represents the travel time between two locations. "May the Matrix be ever in your favor"—or was that the wrong movie?

def get_osm_traffic_time_matrix(locations):
    time_matrix = []
    for i, origin in enumerate(locations):
        row = []
        for j, destination in enumerate(locations):
            if i == j:
                row.append(0)
            else:
                travel_time = get_travel_time_with_traffic(origin, destination)
                row.append(travel_time)
        time_matrix.append(row)
    return time_matrix

5. Solving the Traveling Salesman Problem

We use Google OR-Tools to find the optimal route and also implement a nearest neighbor heuristic for comparison. "I'll be back" once I find the optimal route.

from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp

def solve_tsp(time_matrix):
    manager = pywrapcp.RoutingIndexManager(len(time_matrix), 1, 0)
    routing = pywrapcp.RoutingModel(manager)

    def time_callback(from_index, to_index):
        from_node = manager.IndexToNode(from_index)
        to_node = manager.IndexToNode(to_index)
        return time_matrix[from_node][to_node]

    transit_callback_index = routing.RegisterTransitCallback(time_callback)
    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
    search_parameters = pywrapcp.DefaultRoutingSearchParameters()
    search_parameters.first_solution_strategy = routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC
    solution = routing.SolveWithParameters(search_parameters)

    if solution:
        index = routing.Start(0)
        route = []
        while not routing.IsEnd(index):
            route.append(manager.IndexToNode(index))
            index = solution.Value(routing.NextVar(index))
        route.append(manager.IndexToNode(index))
        return route
    else:
        return None

def solve_tsp_nearest_neighbor(time_matrix):
    n = len(time_matrix)
    visited = [False] * n
    route = [0]
    visited[0] = True
    current_index = 0
    for _ in range(n - 1):
        next_index = min(
            (i for i in range(n) if not visited[i]),
            key=lambda i: time_matrix[current_index][i]
        )
        route.append(next_index)
        visited[next_index] = True
        current_index = next_index
    route.append(0)
    return route

def calculate_total_travel_time(time_matrix, route):
    total_time = sum(time_matrix[route[i]][route[i+1]] for i in range(len(route) - 1))
    return total_time

6. Creating a GUI

To make the application user-friendly, we use Tkinter to create a graphical interface. "There's no place like home," especially when your GUI works perfectly!

import tkinter as tk
from tkinter import filedialog, messagebox
from tkinter.scrolledtext import ScrolledText

def read_addresses_from_file(file_path):
    with open(file_path, 'r') as file:
        addresses = [line.strip() for line in file if line.strip()]
    return addresses

def load_addresses():
    file_path = filedialog.askopenfilename()
    if file_path:
        addresses = read_addresses_from_file(file_path)
        addresses_text.delete('1.0', tk.END)
        addresses_text.insert(tk.END, '\n'.join(addresses))

def optimize():
    addresses = addresses_text.get('1.0', tk.END).strip().split('\n')
    if not addresses:
        messagebox.showerror("Error", "No addresses provided")
        return

    try:
        result = optimize_route(addresses)
        output_text.delete('1.0', tk.END)
        output_text.insert(tk.END, "Optimized Route (OR-Tools):\n")
        output_text.insert(tk.END, "\n".join(result['ortools']['route']))
        output_text.insert(tk.END, f"\nTotal Travel Time: {result['ortools']['travel_time']} seconds\n")
        output_text.insert(tk.END, "\nOptimized Route (Nearest Neighbor):\n")
        output_text.insert(tk.END, "\n".join(result['nearest_neighbor']['route']))
        output_text.insert(tk.END, f"\nTotal Travel Time: {result['nearest_neighbor']['travel_time']} seconds\n")
    except Exception as e:
        messagebox.showerror("Error", str(e))

# Create the main window
root = tk.Tk()
root.title("Route Optimizer")

# Create and place widgets
tk.Label(root, text="Addresses (one per line):").pack()

addresses_text = ScrolledText(root, width=40, height=10)
addresses_text.pack()

tk.Button(root, text="Load from File", command=load_addresses).pack()

tk.Button(root, text="Optimize Route", command=optimize).pack()

tk.Label(root, text="Output:").pack()

output_text = ScrolledText(root, width=40, height=10)
output_text.pack()

# Start the main event loop
root.mainloop()

7. Putting It All Together

Here’s the main optimization function that integrates all the components:

def optimize_route(addresses):
    locations = geocode_addresses(addresses)
    time_matrix = get_osm_traffic_time_matrix(locations)

    ortools_route_indices = solve_tsp(time_matrix)
    if ortools_route_indices is None:
        raise ValueError("Could not solve the TSP using OR-Tools.")
    ortools_route = [addresses[i] for i in ortools_route_indices]
    ortools_travel_time = calculate_total_travel_time(time_matrix, ortools_route_indices)

    nearest_neighbor_route_indices = solve_tsp_nearest_neighbor(time_matrix)
    nearest_neighbor_route = [addresses[i] for i in nearest_neighbor_route_indices]
    nearest_neighbor_travel_time = calculate_total_travel_time(time_matrix, nearest_neighbor_route_indices)

    return {
        'ortools': {'route': ortools_route, 'travel_time': ortools_travel_time},
        'nearest_neighbor': {'route': nearest_neighbor_route, 'travel_time': nearest_neighbor_travel_time}
    }

I apologize for the confusion. Here's a revised conclusion for the blog post, complete with jokes and movie quotes:

Conclusion

With this project, we've built a powerful tool to optimize travel routes using Python. By considering traffic data, we can ensure that the routes we generate are not only short in distance but also quick in time. Let's summarize our journey:

Geocoding Addresses: We transformed street names into geographic coordinates. "Houston, we have no problem!"
Fetching Traffic Data: Using the HERE API, we gathered real-time traffic data to make sure our routes dodge traffic jams like Neo dodges bullets in "The Matrix."
Creating the Time Matrix: This matrix helped us understand the travel times between all our locations. Think of it as our very own "Roads? Where we're going, we don't need roads" moment, but with better data.
Solving the TSP: With Google OR-Tools and the nearest neighbor heuristic, we found the best routes. "I'll be back" once I've found the fastest way!
Building a GUI: Our Tkinter interface made the tool user-friendly. "There's no place like home," especially when you have a working GUI to welcome you.

By the end of this project, you'll have a robust route optimization tool that accounts for historical traffic data and provides an optimal path for multiple stops. It's like having your own personal "Hitchhiker's Guide to the Galaxy" for travel routes, ensuring you never have to panic.

Feel free to try out the code, modify it for your needs, and explore further enhancements like real-time traffic data integration or more sophisticated heuristics for the TSP.

Happy coding, and may your travel routes always be efficient!

And remember: "In coding, there are no shortcuts, only optimized routes!"