Genetic Algorithms for Routing — An Interactive Evolution Simulator

What this simulation shows

Every method covered so far in this series works on one solution at a time. Two-Opt improves the current route. Simulated Annealing follows the current route and occasionally accepts a worse one. Tabu Search keeps a memory about the current route. There is always one plan being modified.

A genetic algorithm abandons that model. It maintains a whole population of candidate routes simultaneously, scores each one, lets the better ones reproduce, and builds the next generation from their offspring. No individual route is being improved — the population improves, because good structural fragments survive across generations while poor ones die out.

This simulator evolves a delivery route around Yorkshire and shows both the current population and the fitness curve over time.

How to use it

Press Start evolution and watch the Fitness over generations chart. The characteristic shape is a steep early improvement followed by a long, flat tail: early generations discover the obvious structure quickly, then progress slows sharply as the population converges and its members start resembling one another.

Then dismantle it with the controls.

Population size governs genetic diversity. Set it small and the population converges in a handful of generations onto whatever it started near — fast, and usually mediocre. Larger populations explore more but cost proportionally more computation per generation.

Crossover rate controls how much recombination happens versus straight copying. Randy mutation rate is the counterweight: mutation is the only mechanism reintroducing genuinely new material once the population has converged. Set it to zero and evolution stalls permanently. Set it too high and inheritance stops meaning anything, degenerating into random search.

Elite routes retained decides how many top performers survive untouched. Without elitism, the best solution found can be lost to a bad generation. With too much, the population is dominated by a few individuals and diversity collapses.

Compare Tournament selection with Roulette-wheel selection. Roulette gives selection probability in proportion to fitness, which lets one early standout dominate the gene pool. Tournaments are less sensitive to that.

Finally, press Demonstrate naive crossover. This is the most instructive control on the page. Splice two valid parent routes at a random point and the child will usually visit some customers twice and others not at all — because a route is a permutation, not an independent list of genes. Real implementations need order-aware operators specifically designed to preserve validity.

What to take away

Genetic algorithms are strong when the search space is large and poorly understood, and awkward in operational software: they are slow, stochastic, and have several interacting parameters requiring tuning. That tuning problem is itself worth studying experimentally — which is what the Design of Experiments dissertation covers, using a genetic algorithm built in Java for the Travelling Salesman Problem.

Back to Simulations