15 min readJust now

–

The Hidden Mathematics Behind Every Uber Ride: A Journey Into Network Flow Optimization

How a 70-year-old mathematical theory powers modern smart cities, saves lives in emergency rooms, and makes your ride-sharing app possible

Consider a scenario: It’s 3 AM on a Tuesday in a particular city. Five emergency calls hit the dispatch center simultaneously. A heart attack in the financial district. A car accident on the North Highway. A stroke patient near the hospital. A house fire in the suburbs. And someone struggling to breathe at the airport.

Five ambulances scattered across the city. Five lives hanging in the balance. Every second counts.

In the old days, dispatchers would make split second decisions based on gut feeling and simple proximity rules, send the closest available ambulance to each emergency. Seems logical, right? But here’s the problem: the “closest” ambulance to the heart attack victim might also be the only ambulance that can reach the stroke patient in time. Send it to the wrong place, and you’ve just made a choice that could cost a life.

Today, that choice doesn’t rest on human intuition alone. In less than 100 milliseconds faster than you can blink , an algorithm solves a mathematical problem that considers every possible combination of ambulances and emergencies, evaluates thousands of scenarios, and produces the globally optimal assignment. Not just good. Optimal. And it does this using a framework that’s simultaneously ancient and cutting-edge: Minimum Cost Network Flow.

This isn’t just about ambulances. Every Uber ride you take, every package Amazon delivers, every bit of data streaming to your phone — all of it flows through networks optimized by the same mathematical principles. And the really remarkable part? The math behind it is actually beautiful, surprisingly intuitive, and once you understand it, you’ll start seeing networks everywhere.

Let me show you how it works.

The Three Essential Components of Any Network Flow Problem

Now that we’ve seen what a network is using the coffee business example, let’s break a network down into its three building blocks. Every network flow problem whether it is coffee, ambulances, or Uber rides always has nodes, arcs, and flow. Nothing more, nothing less.

Press enter or click to view image in full size

Figure 1 by Author: Graph Network for the case study

1. Nodes: Sources, Sinks, and Middlemen

Nodes are the places where things either start, end, or pass through. In network flow theory, every node (i) has a balance value, written as b_i. This single number defines the role of the node.

Supply Nodes → Where Flow Originates

If b_i > 0, the node is a supply node.

Look at the diagram: The green node (Node 1) has b = +25. This is a supply node. Node 1 is the Portland coffee roastery. It produces 25 bags of coffee per week and must ship them out into the network.

Supply nodes are sources of coffee.

Demand Nodes → Where Flow Ends

If b_i < 0, the node is a demand node.

Look at the diagram: The red nodes (Nodes 4 and 5) have b = -10 and b = -15 respectively. These are demand nodes. Node 4 is Vancouver café (needs 10 bags) and Node 5 is Seattle café (needs 15 bags). Both consume coffee and must receive shipments.

Demand nodes are destinations for coffee.

Transshipment Nodes → Pure Middlemen

If b_i = 0, the node is a transshipment node.

Look at the diagram: The blue nodes (Nodes 2 and 3) have b = 0. These are transshipment nodes. Node 2 is the Seattle distribution hub and Node 3 is the Tacoma distribution hub. They don’t produce or consume coffee themselves , they just receive shipments from Portland and forward them to Vancouver and Seattle cafés.

Whatever arrives at Node 2 must leave Node 2. Whatever arrives at Node 3 must leave Node 3. No bags are created or lost.

Press enter or click to view image in full size

Table 1 by Author: Coffee Network Roles

2. Arcs: The Routes and Their Limits

If nodes are places, arcs are the shipping routes between them. Each arc (i,j) represents a directed route from node (i) to node (j).

Look at the diagram: The 6 arrows are the shipping routes:

• Portland → Seattle hub (1→2)
• Portland → Tacoma hub (1→3)
• Seattle hub → Vancouver café (2→4)
• Seattle hub → Seattle café (2→5)
• Tacoma hub → Vancouver café (3→4)
• Tacoma hub → Seattle café (3→5)

