GSoC 2025 final Blog Post

Introduction

Welcome to my final update on the contributions to the Weather Routing Tool as part of Google Summer of Code 2025.

In my midterm blog post “Enhancing the WeatherRoutingTool’s Genetic Algorithm“, I explored ways to implement Continuous Route Optimization with changes in Mutation and Crossover independently. In this final blog post, I present a working genetic algorithm implementation that can optimize a route under complex conditions and lay foundations for future development. I also outline high-level implementation details, challenges, and results of the work.

Implementation

Genetic algorithms are an optimization technique that makes use of operators such as Crossover, Mutation and Selection, inspired by biological evolution. The Weather Routing Tool uses pymoo, a Python framework for genetic algorithms. The implementation of my Genetic algorithm for ship route optimization is outlined within the following hierarchy of steps that pymoo follows.

Population Generation

There are various methods available to generate an initial population

1. Grid Based Population
   This approach generates a population by viewing the map as a grid of waypoints and finds a route from point A to point B using heuristic search.
2. Isofuel Population
   This method utilizes the Isofuel algorithm to generate a set of routes that reach the destination.
3. Static Routes
   These are previously generated GeoJSON files stored in a directory. These can either be manually generated or saved from another algorithm.

I’ve also proposed the implementation of the Mixed Population Class, which utilizes all of the above methods to generate a diverse set of initial populations.

Selection

The Tournament Selection process produces N (in our case N=2) high fitness individuals that are to undergo crossover and mutation.

Crossover

Crossover aims to produce two offspring from two parents such that the offspring explore a route that’s a combination of the two parents. When a crossover operation fails to produce feasible offspring, we can either (1) Repair the offspring in the Repair section of the code or, (2) Return the parents as is to negate this reproduction process and redo from Selection.

The OffspringRejectionCrossover base class is implemented to ensure that unfeasible offspring are not generated at all. It does so with the following algorithm:

• Generate offspring using a child class’ implementation of the  crossover function
• Check if offspring violate discrete constraints
  • if True — refuse both offspring, and return the parents
  • if False — return offspring

The following types of Crossovers are implementations of the same.

1. Single Point Crossover
   Single Point Crossover is a simple approach to crossover where a single point of crossover is picked at random from both of the parents, and a route is patched from the crossover point of parent 1 to the crossover point of parent 2 and vice versa.

   

    

2. Two Point Crossover
   Two Point Crossover utilizes two random points such that the patched path avoids any object that produces a constraint violation in between. We utilize Route Patching (see the Route Patching section) because the chosen random points don’t consistently generate the correct crossover points.

 

Mutation

Mutation produces unexpected variability in the initial route to introduce diversity and improve the chances of the optimum route reaching global optima. The Weather Routing Tool considers the following few Mutation approaches.

1. Random Walk Mutation
   When looking at the waypoints as belonging to a grid, the Random Walk Mutation moves a random waypoint to one of its N-4 neighbourhood positions.

   

2. Route Blend Mutation
   This process converts a sub path into a smoother route using a smoothing function such as Bezier Curves or by replacing a few waypoints using the Great Circle Route.

Repair

The Repair classes play the role of normalizing routes and fixing constraints violations. The current implementation executes two repair processes in the following order:

1. Waypoints Infill Repair
   This process repairs routes by infilling them with equi-distant waypoints when adjacent points are farther than the specified distance resolution. This avoids long-distance jumps that may lead to impractical and unfeasible routes.

   

    

2. Constraint Violation Repair
   This repairs routes by identifying waypoints that are undergoing a constraint violation and finds a route around the points using the IsoFuel algorithm (See the IsoFuel Patcher section below)

   

    

 

Route Patching

Route patching is a necessity for the routing implementation. The route patcher is intended to find a valid route from point A to point B. This produced route need not be the most optimal route, but should not violate any constraints. I considered the following methods for patching routes:

• Great Circle Route
  This produces a granular route along the great circle distance connecting the two points.
  • Advantages: It produces the shortest best route from point A to point B.
  • Disadvantages: It cannot handle complex route navigation, e.g., if there’s a landmass in between the waypoints. It is up to the calling function to update the waypoints.
• Isofuel Algorithm
  This produces an optimum sub-route using the Isofuel algorithm.
  • Advantages: It produces an optimal route navigating complexities.
  • Disadvantages: It can be very slow and can fail based on the isofuel configuration.
  • Can be used if: We parallelize the execution of the Isofuel algorithm to speed up the process.

Duplicates Removal

Duplicates Removal is a critical step that helps maintain the uniqueness of the population at every generation.

Challenges

The implementation of route optimization raised multiple challenges throughout the implementation timeline. Most of the challenges listed below could be solved in different possibilities, and every possibility had its drawbacks. In such cases, I had to choose between the possible options, or build a system that is an amalgamation of all the possibilities.

The following are a few tradeoff challenges and how I solved them.

• The tradeoff between execution time and the performance of the system has been a recurring problem throughout the entire application. This was especially evident with the route patching system (where a valid, not-necessarily-optimal path needs to be found between two given waypoints).
  My solution: Route patching comes with two major options. The great circle distance offers fast execution but produces simple routes. The Isofuel algorithm offers valid feasible solutions, but slower execution. I was able to tackle this problem by optimizing the Isofuel algorithm’s configuration for speedy solutions such that it only evaluates 3 possible routes per step.
• The issue of multiple fitting solutions for a problem was a real challenge for crossover, mutation and population generation. Here, various different types of implementations were all valid solutions. After a little discussion with my mentors, we settled on the following solutions:
  • Crossover & Mutation: The system chooses a crossover operator at random so we can include all the complexities of the choices
  • Population: The developed initial routes are a combination of all different route generation methods.

Results

We evaluated the performance of the system at a setting in the Mediterranean Sea from points 37.506ºN, 12.305ºE to 33.827ºN, 34.311ºE. This setting introduces a lot of constraint complexity because of the large number of islands in the area. The Genetic algorithm was able to converge to a solution similar to the Isofuel algorithm in about 10 generations. Below I visualize the population across 10 generations for the same setting.

PR References

• https://github.com/52North/WeatherRoutingTool/pull/69
  • Implementing Patching, Mutation and Isofuel Populations
  • Introduced Random Walk and Route Blend Mutations
  • Introduced the patcher module
  • Defined the IsofuelPopulation class based on the IsofuelPatcher.
• https://github.com/52North/WeatherRoutingTool/pull/70
  • Implemented the two Repair classes: WaypointsInfillRepair and ConstraintViolationRepair
  • Defined orchestrator classes for Mutation, Crossover and Repair
• https://github.com/52North/WeatherRoutingTool/pull/67
  • Added Sphinx style docstrings for project documentation
  • Explained the algorithm’s implementation in the Genetic algorithms article.

Thank you!

This GSoC season has been an incredibly challenging, enriching, and rewarding journey. I’ve been genuinely excited throughout to work on something so innovative, deeply programmatic, and algorithmically engaging.

I’m especially grateful to Dr. Katharina Demmich and Mr. Martin Pontius for their invaluable guidance and support. My interactions with them continually motivated me to learn and push further. The Weather Routing Tool has been everything I hoped to work on—and more. I look forward to contributing further and watching it continue to grow.

 

These developments took place in connection with the TwinShip project.

 

This work has been co-funded by the European Union’s Horizon Europe programme under grant agreement No. 101192583