How delivery routes are optimized: the vehicle routing problem

Most “AI-planned” delivery routes are not produced by a chatbot or a neural network. They come from a decades-old family of optimization methods known as the vehicle routing problem, or VRP: given a depot, a set of stops and a fleet, find routes that serve every stop at the lowest cost. Understanding it explains why route software is good at some things, such as juggling hundreds of stops, and weak at others, such as knowing a loading dock is blocked today.

What the vehicle routing problem asks

With one vehicle, the VRP collapses to the traveling salesperson problem, the puzzle of visiting every location once and returning home by the shortest path. Add more vehicles and you must also decide which vehicle serves which stop and in what order. Google’s OR-Tools documentation, a widely used open-source toolkit, frames it exactly this way: find optimal routes for multiple vehicles visiting a set of locations.

The choice of objective matters more than newcomers expect. If you only minimize total distance and impose no other limits, the cheapest answer is to send one vehicle to every stop. The OR-Tools guide instead suggests minimizing the length of the longest single route, which fits the real goal of finishing all deliveries as soon as possible and spreading work across drivers.

Constraints make it realistic

Real fleets face limits that turn the basic puzzle into a family of variants:

• Capacity (CVRP). Vehicles have a maximum load, so a van cannot take every parcel.
• Time windows (VRPTW). Each stop must be served within a specific interval, such as a customer who is home between 2 and 4 pm.
• Pickups and deliveries. An item must be collected at one place and dropped at another by the same vehicle, as in courier and ride services.

Each added rule shrinks the set of valid plans but makes the search harder. Because the number of possible orderings grows explosively with the number of stops, solvers rely on heuristics that find good answers quickly rather than proving the single best one.

How a solver works, step by step

The OR-Tools tutorial walks through a small example of 16 locations and 4 vehicles. The steps show the general shape of a routing model:

1. Prepare the data. A distance matrix (in meters in the example), the number of vehicles, and the depot index where every route starts and ends.
2. Create an index manager and a routing model. The manager maps between the solver’s internal indices and your location numbers.
3. Register a distance callback. This function returns the cost of travelling between two stops and is set as the cost of every vehicle’s trips.
4. Add a dimension. A distance dimension tracks cumulative distance per vehicle and enforces a maximum, set to 3,000 in the example.
5. Set the global span cost. A coefficient of 100 makes the longest route dominate the objective.
6. Choose search parameters and solve. The Python program uses the PATH_CHEAPEST_ARC first-solution strategy, which builds an initial plan by repeatedly adding the cheapest next leg.

The result: four routes of 1,712, 1,484, 1,552 and 1,552 meters, so the longest is 1,712 meters. The objective value of 177,500 equals 100 times the longest route plus the sum of all routes (6,300), an inference from the published numbers that checks out arithmetically.

From toy to street: distance matrices

Straight-line distance is rarely right. The same tutorial builds a matrix for 16 real addresses in Memphis, Tennessee using the Google Distance Matrix API, which limits each request to 100 origin-destination pairs, so the matrix is assembled in batches. Swapping distance for duration produces a travel-time matrix instead. In that example, one of four vehicles ended up unused, which is a legitimate result: if the limits allow it, fewer vehicles can cover all stops.

Where machine learning fits

Optimization solvers decide the plan; machine learning mostly improves the inputs. Models can predict travel times from traffic history, estimate how long a stop takes, or forecast demand so tomorrow’s stops are known earlier. Our overview of AI in logistics and supply chains covers those uses, and our piece on AI in aviation, rail and public transport shows similar scheduling problems in other modes. This division of labor, forecasting plus a classical solver, is our summary rather than a claim about any specific company’s system.

Limits to keep in mind

• Output quality depends on the matrix. A plan built on stale or wrong travel times is optimal for a world that does not exist.
• Solvers optimize what you tell them. Forgetting a rule, such as a driver’s legal break, yields an infeasible plan.
• Heuristic solutions are good, not guaranteed best, especially for large instances.
• Human knowledge, such as which customer needs a call first, is hard to encode.

What to watch next

• Time-window and pickup-delivery models, which the OR-Tools documentation covers on separate pages.
• Routing that accounts for electric vehicle charging, which adds new constraints.
• Tools that let planners tweak a solver’s output without rebuilding the model.
• Real-time re-optimization when orders change mid-route.

Key takeaways

• The vehicle routing problem asks for the best routes for several vehicles serving many stops.
• Minimizing the longest route is often a better goal than minimizing total distance.
• Capacity, time windows and pickups turn it into harder variants.
• Solvers use heuristics, and the quality of the distance or time matrix is critical.
• Machine learning typically improves the inputs, while a classical solver builds the routes.

Frequently asked questions

What is the vehicle routing problem?

It is the task of finding the best set of routes for multiple vehicles that start at a depot, visit a set of locations and return, under a chosen objective such as the shortest longest route.

Is route optimization artificial intelligence?

It belongs to operations research. Modern systems combine it with machine learning forecasts, but the route construction itself is usually done by optimization algorithms.

Can I try it myself?

Yes. OR-Tools is open source, and its documentation includes complete examples in Python, C++, Java and C#.