Dynamic route optimization when indexes aren't enough

Route recalculation is slow because it is genuinely dynamic: the system has to work out a good route again every time the set of stops changes. When a dispatcher adds or removes an order, the delivery addresses shift, and the ordering that was optimal a moment ago may no longer be. Nothing about the previous answer can be trusted to still hold.

Underneath, this is the vehicle routing problem — the task of finding efficient routes for one or more vehicles visiting a set of locations. It is computationally hard: the number of possible orderings grows explosively as stops are added, so finding a provably optimal route quickly becomes impractical at real volumes. Production systems lean on heuristics and metaheuristics that return a good route fast rather than the perfect one slowly, the approach taken in the Google OR-Tools vehicle routing documentation. The point for performance is that this is real computation rather than a database lookup, so it cannot be fixed by adding an index.

dynamic-route-recalculation-loop

Dynamic route optimization recalculates the route whenever orders change, which is why the slow path is computation rather than a database index.

Product availability is slow for a different reason: a single check quietly resolves a stack of conditions at once. In a multi-vendor delivery marketplace, deciding whether a given customer can buy a given product depends on several things evaluated together on the same request:

• the customer's coordinates fall inside the vendor's zone and within the supplier's delivery radius
• the item is in stock
• the vendor is active and approved to sell
• the product belongs to a module this customer is allowed to see
• any admin priority rules are applied

Two of those conditions are geospatial — a point-in-polygon test for the zone and a distance test for the radius — and geospatial predicates are heavier than a plain equality match. MySQL, the database behind the marketplace in question, provides spatial types and spatial indexes for exactly this work, as described in the MySQL spatial data types documentation, but a spatial index only helps when the query is written to use it and the candidate set is narrowed first. The logic of which supplier covers which address is a separate topic, covered in location-based order routing and where it breaks; here the concern is the performance of resolving it at scale.

Why indexes alone stop working

Adding an index is the right first move, and often the only one a query needs. It stops being enough when the work is spread across geospatial tests, several joins, and status filters at once, because no single index covers all of them and the planner still has to combine intermediate results. Indexes also cost something: each one has to be maintained on every insert, update, and delete, so piling on indexes to chase one slow read can quietly slow down writes everywhere else. The MySQL guidance on optimization and indexes makes the same point: the aim is a small set of indexes that helps many queries, not one index per column.

The fix on that marketplace combined three techniques, each matched to a different cause. Route recalculation was re-architected, product availability was cached, and the shared calculation behind both was simplified where steps repeated work. Route recalculation dropped from five-to-seven seconds to under one, and availability fell from three-to-five seconds to about one, with each gain coming from a different move rather than one universal optimization.

A quick way to map symptoms to the right technique:

Re-architect what is genuinely recomputed

Re-architecting is the answer when the work is real computation that changes every time, like the route order. The options are to use a faster heuristic, to shrink the problem the solver sees, or to update the route incrementally instead of re-solving it from scratch when a single order moves. The goal is a good route produced quickly, on the understanding that a good route now beats a perfect one that arrives too late for an operator who is reshuffling deliveries all day.

Cache what changes rarely

Caching is the answer when a result is expensive to compute and its inputs change far less often than they are read. Product availability fits: price, stock, zone, and vendor status change occasionally, while the availability check runs on every page view. A cache-aside approach suits this — the application reads from the cache, falls back to the database on a miss, stores the result for next time, and invalidates the entry when the underlying data changes. The cache-aside pattern in Microsoft's Azure Architecture Center covers the mechanics, and the AWS Well-Architected guidance on caching data-access patterns frames the decision from the data side: read-heavy values with a high read-to-write ratio that are expensive to produce are the strongest candidates, paired with a clear invalidation strategy such as a time-to-live.

Simplify the work itself

Simplification is the quiet third option, and often the cheapest. Before re-architecting or caching, it is worth checking whether the calculation repeats work it does not need to — recomputing the same intermediate value on every pass, joining a table it could skip, or checking a condition that an earlier filter already settled. Cutting redundant steps narrows the candidate set the heavier logic runs on, which makes both the algorithm and the cache cheaper to operate.

If indexes and query rewrites have already stopped moving your numbers, the slow path is probably structural, and that is a specific thing to diagnose. Our engineering team's performance work focuses on exactly this: finding where delivery and availability code spends its time and reworking the path at the root.

Caching helps only when the inputs are stable enough that a stored result stays correct between reads. Apply it to a value that changes on almost every request and the cache either serves stale data or gets invalidated so often that it never pays for itself. A delivery route is the clearest example: because it is re-solved whenever an order is added or removed, caching the route would mostly hand back an answer that is already wrong.

Stock is a subtler case — it changes often enough that an availability cache needs careful invalidation, or a short time-to-live, so the storefront does not show a product that just sold out. The judgment is matching the technique to how often the data actually changes, which is why the same marketplace cached availability and re-architected the route instead of treating them the same way.

None of this is real until it is measured under load that resembles production. A change that looks faster on a laptop with two hundred orders can still collapse at two thousand, because the costs that dominate at scale — geospatial work, joins, route size — barely register on small data. Measure response time before and after each change, at realistic volume, and track percentiles rather than averages: the p95 and p99 are what an operator feels when the system is busy.

Performance also regresses quietly as a marketplace grows, so the same measurement has to be repeated as volume climbs, and the broader patterns for building systems that scale as load grows apply directly here.

There is a point where adding indexes and rewriting queries stops moving the numbers, and that is usually the signal that the problem is structural. From there, the remaining gains live in the algorithm, the caching strategy, and the data model together — different work than query tuning, and a different skill set. A focused performance audit can often locate where the time goes in a day or two, while a rewrite of the route engine or the availability layer is a larger commitment, so knowing which one you need is worth settling before committing engineering time.

The numbers in this article come from the Kortreistved marketplace build, a Norwegian delivery platform, and the same diagnosis applies to most delivery and multi-vendor marketplaces once volume exposes the slow paths.

• Route recalculation is slow because it is a dynamic vehicle routing problem, re-solved whenever orders or addresses change, so the route order itself is what needs re-architecting.
• Product availability is slow because one check resolves many conditions at once — geospatial predicates, several joins, and status filters — which indexes alone cannot rescue.
• The fix is usually a combination: re-architect what is genuinely recomputed, cache what changes rarely, and simplify steps that repeat work.
• Caching helps when inputs change rarely and reads dominate; caching a route that changes on every order move only serves stale data.
• No optimization is real until measured under representative load, because code that is fast at today's volume can regress quietly as orders grow.

The slow paths in a delivery marketplace rarely share one cause, so they rarely share one fix. Route recalculation is computation that changes constantly and needs a better algorithm; availability is an expensive result with stable inputs and wants a cache; both benefit from cutting work that was never necessary. The skill is diagnosis — reading each slow path by what actually drives its cost — because once indexes and query rewrites are spent, the real gains come from the algorithm, the caching strategy, and the data model working together.

If your route recalculation or availability queries are creeping up and the usual fixes are spent, a short review will tell you whether the answer is tuning or a rebuild. Ask for a performance review.