What Is Route Optimization? Algorithms, Constraints, and APIs

Route optimization is the practice of ordering stops and assigning vehicles so a fleet finishes its work in the least time, distance, or cost. It is the difference between a delivery driver who finishes at 4 PM and one who finishes at 7 PM with the same van and the same stops. Underneath every "optimised route" button in a logistics app sits a solver that has just chewed through millions of possible orderings and picked one.

This guide explains what route optimization actually is, how the solvers approach it, where it shows up in the real world, and which constraints and pitfalls separate a demo from production.

What Route Optimization Really Is

In computer science, route optimization lives inside two classic problems. The Travelling Salesman Problem (TSP) asks: given a list of cities and the distances between them, what is the shortest route that visits every city exactly once and returns to the start? It is a single-vehicle problem. The Vehicle Routing Problem (VRP) generalises this to a fleet: given a depot, a set of customers, and several vehicles, how should the customers be split between the vehicles, and in what order should each vehicle visit them?

Both problems are NP-hard. The number of possible orderings grows factorially with the number of stops. Twenty stops already produce more than 10 to the 18 possible routes. No exact algorithm can search that space in real time. Optimization, in production, is therefore not about finding the perfect answer. It is about finding a very good answer fast enough to act on.

How Solvers Approach the Problem

Because the search space is enormous, real solvers blend several techniques.

For small problems, exact methods like branch-and-bound or integer programming can return a provably optimal solution in seconds. Pure TSP instances with tens of thousands of cities have been solved to optimality, but once time windows, capacities, and shifts enter the model, exact methods stop being practical at production scale and the field switches to heuristics.

A typical pipeline starts with a constructive heuristic such as nearest-neighbour or the Clarke-Wright savings algorithm to produce an initial route. That route is then handed to a metaheuristic, which iteratively swaps stops, reverses sub-tours, or moves stops between vehicles to improve the objective. Simulated annealing, tabu search, large neighbourhood search, and genetic algorithms are the most common choices. Each has the same shape: try a change, decide whether to accept it, repeat for a fixed time budget.

The other critical input is the distance matrix: a precomputed table of travel time and distance between every pair of stops. The optimizer queries the matrix millions of times during its search, so the matrix is built once up front by a routing engine and held in memory while the solver runs.

Where Route Optimization Shows Up

Route optimization quietly powers a long list of operational businesses.

• Last-mile delivery: parcel carriers, grocery delivery, and e-commerce fulfilment all sequence dozens to hundreds of stops per van per day
• Field service: HVAC technicians, telecom installers, and home health workers visit customers across a region with appointment windows and skill requirements
• Mobile workforce: utility crews, meter readers, and inspectors covering territories with mixed task types
• Food delivery: restaurant aggregators batching multiple orders into a single rider trip when the geography lines up
• Waste collection: municipal trucks running fixed weekly rounds where small reorderings save real fuel
• Sales reps: territory planning where a rep visits 8 to 12 accounts per day and the order matters for drive time and meeting density

In every case the user sees a list of stops in the right order. The work happens in the optimizer behind it.

Constraints That Matter

A solver that only minimises distance is a toy. Production routing is defined by its constraints.

• Vehicle capacity: each van has a weight, volume, or pallet limit that the assigned stops must not exceed
• Time windows: customers expect delivery between, say, 9 and 11 AM, and arriving at 11:05 is a failure
• Driver shifts: maximum working hours, mandatory breaks, and start and end at specific depots
• Skill or vehicle matching: a fridge install needs a two-person team, a cold-chain delivery needs a refrigerated van
• Multi-depot: large fleets dispatch from several warehouses and the solver decides which depot handles which stop
• Return-to-base: some routes are open (driver ends at home), others are closed (driver returns to depot)

Each constraint shrinks the feasible set of routes and pushes the solver toward solutions that look slightly worse on paper but are actually deliverable.

Multi-stop route planning

The simplest optimization problem is one vehicle and a list of stops: a sales rep with 12 visits, a technician with 8 jobs, a van with 30 drops. The start and end are fixed, usually the depot or home, and the solver chooses the order in between. This is the problem a multi-stop route planner solves.

The number of possible orders is the factorial of the number of stops: 120 for 5 stops, 3,628,800 for 10, about 1.3 trillion for 15 and 2.65 × 10³² for 30. Trying every order stops being possible after about a dozen stops, so planners build a good route instead of proving the best one:

1. Build the matrix. Ask a distance matrix for the travel time and distance between every pair of points. For a depot and 30 stops that is 31 × 31 = 961 pairs, one Matrix API request.
2. Construct a first route. Nearest neighbour drives to the closest unvisited stop each time. It is fast and usually decent, but it leaves long legs at the end, when the only stops left are the ones it skipped.
3. Improve it. 2-opt takes two legs of the route, reverses the stops between them and keeps the change when the route gets shorter. It repeats until no swap helps, which removes the crossings that make a route look like spaghetti.

Two choices change the answer more than the algorithm does. A closed route returns to the depot, an open route ends at the last stop, which suits drivers who go home from their final job. And the objective can be time or distance: the fastest route often uses a ring road, so it is longer in kilometres.

