The travelling salesman problem, explained for dispatchers

What is the travelling salesman problem?

A driver must deliver to 20 addresses then return to the depot. In what order to cover the fewest kilometres? That question has a name: the travelling salesman problem (TSP). Add several vehicles, load capacities and time slots, and it becomes the vehicle routing problem (VRP) — the mathematical core of every dispatch tool.

Why it's harder than it looks

The VRP is NP-hard: it reduces to the travelling salesman problem, for which no fast exact algorithm is known at scale. The reason is combinatorial. For ten stops there are already hundreds of thousands of possible orders; for twenty, the number of combinations is staggering. Testing every option — "brute force" — becomes impossible beyond a handful of points, even for a computer.

That's why a human planner, however experienced, cannot mentally optimise 40 deliveries under time constraints. The brain finds a "decent" solution, rarely the best.

The answer: heuristics

Since the optimum can't be guaranteed, we look for a very good solution, very fast. That's the role of heuristics. The most famous, 2-opt, was proposed by Croes in 1958: it takes a route, removes two segments and reconnects them differently; if total distance falls, the change is kept, and so on until no further improvement is possible. Combined with other techniques, it produces near-optimal routes in seconds.

Real-world constraints

A good engine doesn't only minimise distance. It factors in vehicle capacity, delivery windows, service time per stop, required skills and, increasingly, real-time traffic. Each added constraint makes the calculation heavier — hence the value of a dedicated tool rather than a map and a spreadsheet.

What it changes in practice

The stakes are financial. According to industry analyses of the fleet-management market, route optimisation, idle reduction and driver-behaviour monitoring deliver fuel reductions of around 10 to 30%. For an SME with a few vehicles, that's an entire cost line being streamlined.

Let the algorithm compute your routes. Try dropfleet free for 14 days — no credit card, ready in 5 minutes.