You will never write one of these. But when a vendor says "our proprietary AI engine", it helps to know which forty-year-old family of methods sits underneath, and what genuinely differentiates one implementation from another.
The problem class
Route optimisation is a Vehicle Routing Problem (VRP), a generalisation of the Travelling Salesman Problem. Both are NP-hard: as the problem grows, the time needed to guarantee the best answer grows explosively. Practical software therefore aims for good answers fast, not provably perfect ones.
The commercial variants you will meet:
| Variant | Adds | Typical use |
|---|---|---|
| CVRP | Vehicle capacity | Basic distribution |
| VRPTW | Time windows | Retail delivery, service |
| MDVRP | Multiple depots | Regional distribution |
| PDPTW | Paired pickup and delivery | Courier, waste, swaps |
| Periodic VRP | Visit frequency patterns | Vending, pest control, waste |
| Rich VRP | Skills, compartments, driver rules, breaks | Real operations |
Most real problems are "rich": the constraints that make your business distinctive are exactly the ones that make the model hard.
Stage one: construction
The engine needs a starting solution.
Clarke–Wright savings (1964) merges routes where combining two customers saves more than serving them separately. Still competitive, still used, still the basis of a surprising number of "modern" engines.
Insertion heuristics repeatedly add the customer whose insertion costs least. Cheap, and easy to extend with time windows.
Sweep sorts customers by angle around the depot and cuts routes at capacity limits. Fast and geographically tidy, weak on time windows.
Cluster-first, route-second partitions customers into vehicle-sized clusters, then solves each cluster as a TSP. Intuitive for planners and useful when territories must stay geographically clean.
Stage two: improvement
Construction gives you something workable but mediocre. Local search improves it by trying defined moves:
- 2-opt / 3-opt — reverse a segment within a route to remove crossings.
- Or-opt — move a short chain of consecutive stops elsewhere.
- Relocate — move one stop to another route.
- Exchange — swap stops between routes.
- Cross-exchange — swap chains between routes.
Each move is evaluated and kept if it improves the objective. Repeat until no improving move exists — a local optimum, which may be far from the best available.
Stage three: escaping local optima
This is where implementations diverge.
Tabu search keeps a short memory of recent moves and forbids reversing them, forcing the search into new territory. Robust, well understood, still widely deployed.
Simulated annealing sometimes accepts a worsening move, with a probability that falls over time. Simple, effective, and easy to tune badly.
Large neighbourhood search (LNS) — currently the dominant approach — destroys part of the solution (remove 15% of stops by some rule) and repairs it with a fast insertion heuristic. Adaptive LNS learns which destroy-and-repair operators are working on your instance. It handles rich constraints unusually well, which is why it took over.
Genetic and memetic algorithms maintain a population of solutions and recombine them. Strong on classical benchmarks, less popular commercially because constraint handling gets awkward.
Constraint programming and MILP solve small subproblems exactly, often inside a larger heuristic framework. Sometimes used for the final polish or for scheduling sub-problems.
Why two engines give different answers to the same problem
- Different objective functions. One minimises distance, another a weighted cost. Identical inputs, different plans, both "optimal".
- Different constraint interpretation. Is a break allowed mid-stop? Does a time window apply to arrival or to completion? Vendors differ, and rarely document it.
- Different travel-time data. Road network vendor, speed profiles and turn restrictions vary substantially.
- Different time budgets. Any heuristic given 60 seconds beats itself given 5.
- Randomisation. Many metaheuristics are stochastic; two runs of the same engine on the same data can differ by a percent or two.
That last point matters in evaluation: run each vendor's engine three times on the same data set before drawing conclusions.
What actually differentiates a good implementation
- Constraint expressiveness — can it model your awkward reality without custom development?
- Infeasibility handling — does it explain which constraint blocked a stop, or just drop it?
- Warm starting — can it re-optimise from yesterday's plan to preserve driver familiarity?
- Determinism controls — can you fix a seed so a re-run reproduces the plan?
- Scalability curve — how does runtime grow from 500 to 5,000 stops?
- Objective transparency — can you see and adjust the cost weights?
Ask these five questions and you will learn more than from any benchmark table.
Benchmarks and why they mislead
Academic benchmark sets (Solomon, Gehring–Homberger, Uchoa) are useful for researchers and nearly useless for buyers. They contain none of your constraints, none of your data quality problems and none of your operational exceptions. A vendor beating a benchmark by 0.3% tells you nothing about whether their engine can handle your Tuesday.
Insist on a proof of concept with your own data. Compare against your current plan on the metrics you actually manage: vehicle count, driver hours, distance, window compliance.
Frequently asked questions
Is a "proprietary algorithm" claim meaningful?
Rarely. Nearly all commercial engines are variations on published metaheuristics, well engineered. The engineering — data structures, parallelisation, constraint handling — is where genuine differentiation lives, and it is legitimate. Judge outputs, not adjectives.
Should I care which solver library is used?
Only if you are building rather than buying. Open-source options such as OR-Tools are perfectly capable for many problems; several commercial products embed one. The wrapper — data model, UI, exception handling, integrations — is what you are paying for.
Can the engine handle 10,000 stops?
Most can, with enough runtime and appropriate decomposition (by depot, region or day). Ask specifically about runtime at your peak volume and whether decomposition harms cross-territory efficiency.
Why does the same plan run differently each time?
Stochastic search. Ask whether the product supports a fixed random seed, and whether it supports warm starting from an existing plan — both matter operationally more than raw solution quality.
Do machine learning approaches replace classical solvers?
Not in production, not yet. Learned heuristics are promising in research and are appearing as components — predicting service times, guiding operator selection — rather than as replacements for the solver.