Every arc has two critical attributes:

Cost : What It Costs to Ship on This Route

Each arc has a unit cost c_ij (dollars per bag).

Look at the diagram: Every route is labeled with c = some number:

• Portland → Seattle hub: c = 4 (costs $4 per bag)
• Portland → Tacoma hub: c = 3 (costs $3 per bag)
• Seattle hub → Vancouver cafe: c = 2
• Seattle hub → Seattle cafe: c = 3
• Tacoma hub → Vancouver café: c = 2
• Tacoma hub → Seattle cafe: c = 1 (cheapest route)

The optimization algorithm prefers cheaper routes. Route 3→5 costs only $1 per bag, so it is attractive for shipping to Seattle café.

Capacity: How Many Bags Can Ship on This Route

Each arc has a maximum capacity u_ij (bags per week).

Look at the diagram: Every route shows u = some number:

• Portland → Seattle hub: u = 15 (can ship at most 15 bags)
• Portland → Tacoma hub: u = 20 (can ship at most 20 bags)
• Seattle hub → Vancouver cafe: u = 10
• Seattle hub → Seattle cafe: u = 8
• Tacoma hub → Vancouver cafe: u = 12
• Tacoma hub → Seattle cafe: u = 10

Even though the cheap route (3→5) costs only $1 per bag, it can only carry 10 bags. If we need to ship more, we must use other routes.

Direction : Routes Go One Way

Arcs are directional. Portland ships to the hubs, not the other way around.

Look at the diagram: The arrows show:

• 1→2 exists (Portland can ship to Seattle hub)
• 2→1 does not exist (Seattle hub cannot ship back to Portland)

Complete Picture

Press enter or click to view image in full size

Table 2 by Author

The question: What is the cheapest way to ship all 25 bags from Portland, through the hubs, to the two cafes, while respecting all capacity limits?

That is the Minimum Cost Network Flow problem!

3. Flow: The Decision Variables

Finally, we come to flow , the actual decisions we make.

For every arc (i,j), we define a variable:

X_ij = amount of coffee sent from node i to node j

In plain English, looking at this:

Press enter or click to view image in full size

Equation 1 By Author

These 6 number sare the decisions we need to make.

But they are not chosen independently. They must obey one fundamental rule.

Flow Conservation: The Glue Holding Everything Together

At every node, this constraint must hold:

Flow out − Flow in = Balance (b_i)

This ensures:

• Supply nodes (Portland) send out exactly what they produce
• Demand nodes (Vancouver, Seattle) receive exactly what they need
• Transshipment nodes (hubs) stay perfectly balanced

Press enter or click to view image in full size

Table 3 by AuthorEquation 2 by Author

The table shows how the same flow-balance principle is applied at each node in the network. Each row corresponds to one node and enforces conservation of flow locally at that location. At the Portland node, which is a supply node, the total flow leaving the node must equal its supply of 25 bags, so all outgoing shipments add up to 25. At the Seattle and Tacoma hubs, which are transshipment nodes, there is no supply or demand; therefore, whatever flow enters these hubs must leave them, resulting in outgoing flow being exactly equal to incoming flow. At the Vancouver and Seattle cafés, which are demand nodes, there is no outgoing flow, and the total incoming flow must exactly match their respective demands of 10 and 15 bags. Although the equations in the table are written in simplified form, each row is a direct rearrangement of the same underlying rule: flow out minus flow in equals the node’s supply or demand. Together, these rows ensure that coffee is neither created nor lost anywhere in the network.

The Optimization Problem

Up to now, we were just setting up the “laws of physics” of our coffee network:

• Flow balance: coffee cannot magically appear or vanish at a node
• Capacities: some routes can only carry so much
• Non-negativity: you can’t ship negative coffee (sadly)

Now we finally ask the real business question:

What should we ship on each route so the total shipping cost is as small as possible?

1. Decision variables (flows)

For each route (i,j), let:

Equation 3 By Author: Decision Variable

In our network, the decisions are:

Equation 4 By Author: Decision Variables

