How to solve a Routing Problem with a Genetic Algorithm: A Practical Guide
In the fast-paced world of logistics and transportation, the efficiency of routing from one city to another is a cornerstone of economic and operational success, significantly impacting costs and delivery times. Traditional methods such as shortest path algorithms can solve simple routing problems. However, when faced with dynamic cost matrices and a network of varying constraints, these methods fall short. Enter the genetic algorithm (GA) — a heuristic that emulates the process of natural selection to deliver solutions for complex optimisation challenges. In this article, we will delve into how GAs can be harnessed to determine the most cost-effective route within a transportation network and how to create engaging visualisations to illustrate these solutions.
Why Genetic Algorithms?
Genetic and evolutionary algorithms are rather powerful and versatile tools, particularly well-suited for solving complex optimisation and search problems that are otherwise challenging for traditional methods. Their ability to evolve solutions through processes mimicking natural selection allows them to explore a vast space of potential solutions effectively and efficiently.
Take, for instance, NASA’s innovative approach to antenna design. Utilizing genetic algorithms, NASA engineers have autonomously evolved designs for satellite antennas. This method led to the creation of highly efficient, unconventional antenna structures for the ST5 mission, designs that traditional engineering might never have conceived. This is just one example of how GAs are pushing the boundaries of what’s possible in advanced technological applications.
The applications of GAs extend far beyond aerospace, touching various aspects of our daily lives. From optimizing machine learning pipelines in Automated Machine Learning to enhancing the design and control of robots in robotics, these algorithms are making significant strides. They’re revolutionizing aircraft design in aerospace engineering, accelerating drug discovery in the pharmaceutical industry, and reshaping financial strategies in portfolio optimization and algorithmic trading. In the energy sector, GAs are optimizing wind farm layouts and smart grid management, while in logistics, they’re streamlining supply chain processes. Even in the gaming industry, GAs are behind the intelligent behavior of Non-Player Characters and the dynamic world-building in your favorite games. And in the realms of environmental modeling and civil engineering, they’re enabling more efficient and sustainable practices.
GAs are particularly suitable in scenarios where the search space is large, complex, or poorly understood. Although they often provide a near-optimal solution, they do not guarantee the global optimum. They are, thus, ideal for problems with multiple potential solutions where the goal is to find a ‘good enough’ solution efficiently when an exact solution is not necessary or too costly to compute. They excel in environments that require adaptability and robustness, where the fitness landscape changes over time, and where traditional optimisation methods fail to provide quality solutions. A potential drawback is that GAs may require a significant number of function evaluations, making them potentially resource-heavy.
Diving deeper into the world of genetic algorithms, we’ll discover how these tools can be ingeniously applied to a practical challenge: optimising a routing problem. Consider the challenge in the world of logistics: navigating a network of cities, each connected by transportation links. The goal is to find the most efficient route from a designated origin to a destination. This task, akin to the well-known Shortest Path Problem, escalates in complexity with the addition of more cities and routes, making it a perfect candidate for the application of genetic algorithms. These algorithms can adeptly handle the dynamic and intricate nature of such problems, where traditional methods might not suffice.
Basics of Genetic Algorithms
Genetic algorithms draw inspiration from the marvel of natural evolution. A classical example that helps to illustrate the principle behind genetic algorithms is the giraffe’s long neck. Just as giraffes’ necks are believed to have lengthened over generations to allow them to reach higher leaves and survive in their environment, genetic algorithms operate on the principle of survival of the fittest. These algorithms simulate an evolutionary process where, over many generations, optimal solutions ‘survive’ through a combination of the best characteristics of previous solutions. They begin with a diverse population of possible solutions to a problem and iteratively apply operations analogous to genetic recombination and mutation to evolve the solutions towards better fitness.
In the context of the routing problem, a population is composed by various chromosomes, each representing a route, i.e. a possible solution for the optimisation problem. Within these chromosomes, the genes are the cities that make up the route. The fitness of each chromosome is determined by a score reflecting the total costs associated with traversing the route it represents, which we aim to minimise. As the algorithm progresses, these populations evolve through successive generations, driven by the genetic operations of selection, crossover, and mutation. This iterative process continues until the algorithm converges on the best individual, which represents the optimal or near-optimal solution for the routing challenge at hand.
Setting Up the Genetic Algorithm for Routing
The implementation begins with defining our cost matrix and handling costs in the get_data function. The cost matrix is a grid that quantifies the travel costs between each pair of cities, while handling costs are fixed fees associated with processes within the warehouses or transportation nodes.
The cost matrix determines all the connections between cities that the solution can consider. Nonexistent connections are assigned a cost of infinity to indicate their unfeasibility.
Let’s assume we are considering a transportation network with some connections between the European cities of Lisbon, Porto, Madrid, Barcelona, Toulouse, Paris, Strasbourg, Berlin, Hamburg, Frankfurt, Amsterdam, Ghent, Brussels, Milan and Rome.
In the following code snippet, the cost matrix, list of cities, and handling costs are hard-coded for the sake of simplicity and to illustrate the concept clearly. However, it’s important to note that in a practical application these elements should ideally be extracted from external datasets. In real-world scenarios, the cost matrix and handling costs would typically be dynamic, subject to frequent updates and variations based on numerous factors such as fuel prices, traffic conditions, and seasonal demand fluctuations. Therefore, in a production environment, the code should be designed to load this data from up-to-date and reliable sources, such as databases, spreadsheets, or APIs.
import numpy as np
import pandas as pd
import random
import copy
from PIL import Image # for visualisation purposes (Optional)
import matplotlib.pyplot as plt # for visualisation purposes (Optional)
import folium # for visualisation purposes (Optional)
from folium import IFrame # for visualisation purposes (Optional)
import os # for visualisation purposes (Optional)
from selenium import webdriver # for visualisation purposes (Optional)
from selenium.webdriver.chrome.service import Service # for visualisation purposes (Optional)
from selenium.webdriver.chrome.options import Options # for visualisation purposes (Optional)
import io # for visualisation purposes (Optional)
import time # for visualisation purposes (Optional)
def get_data():
"""Get the data for the problem"""
# Define the cost matrix
connections_cost = np.array([
# LIS MAD PAR BER AMS ROM ZUR VIE POR BCN TLS SXB GNT BRU HAM FRA MIL
[np.inf, 10, 30, np.inf, 55, 65, np.inf, 80, 5, 20, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf], # LIS
[10, np.inf,10, 15, np.inf,25, 30, 30, 15, 10, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf], # MAD
[30, 15, np.inf,15, 15, 30, 25, 35, np.inf,25, 10, 20, np.inf, np.inf, np.inf, np.inf, np.inf], # PAR
[40, 15, 25, np.inf, 10, 20, 10, 15, np.inf, np.inf, 15, 15, np.inf, np.inf, 20, np.inf, np.inf], # BER
[50, 20, 20, 10, np.inf, 35, 25, 30, np.inf, np.inf, np.inf, np.inf, 10, 5, 30, 20, np.inf], # AMS
[70, 25, 35, 20, 35, np.inf,20, 25, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, 10], # ROM
[75, 30, 25, 15, 25, 20, np.inf, 10, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, 20], # ZUR
[75, 35, 45, 15, 30, 25, 10, np.inf,np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf], # VIE
[5, 15, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, 15, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf], # POR
[20, 10, 25, np.inf, np.inf, np.inf, np.inf, np.inf, 15, np.inf, 15, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf], # BCN
[np.inf, np.inf, 10, 15, np.inf, np.inf, np.inf, np.inf, np.inf, 15, np.inf, 10, np.inf, np.inf, np.inf, np.inf, np.inf], # TLS
[np.inf, np.inf, 20, 15, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, 10, np.inf, 15, 10, np.inf, np.inf, np.inf], # SXB
[np.inf, np.inf, np.inf, np.inf, 10, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, 15, np.inf, 5, 25, np.inf, np.inf], # GNT
[np.inf, np.inf, np.inf, np.inf, 5, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, 10, 5, np.inf, 20, 15, np.inf], # BRU
[np.inf, np.inf, np.inf, 20, 30, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, 25, 20, np.inf, 10, np.inf], # HAM
[np.inf, np.inf, np.inf, np.inf, 20, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, 15, 10, np.inf, 30], # FRA
[np.inf, np.inf, np.inf, np.inf, np.inf, 10, 20, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, np.inf, 30, np.inf], # MIL
])
# Cities
cities = ['Lisbon', 'Madrid', 'Paris', 'Berlin', 'Amsterdam', 'Rome', 'Zurich', 'Vienna', 'Porto', 'Barcelona', 'Toulouse', 'Strasbourg', 'Ghent', 'Brussels', 'Hamburg', 'Frankfurt', 'Milan']
cost_matrix = pd.DataFrame(connections_cost, index=cities, columns=cities)
# Define the handling costs
handling_costs = {'Lisbon': 2, 'Madrid': 3, 'Paris': 4, 'Berlin': 5, 'Amsterdam': 5, 'Rome': 4, 'Zurich': 6, 'Vienna': 6, 'Porto': 2, 'Barcelona': 3, 'Toulouse': 4, 'Strasbourg': 5, 'Ghent': 5, 'Brussels': 4, 'Hamburg': 6, 'Frankfurt': 6, 'Milan': 6}
# Origin
origin = 'Porto'
# Destination
destination = 'Zurich'
# City coordinates - for visualisation purposes (Optional)
cities_coords = {
'Lisbon':{'latitude': 38.722, 'longitude': -9.139},
'Madrid':{'latitude': 40.416, 'longitude': -3.703},
'Paris':{'latitude': 48.856, 'longitude': 2.352},
'Berlin':{'latitude': 52.520, 'longitude': 13.404},
'Amsterdam':{'latitude': 52.370, 'longitude': 4.895},
'Rome':{'latitude': 41.902, 'longitude': 12.496},
'Zurich':{'latitude': 47.376, 'longitude': 8.541},
'Vienna':{'latitude': 48.208, 'longitude': 16.373},
'Porto':{'latitude': 41.157, 'longitude': -8.629},
'Barcelona':{'latitude': 41.385, 'longitude': 2.173},
'Toulouse':{'latitude': 43.604, 'longitude': 1.444},
'Strasbourg':{'latitude': 48.583, 'longitude': 7.745},
'Ghent':{'latitude': 51.054, 'longitude': 3.717},
'Brussels':{'latitude': 50.850, 'longitude': 4.351},
'Hamburg':{'latitude': 53.551, 'longitude': 9.993},
'Frankfurt':{'latitude': 50.110, 'longitude': 8.683},
'Milan':{'latitude': 45.464, 'longitude': 9.189}
}
return cities, origin, destination, handling_costs, cost_matrix, cities_coordsNetwork visualisation
Optionally, we can create a visualisation of the network map to better illustrate the interconnections of the routes between cities. In this visualisation, we will also adjust the line thickness according to cost, so that cheaper and more attractive routes appear thicker than the more expensive ones. This visual representation can help making it easier to comprehend how the genetic algorithm navigates and optimises the routing challenges within an intricate web of cities and transportation links.
Please note that the visualisations suggested in this article can significantly extend the algorithm’s running time. If a shorter running time is a priority, consider commenting out or omitting this part of the code.
def create_network_map(cities, cost_matrix, cities_coords):
"""Create a visual representation of the network"""
# Calculate average latitude and longitude for the initial map center
avg_lat = sum(coord['latitude'] for coord in cities_coords.values()) / len(cities_coords)
avg_lon = sum(coord['longitude'] for coord in cities_coords.values()) / len(cities_coords)
# Create a map centered around the average location
map = folium.Map(location=[avg_lat, avg_lon], zoom_start=5)
# Add markers for each city
for city, coords in cities_coords.items():
folium.Marker([coords['latitude'], coords['longitude']], popup=city).add_to(map)
# Determine min and max costs for normalization
min_cost = np.min(cost_matrix[cost_matrix != np.inf])
max_cost = np.max(cost_matrix[cost_matrix != np.inf])
# Function to normalize costs to a range for line widths
def normalize_cost(cost, min_cost, max_cost, min_width=1, max_width=5):
# Inverse normalization to make cheaper routes thicker
return max_width - (cost - min_cost) * (max_width - min_width) / (max_cost - min_cost)
line_color = '#69b8d6' # Color for the lines
# Draw connections with varying line widths
for i, city1 in enumerate(cities):
for j, city2 in enumerate(cities):
if i != j and cost_matrix.iloc[i, j] != np.inf:
cost = cost_matrix.iloc[i, j]
line_width = normalize_cost(cost, min_cost, max_cost)
location1 = [cities_coords[city1]['latitude'], cities_coords[city1]['longitude']]
location2 = [cities_coords[city2]['latitude'], cities_coords[city2]['longitude']]
line = folium.PolyLine(locations=[location1, location2], weight=line_width, color=line_color)
map.add_child(line)
return mapThis creates an HTML file representing a map that can be zoomed in and out. It displays all city connections, with the thickness of each link varying according to its cost.
Genetic Algorithm Configuration
In genetic algorithms, several key concepts govern the evolution of solutions:
Elitism
Elitism is a strategy to ensure the preservation of the best solutions found during the evolutionary process. A certain percentage of the fittest individuals from the current generation are automatically passed to the next generation without undergoing crossover or mutation. This strategy guarantees that the quality solutions discovered are not lost, maintaining a high standard of fitness within the population.
Tournament Selection
Tournament selection is a method used to choose individuals for the next phase of genetic operations, such as crossover and mutation. In this process, a ‘tournament’ is conducted among a randomly selected subset of individuals. The size of this group is defined by the tournament size. The fittest individual from this group is then selected for breeding. This method balances the exploration of the search space with the exploitation of the current best solutions.
Stagnation
Stagnation refers to a situation in genetic algorithms where there is little or no improvement in the solution quality over successive generations. This often indicates that the population has converged to a local optimum or lacks the genetic diversity necessary to produce better offspring. Recognizing stagnation is crucial for the efficient use of computational resources and often triggers the termination of the algorithm.
Termination Criteria
The termination of a genetic algorithm is a critical aspect of its design. It can be determined by various criteria, such as reaching a maximum number of generations or encountering a prolonged period of stagnation, where no significant improvement is observed. Setting appropriate termination criteria is essential to prevent the algorithm from running indefinitely and to ensure that computational resources are allocated effectively.
The get_ga_config() function below outlines the parameters of our GA: population size, tournament size for selection, and other critical variables that dictate the behavior and termination of our GA.
def get_ga_config():
"""Get the configuration for the genetic algorithm"""
population_size = 20 # Number of individuals in the population
elitism_percentage = 0.2 # Percentage of the population to be selected for elitism
tournament_size = 5 # Number of chromosomes to select for tournament
max_generations = 100 # Number of generations to run the algorithm for
max_stagnation = 20 # Number of generations to wait before terminating due to stagnation
return population_size, elitism_percentage, tournament_size, max_generations, max_stagnationInitialising the Population
When initialising a population for a genetic algorithm, it’s crucial to include a diverse range of solutions, encompassing both known possibilities for the problem and a substantial number of random solutions. Although these random solutions might not be near the optimal or even feasible initially, their inclusion ensures a broad exploration of the solution space, which enhances the algorithm’s ability to thoroughly search for the best solution as it progresses through successive generations.
Our initialise_population() function seeds the algorithm with an initial set of possible routes, including the shortest and longest possible paths. This genetic diversity is vital to avoid converging on suboptimal solutions prematurely.
def initialise_population(pop_size, cities, origin, destination):
"""Create a population of chromosomes"""
population = []
shortest_path_chromosome = {}
longest_path_chromosome = {}
# List all other cities besides the origin and destination
connection_cities = [city for city in cities if city not in [origin, destination]] # exclude origin and destination
# Add a cromosome with the shortest path
shortest_path_chromosome['route'] = [origin] + [destination]
population.append(shortest_path_chromosome)
# Add a chromosome with the longest path (going through all cities)
longest_path_chromosome['route'] = [origin] + connection_cities + [destination]
population.append(longest_path_chromosome)
# Add chromosomes with random paths between origin and destination until we reach the total number of individuals in the population
for _ in range(pop_size - 2):
random_chromosome = {}
# Randomly decide how many intermediate cities to include
num_intermediate = random.randint(0, len(connection_cities) - 2)
# Randomly select the intermediate cities
intermediate_cities = random.sample(connection_cities, num_intermediate)
# Build the chromosome
random_chromosome['route'] = [origin] + intermediate_cities + [destination]
# Add chromosome to population
population.append(random_chromosome)
return populationEvaluating Fitness
We assess the suitability of each route using the evaluate_and_sort_population function. The cost of traversing each route, including the handling costs, defines the fitness of that route: the lower the cost, the fitter the route. The GA seeks to minimise this cost function.
def evaluate_and_sort_population(population, cost_matrix, handling_costs):
"""Evaluate the population and sort it in ascending order of cost"""
for chromosome in population:
if 'cost' not in chromosome.keys():
total_cost = 0
for i in range(len(chromosome['route'])-1):
city1 = chromosome['route'][i]
city2 = chromosome['route'][i + 1]
total_cost += cost_matrix.loc[city1, city2] + handling_costs[city1]
chromosome['cost'] = total_cost
return sorted(population, key=lambda x: x['cost'])If the routing is subject to certain constraints, like a maximum lead time, these can be integrated into the chromosome evaluation. For instance, routes that exceed the maximum allowed lead time can be deemed unfeasible and assigned an infinite cost. This effectively filters out solutions that do not meet the specified criteria, ensuring that the genetic algorithm only considers viable routes that comply with all the imposed constraints.
Selection Process
The tournament_selection() function simulates a survival-of-the-fittest scenario where the best routes are selected to parent the next generation. This step ensures that high-quality attributes (efficient sub-routes) are passed on.
def tournament_selection(population, tournament_size):
"""Select two parents from the population using tournament selection"""
selected_parents = []
for _ in range(2): # Select two parents
# Randomly select tournament_size chromosomes for the tournament
tournament = random.sample(population, tournament_size)
# Select the best chromosome from the tournament
winner = min(tournament, key=lambda x: x['cost'])
selected_parents.append(winner)
return selected_parentsCrossover and Mutation
There are numerous options for crossover and mutation operations. The choice of which to apply should be guided by our desired modifications to the solutions, aiming to enhance their viability and steer them toward an optimal solution, all of which depend on the specific problem at hand.
Through crossover, as handled by the crossover() function, we combine segments of two routes to create offspring with features from both parents. If any of the offsprings generated have inconsistencies like repeated cities, their route is repaired.
def crossover(parent1, parent2, origin, destination):
"""Create two new chromosomes by applying crossover to two parent chromosomes"""
route1 = copy.deepcopy(parent1['route'])
route2 = copy.deepcopy(parent2['route'])
#Proceed to crossover if both parents have more than two cities and if parents are different
if min(len(route1), len(route2)) > 2 and route1 != route2:
# If one of the parents has only 3 cities, then add the other parent's cities to the offspring (otherwise we end up with offsprings which are the same as the parents)
if min(len(route1), len(route2)) == 3:
# Randomly select a crossover point
crossover_point = random.randint(1, min(len(route1), len(route2))-1)
# Perform crossover
offspring1_route = route1 + route2[crossover_point:]
offspring2_route = route2 + route1[crossover_point:]
else:
# Randomly select a crossover point (between 2 and the minimum length of the two routes -2, to maximise odds of having offsprings different from parents)
crossover_point = random.randint(2, min(len(route1), len(route2)) - 2)
# Perform crossover
offspring1_route = route1[:crossover_point] + route2[crossover_point:]
offspring2_route = route2[:crossover_point] + route1[crossover_point:]
# Repair the offsprings routes to avoid repeating cities
offspring1_route = repair_route(offspring1_route, origin, destination)
offspring2_route = repair_route(offspring2_route, origin, destination)
# Create offsprings
offspring1 = {"route": offspring1_route}
offspring2 = {"route": offspring2_route}
return offspring1, offspring2
# If one or both parents have only one leg, return the parents since offsprings would be the same as parents
else:
return parent1, parent2
def repair_route(route, origin, destination):
"""Repair a route by ensuring it starts and ends at the origin and destination, respectively, and by removing repeated cities"""
# Ensure first city is origin and last city is destination and remove intermediate cities if they are origin or destination
if route[0] != origin:
route[0] = origin
if route[-1] != destination:
route[-1] = destination
route = [route[0]] + [city for city in route[1:-1] if city != origin and city != destination] + [route[-1]]
# Remove repeated cities
seen = set()
repaired_route = [seen.add(city) or city for city in route if city not in seen] # adds city to seen if not already there and, in that case, adds city to fixed_route
return repaired_routeMutation, on the other hand, introduces random changes to a route, allowing the algorithm to explore routes beyond the local optimum. The mutation() function ensures diversity within the population, preventing premature convergence.
It is common to attribute a certain probability for crossover and mutations to happen. For this problem, however, this traditional approach was not taken in favor of introducing a higher degree of variability into the population at an accelerated rate.
# Mutation Function
def mutation(chromosome, cities, origin, destination):
"""Create two new chromosomes by applying mutations to a chromosome"""
route1 = copy.deepcopy(chromosome['route'])
route2 = copy.deepcopy(chromosome['route'])
# Ensure we only add cities that are not the origin, destination, or already in the route
possible_cities_to_add = [city for city in cities if city not in chromosome['route']]
# If chromosome has only 2 cities, create two new chromosomes by adding a city between the origin and destination (position 1):
if len(chromosome['route']) == 2:
route1.insert(1, random.choice(possible_cities_to_add))
route2.insert(1, random.choice(possible_cities_to_add))
# If chromosome has 3 or more cities, create a new chromosome by removing a city
elif len(chromosome['route']) >= 3:
route1.pop(random.randint(1, len(chromosome['route'])-1))
# If chromosome has 3 cities, create a new chromosome by adding a city between the origin and destination (position 1):
if len(chromosome['route']) == 3:
route2.insert(1, random.choice(possible_cities_to_add))
# If chromosome has 4 or more cities, create a new chromosome by swapping two cities
elif len(chromosome['route']) >= 4:
idx1, idx2 = random.sample(range(1, len(chromosome['route'])-1), 2) # Get two distinct indices
# Perform the swap
route2[idx1], route2[idx2] = route2[idx2], route2[idx1]
# Repair routes if necessary
route1 = repair_route(route1, origin, destination)
route2 = repair_route(route2, origin, destination)
# Create offsprings
mutated_chromosome1 = {"route": route1}
mutated_chromosome2 = {"route": route2}
return mutated_chromosome1, mutated_chromosome2Animate the best route evolution across generations
If you would like to add a sprinkle to your algorithm, visualising the evolution of the best route across generations can be remarkably insightful. The visualisation serves a dual purpose: it makes it easier to communicate the algorithm’s effectiveness to stakeholders and provides a debugging tool to improve the GA’s performance. This code snippet shows how this can be achieved by plotting the cities and the evolving route at each generation and saving each frame as an image. These images are then compiled into a GIF, providing a dynamic visualisation of how the genetic algorithm improves the route over time.
Remember, this visualization can increase the algorithm’s running time, so skip it if speed is your priority.
def animate_best_routes(best_routes_per_generation, cities, cost_matrix, cities_coords):
"""Create an animation to show the best route evolving with generations"""
# Generate the frames
images_paths = []
unique_best_routes = [] # to avoid repeated routes in best_routes_per_generation
_ = [unique_best_routes.append(x) for x in best_routes_per_generation if x not in unique_best_routes]
# Use this for a GIF with all best route solutions
for frame, (route, cost) in enumerate(best_routes_per_generation):
# # Use this, instead, for a GIF with only unique solutions
# for frame, (route, cost) in enumerate(unique_best_routes):
map = create_network_map(cities, cost_matrix, cities_coords)
route_colour = '#004E6B' # Color for the route
# Add the evolving route for this generation to the map
route_coords = [[cities_coords[city]['latitude'], cities_coords[city]['longitude']] for city in route]
folium.PolyLine(route_coords, color=route_colour, weight=5, opacity=1).add_to(map)
# Calculate average latitude and longitude for legend
avg_lat = sum(coord['latitude'] for coord in cities_coords.values()) / len(cities_coords)
avg_lon = sum(coord['longitude'] for coord in cities_coords.values()) / len(cities_coords)
# Add a legend with the cost
legend_html = f'''
<div style="position: fixed;
bottom: -250px; left: 220px; width: 150px; height: 90px;
border:2px solid grey; z-index:9999; font-size:14px;
background-color:white; padding:10px;">
<b>Cost: {cost}</b><br>
Best solution in Generation {frame}
</div>
'''
iframe = IFrame(legend_html, width=170, height=110)
folium.Marker(location=[avg_lat, avg_lon], icon=folium.DivIcon(html=legend_html)).add_to(map)
# Save the map as an HTML file for this frame
html_path = f'data/output/animation/frame_{frame}.html'
map.save(html_path)
# Append image path to list
image_path = f'data/output/animation/frame_{frame}.png'
images_paths = images_paths + [image_path]
convert_html_to_image(html_path, image_path)
# Optionally delete html file
os.remove(html_path)
gif_path = f'data/output/animation/best_route_evolution_{best_routes_per_generation[0][0][0]}_{best_routes_per_generation[0][0][-1]}.gif'
create_gif(images_paths, gif_path)
# Optionally delete the image files after creating the GIF
for image_path in images_paths:
os.remove(image_path)
return gif_path
def convert_html_to_image(html_path, image_path):
"""Convert an HTML file to an image and save it"""
# Set up headless Chromium options
chrome_options = Options()
chrome_options.add_argument("--headless")
chrome_options.add_argument("--disable-gpu")
chrome_options.add_argument("--no-sandbox")
chrome_options.binary_location = "/usr/bin/chromium"
# Specify the path to chromedriver using Service
service = Service(executable_path="/usr/bin/chromedriver")
# Initialize the driver
driver = webdriver.Chrome(service=service, options=chrome_options)
# Load the HTML file
absolute_html_path = os.path.abspath(html_path)
driver.get("file://" + absolute_html_path)
# # If image is blank, wait for the content to load
# time.sleep(1) # Adjust the time as needed
# Set the size of the window to capture the entire page
total_width = driver.execute_script("return document.body.offsetWidth")
total_height = driver.execute_script("return document.body.scrollHeight")
driver.set_window_size(total_width, total_height)
# Take a screenshot and save it
screenshot = driver.get_screenshot_as_png()
driver.quit()
# Convert screenshot to an image and save
image = Image.open(io.BytesIO(screenshot))
image.save(image_path)
def create_gif(images_paths, gif_path):
"""Create a GIF from a list of image paths"""
images = [Image.open(image) for image in images_paths]
# Set the duration for each frame (in milliseconds)
default_duration = 300 # Duration for all frames except the last one
durations = [default_duration] * (len(images) - 1) # Apply default duration to all frames except the last
durations.append(2000) # Higher duration for the last frame so that end of loop in GIF is obvious
images[0].save(gif_path, save_all=True, append_images=images[1:], duration=durations, loop=0)
Running the Genetic Algorithm
Within the genetic_algorithm() function, the GA is set in motion. It iteratively selects the fittest routes, combines them, introduces mutations, and evaluates the new generation. The process repeats, steering the population towards increasingly efficient solutions. If the population stagnates or reaches a maximum number of generations, the algorithm concludes, presenting an optimal or near-optimal route.
def genetic_algorithm():
"""Run the genetic algorithm (GA)"""
# Get data
cities, origin, destination, handling_costs, cost_matrix, cities_coords = get_data()
# Create visual representation of network (Optional)
map = create_network_map(cities, cost_matrix, cities_coords)
# Save the map to an HTML file
map.save('data/output/animation/network_map.html')
# Get GA configurations
population_size, elitism_percentage, tournament_size, max_generations, max_stagnation = get_ga_config()
# Initialise population
population = initialise_population(population_size, cities, origin, destination)
# Evaluate and sort the initial population
population = evaluate_and_sort_population(population, cost_matrix, handling_costs)
# Stagnation variables
best_cost = float('inf')
stagnation_counter = 0
# Store best route for visualisation purposes
best_routes_per_generation = []
# Main GA loop
for generation in range(max_generations):
new_population = []
# Apply elitism - select the best chromosomes from the population
elite_chromosomes = population[:int(elitism_percentage * population_size)]
new_population.extend(elite_chromosomes)
while len(new_population) < population_size:
# Apply tournament selection
parent1, parent2 = tournament_selection(population, tournament_size)
# Create new chromosomes applying crossover
offspring1, offspring2 = crossover(parent1, parent2, origin, destination)
# Create new chromosomes applying mutation to the new offsprings
offspring3, offspring4 = mutation(offspring1, cities, origin, destination)
# Add offsprings to new population
new_population.extend([offspring1, offspring2, offspring3, offspring4])
population = new_population
population = evaluate_and_sort_population(population, cost_matrix, handling_costs)
# Get best route
best_chromosome = population[0]
best_routes_per_generation.append((best_chromosome['route'], best_chromosome['cost']))
# Check for stagnation
current_best_cost = best_chromosome['cost'] # Population is sorted in ascending order of cost
if current_best_cost < best_cost:
best_cost = current_best_cost
print(f'Generation {generation} best cost {best_cost}')
stagnation_counter = 0 # Reset stagnation counter
else:
stagnation_counter += 1
if stagnation_counter >= max_stagnation:
print(f"Terminating due to stagnation at generation {generation}.")
break
if generation == max_generations - 1:
print(f"Info: Terminating due to reaching maximum of {generation} generations.")
print(f"Info: Best cost found: {best_cost}")
print(f"Info: Best route found: {best_chromosome['route']}")
# Create animation to show best route evolving with generations
gif_path = animate_best_routes(best_routes_per_generation, cities, cost_matrix, cities_coords)
print(f"Info: Animation of best route evolution is available in: {gif_path}")
return
if __name__ == "__main__":
genetic_algorithm()Results and Discussion
The GA algorithm was run for a few examples and its performance was compared to the optimal solution. The number of generations required for the algorithm to converge was also recorded. The table below summarises some of these tests.
In most cases, the algorithm successfully converged to the optimal solution. However, in the specific case of Hamburg to Lisbon route, where the optimal solution involves 4 legs, the algorithm struggled to converge to this optimal solution. This suggests that introducing more mutations might be beneficial, particularly to generate larger chromosomes (corresponding to routes with many legs) and to increase the randomness of the solutions.
In most examples, the algorithm converged to the best-found solution quite rapidly, typically not exceeding 10 generations and usually terminating due to stagnation. A low number of generations until convergence could suggest that the initial conditions are already well-suited for finding a solution close to optimality. Alternatively, it might indicate that the algorithm is somewhat greedy, potentially not exploring the solution space sufficiently, especially in cases where it does not find the optimal solution. An effective strategy to boost efficiency is to combine the genetic algorithm with other metaheuristic techniques, such as Tabu Search or Simulated Annealing. In particular, implementing a Tabu Search that prevents revisiting previously generated solutions could enhance the algorithm’s performance. This approach would encourage a broader exploration of different solutions, thereby covering more of the solution space.
These insights into the algorithm’s performance and potential improvements underscore its practical value. The GA yields a route with the lowest cumulative cost found throughout its run. This route represents the most cost-effective path through the network given the current cost matrix and handling fees. It’s an elegant demonstration of how a bio-inspired algorithm can tackle a complex optimisation problem that’s both dynamic and constrained.
Adapting for more complex routing problems
The example in this article represents a very simple use-case. However, real-world routing problems often involve numerous constraints and a vast array of possible combinations. Take supply-chain operations, for instance, where there might be a maximum allowable lead time from origin to destination, varying according to the type of goods. Strategies such as consolidating goods for part of the journey to reduce costs, choosing between different capacity transportation modes, and selecting from various transportation companies with differing service levels are some examples of layers of complexity that can be added.
Adapting a GA to tackle these more intricate problems generally involves two key strategies: expanding the combinatorial possibilities within the chromosome definition and incorporating constraints into the fitness evaluation process. For example, to account for a lead time constraint and varying service levels, we could modify the chromosome structure as follows: Each gene in the chromosome becomes a vector or a dictionary comprising several units — one for the city-pair, another for the time slot of that connection, and a final one for the service level. The fitness evaluation function would then calculate the cost of each gene based on these specifics (transportation between the city pair, using the chosen service level at the designated time slot). Additionally, a mechanism should be established, either through a chromosome repair function or within the fitness evaluation itself, to ensure all constraints are met. For instance, the fitness function could assign an infinite cost to any chromosome that violates the maximum lead time constraint. Mutation and crossover methods might also be tailored to target all or specific units of the genes, depending on the objectives of the particular mutation or crossover.
Conclusion
The genetic algorithm provides a robust framework for solving routing problems that are otherwise intractable with conventional optimisation methods. Through a process inspired by natural selection, GAs can evolve solutions to complex problems, adapting to dynamic environments and constraints.
The application of GAs extends beyond theoretical exercises and into real-world scenarios where routing costs fluctuate with time and demand. Logistics companies can use GAs to optimize delivery routes in real-time, adjusting to traffic, weather, and varying fuel costs. Similar principles apply in telecommunications for data routing, and in manufacturing for streamlining supply chains.
While this article provides an introductory exploration of using genetic algorithms for routing problems, it’s important to note that the approach outlined here is a simplified representation of a complex field. This article is meant to give you a taste of what’s possible, especially in the world of routing problems. Every real-world situation is unique, and you’ll likely need to tweak and adjust the methods I’ve shown to fit the specific requirements of your use-cases.
I’d love to hear your thoughts on this topic! If you’ve got ideas, experiences, or questions about applying genetic algorithms in your projects, feel free to drop a comment below. Let’s keep the conversation going!
I am grateful to Maersk for fostering such a rich learning environment and actively encouraging knowledge sharing and publications. I would also like to thank my dear friends and colleagues at Maersk, Pedro Esmeriz and Teresa Valério, for their invaluable insights, which contributed to the enhancement of this article.
