Background

The Genetic Algorithm

To tackle the complexities of the Vehicle Routing Problem (VRP), we utilise the Genetic Algorithm (GA). This approach draws inspiration from natural selection to iteratively find high-quality solutions. First, there are some core terms to be aware of.

Terminology

• Generation – A single iteration of the GA, during which a set of candidate solutions is evaluated and evolved.
• Population – The complete set of candidate solutions (chromosomes) being considered.
• Chromosome – One complete candidate solution to the problem being optimised.
• Gene – A single element or component within a chromosome.

In the context of the VRP, the GA operates with a population of potential solutions, where each chromosome represents a complete set of valid vehicle routes. The genes within a chromosome correspond to individual delivery locations, determining the sequence of stops each vehicle must make.

Populations are evaluated for their fitness based on criteria such as total distance, adherence to time windows, and capacity constraints. The GA uses several genetic operations, inspired by evolution, to modify routes and iteratively improve the population through successive generations. After each operation, the resulting new solutions are evaluated, and only those that are fitter than their predecessors, or at least meet a defined threshold, are selected to survive and potentially contribute to future generations.

The following genetic operations are used to adjust and re-order the population to maintain diversity and guide the search toward better solutions. Effective use prevents premature convergence on poor solutions while avoiding wasted computation from slow progress.

Selection

Selection chooses which solutions become parents for the next generation. In our VRP system, it favours higher-fitness solutions — those meeting objectives like minimal distance, time window adherence, and capacity limits — while still allowing some lower-fitness ones to maintain diversity.

A common technique we'll use is tournament selection, where a random subset is chosen and the fittest becomes a parent. This method is simple, offers good control over selection pressure, and performs well even when fitness scores are close.

Crossover

Crossover combines genetic material from two parent solutions to create offspring, exploring new delivery sequences and inheriting beneficial route structures from both.

In a one-point crossover, segments of two parent routes are swapped at a chosen index. For example, given two parent routes, a crossover point is selected (e.g., between index 1 and 2), and the leading segment from one parent is combined with the trailing segment from the other. This produces new route configurations while preserving intact sub-routes.

Mutation

Mutations introduce small, random changes to candidate solutions, helping maintain diversity and avoid local optima. In the VRP, they typically adjust stop order or reassign deliveries between routes.

Swap

Swaps two randomly selected stops within the same route, changing the visit order without altering vehicle assignments.

Inversion

Reverses the order of a selected subsequence of stops within a route, potentially reducing travel distance.

Insertion

Moves a stop from its current position to another, either within the same route (intra-route) or a different route (inter-route). Inter-route inserts can rebalance workloads by shifting stops between vehicles, while intra-route inserts fine-tune stop ordering.

Fitness Function

The fitness function evaluates how well a solution meets the problem’s objectives. For the CVRPTW, it penalises violations of capacity and time window constraints, while rewarding shorter travel distances and balanced route durations. Higher scores indicate more optimal and practical routing plans.

The equation used in this system is detailed in the system design.