---
title: "Route Optimization Above 500 Vehicles: The Computational Limits That Break SMB Tools"
id: "26159"
type: "post"
slug: "route-optimization-500-vehicles-computational-limits-2026"
published_at: "2026-08-31T17:00:00+00:00"
modified_at: "2026-09-01T12:00:32+00:00"
url: "https://locus.sh/blogs/route-optimization-500-vehicles-computational-limits-2026/"
markdown_url: "https://locus.sh/blogs/route-optimization-500-vehicles-computational-limits-2026.md"
excerpt: "Above roughly 500 vehicles across multiple depots, four computational effects dominate. The failure mode is not an error message, it is a plausible bad plan. What to test before you buy."
taxonomy_category:
  - "General"
---

#### [General](https://locus.sh/blogs/category/general/)

# Route Optimization Above 500 Vehicles: The Computational Limits That Break SMB Tools

[Anas T](/author/anas_locus/)

Aug 31, 2026

15 mins read

## Key Takeaways

- Vehicle routing is combinatorial, so problem difficulty grows faster than fleet size. Doubling the vehicles more than doubles the work of solving well.
- At scale the failure mode is not an error. A tool that cannot solve your problem properly returns a plausible plan that is quietly worse, with nothing on screen indicating the solve was truncated.
- Multi-depot is not several single-depot problems. Boundary orders can be served from more than one depot, and assigning them well requires solving the depots together.
- The real-time requirement is not raw solve speed. It is a bounded re-solve on a partial problem, which is an architectural property rather than a tuning exercise.
- Concurrency is the forgotten dimension. Above 500 vehicles, planning competes with hundreds of driver apps, telematics feeds, order ingestion, and customer tracking queries at the same time.
- Test with your full order file. A sample hides the combinatorial effect completely, which is why proofs of concept at scale so often mislead.

## Where the fleet-size thresholds come from

Route optimization tools are usually described by capability. They are better described by the size of problem they were architected to solve, because that determines which capabilities are real at your volume.

The operational tiers are reasonably well established. Under about 50 vehicles from a single depot, the problem is sequencing, and lightweight tools handle it well. Between 50 and 200 vehicles across one or two depots, the problem becomes constrained assignment and mid-market platforms cover it. Above 200 vehicles with multiple depots and a mixed fleet, the operation has enterprise characteristics: constraint depth, network-level trade-offs, and mid-day change that has to be absorbed rather than escalated.

This piece is about what happens further up. Above roughly 500 vehicles across five or more depots, four computational effects stop being background considerations and become the dominant factors in whether a plan is any good. They are rarely discussed in evaluations because none of them is visible in a demo, and all four are architectural rather than configurable.