2. Objective: Minimize total shipping cost

Each route has a per-bag shipping cost. So the total cost is:

Press enter or click to view image in full size

Equation 5 Objective Function: By Author

3. Constraints

(A) Flow conservation (the 5 node balance equations) These are exactly the ones from the table 2 above (one per node).

(B) Capacity constraints (each road has a limit)

Equation 6 by Author

C) Non-negativity

Equation 7 by Author

The Magic: Total Unimodularity (Why This Problem Is Weirdly “Easy”)

Here is the surprising part.

Even though “bags of coffee” are obviously integer (you don’t ship 3.7 bags unless your business model includes a vacuum cleaner), we don’t actually need integer programming.

Why?

Because the constraint matrix behind minimum-cost network flow has a special property called: Total Unimodularity (TU)

What TU means in plain English

If:

• all the supplies/demands b_i are integers (like 25, 10, 15), and
• all capacities are integers,

then:

Solving the problem as a normal linear program (allowing fractional flows) automatically gives an integer optimal solution anyway.

So you can pretend fractional coffee is allowed… and the solver still returns whole bags.

That is not a “nice coincidence.” It’s a mathematical guarantee.

1. Why this matters: avoiding Branch-and-Bound pain

In a general integer programming (IP) problem, decision variables are required to take integer values. Because solving such problems directly is hard, most solvers use a technique called branch and bound.

The process works as follows:

1. Relax the integrality constraints and solve the problem as a linear program (LP). This step is fast and gives a lower bound on the optimal objective value.
2. **Check integrality of the solution: **If all variables are integers, the solution is optimal and we are done
3. **Branch on a fractional variable: **If a variable takes a fractional value (for example, x=3.7), the solver creates two subproblems: (x≤3 and x≥4)

4. **Solve both subproblems: **repeat, keep splitting…

This branching can explode:

• With 10 fractional decisions, worst case is 2^10=1024 branches
• With 100… 2¹⁰⁰ (this is where your laptop quietly resigns)

2. The advantage with network flow

Network flow problems sidestep all of this:

• No branch-and-bound needed
• Solve as an LP
• Still get integer flows
• A network with millions of variables can often be solved in seconds or minutes

So for our Portland coffee network, the workflow becomes:

Solve one linear program → get the optimal shipping plan → it’s already whole bags → done.

No rounding tricks. No search tree. No drama.

Just coffee moving through a network at minimum cost , like it was always meant to be.

Extension

Now that we understand the mathematical backbone of network flow optimization, it’s time to zoom out and recognize something important: not every real-world problem looks like our Portland coffee roastery.

Sometimes you don’t have transshipment hubs. Sometimes there are no capacity constraints. Sometimes the problem has such a special structure that we can solve it even faster than the generic MCNF algorithm.

Get Saif Ali Kheraj’s stories in your inbox

Join Medium for free to get updates from this writer.

These aren’t different problems. They’re special cases — variations on the same mathematical theme. And because they appear so frequently in practice, they’ve earned their own names, their own study, and their own optimized algorithms.

Five problems dominate this landscape:

1. Transportation Problem : Direct shipments from factories to markets
2. Assignment Problem : Matching workers to jobs, or tasks to machines
3. **Transshipment Problem: **The generalized version with intermediate hubs
4. **Maximum Flow Problem: **Push as much as possible through a network
5. **Shortest Path Problem: **Find the cheapest route from point A to point B

Let’s examine each one, see how it fits into the MCNF framework, and understand why they matter.

Understanding the Hierarchy: From Simple to Complex

We’ll now explore three major special cases of MCNF. Start with the simplest scenario and gradually add complexity. Each builds on the previous one, showing how MCNF is the master framework that contains them all.

1. The Transportation Problem: Direct Routes Only

The Simplest Network

Imagine the Portland coffee roastery decides to ship directly to cafés without using distribution hubs.

• Portland roastery produces 25 bags per week
• Vancouver café needs 10 bags per week
• Seattle café needs 15 bags per week
• Direct shipping routes: Portland → Vancouver and Portland → Seattle
• Each route has a different cost per bag