What stop order saves, measured

We measured it on real roads. For each of three cities we took 30 pharmacies from OpenStreetMap as stops and a fixed depot in an industrial street on the edge of town (Rhôneweg in Amsterdam, Bleichertstraße in Berlin, Calle Salsipuedes in Madrid). One MapAtlas Matrix API request per city gave driving times and distances for every pair. We then compared three routes for one van that visits all 30 stops and returns to the depot:

The listed order is the order the stops came in, which has nothing to do with geography, so it is a worst case rather than what a dispatcher would plan by hand. The useful comparison is the last two columns: 2-opt on top of nearest neighbour saved another 5 to 11 percent of driving time in every city. Times are free-flow driving times without traffic and without the minutes spent at each stop.

The vehicle routing problem

Add more vehicles and the problem becomes the vehicle routing problem (VRP). The solver now makes two decisions: which vehicle gets which stop, and in which order each vehicle drives its share. Real fleets add constraints on top, and each common combination has its own name:

The split between vehicles matters as much as the order. We ran the same 30 stops per city with three vans of 10 stops each, all starting and ending at the depot:

The geographic split is the classic sweep method: sort the stops by their bearing from the depot and cut the circle into three slices of 10. It is a simple cluster-first, route-second approach, and it still beat optimising the order inside a poor split in all three cities. Production solvers go further and move single stops between vehicles while they improve the routes, which also lets them respect capacities and time windows that a fixed slice ignores.

Method. Stops: 30 OpenStreetMap amenity=pharmacy features per city, picked by OSM id at a fixed interval; one Amsterdam stop that the router could not leave was replaced by the next pharmacy in the list. Matrix: one MapAtlas Matrix API request per city (a second one in Amsterdam after the replacement), car profile, free-flow times. Solvers: nearest neighbour and 2-opt on travel time, run locally on the matrix. The script is scripts/seo/blog-keyword-research/what-is-route-optimization.mjs and the stops and results are in docs/blog-keyword-research/what-is-route-optimization-2026-09-30.json. Pharmacy data © OpenStreetMap contributors (ODbL).

Estimating What Optimization Saves

The baseline to beat is usually the naive route: stops visited in the order the orders came in, regardless of geography. In a dense city that produces the familiar spaghetti route, with the driver crossing their own path several times a day. Optimization removes that backtracking, which is why dense urban rounds tend to gain the most.

To size the benefit for your own fleet, price a route in distance and in driver time, then apply the reduction you measure in a pilot. As an illustration, take a van that drives 210 km and works 7.5 hours a day, with fuel at €0.38 per km and a driver at €22 per hour:

• Daily cost today: (210 x €0.38) + (7.5 x €22) = €79.80 + €165 = €244.80
• If a pilot shows 30 percent less distance and 20 percent less time: (147 x €0.38) + (6 x €22) = €55.86 + €132 = €187.86
• Difference: €56.94 per van per day, or about €142,000 a year for 10 vans over 250 working days

The percentages are the part to measure, not assume. Run the optimizer on a few weeks of historical stops, compare its plans to what drivers actually drove, and use those numbers. Also check what the solver reports when a constraint cannot be met: a good one returns the stops it could not fit inside their time windows, so dispatch can move a departure earlier or hand the stop to another vehicle.

Pitfalls in Production

Route optimization is a category where the demo always works and the rollout often does not.

Optimising the wrong objective. Minimising distance is the default, but for many fleets revenue or service-level compliance matters more than kilometres saved. A route that drops one extra parcel at the cost of 2 km is usually a win.

Free-flow vs traffic-aware times. A matrix built from raw road speeds will tell you a route takes 4 hours when in rush-hour traffic it takes 6. Use a routing engine that exposes traffic-aware travel times for the time of day the route will run.

No real-time replanning. Plans drift the moment a driver hits unexpected traffic, a customer cancels, or a new stop comes in. Operations teams need a way to re-optimise the remaining stops mid-day without throwing away the morning's work.

Frozen plan staleness. A weekly fixed route looked optimal in January and is now 20 percent worse because customers moved, volumes shifted, and a one-way street appeared. Re-run the optimization periodically and compare the new plan to the live one before forcing a change on drivers.

Route Optimization in MapAtlas

The MapAtlas Optimize Route API solves single-vehicle and fleet routing problems with the constraints that operations teams actually need: capacity, time windows, shifts, skills, and multi-depot setups. It returns a sequenced plan per vehicle along with predicted arrival and departure times for every stop.

It pairs naturally with two other endpoints in the MapAtlas stack. The Distance Matrix API builds the travel-time table the solver consumes, with traffic-aware times so plans hold up at rush hour. The Directions API draws the actual turn-by-turn road paths between consecutive stops once the order is fixed, so a driver app can show a real polyline rather than a straight line.

Route optimization will not look glamorous in a slide deck. It is a solver, a matrix, and a list of constraints. But it is the layer that decides whether a fleet finishes its day on time and on budget, and getting it right is what separates a routing feature that ships from one that gets quietly turned off.