Revolutionizing Delivery Routes with Simulated Annealing

In the world of logistics, efficient delivery routes are paramount. Every extra mile adds to the cost and time, making optimization a key focus for delivery companies.

Image generated using DALL-E 3

Optimizing delivery routes is crucial for businesses aiming to streamline their operations and reduce costs. Whether it’s a local courier service or a multinational logistics company, efficiently navigating through multiple stops can lead to significant savings in time, fuel, and resources. One of the most powerful techniques in this domain is Simulated Annealing. It’s a metaheuristic algorithm inspired by the annealing process in metallurgy. This algorithm iteratively swaps delivery locations to find the shortest route possible. In this blog post, we’ll delve into the implementation of Simulated Annealing for optimizing delivery routes using Python.

Understanding Route Optimization

Route optimization involves finding the most efficient path to traverse a set of locations, considering factors such as distance, traffic conditions, and delivery priorities. While simple for a small number of stops, this task quickly becomes complex as the number of locations increases exponentially. Traditional methods like exhaustive search become impractical due to their high computational cost.

This is where optimization algorithms come into play. These algorithms, inspired by natural phenomena or mathematical principles, offer efficient solutions to complex optimization problems. One such algorithm is simulated annealing, which mimics the process of annealing in metallurgy to find the global optimum of a function.

Understanding the Code

Let’s dissect the provided Python code, which demonstrates the application of simulated annealing to optimize delivery routes. We’ll go through each section step by step:

Installation and Imports

The first step is to install the googlemaps package. We then import necessary libraries like numpy, random, math, googlemaps, and folium for various functionalities including numerical operations, randomization, geographical calculations, and map visualization.

!pip install googlemaps

import numpy as np
import random
import math
import googlemaps
import folium
from datetime import datetime
from folium.plugins import FloatImage

API Key Retrieval

This section defines a function read_api_key() to read the Google Maps API key from a file. It's crucial for accessing Google Maps services. If the API key is not found, the program exits. The link explains how to download the google api_key.

def read_api_key(filename='api_key.txt'):
    try:
        with open(filename, 'r') as f:
            api_key = f.read().strip()
        return api_key
    except FileNotFoundError:
        print(f"API key file '{filename}' not found.")
        return None

api_key = read_api_key()  # Read API key from file
if api_key is None:
    exit()

Delivery Locations

A dictionary delivery_locations is defined, containing the names and addresses of delivery locations in Germany.

delivery_locations = {
    'Berlin, Germany': 'Berlin, Germany',
    'Hamburg, Germany': 'Hamburg, Germany',
    'Munich, Germany': 'Munich, Germany',
    'Cologne, Germany': 'Cologne, Germany',
    'Frankfurt, Germany': 'Frankfurt, Germany',
    'Stuttgart, Germany': 'Stuttgart, Germany',
    'Düsseldorf, Germany': 'Düsseldorf, Germany',
    'Dortmund, Germany': 'Dortmund, Germany',
    'Essen, Germany': 'Essen, Germany',
    'Leipzig, Germany': 'Leipzig, Germany',
    'Nuremberg, Germany': 'Nuremberg, Germany',
    'Dresden, Germany': 'Dresden, Germany',
    'Bremen, Germany': 'Bremen, Germany',
    'Hanover, Germany': 'Hanover, Germany',
    'Duisburg, Germany': 'Duisburg, Germany',
    'Bochum, Germany': 'Bochum, Germany',
    'Wuppertal, Germany': 'Wuppertal, Germany',
    'Bielefeld, Germany': 'Bielefeld, Germany',
    'Bonn, Germany': 'Bonn, Germany',
    'Münster, Germany': 'Münster, Germany',
}

Coordinates Retrieval

This function fetch_coordinates() uses the Google Maps Geocoding API to retrieve latitude and longitude coordinates for each delivery location.

Let us explain each code line in detail:

1. gmaps = googlemaps.Client(key=api_key): This line creates a Google Maps API client object (gmaps) using the provided API key (api_key).
2. coordinates = {}: This initializes an empty dictionary (coordinates) to store location names as keys and their corresponding coordinates as values.
3. The loop iterates over each key-value pair in the locations dictionary, where loc_name is the name of the location and address is its address.
4. Inside the loop, it tries to fetch the coordinates for each address using the geocode() method of the gmaps object. This method returns a list of results containing information about the location.
5. If the result list is not empty (if result:), it extracts the coordinates (latitude and longitude) from the first result and stores them in the coordinates dictionary under the corresponding loc_name.
6. If the result list is empty, it prints a message indicating that coordinates could not be fetched for the location.
7. If any exception occurs during the process (e.g., network error, API quota exceeded), it catches the exception, prints an error message, and sets the coordinates for the location to None.
8. After processing all locations, the coordinates dictionary contains the fetched coordinates for each location (if available) or None if coordinates could not be fetched.

