Route Optimization: How It Works, With a Worked Example for a 40-Stop Day

Route optimization works by taking your stops, your vehicles and the rules each stop imposes, then searching for the sequence and assignment that costs the least. Every route optimizer solves a version of the vehicle routing problem: given a depot, a set of stops, a set of vehicles and a cost (distance, time or money), find routes that visit every stop once at the lowest total cost. With one vehicle and no rules, that is the travelling salesman problem, which has no efficient exact solution. With forty stops the number of possible orderings is far too large for any computer to check one by one. Real fleets add rules on top: time windows at each stop, vehicle capacity, driver shifts, a stop that needs a liftgate, a customer who won't take deliveries before ten. Each rule removes orderings but makes each remaining one harder to check.

The software doesn't try every ordering. It builds a good solution quickly and then improves it, so you get an answer in seconds instead of years.

Step one is the travel matrix: the drive time between every pair of stops, calculated on a road network with traffic for that time of day. Step two is construction, a fast heuristic such as inserting each stop wherever it adds the least time, or sweeping stops by angle from the depot. Step three is improvement. The optimizer keeps swapping stops between routes and reversing segments within a route, and it keeps any change that lowers cost without breaking a rule. Methods called local search, tabu search or simulated annealing stop it from getting stuck. It quits when improvement stalls or a time limit runs out. Nobody can prove the result optimal, but it usually beats a plan a dispatcher builds by hand, and it is repeatable.

Take a Montreal distributor with forty deliveries and three vans. Two stops have a 7-to-9 a.m. window, one stop on the South Shore needs a liftgate (only one van has it), and drivers work eight-hour shifts. The dispatcher builds a plan by hand around the same neighbourhoods as last week. It runs 412 km and finishes at 5:20 p.m., and one van does the South Shore at the end of the day after crossing the bridge twice. The optimizer sends the liftgate van to the South Shore stop first thing, puts both early-window stops on the same route, and balances the rest by drive time instead of neighbourhood. Its plan runs 348 km, finishes at 4:10 p.m. and misses no window. On one ordinary day, that saves 15% of the distance and about three hours of paid driver time across the three vans.

A plan is only as good as its inputs, and telematics supplies them. Geofence data gives you the actual service time at each stop, replacing the guessed fifteen minutes. Actual travel times on your roads at your hours replace the map's averages. During the day, each van's live position lets the optimizer re-sequence when a customer cancels or a truck gets stuck on the Champlain Bridge. Fleets that connect the optimizer to their GPS tracking platform get plans built on their own operation, and that is often the gap between an optimizer that saves little and one that saves a lot.

Here is the Montreal example as the dispatcher would compare the two plans, using the figures from that day.