Drone Delivery Route

A delivery drone has to visit a set of stops on a 2D map and return to its depot. The Genetic Algorithm (GA) evolves the order it visits them in, looking for a short tour.

How it works

1. Each chromosome is a permutation of the ten stop indices. The depot is the implicit start and end of every tour.
2. Each generation has fifteen tours. They are all drawn on the map, and the drone flies the shortest one, accelerating, braking and hovering at each delivery stop.
3. Fitness is the inverse of the total flight distance. Shorter tour, higher fitness.
4. The fittest tours become parents. A child keeps a stretch of one parent's route and visits the other stops in the order the other parent does, then a random stretch of the route is flown in reverse, the move that untangles a route that crosses itself.

What to watch

• The first generation looks like spaghetti. After a handful of generations the bold route tightens up and stops crossing itself, and it often ends on the shortest tour there is.
• The goal is a route 35% shorter than an average random one on this map. The readout marks it when a tour gets there.

Runs live in your browser. No sign-in needed.