Chapter 3 of 4

Optimization Models for Network and Transportation Decisions

3 sections · ~9 min read · 3 practice questions · part of SC Analytics & Technology

Learning objectives

  • Formulate a balanced transportation problem as a minimum-cost flow linear program.
  • Verify that an allocation is optimal using reduced costs, and recognise alternative optima.
  • Choose between exact optimization, heuristics, and simulation for a given class of decision.

Formulating the Transportation Problem

The transportation problem allocates a known supply at each source to a known demand at each destination at minimum total cost. The formulation is a linear program: choose the flow on each lane to minimise the sum over all lanes of unit cost multiplied by flow, subject to each source shipping exactly its supply, each destination receiving exactly its demand, and every flow being non-negative. Two structural points make this model unusually well behaved. First, it is balanced only when total supply equals total demand; when they differ, add a dummy source or destination with zero costs to absorb the difference, and read the dummy's flows as unmet demand or idle capacity. Second, when supplies and demands are integers, the optimal solution comes out in integers automatically without any need for integer programming, which is why these problems solve so quickly at scale. The same skeleton extends a long way. Add capacity limits on individual lanes and it handles carrier commitments. Add an intermediate layer of nodes with balance constraints and it becomes a transshipment model that can site distribution centres. Add binary variables for opening a facility and it becomes the facility location problem, which is genuinely harder and loses the integrality property. Knowing where that boundary sits is what tells you whether a network question will solve in seconds or overnight.

Verifying Optimality and Reading Shadow Prices

Any solver will return an allocation; the analyst's job is to know whether to believe it and what else it is telling you. Reduced costs give both. Assign a dual value to each source and each destination such that, on every lane actually used, the two dual values sum exactly to that lane's unit cost. One dual can be fixed arbitrarily at zero because only differences matter. The reduced cost of an unused lane is then its unit cost minus the sum of its two duals. If every unused lane has a non-negative reduced cost, the solution is optimal, and this check is fast enough to do by hand on a small problem. A reduced cost of exactly zero on an unused lane is worth noticing: it means an alternative optimal solution exists with the same total cost but a different flow pattern, and you are free to choose between them on criteria the model never captured, such as carrier relationships or risk concentration. The destination duals are the more useful output in practice. Each one is the marginal cost of serving one additional unit of demand at that destination, which is precisely the number needed to price a new customer or to decide where a promotion is cheapest to run. The source duals rank capacity: the difference between two source duals is what an extra unit of capacity is worth at one plant rather than another, which turns an allocation model into a capital allocation argument.

When to Optimize, When to Heuristic, When to Simulate

Three modelling approaches cover most supply chain questions and they answer genuinely different ones. Exact optimization suits problems with a clean objective, hard constraints, and deterministic inputs, and its output is a decision plus the dual information described above. Its weakness is that it takes its inputs literally: an optimizer handed a cost matrix built on average transit times will confidently produce a plan that is optimal for a world where nothing varies. Heuristics suit problems that are too large or too combinatorial to solve exactly within the time available, which in practice means most vehicle routing. A good heuristic gives up a small and usually unmeasurable amount of optimality for the ability to re-run whenever the order book changes, and that responsiveness is normally worth more than the gap. Simulation suits questions about variability rather than about the best decision. It does not tell you what to do; it tells you what happens to a policy you have already chosen when demand, lead times, and yields behave randomly. The distinction that matters is this: optimization answers what should we do, and simulation answers what could go wrong with it. Serious network studies use both in sequence, optimizing to generate two or three candidate designs and then simulating each under demand and disruption scenarios, because a design that wins on expected cost and fails under a plausible scenario is not the design you want.

Worked example

Problem

Two plants (P1, P2) ship to three warehouses (W1, W2, W3). P1 has supply 800 units; P2 has supply 1,200 units. W1 demand 500; W2 demand 700; W3 demand 800. Unit costs: P1 to W1 $5, P1 to W2 $7, P1 to W3 $9; P2 to W1 $8, P2 to W2 $4, P2 to W3 $6. Find a minimum-cost allocation, prove it is optimal using reduced costs, and interpret the duals.

