How AI Route Optimization Works for Last-Mile Delivery, Step by Step

Route optimization works in four steps: it turns addresses into map coordinates, builds a matrix of estimated driving times between every pair of stops, searches for the stop order (and, for fleets, the vehicle assignment) with the lowest total time that respects your rules, and then returns the driving legs for navigation. Small routes can be solved exactly. Large routes are solved with heuristics that find near-optimal routes in seconds.

This article explains each step in plain English, with a small worked example, so you can judge any route optimization tool, including ours. For the buying side, see AI route optimization software for delivery fleets.

Step 1: Geocoding: from addresses to coordinates

Every stop must become a latitude and longitude before anything can be optimized. This is called geocoding.

Geocoding is where most "bad routes" start. "12 Smith St" exists in many suburbs; "Unit 4/12" may be dropped; a new estate may not be in the map data yet. If a pin lands in the wrong place, the optimizer will faithfully produce the best route to the wrong place.

Practical rule: check that every pin looks right before optimizing, especially for addresses without a suburb or postcode.

Step 2: The travel-time matrix

Next, the software needs the cost of going from every stop to every other stop. For 20 stops plus a start and an end, that is a 22 × 22 grid of 462 one-way trips (excluding each stop to itself).

The cost is usually estimated driving time, taken from a road-network data source. Some tools use distance instead, or a mix of time and distance. Straight-line distance is a poor substitute: two stops 177 m apart can be over 3 km apart by road, as in our real 24-stop example.

Worked example. A driver leaves a depot, visits A, B and C, and returns to the depot. Illustrative estimated driving times in minutes:

From \ To	Depot	A	B	C
Depot	-	8	15	12
A	8	-	6	14
B	15	7	-	5
C	11	14	5	-

Note that the matrix is not symmetric (A to B is 6, B to A is 7). One-way streets, turn restrictions and motorway ramps make real driving times directional.

Travel times can be:

• Average conditions: a typical driving time, independent of the hour.
• Time-of-day predictions: different times for 7 am and 2 pm.
• Live traffic: current conditions, for re-planning during the day.

Google's own documentation, for example, says that when no departure time is given, durations are based on "average time-independent traffic conditions". More in traffic-aware routing.

Step 3: Solving the stop order

With the matrix, the problem becomes: in which order should the stops be visited to make the total time as small as possible?

• One vehicle visiting all stops is the Travelling Salesman Problem (TSP). A delivery run usually has a fixed start and a fixed or open end, so it is an "open path" version.
• Several vehicles, often with capacities, time windows or shifts, is the Vehicle Routing Problem (VRP). It decides which vehicle gets which stops and the order of each route. With several starting points, see multi-depot problems.

In the worked example, there are 3 stops, so 3 × 2 × 1 = 6 possible orders:

Order	Total (min)
Depot → A → B → C → Depot	8 + 6 + 5 + 11 = 30
Depot → A → C → B → Depot	8 + 14 + 5 + 15 = 42
Depot → B → A → C → Depot	15 + 7 + 14 + 11 = 47
Depot → B → C → A → Depot	15 + 5 + 14 + 8 = 42
Depot → C → A → B → Depot	12 + 14 + 6 + 15 = 47
Depot → C → B → A → Depot	12 + 5 + 7 + 8 = 32

The best order takes 30 minutes; the worst 47. That spread, multiplied across 60 stops a day, is what route optimization recovers.

Why can't the software just try every order?

Because the number of orders explodes. With a fixed start and end, the number of possible orders of n stops is n! (n factorial):

Stops between start and end	Possible orders
5	120
10	3,628,800
15	about 1.3 trillion
20	about 2.4 × 10^18

So solvers use smarter methods:

• Exact dynamic programming (Held-Karp, 1962). Guarantees the best order with respect to the matrix, much faster than trying every order, but its work still doubles with every extra stop. Practical only for small routes.
• Construction heuristics. Build a reasonable route quickly, for example "always go to the nearest unvisited stop", or "add the cheapest arc first".
• Local search. Improve a route with small changes. 2-opt reverses a section of the route (which removes crossings); Or-opt moves a run of one to three stops to a better position.
• Metaheuristics. Strategies that stop local search getting stuck. Guided Local Search, available in Google OR-Tools, penalises features of the route that keep appearing in poor solutions, pushing the search to explore elsewhere.

