Quantitative Methods

Network Flow and the Vehicle Routing Problem

One side of this line solves to proven optimality at enormous scale in seconds. The other side does not, and never will. Learn which of your logistics problems sits where — because the answer changes what you should buy.

  • Advanced
  • 12 min total
  • 14 chapters

What decision this helps you make: Whether to solve your freight or assignment problem exactly today with tools you already own, or accept a heuristic route plan with no bound — and where the real routing savings actually come from.

What this topic is

Network flow problems move quantities across a graph of nodes and arcs at minimum cost: plants to warehouses, warehouses to stores, people to jobs, cash across accounts. They have a structural property that makes their linear relaxations produce whole-number answers automatically, so they solve at enormous scale. Vehicle routing asks a different question — what sequence should one truck visit stops in — and that question is combinatorially explosive in a way flow problems are not.

Why it matters

These two problems live in the same department and are treated as one thing, which leads to two symmetrical mistakes. Companies pay for sophisticated software to solve flow problems a spreadsheet solver would prove optimal in ten seconds, and companies expect proven-optimal answers from routing problems where no such answer is available at any price. Knowing which side of the line you are on determines what to buy, what to promise, and where the savings actually are.

Who should learn it

Distribution and logistics managers, network planners, operations leaders evaluating routing software, and anyone whose cost base is dominated by moving things between fixed points.

What you will understand

  • Why transportation and assignment models give integer answers with no integer variables, and how to recognise one on sight
  • How to solve a small transportation problem by hand and read its duals as the marginal cost of serving one more unit
  • Why routing explodes combinatorially, and what a savings heuristic actually computes
  • Why most real routing gains come from changing constraints rather than changing algorithms

Prerequisites

Common misconception

"Routing software finds the optimal routes." It does not, and reputable vendors do not claim it. Vehicle routing with capacities and time windows is solved by heuristics that produce a good plan with no proof of how good — you get a number, not a bound. That is fine, and it is still worth a great deal of money. But it means two vendors' answers cannot be compared by looking at either one, and it means the honest question in a procurement is not "is it optimal" but "on our own historical week, against our own current plan, how much mileage does it remove and under what constraints".