def fetch_coordinates(locations, api_key):
    gmaps = googlemaps.Client(key=api_key)
    coordinates = {}
    for loc_name, address in locations.items():
        try:
            result = gmaps.geocode(address)
            if result:
                coords = result[0]['geometry']['location']
                coordinates[loc_name] = (coords['lat'], coords['lng'])
            else:
                print(f"Could not fetch coordinates for {loc_name}")
                coordinates[loc_name] = None
        except Exception as e:
            print(f"Error fetching coordinates for {loc_name}: {str(e)}")
            coordinates[loc_name] = None
    return coordinates

coordinates = fetch_coordinates(delivery_locations, api_key)

# Print coordinates
print("Coordinates:")
print(coordinates)

The output

The google API has been able to correctly fetch all the coordinates of the aforementioned locations.

Distance Calculation

This function fetch_distances() calculates the distance matrix between all pairs of delivery locations using the Google Maps Distance Matrix API.

Here’s a breakdown of the code and individual code lines:

1. gmaps = googlemaps.Client(key=api_key): This line initializes a client object for interacting with the Google Maps API using the provided API key.
2. num_locations = len(coordinates): This line calculates the number of locations based on the length of the coordinates dictionary.
3. distance_matrix = np.zeros((num_locations, num_locations)): This line initializes a NumPy array filled with zeros to store the distances between locations. The shape of the array is (num_locations, num_locations).
4. for i, (loc1, coord1) in enumerate(coordinates.items()):: This loop iterates over the items of the coordinates dictionary, where loc1 is the name of the first location and coord1 is its corresponding coordinates.
5. for j, (loc2, coord2) in enumerate(coordinates.items()):: Within the outer loop, another loop iterates over the items of the coordinates dictionary to compare each location with every other location.
6. if i != j:: This condition ensures that the distance between a location and itself is not calculated.
7. result = gmaps.distance_matrix(coord1, coord2, mode='driving', departure_time=datetime.now()): This line sends a request to the Google Maps API to calculate the distance matrix between coord1 and coord2 using driving mode and the current time as the departure time.
8. distance_matrix[i][j] = result['rows'][0]['elements'][0]['distance']['value'] / 1000: This line extracts the distance value from the API response and stores it in the corresponding position of the distance_matrix array. It converts the distance from meters to kilometers.
9. except Exception as e:: This block catches any exceptions that occur during the API request.
10. distance_matrix[i][j] = np.inf: If an exception occurs, this line assigns infinity as the distance between the locations.

def fetch_distances(coordinates, api_key):
    gmaps = googlemaps.Client(key=api_key)
    num_locations = len(coordinates)
    distance_matrix = np.zeros((num_locations, num_locations))
    for i, (loc1, coord1) in enumerate(coordinates.items()):
        for j, (loc2, coord2) in enumerate(coordinates.items()):
            if i != j:
                try:
                    result = gmaps.distance_matrix(coord1, coord2, mode='driving', departure_time=datetime.now())
                    distance_matrix[i][j] = result['rows'][0]['elements'][0]['distance']['value'] / 1000  # Convert to kilometers
                except Exception as e:
                    print(f"Error fetching distance between {loc1} and {loc2}: {str(e)}")
                    distance_matrix[i][j] = np.inf
    return distance_matrix

distance_matrix = fetch_distances(coordinates, api_key)

# Print distance matrix for debugging
print("Distance Matrix:")
print(distance_matrix)

The output

As you can see, we have received the expected distances between the locations without any errors. The matrix is symmetric since the distance from location A to location B is the same as the distance from location B to location A. Each row and column corresponds to a specific location in the delivery_locations dictionary. The value at row i and column j represents the distance from the location associated with the i-th row to the location associated with the j-th column.

For Instance: Consider the value at row 0 and column 1 i.e. 291.365. This means that the distance from the first location (Berlin, Germany) to the second location (Hamburg, Germany) is approximately 291.365 kilometers. Similarly, the value at row 2 and column 3 is 575.242, which indicates that the distance from the third location (Munich, Germany) to the fourth location (Cologne, Germany) is approximately 575.242 kilometers.