Constraints (time windows, capacities, shift ends, pickups before deliveries) are handled inside the search: any route that breaks them is rejected or penalised.

Step 4: Turning the order into a drivable route

Once the order is fixed, the software requests the actual road legs between consecutive stops so the route can be drawn on a map and handed to navigation. Many tools also calculate an estimated arrival time at each stop, using the travel times plus a service time per stop.

Where "AI" fits

Most of the above is classical optimization from operations research, not machine learning. Machine learning appears in route optimization mainly to predict inputs: travel times by time of day, how long a stop will take, or whether a delivery is likely to fail. Some vendors also use it to rank address matches or read addresses from images. When a product says "AI-powered", ask which step uses it. See also why navigation apps don't do this.

How MiliRoute does it

MiliRoute is an AI route optimization app for couriers, delivery drivers and small delivery fleets. Its pipeline, verified against the code:

1. Geocodes every stop, after address entry with autocomplete or the camera scanner (which uses image text recognition to read addresses and business names).
2. Builds a matrix of estimated driving times and distances between every pair of stops from Google's road-routing data, with the same avoid-tolls setting used for the final route.
3. Solves an open path with a fixed start (your GPS position or an address) and a fixed end (an address, or the last stop):
4. up to 13 stops between start and end: exact (Held-Karp dynamic programming);
5. larger routes: Google OR-Tools with Guided Local Search, with local-search fallbacks (2-opt and Or-opt).
6. Tidies the route: removes crossing route lines where possible and re-improves on driving time, so the route is easier to follow.
7. Draws the driving legs and records the distance and time of the original entered order, so the app can show how much the optimized order saves.

MiliRoute optimizes one route per driver on average driving conditions; it does not solve multi-vehicle assignment or time windows.

Limits of any route optimizer

• Garbage in, garbage out. Wrong pins, missing service times or unrealistic constraints produce unrealistic routes.
• Estimates are estimates. Travel times come from models of the road network, not from your van on your day.
• Optimal is relative to the inputs. An "optimal" route is optimal for the matrix and rules it was given, not for parking, loading docks or customers who need a call first.

Conclusion

Route optimization is a pipeline: good addresses, a realistic travel-time matrix, a solver that fits the size of the problem, and constraints that reflect real work. Understanding the steps makes it easy to ask vendors the right questions and to spot why a route looks the way it does. Next, read about multi-stop delivery route optimization in practice.

See it on your own stops: create a free MiliRoute account, add up to 10 stops (solved exactly on the free plan), and check the order.

Frequently asked questions

What algorithm is used for route optimization?

Small single-vehicle routes can be solved exactly with dynamic programming such as Held-Karp. Larger problems use heuristics such as nearest-neighbour construction, 2-opt and Or-opt local search, and metaheuristics such as Guided Local Search.

Is route optimization the travelling salesman problem?

For one vehicle visiting all stops, yes, it is a version of the travelling salesman problem. With several vehicles and constraints it becomes the vehicle routing problem.

Does route optimization use straight-line distance?

Good tools use estimated road driving times or distances. Straight-line distance ignores the road network and can make a far stop look near.

How long does it take to optimize a route?

Typically seconds. Exact methods are instant for small routes; heuristics for large routes usually run for a fixed time budget of a few seconds.

Is the optimized route always the shortest?

It is the best route found for the chosen goal, usually total driving time. The fastest route is not always the shortest in kilometres.

Where is AI used in route optimization?

Mostly in predicting inputs, such as time-of-day travel times or service times, and in reading or matching addresses. The ordering itself is usually classical optimization.

Why does my optimized route look strange on the map?

Usually because road layout, one-way streets or barriers make the "obvious" order slower. Check driving time between the stops, not map distance.