Step by step

  1. Check balance: supply = 800 + 1,200 = 2,000; demand = 500 + 700 + 800 = 2,000. Balanced, so no dummy node is needed.
  2. Construct a starting allocation greedily by cheapest lane into each destination. W1 is cheapest from P1 at $5, so ship 500 from P1, leaving P1 with 300. W2 is cheapest from P2 at $4, so ship 700 from P2, leaving P2 with 500. W3 needs 800 and only 300 remain at P1 and 500 at P2, so ship both: 300 on P1 to W3 at $9 and 500 on P2 to W3 at $6.
  3. Total cost = (500 x $5) + (300 x $9) + (700 x $4) + (500 x $6) = $2,500 + $2,700 + $2,800 + $3,000 = $11,000.
  4. Feasibility check: P1 ships 500 + 300 = 800 = supply. P2 ships 700 + 500 = 1,200 = supply. W1 gets 500, W2 gets 700, W3 gets 300 + 500 = 800. All constraints hold exactly.
  5. Now verify optimality. Set the dual on P1 to zero. Used lanes must satisfy u(source) + v(destination) = unit cost. From P1 to W1: 0 + v1 = 5, so v1 = 5. From P1 to W3: 0 + v3 = 9, so v3 = 9. From P2 to W3: u2 + 9 = 6, so u2 = -3. From P2 to W2: -3 + v2 = 4, so v2 = 7.
  6. Reduced cost of each unused lane = unit cost - (u + v). P1 to W2: 7 - (0 + 7) = 0. P2 to W1: 8 - (-3 + 5) = 8 - 2 = 6.
  7. Both reduced costs are non-negative, so the allocation is optimal and $11,000 is the true minimum.
  8. The zero reduced cost on P1 to W2 signals an alternative optimum. Shifting flow onto that lane changes the pattern without changing total cost: for instance P1 to W1 500, P1 to W2 300, P2 to W2 400, P2 to W3 800 also costs $2,500 + $2,100 + $1,600 + $4,800 = $11,000.
  9. Interpret the duals. The destination duals v1 = 5, v2 = 7, v3 = 9 are the marginal cost of one more unit of demand at each warehouse, so incremental volume is cheapest to place at W1 and nearly twice as expensive at W3. The source duals differ by 3, meaning an extra unit of capacity at P2 is worth $3 more than the same unit at P1, which is the number to bring to a capacity investment discussion.

Answer. Optimal allocation: P1 to W1 = 500, P1 to W3 = 300, P2 to W2 = 700, P2 to W3 = 500, at a total cost of $11,000. Optimality is confirmed because both unused lanes have non-negative reduced costs (0 and 6). The zero on P1 to W2 means at least one alternative optimum exists at the same cost, so the tie can be broken on criteria outside the model, such as avoiding single-sourcing W2 from P2. Marginal cost of additional demand is $5 at W1, $7 at W2, and $9 at W3, and capacity at P2 is worth $3 per unit more than at P1. Limitation: this is a single-period, deterministic model with no lane capacity limits and no inventory. Before committing to a physical flow plan, re-run it across several demand periods and stress the lanes that the solution loads to their limit.

Practice

Work each question before opening the solution.

  1. Total supply is 2,000 but demand rises to 2,300. Describe how to keep the model solvable, and what the solution then tells you.

    Show solution for question 1

    Add a dummy source with a supply of 300 and a cost of zero on every lane out of it, which restores balance. The solver will assign that dummy supply to whichever destinations are most expensive to serve from real capacity, and those assignments are the model's recommendation about where to accept shortfall. Read the result as a shortage allocation plan rather than a shipping plan. If shortfall is not equally acceptable everywhere, replace the zero costs with per-unit shortage penalties reflecting the real commercial cost of missing each destination, since a zero cost tells the model that going short is free.

  2. An unused lane has a reduced cost of 6. What would have to change for that lane to enter an optimal solution, and what does the number mean commercially?

    Show solution for question 2

    The reduced cost of 6 on P2 to W1 says that forcing one unit onto that lane would raise total cost by $6, because it costs $8 while the dual values imply the network can already serve that unit for $2. The lane enters an optimal solution only if its own cost falls by more than $6, to below $2, or if the surrounding duals shift because supplies, demands, or other lane costs change. Commercially the number is a negotiating threshold: a carrier quoting that lane would need to come down more than $6 per unit before the lane is worth using at all, which is usually enough to end the conversation quickly.

  3. A team optimizes a network on average transit times and the plan underperforms in practice. Explain the failure and what modelling approach addresses it.

    Show solution for question 3

    The optimizer treated average transit times as certainties and drove every buffer out of the plan, because in a world with no variability slack has no value. Reality supplies variability, and a plan with no slack absorbs it as missed service and expedite cost. The failure is not in the arithmetic but in giving a deterministic model a stochastic problem. The fix is to keep optimization for generating candidate designs and add simulation to evaluate them: run each candidate against sampled demand and transit-time distributions and compare service and cost distributions rather than single expected values. A design that is slightly worse on expected cost but far less sensitive across scenarios is usually the better one to operate.