2-opt, clustering, insertion: optimisation heuristics decoded

Why heuristics?

Computing the perfect route is an NP-hard problem: beyond a few dozen stops, no computer can test every combination. So we drop the guaranteed optimum and aim for an excellent solution, found fast. That's exactly what heuristics do. Three families complement each other.

1. Clustering

Before ordering anything, we split addresses into coherent geographic clusters. One vehicle = one area. This step avoids the costliest mistake: sending a driver across town for one isolated stop. Clustering doesn't compute the order; it defines each route's perimeter.

2. Local improvement: 2-opt

Once a route is built, we improve it. The 2-opt method, proposed by Croes in 1958, is the best known: it removes two segments of the route and reconnects them the other way. If total distance falls, keep it; otherwise, undo. Repeated thousands of times in a fraction of a second, this "untangles crossings" and trends toward a smooth route. A classic precisely because it's simple and formidably effective.

3. Cheapest insertion

How do you add a new stop to an already-computed route — say, an urgent order that arrives mid-day? The insertion heuristic tests every possible position and picks the one that adds the fewest kilometres. That's what absorbs the unexpected without recomputing everything.

How they work together

A good engine chains these logics: clustering to split, initial construction, then 2-opt to polish, and insertion for hot additions — all under real constraints (capacity, time windows, skills). The user only sees an "optimise" button and the kilometre gain shown before/after.

Ready-to-use optimisation, no maths PhD required. Try dropfleet free for 14 days — no credit card, ready in 5 minutes.