**Also Read:** [Enterprise vs SMB Route Optimization: Why Enterprise Logistics Needs More Than Simple Route Planning](https://locus.sh/blogs/enterprise-vs-smb-route-optimization-comparison/)

## Effect one: the problem does not grow linearly

Vehicle routing belongs to a class of problems where the number of possible solutions grows combinatorially with the number of stops and vehicles. It is NP-hard, which in practical terms means no known method finds the guaranteed best answer for a large instance in reasonable time. Every production system uses heuristics and approximations, and that is entirely normal.

What matters commercially is how a given implementation behaves as the instance grows. A solver that produces an excellent plan for 50 vehicles in thirty seconds does not produce an equally good plan for 500 vehicles in five minutes. The search space is vastly larger, so within any fixed time budget the solver explores a much smaller fraction of it.

Here is the part that makes this an evaluation problem rather than a technical footnote. **The tool does not fail. It returns a plan.**

The plan looks correct. Routes are sequenced, constraints appear satisfied, the map looks sensible, and the summary reports a total distance. Nothing indicates that the search terminated early, or that the answer sits several percent worse than what a better-scaled approach would have found. There is no error message for “this plan is worse than it should be.”

So the loss at scale is silent and recurring. It shows up as cost per drop that is stubbornly higher than benchmarks suggest, on routes nobody can point to as wrong, and it gets attributed to geography, traffic, or driver performance rather than to the solve.

The practical test follows directly and appears later in this piece: run your real volume, then run double it, and watch what happens to solution quality rather than to solve time.

**Also Read:** [Top 12 Vehicle Routing Problem Software in 2026](https://locus.sh/blogs/vehicle-routing-problem-software/)

## Effect two: multi-depot is not several single-depot problems

An operation with six depots and a single-depot tool has an obvious workaround, which is to run the tool six times. Existing guidance in this category puts the consequence well: six locally sensible plans produce a globally worse network. It is worth understanding exactly why, because the mechanism determines how much it costs you.

The cause is boundary orders. Any order located between two depots can be served from either. Which depot should take it depends on what else each depot is serving that day, how full their vehicles are, and where their other stops sit. That is a joint decision, and it cannot be made correctly by either depot alone.

When depots are planned separately, the boundary is fixed in advance, usually by postcode or by historical convention. Every boundary order is then assigned by a rule rather than by the day’s actual geometry. On most days some of those assignments are wrong, and a wrong assignment does not cost one stop’s worth of inefficiency. It distorts the route it lands on, which displaces other stops, which propagates.

Two things make this worse as fleet size rises. More depots means more boundaries, and boundary zones are where urban density is usually highest, so boundary orders are a disproportionate share of volume rather than an edge case. Above 500 vehicles with five or more depots, this is typically one of the largest single sources of avoidable cost in the network, and it is invisible in per-depot reporting because each depot’s plan looks fine.

**Also Read:** [Enterprise Route Optimization Software: Why Locus](https://locus.sh/blogs/enterprise-route-optimization-software-vs-point-solutions-2026/)

## Effect three: re-solve latency has an operational budget

Most evaluations treat real-time re-optimization as a yes or no capability. At scale the relevant question is narrower: how long does a re-solve take, and what does it re-solve.

Consider the same computation at two moments. At 05:30, building the day’s plan, a twenty-minute solve is entirely acceptable. At 11:10, when a vehicle has broken down with thirty undelivered stops on board, a twenty-minute solve is useless, because the operation cannot hold thirty customers and four adjacent drivers in suspense while it runs, and because the world will have moved again by the time it finishes.

So the requirement is not raw speed. It is a bounded response on a partial problem: re-solve the affected subset, quickly, without disturbing the routes that do not need to change.

That last clause is the architectural test, and it is where scale bites. A system that can only re-solve the whole network will either take too long or return a plan in which every driver’s remaining sequence has changed, which is operationally worse than the original problem. A system designed for partial re-solve can bound both the time and the disruption.

The question worth asking a vendor is therefore two-part: what is the median re-solve time for a single-vehicle failure at our fleet size, and how many unaffected routes change as a result. The second number should be close to zero, and at SMB scale nobody ever thinks to ask it because whole-network re-solves are fast enough to hide the issue.

## Effect four: concurrency is the forgotten dimension

Solver performance gets discussed. System concurrency almost never does, and above 500 vehicles it is frequently what actually degrades first.

At that scale, the platform is simultaneously handling order ingestion at volume, position and status updates from hundreds of driver applications, telematics feeds, warehouse and inventory events, customer-facing tracking queries, and planning or re-planning activity. These are not sequential. They peak together, because the busiest delivery hour is also the hour with the most tracking lookups and the most status events.

A platform architected for one planner and forty drivers has never encountered that load profile. The failure mode is not a crash, which would at least be obvious. It is latency creep: the driver app takes eight seconds to confirm a delivery, the tracking page times out intermittently, a re-solve queues behind an ingestion batch. Each is individually minor and collectively it means the system is least responsive exactly when the operation most needs it.

This is worth specifying in procurement, because it is invisible in every demo. Demos run on small data with one user. Ask for concurrency figures at peak rather than averages, and ask what has been load-tested rather than what is theoretically supported.

**Also Read:** [Rider Management at Scale: Running Large Fleets](https://locus.sh/blogs/rider-management-large-fleet-logistics/)

## What changes at each tier

| Dimension | Under 50 vehicles | 50 to 200 | 200 to 500 | Above 500 |
| --- | --- | --- | --- | --- |
| Dominant problem | Stop sequencing | Constrained assignment | Network trade-offs | Computational scale |
| Depots | One | One or two | Several | Five or more, jointly planned |
| Constraint count in play | Few | Moderate | Many | Many, interacting |
| Typical solve approach | Fast heuristic, near-optimal | Heuristic with constraints | Constraint solver | Constraint solver with partial re-solve |
| First thing to break | Nothing | Constraint depth | Multi-depot boundaries | Solution quality, silently |
| Re-solve expectation | Whole network, fast | Whole network | Partial, bounded | Partial, bounded, low disruption |
| Concurrency load | Trivial | Low | Material | Peak-critical |
| Failure signature | Visible errors | Manual workarounds | Plans that need editing | Plausible plans that cost more |

The row worth studying is the second from last. As scale rises, failures become progressively less visible, which is why operations frequently outgrow a tool for a year or more before anyone identifies the tool as the problem.

## What to test in a proof of concept

Five tests, in order of how much they reveal. All five are things a vendor can do in a structured pilot and none is standard practice.

**Run your full order file, not a sample.** This is the single most important instruction in this piece. A ten percent sample removes the combinatorial effect entirely and will make almost any tool look adequate. Sampling is the reason proofs of concept at enterprise scale so often fail to predict production behavior.

**Then double it.** Ask for both the solve time and the objective value, at your real volume and at twice your real volume. If time grows and quality holds, the implementation scales. If solve time stays flat while total distance or cost rises disproportionately, you have found the truncation, and it will be silently costing you every day in production.

**Plan all depots together, then separately, and compare.** The difference in total cost is your boundary-order exposure, expressed as a number. Most operations have never seen it.

**Break a vehicle at 11:00.** Time the re-solve, and count how many unaffected routes changed. The second number is the one that determines whether the capability is usable during an operating day.

**Load-test at peak concurrency.** Not average. Simulate your busiest hour with the real number of driver apps and tracking queries alongside planning activity, and measure response times rather than throughput totals.

## What to measure in production

**Plan quality drift as volume grows.** Cost per drop indexed against volume, watched for the point where it stops improving with density. That inflection is often the solver rather than the network.

**Median and 95th percentile re-solve time,** split by trigger type.

**Unaffected-route change rate on re-solve.** How much of the network moves when it should not. This drives driver trust and it is rarely reported.

**Boundary-order cost.** The recurring delta between jointly planned and separately planned depots, if you plan separately today.

**Peak-hour latency on driver and customer surfaces.** Confirmation time in the driver app and tracking page response, measured at peak rather than averaged across the day.

**Also Read:** [Route Optimization Software: Dynamic Re-Routing 2026](https://locus.sh/blogs/route-optimization-software-dynamic-re-routing-2026/)

## How Locus handles enterprise scale

Locus, the world’s first Decision-Intelligent, Agentic TMS, is architected for the tier this piece describes rather than scaled up to it, and the distinction shows in three places that map onto the effects above.

**Simultaneous rather than sequential allocation.** The DispatchIQ engine processes the entire dispatch queue at once, evaluating every order against every available asset and carrier option against a model of more than 250 real-world constraints per computation, rather than assigning work in sequence and accepting whatever interaction effects result. Sequential assignment is adequate at 50 vehicles and is the source of most avoidable cost above 500, because the interactions between allocations are where the money is.

**Bounded re-optimization during the day.** Route changes are processed in under 30 seconds, which is what makes mid-day re-planning an operational capability rather than a batch job with a shorter name. Within the DiSCO framework, the Digital Supply Chain Officer, the Dispatch agent re-sequences while the Capacity agent holds roster state and the Orchestrator keeps them consistent, which is the mechanism for changing what needs to change without disturbing what does not.

**Production scale as evidence rather than specification.** More than 1.5 billion deliveries processed for 360-plus enterprise customers across 30-plus countries at 99.99% uptime, with over 1,000 carriers orchestrated. Uptime at that transaction volume is a concurrency claim as much as an availability one.

Locus is recognized by Gartner for seven consecutive years, featured in the 2026 Hype Cycle for Supply Chain Execution and Logistics Technologies, named a Leader in TMS by QKS Group (SPARK Matrix), and ranked #1 in Route Planning on G2’s 2026 Best Software Awards. In October 2025, Ingka Investments, the investment arm of Ingka Group, the world’s largest IKEA retailer, acquired Locus. Locus continues to operate independently. Further [analyst recognition](https://locus.sh/analyst-recognition/)
 is published in full.

Two deployments sit squarely in the above-500 tier.

A [Fortune 50 parcel and logistics provider](https://locus.sh/case-studies/fortune-50-parcel-centralized-dispatch/)
 centralized dispatch across 51 sites in a 120-country network, running more than a million freight shipments a year against a driver pool of 4,500 split between captive and third-party capacity, at 99.99% uptime. Two details matter for this piece. Fifty-one sites planned centrally rather than locally is the multi-depot argument at its largest practical scale, and the more than $14 million in unused contracted capacity it surfaced, including $565,000 at a single site, is precisely the kind of loss that separate per-site planning conceals. Weekly execution rate rose from 75% to 92%.

A [global FMCG operation](https://locus.sh/case-studies/global-fmcg-logistics-automation/)
 across ten countries coordinates more than 1,000 distributors and a rider pool exceeding 5,000, reaching over 1.8 million retail outlets, with more than $4 billion in orders optimized and over 12,000 trips saved per month at 3X ROI. Twelve thousand trips a month is the compounding value of allocation quality at scale, which is the effect a truncated solve gives away quietly.

Request a Locus [enterprise scale assessment](https://locus.sh/schedule-demo/)
 to run your full order file at current and doubled volume, measure your boundary-order cost across depots, and time a partial re-solve at your fleet size.

## Run the double-volume test before anything else

If you are evaluating route optimization for a fleet above 500 vehicles, one test is worth more than the rest of the process.

Give each shortlisted vendor your complete order file for your busiest recent day. Ask for the plan, the solve time, and the total planned cost or distance. Then give them the same file with volume doubled and ask for all three again.

A platform architected for your tier will take longer and hold quality. A platform scaled up from a smaller tier will return an answer in a similar time and a materially worse plan, and it will not tell you which one happened.

That is the whole difference between the two categories, and it is measurable in an afternoon.

## Frequently Asked Questions (FAQs)

At what fleet size does route optimization software stop scaling?

There is no single cliff, but the tiers are reasonably consistent. Under about 50 vehicles from one depot, lightweight tools perform well. Between 50 and 200, constraint depth becomes the limiting factor. Above 200 with multiple depots, network-level trade-offs dominate. Above roughly 500 vehicles across five or more depots, computational effects become the dominant factor in plan quality, and the limits are architectural rather than configurable.

Why does route optimization get harder faster than fleet size grows?

Because vehicle routing is combinatorial. The number of possible solutions grows far faster than the number of stops or vehicles, and the problem is NP-hard, meaning no known method guarantees the best answer for a large instance in usable time. Every production system approximates. What differs between implementations is how much solution quality is lost as the instance grows, within a fixed time budget.

How can you tell if a route optimizer is producing a worse plan at scale?

By comparing solution quality rather than solve time across volumes. Run your real order file, record solve time and total planned cost, then run double the volume and record both again. A tool that returns an answer in similar time on a much larger problem has explored proportionally less of the solution space, and the cost shows up as a worse plan rather than an error, because there is no error message for a suboptimal result.

Why can’t you run a multi-depot operation as separate single-depot plans?

Because orders located between depots can be served from either, and choosing correctly depends on what each depot is serving that day, how full its vehicles are, and where its other stops fall. Planning depots separately fixes that boundary by rule instead of by the day’s geometry, and a misassigned boundary order distorts the route it lands on rather than costing one stop’s inefficiency. With more depots, boundary volume grows, and it is invisible in per-depot reporting.

What matters more at scale, solve speed or re-solve behavior?

Re-solve behavior. A twenty-minute overnight solve is fine; the same computation is useless at 11:00 when a vehicle fails. The requirement is a bounded re-solve on the affected subset that leaves unaffected routes alone, which is an architectural property. Ask for median re-solve time at your fleet size and for the number of unaffected routes that change as a result, since the second number determines whether drivers can trust the plan.

What should an enterprise route optimization proof of concept include?

Your full order file rather than a sample, since sampling removes the combinatorial effect that causes scale failures. A doubled-volume run to expose silent quality degradation. A comparison of jointly planned against separately planned depots to price boundary-order exposure. A mid-day vehicle failure to time a partial re-solve and count disruption. And a concurrency load test at peak rather than average, covering driver apps and tracking queries alongside planning.

MEET THE AUTHOR

Anas T

Senior Content Writer - Product Marketing

Anas is a product marketer at Locus who enjoys turning complex logistics problems into simple, clear stories. Outside of work, he’s usually unwinding with a book or catching a good movie or series.

### Related Tags:

[https://locus.sh/blogs/agentic-tms-two-person-delivery-productivity-2026/](https://locus.sh/blogs/agentic-tms-two-person-delivery-productivity-2026/)
#### [General](https://locus.sh/blogs/category/general/)

## [How Agentic TMS Improves Two-Person Delivery Productivity: The Crew Day is Bounded by Job Mix](https://locus.sh/blogs/agentic-tms-two-person-delivery-productivity-2026/)

[Aseem Sinha](https://locus.sh/blogs/author/aseem_locus/)

Aug 31, 2026

In big and bulky, service time dominates and crews only ever run over. Why job mix bounds the crew day, and what agentic decisioning changes when a job overruns at 10:40.

[Read more](https://locus.sh/blogs/agentic-tms-two-person-delivery-productivity-2026/)

[https://locus.sh/blogs/new-driver-first-thirty-days-dispatch-calibration-2026/](https://locus.sh/blogs/new-driver-first-thirty-days-dispatch-calibration-2026/)
#### [General](https://locus.sh/blogs/category/general/)

## [What a Driver’s First Thirty Days Actually Cost, and Which Part is Dispatch’s Fault](https://locus.sh/blogs/new-driver-first-thirty-days-dispatch-calibration-2026/)

[Aseem Sinha](https://locus.sh/blogs/author/aseem_locus/)

Aug 31, 2026

Route size, service time, ETAs, and scorecards are all calibrated on tenured performance. A new driver gets a plan built for someone who does not exist yet, then gets measured against it.

[Read more](https://locus.sh/blogs/new-driver-first-thirty-days-dispatch-calibration-2026/)

## Route Optimization Above 500 Vehicles: The Computational Limits That Break SMB Tools

- Share
- [Print](javascript:window.print())
- [Download](#)
- [Schedule a Demo](https://locus.sh/schedule-demo/)

### Is your team spending more time on fixing logistics plan than running the operation?

- Agentic transportation management from order intake to freight settlement
- Route optimization built on 250+ real-world constraints
- AI-driven dispatch with automatic execution handling

20%Cost Reduction

66%Faster Planning Cycles

[Schedule a demo](/schedule-demo/)

Insights Worth Your Time

#### [General](https://locus.sh/blogs/category/general/)

## [Locus 2026 US Consumer Survey: Generative AI isn’t Just Changing How Consumers Shop, it’s Breaking the Demand Patterns US Retail Was Built On](https://locus.sh/blogs/generative-ai-shopping-effect-retail-fulfillment-operations-locus-q2-2026-consumer-survey/)

[Ishan Bhattacharya](https://locus.sh/blogs/author/ishan_locus/)

May 29, 2026

#### [General](https://locus.sh/blogs/category/general/)

## [Embedded vs Bolted-On AI: The Architecture Question European Logistics Buyers Are Asking](https://locus.sh/blogs/embedded-vs-bolted-on-ai-european-logistics-platform-architecture-business-benefits/)

[Aseem Sinha](https://locus.sh/blogs/author/aseem_locus/)

May 21, 2026

#### [General](https://locus.sh/blogs/category/general/)

## [Hybrid Fleet Management: How Owned, 3PL, Gig, ICE, and EV Capacity Actually Operate at Most Enterprises](https://locus.sh/blogs/three-workforce-fleet-reality-owned-3pl-gig-drivers/)

[Aseem Sinha](https://locus.sh/blogs/author/aseem_locus/)

May 7, 2026

#### [General](https://locus.sh/blogs/category/general/)

## [US Returns Hit $850 Billion in 2025: Why US Retailers Are Restructuring Reverse Logistics in 2026](https://locus.sh/blogs/850-billion-us-returns-ai-routing-reverse-logistics-2026/)

[Ishan Bhattacharya](https://locus.sh/blogs/author/ishan_locus/)

May 7, 2026