The question: How should we split the 25 bags between the two cafés to minimize shipping cost?

This is the transportation problem.

Real-World Scenarios

You see transportation problems when:

• A bakery supplies nearby shops directly (no warehouses in between)
• A factory ships directly from one location to multiple retailers
• A warehouse supplies several nearby stores without distribution hubs
• A coffee roastery ships directly to end-customer cafés

What Makes It Special?

Compared to the full MCNF framework, transportation is simpler because:

1. **No intermediate nodes: **Only supply nodes (Portland) and demand nodes (cafés). No hubs, no middle stops.
2. No capacity limits : You can ship as much as you want on each route (capacities are unlimited or so large they don’t matter).

That’s it. Everything else (costs, flow conservation, minimization) works the same as MCNF.

Why it is Called “Transportation”?

The problem is called transportation because it models the classic logistics scenario: goods move directly from sources (production) to destinations (consumption). No intermediate consolidation or storage points.

2. The Assignment Problem: One-to-One Matching

A Different Perspective

Now let’s reinterpret our Portland coffee network differently.

Instead of shipping bags of coffee, imagine the roastery manager needs to assign work to resources. There are 6 shipping routes that need to be operated:

1. Portland → Seattle hub
2. Portland → Tacoma hub
3. Seattle hub → Vancouver café
4. Seattle hub → Seattle café
5. Tacoma hub → Vancouver café
6. Tacoma hub → Seattle café

And there are 6 delivery trucks available: Truck A, B, C, D, E, F

Each truck operates exactly one route, and each route needs exactly one truck. The cost varies based on which truck handles which route.

The question: Assign each route to exactly one truck (and each truck to exactly one route) to minimize total operating cost.

This is the assignment problem.

What Makes Assignment Different?

The key constraint: one to one matching. A truck cannot handle two routes, and a route cannot use two trucks.

Compare transportation vs. assignment:

Press enter or click to view image in full size

Table 4 by Author: Comparison

Real-World Examples

• Worker to job matching: Assign 10 workers to 10 different tasks (each person does one job)
• Doctor scheduling: Assign doctors to patient cases (each doctor handles one case)
• Project staffing: Assign team members to projects (each person works on one project)

Why it is still MCNF?

The assignment problem is just a very constrained transportation problem:

**In transportation: **Portland can send any amount to each café (5 bags, 10 bags, 8 bags, etc.)

**In assignment: **Each route gets exactly 1 unit (one truck), Each truck handles exactly 1 unit (one route), Solutions naturally come out as 0–1 (either assign or don’t assign)

It is transportation where every supply is 1 and every demand is 1.

The Power of Total Unimodularity

Because of total unimodularity (from our earlier discussion), a standard LP solver automatically returns 0–1 assignments. No branch-and-bound needed. The mathematics naturally prevents fractional assignments.

3. The Transshipment Problem: Adding Intermediate Nodes

Back to the Full Network

Now we return to the complete Portland coffee network with all its real-world complexity.

This time, we’re not simplifying, we are modeling reality:

• Portland roastery produces 25 bags (supply)
• Seattle hub receives and forwards coffee (no consumption)
• Tacoma hub receives and forwards coffee (no consumption)
• Vancouver café consumes 10 bags (demand)
• Seattle café consumes 15 bags (demand)

The hubs are intermediate nodes that neither produce nor consume ,they exist purely to route flow.

This is the transshipment problem.

Why Intermediate Nodes Matter

Almost every real logistics network has intermediate nodes:

• Coffee supply: Roastery → Regional hubs → Local cafés
• Telecommunications: Data center → Regional router → Local switch → User
• Package delivery: Sorting facility → Regional hub → Local hub → Delivery point

The intermediate nodes are where consolidation, sorting, transformation, or temporary storage happens.

What Gets Added?

Compared to transportation, transshipment adds:

Intermediate nodes with zero balance : Nodes where flow in equals flow out. Nothing is created or lost at these nodes. That’s the only addition. But it’s powerful because it lets you model the actual structure of real networks instead of forcing everything into a direct source-to-destination model.

Why This Matters?

Without transshipment nodes, you would have to model:

• Portland → Vancouver café directly
• Portland → Seattle café directly
• Ignoring that flow actually goes through hubs

With transshipment nodes, you model the actual routes:

• Portland → Seattle hub → Vancouver and Seattle cafés
• Portland → Tacoma hub → Vancouver and Seattle cafés

The transshipment model is more realistic and often more efficient computationally because it captures how the network actually works.

How Each Fits In?

Press enter or click to view image in full size

Table 5 by Author

4. The Shortest Path Problem: Finding the Quickest Route

The Real-World Question

Imagine you’re at Portland and need to reach Seattle. There are many possible routes through the network:

• Portland → Seattle hub → Seattle café (costs: $4 + $3 = $7)
• Portland → Tacoma hub → Seattle café (costs: $3 + $1 = $4)
• Portland → Seattle hub → Vancouver café → ??? (this doesn’t lead to Seattle)

The question: What is the cheapest (or fastest) route from Portland to Seattle?

This is the shortest path problem.

What Makes It Different?

In all previous problems, we asked: “What’s the optimal way to distribute multiple units through a network?”

In shortest path, we ask: “What’s the optimal single path from point A to point B?”

Press enter or click to view image in full size

Table 6 by Author

The weights on arcs are distances, times, or costs. We want to minimize the total distance traveled.

Real-World Examples

• GPS navigation: Find shortest driving route from home to office
• Airline routing: Find cheapest flight path (with connections) from city A to city B
• Telecommunications: Find lowest-latency path for data packets from source to destination

How it is Still MCNF?

Shortest path is just MCNF with exactly one unit of flow.

The trick:

• Create a supply node s with supply = +1 (one unit to send)
• Create a demand node t with demand = -1 (one unit needed)
• All other nodes are transshipment nodes with balance = 0
• The weights on arcs become costs in MCNF
• Minimize total cost (which is the same as minimizing path distance)

When you solve this MCNF with one unit of flow, the optimal solution naturally routes that one unit along the shortest path.

5. The Maximum Flow Problem: Pushing as Much as Possible

A Different Kind of Question

Now imagine a different scenario. The Portland roastery wants to understand its network capacity.

Given the current infrastructure:

• Portland → Seattle hub: can handle up to 15 bags per hour
• Portland → Tacoma hub: can handle up to 20 bags per hour
• Seattle hub → Vancouver café: can handle up to 10 bags per hour
• Seattle hub → Seattle café: can handle up to 8 bags per hour
• Tacoma hub → Vancouver café: can handle up to 12 bags per hour
• Tacoma hub → Seattle café: can handle up to 10 bags per hour

The question: What is the maximum number of bags per hour we can deliver from Portland roastery to both cafés combined?

This is the maximum flow problem.

What Makes It Different?

In all previous problems, we minimize total cost. We try to be as cheap as possible. In maximum flow, we maximize the amount of flow. We try to push as much as possible through the network.

Summary and Conclusion

Press enter or click to view image in full size

Table 7 by Author: Summary

We discussed the Minimum Cost Network Flow (MCNF) framework and its core components: nodes, arcs, and flows. We showed how assignment, transportation, transshipment, and max-flow problems arise by gradually changing constraints and objectives. Each model adds flexibility, such as allowing quantities, intermediate hubs, or capacity limits. We explained node roles through supply, demand, and zero-balance behavior. We also introduced virtual (dummy) nodes to handle imbalance without affecting real decisions. Overall, MCNF acts as a unified model from which many classical network problems are derived.

References:

[1] https://en.wikipedia.org/wiki/Minimum-cost_flow_problem

[2] https://cp-algorithms.com/graph/min_cost_flow.html

[3] https://developers.google.com/optimization/flow/mincostflow

[4] https://jeffe.cs.illinois.edu/teaching/algorithms/notes/G-mincostflow.pdf