Ask an operations team how many vehicles they need and the honest answer is usually “this many, because that’s what we’ve always run.” Fleets are sized by experience — and experience over-provisions. It has to: a planner sizing by hand cannot see all the ways one bus, truck, or van could finish one job and still make the next, so they keep a cushion. That cushion is real money parked in a yard.

Reducing fleet size is not about driving faster or cutting trips. It is about chaining the work you already do onto fewer vehicles. That is an optimization problem, and it has a clean, exact answer.

The reframe: trips into vehicle “blocks”

Start with the trips you must run — fixed, non-negotiable, each with a start time and place and an end time and place. A single vehicle can cover trip A and then trip B only if it can finish A, travel empty from A’s end to B’s start, and still arrive before B departs. That empty repositioning has a name — deadhead — and it is the hidden cost that hand planning never accounts for.

Chain compatible trips together and you get a “block”: one vehicle’s day. The question “what is the fewest vehicles that cover every trip?” becomes “what is the fewest blocks?” — and that is where the math turns from guesswork into a guarantee.

Why the minimum fleet is an exact number, not an estimate

Order the trips by time and draw an arrow from every trip to each trip that could legally follow it. That graph has a special structure, and a classical result (Dilworth’s theorem, computed as a maximum matching) says the minimum number of vehicles equals the number of trips minus the size of the largest matching on it.

The minimum fleet is not a solver’s best guess after running for an hour. It is provably the fewest vehicles that cover the schedule — you can put a number on the slack and defend it.

That distinction matters when you are asking someone to cut a capital line. A heuristic says “we found a plan with fewer buses.” An exact method says “this is the minimum; there is no plan with fewer.” One is a suggestion; the other ends the argument. You can watch this run on real MARTA data in our transit demo — flip between the naive plan and the optimized one and the removed vehicles are the gap.

What before/after actually looks like

The naive plan opens a fresh vehicle whenever none is free — simple, and exactly how most operations grew. The optimized plan reuses vehicles across the day by paying small, deliberate deadhead moves to keep them productive. The visible outputs are three:

  • Fewer vehicles at the peak — the number that drives capital and depot cost.
  • A deadhead percentage — the non-revenue time you traded to consolidate, shown honestly rather than hidden.
  • A driver-duty and roster plan that fits the new blocks, because a smaller fleet is worthless if it needs illegal shifts to run.

The proof: a fifth of the fleet, in production

This is not theory for us. Renan designed and led a Python vehicle-routing engine for Brazil’s largest sugar producer — started at Nitryx and carried through the Progress Rail (Caterpillar) acquisition — across a network of more than 40,000 locations. The engine cut fleet needs by roughly 20% and saved about $60,000 per month in cloud cost, taken from concept to production-ready in 16 months with a team of six.

Twenty percent of a large fleet is a number that changes a budget. And it came not from a faster route here or there, but from the structural reframe: stop sizing by habit, size by the math.

When it pays — and the honest caveats

Minimum-fleet optimization pays most when trips are frequent, connectable, and expensive to serve — transit, distribution, field service, any operation where vehicles and their crews are the dominant cost. It pays less when the schedule is already tight or the trips genuinely cannot be chained.

And it is only as good as its inputs. Deadhead has to reflect real road times, not straight lines. Real constraints — vehicle types, depots, maintenance windows, driver rules — have to be in the model, or the “optimal” plan is optimal for a fantasy. That is exactly the line between a demo and a system, and it is where the engineering lives.

If your fleet is sized by experience, there is almost certainly slack in it. The only question is how much — and that is a question with an exact answer.