Drone Delivery Route

The Drone Delivery demo drops a depot and ten delivery stops onto a 2D map and asks the genetic algorithm to find a short tour that visits every stop and returns to the depot. It is a small Travelling Salesman Problem: each generation has fifteen candidate tours, and the drone flies the shortest one.

The Problem¶

A tour is just an order. With ten stops there are about three and a half million possible orders, which is small enough that a smart person with paper could solve it, and large enough that picking one at random is almost never good. The cost of any tour is its total flight distance, depot to first stop to second stop to last stop back to the depot. The map is a 10 km by 6 km delivery area (each grid square is 1 km), and distances are shown in km.

How a Run Looks¶

Click Start. All fifteen candidate tours of the generation appear on the map as faint lines. The shortest one is drawn bold, and the drone flies it from the depot, slowing down and hovering at each stop. Its stops are numbered in visit order, so you can follow the route it takes. Turn off Show all routes next to the Start button to hide the faint tours and keep only the shortest one. The flight plays at three times real time, and the Speed menu makes it faster still. A generation ends when the drone is back at the depot.

The readout under the map shows the generation number, the shortest tour in this generation, the shortest tour so far, and the target length for this map. The target is marked as reached once a tour gets there.

The platform then evolves the population. Four elites carry over unchanged. The other eleven children come from tournament-of-three winners combined with order crossover: a child copies a stretch of one parent's tour as it is, then visits the remaining stops in the order the other parent visits them, so every child is still a valid tour. Then, by default, six in ten children have a random stretch of their tour reversed: the drone flies that part the other way round. That is the move that untangles a route that crosses itself, since it swaps the two crossing legs for two that don't. The next round arrives a moment later and the drone flies the new shortest tour.

Within roughly ten generations on a typical map, the best tour stops crossing itself and looks like a real delivery route. In our tests (240 maps, default settings, 100 generations), every map reached the target, the final route crossed itself on just 1, and nearly three in four ended on the shortest possible tour. The history strip under the canvas keeps the best tour from every generation so you can scroll back and watch the shape converge.

What the Achievement Rewards¶

The target length is thirty-five percent shorter than the average random tour on the current map. The first time a best-of-generation tour reaches it, the Drone routes mastered achievement unlocks for signed-in users. The best of the first fifteen random tours almost never gets there, so it takes some evolving: a median of about seven generations with the default settings. The bar is computed per seed at session start, so harder layouts make the badge a little harder to earn. On the rare map whose random tours are very long, the target is capped at 35.5 km.

For more on how the demos catalog works, see What the Demos Do.