Multiple Plants, Multiple Customers — How Much Does Each Plant Ship to Each Customer to Minimise Total Freight?

Editor’s note

This problem is called on the operations floor “flow plan”, “shipment allocation”, or “the plant-customer matrix”. The academic name is the Transportation Problem, also written in some sources as Hitchcock Problem or Hitchcock-Koopmans Problem. Frank Hitchcock defined the problem in numerical form in his 1941 MIT paper; Tjalling Koopmans wrote an independent economic formulation in 1947 (this work is cited in his 1975 Nobel Prize in Economics); George Dantzig developed the Simplex method specifically through this problem in 1951. It is the founding problem of linear programming and the ancestor of the next generation — TSP, VRP, vehicle routing — that built on it.

Distinction from VRP (#002, #069) is critical: VRP is vehicle routing — a depot-customer-customer-depot tour, in what sequence each vehicle visits which customers. The transportation problem is flow allocation: how many units each plant ships to each customer; there is no route, only quantity. The two are complementary — the transportation problem first decides weekly flow, then VRP decides daily routing. They run in sequence in the same chain. Distinction from facility location (#010): facility location is the open-new-plant/warehouse decision (with fixed opening cost); the transportation problem is flow allocation across existing facilities (no opening cost). Distinction from p-median (#074): p-median selects a fixed number of facilities, while the transportation problem takes existing facilities as given.

The point most often overlooked in this segment: dual variables and shadow prices. The primal flows (how many tons each plant ships to each customer) are what the practitioner reads off the output; the dual variables assign a shadow price to each source and destination — “if plant i’s capacity rises by 1 ton, by how much does total freight cost fall”, “if customer j’s demand rises by 1 ton, by how much does total cost rise” are answered exactly. This is direct input for investment decisions: which plant benefits most from capacity expansion, which customer has marginal freight cost higher than others. The practitioner typically uses only primal flows and does not read duals — a critical loss for capacity-investment prioritisation. The second overlooked point: the unbalanced problem. In reality, total capacity rarely equals total demand exactly (excess capacity or under-production). The solver adds a dummy source or destination — that dummy row or column is the idle-capacity report; if missed, what the idle capacity corresponds to is not understood.

A step-by-step path for an SMB

Stage 1 — Measure first, plan later. At least 6-12 months of data: monthly shipment quantity per plant-customer pair, per-unit freight cost (distance + vehicle type + contract), plant weekly capacity, customer weekly demand. Build the cost matrix as a separate table — rows are plants, columns are customers, cells are TRY/ton (or TRY/pallet). Critical: has the fuel price changed in the past 12 months — has the cost matrix been refreshed? If not, even the first LP run will show 5-10% savings.

Stage 2 — Extract the knowledge capital. List which plants are physically-impossible for which customers (distance, product fit, contract restriction) — these constraints enter the model as ‘forbidden cells’ (large cost). Plant capacity: real sustained capacity or with maintenance windows? Customer demand: stable or seasonal?

Stage 3 — Pilot. 8-12 weeks. Build the LP model for a sub-region (e.g. one product line or one regional customer set), run the solver, and compare the result to the current manual allocation in parallel. The decision stays with the planner; the LP makes a suggestion. The success criterion is set in writing, before the pilot: total freight cost down at least 10%, idle-capacity or unmet-demand report clear. Do not hesitate to ask for the dual-variable table as a separate output — this table is gold for capacity investment.

Stage 4 — Rollout. Over 6-12 months, expand to all product lines and regions. Move to a monthly re-solve cadence — fuel change, new customer, capacity maintenance as triggers. Quarterly planning committee: realised flows vs plan, dual-variable report (shadow price), cost-matrix refresh date.

Risks — what can go wrong

1. Plant capacity shifts in real time. A static LP model takes weekly or monthly capacity as fixed; maintenance, shift loss, or raw-material outages move it daily. Fix: shorter (weekly) re-solve cadence plus a safety margin trimmed off above-average capacity.
2. Cost matrix is not refreshed. Fuel went up 20% but the matrix is on 2-year-old numbers — the LP optimises an obsolete matrix and loses money in reality. Fix: refresh the cost matrix every 3 months (fuel + freight contract + vehicle cost).
3. Customer special requests not modeled. Some customers have a delivery time window, a package-size restriction, or a product-mix rule — pure transportation problem does not carry these; they must be passed to a VRP or planning layer. A flow technically correct on the LP may be operationally infeasible.
4. Single-supplier dependence (WMS/TMS lock-in). If the software keeps source-destination definitions, cost matrix, and solution history in a proprietary format, leaving means losing the operator’s flow memory. The contract must include “flow-matrix history and cost-matrix annual export in a standard format” as a clause.

A technical view of the solution method

Objective function choice:

• Objective 1 — Total freight cost minimum: Classical. Typical for FMCG, raw-material-to-contract-shop chains.
• Objective 2 — Total distance or fuel minimum: For carbon-footprint or fuel-heavy operations.
• Objective 3 — Service time (delivery time) weighted minimum: For fast-distribution segments (food, cold chain).
• Objective 4 — Blend (weighted): freight + service + penalty: For a customer base with contractual late-delivery penalties.

The Assignment Problem is a special case of the transportation problem: source count equals destination count, each source to exactly one destination (capacity = demand = 1, x_ij binary decision). Staff-task assignment, machine-task assignment, vessel-berth assignment (a sub-layer of BAP in #026), node-matching problems fall in this shape. The Hungarian method (Kuhn 1955) solves the assignment problem in O(n³) — far faster than the more general simplex on the same data, but only for the assignment special case.

Multi-period extension: x_ijt — quantity shipped from plant i to customer j in period t; each period has its own capacity and demand, with inter-period inventory carrying cost added. This grows into the multi-period production-distribution planning problem — keeps the transportation problem at its core but adds lot-sizing and inventory layers.

Stochastic extension: d_j is a random variable; the solution gives an allocation that does not exceed capacity in any scenario and minimises expected cost — stochastic LP or scenario-based MIP.

Academic references

Listed in the sources block of this page’s frontmatter. Hitchcock (1941) and Koopmans (1947) are the two founding papers; Dantzig (1951) developed the Simplex method specifically through this problem. Bazaraa-Jarvis-Sherali (2010) and Murty (1992) are modern textbook references. INFORMS and the European Journal of Operational Research archives carry many deployment cases in supply chains and production-distribution networks.