The solve still has not finished and the first van is loaded

Before touching a single search parameter, put a timer around the matrix build and another around the search, and log both on every run. In most production routing systems the two are wildly unbalanced, and the balance is usually the opposite of what the team expects: the search finishes in seconds and the matrix takes minutes. Solver tuning does nothing to a matrix. Weeks disappear into first-solution strategies and metaheuristics while the actual bottleneck sits in a loop of outbound requests nobody has instrumented.

The two halves fail for unrelated reasons and are fixed by unrelated means, so the split is the whole diagnosis. Everything that follows assumes the plan is at least feasible — a run that never terminates because the day cannot be served is a different problem, taken apart separately in the routing, dispatch and optimisation cluster.

The half that grows with the square of your stop count

A travel-time matrix holds an entry for every ordered pair of nodes. Five hundred stops plus one depot is 501 nodes, which is 251,001 entries. That number is the whole story, because commercial matrix providers cap how many entries one request may return.

Two things fall straight out of that table. First, asking for the highest-fidelity traffic mode multiplies your request count by roughly six against the same provider, because the element cap drops from 625 to 100. Second, the difference between a synchronous matrix build and a cached one is not a percentage — it is the difference between hundreds of round trips inside your dispatch window and none. The tiering that makes this affordable rather than merely fast is covered in building a travel-time matrix you can afford to rebuild every morning.

A search with no deadline will not notice yours

The second half behaves completely differently. A routing search has two phases: a construction heuristic that produces a first feasible plan, and a local-search improvement phase that keeps rearranging it. The first is fast and bounded. The second is unbounded by design.

This is worth stating precisely because the defaults are surprising. OR-Tools exposes the search time limit as time_limit.seconds and documents its default as kint64max — the largest 64-bit value, which in practice means no limit at all. Pair that with a metaheuristic such as GUIDED_LOCAL_SEARCH or TABU_SEARCH, neither of which has a natural stopping point, and the search will keep improving a plan you needed twenty minutes ago. A separate lns_time_limit.seconds governs the large-neighbourhood phase and is documented with a default of 100 seconds. Neither default was chosen with your depot in mind.

A search without a deadline is not optimising your day. It is optimising a day that has already started without it.

• Set the wall-clock limit explicitly, always, in every environment. A limit that exists only in production is a limit nobody has tested.
• Choose the construction heuristic on instance shape rather than reputation. PATH_CHEAPEST_ARC is quick and crude; SAVINGS and PARALLEL_CHEAPEST_INSERTION often start much closer on clustered urban work, which matters enormously when the budget is 90 seconds rather than an hour.
• Watch what each constraint dimension costs. Every additional capacity dimension is another quantity the solver propagates along every candidate route, and a load that is heavy, bulky and in cages is three dimensions rather than one — the modelling trade-offs are in modelling weight, volume, pallets and cages together.
• Log the objective value at fixed intervals through the search. If the curve is flat after 45 seconds, a five-minute budget is buying nothing, and you have just recovered four minutes of your dispatch window.

Cutting the instance before cutting the search

The largest single lever is not a parameter. It is refusing to solve one enormous instance when the operation is not actually one problem. Because the matrix is quadratic, splitting an instance pays twice: four balanced territories of 125 stops each replace one matrix of roughly 251,000 elements with four of roughly 16,000, a reduction of about 75 per cent in total elements, and each search then runs over a fraction of the state space.

1. Split by depot first. Vehicles that start and end at different depots almost never belong in the same solve, and where they might, that is a network design question rather than a daily one.
2. Split by territory within a depot only where the boundary is operationally real — a river, a toll ring, a service agreement. An arbitrary boundary trades solve time for genuinely worse plans at the seam.
3. Split by day before splitting by geography. Moving flexible orders to an adjacent day reduces both halves at once and is usually available in operations with any standing schedule.
4. Measure the cost of the split honestly. Solve one representative day both ways when time allows, and record the difference in vehicles used and total drive time. If the seam costs less than a per cent, take the speed.

A budget, an incumbent, and a cut-off the depot can trust

The durable fix is not a faster solve. It is a system that cannot miss the deadline, because the deadline is the input rather than the outcome. Three properties make that true.

A fixed budget, derived by working backwards from when the first vehicle loads and subtracting the time the desk needs to review. A guaranteed incumbent: from the moment the construction heuristic returns, a complete, feasible, publishable plan exists in memory, and every later improvement replaces it atomically. And a published cut-off — a specific time, printed on the screen, at which whatever is current is released. A desk that knows the plan lands at 05:45 organises around 05:45. A desk that has learned the plan lands somewhere between 05:30 and 06:20 starts rebuilding yesterday's plan by hand at 05:35, and no improvement in average solve time will stop it.

Improvements found after the cut-off are not wasted; they belong to the next decision point rather than to this one. Feeding them into the midday re-plan, where the constraint is which work is already under way rather than which work exists, is the design in re-optimising at midday when half the stops are already done.

Three things a faster solve does not buy you

• A better plan. Under a tight budget the search stops in a local optimum, and local optima produce the doubling-back and self-crossing legs drivers argue about — worth separating from the sequences that only look wrong, which is the subject of the route crosses its own path twice.
• Correct inputs. The service and travel times feeding the model are derived from arrival and departure events, and if those events fire late, early or twice, a faster solve simply reaches the wrong answer sooner. The event-quality problem is diagnosed in arrival detected late or twice at a stop.
• A desk that uses the output. Speed removes one reason to override a plan and leaves the others intact, and a plan delivered on time that still ignores what the desk knows will still be rebuilt by hand.

Treat the whole thing as an operational service with a latency budget rather than as an algorithm with a quality target. Instrument matrix time, search time, objective-versus-time, and cut-off adherence, and put all four on the same screen the dispatch team already uses. That is ordinary internal tools and operations work, and it is what turns route planning in a logistics and mobility operation from a thing that usually finishes into a thing the depot can set its watch by.

• route optimisation
• performance
• travel-time matrix
• dispatch