Simulated Annealing Algorithm

The simulated_annealing() function implements the simulated annealing algorithm. It iteratively explores neighboring routes, allowing for uphill movements based on a probability criterion.

def simulated_annealing(distance_matrix):
    # Initialization
    current_route = list(range(len(delivery_locations)))  # Initial route as indices
    random.shuffle(current_route)  # Randomly shuffle initial route
    current_distance = total_distance(current_route, distance_matrix)
    best_route = current_route.copy()
    best_distance = current_distance
    temperature = 1000
    cooling_rate = 0.003

    # Annealing process
    while temperature > 1:
        new_route = generate_neighbor(current_route)
        new_distance = total_distance(new_route, distance_matrix)
        if acceptance_probability(current_distance, new_distance, temperature) > random.random():
            current_route = new_route
            current_distance = new_distance
            if current_distance < best_distance:
                best_route = current_route.copy()
                best_distance = current_distance
        temperature *= 1 - cooling_rate

    return best_route, best_distance

Helper Functions

These are helper functions utilized in the simulated annealing process. total_distance() calculates the total distance of a given route, acceptance_probability() computes the probability of accepting a new solution, and generate_neighbor() generates a neighboring route by swapping two locations.

# Helper functions
def total_distance(route, distance_matrix):
    # Calculate total distance for a given route
    total_dist = 0
    for i in range(len(route) - 1):
        total_dist += distance_matrix[route[i]][route[i+1]]
    return total_dist

def acceptance_probability(old_dist, new_dist, temperature):
    # Calculate acceptance probability based on temperature
    if new_dist < old_dist:
        return 1
    return math.exp((old_dist - new_dist) / temperature)

def generate_neighbor(route):
    # Generate a neighboring route by swapping two locations
    neighbor = route.copy()
    if len(route) > 2:
        i, j = random.sample(range(1, len(route) - 1), 2)
        neighbor[i], neighbor[j] = neighbor[j], neighbor[i]
    elif len(route) == 2:
        neighbor[1], neighbor[0] = neighbor[0], neighbor[1]  # Swap the only two locations
    return neighbor

Route Optimization

This line utilizes the simulated_annealing function defined above and optimizes the delivery route using the simulated annealing algorithm.

# Optimize route using simulated annealing
best_route, best_distance = simulated_annealing(distance_matrix)

# Print optimized route and distance
print("Optimized route:", [list(delivery_locations.keys())[i] for i in best_route])
print("Total distance:", best_distance)

The output

Map Visualization

Finally, this part visualizes the optimized route on an interactive map using Folium library. Markers represent delivery locations, blue lines indicate the route, and red arrows denote the direction of travel between locations.

# Create an interactive map
m = folium.Map(location=list(coordinates.values())[0], zoom_start=6)

# Add markers for delivery locations
for location, coords in coordinates.items():
    folium.Marker(location=coords, popup=location).add_to(m)

# Add polyline for the optimized route with arrows
route_coords = [list(coordinates.values())[i] for i in best_route]
for i in range(len(route_coords) - 1):
    folium.Marker(location=route_coords[i], icon=folium.Icon(color='green')).add_to(m)
    folium.PolyLine(locations=[route_coords[i], route_coords[i+1]], color='blue').add_to(m)
    # Calculate arrow position
    arrow_pos = [(route_coords[i][0] + route_coords[i+1][0]) / 2, (route_coords[i][1] + route_coords[i+1][1]) / 2]
    folium.RegularPolygonMarker(location=arrow_pos, fill_color='red', number_of_sides=3, radius=10,
                                rotation=math.degrees(math.atan2(route_coords[i+1][1]-route_coords[i][1],
                                                                route_coords[i+1][0]-route_coords[i][0]))).add_to(m)

# Add marker and polyline for the last location
folium.Marker(location=route_coords[-1], icon=folium.Icon(color='green')).add_to(m)

# Display map in Google Colab
m

The output

Conclusion

In this blog post, we’ve explored the implementation of Simulated Annealing for optimizing delivery routes. By leveraging Google Maps APIs and Python libraries like numpy and folium, we've developed a robust solution for route optimization. This approach can significantly reduce delivery costs and time, making it a valuable tool for logistics companies striving for efficiency in their operations.

Code

Route Optimization