Transport problem¶
An optimization problem that allocates or couples supply at source locations with demand at destination locations while minimizing total transport cost under mass-balance or assignment constraints.
Core Idea¶
The transport problem asks how to move or couple a source distribution to a target distribution at minimum total cost. A plan specifies how much of each source goes to each destination, respects supply and demand, and is scored by the cost assigned to every source–destination transfer.
Monge's original form uses a map and does not split source mass; Kantorovich's relaxation uses a coupling and can divide it. A finite equal-unit case becomes an assignment problem, while the Hitchcock–Koopmans formulation is linear programming. The same structure supports modern optimal-transport geometry, but the formulation and cost must be stated.
Structural Signature¶
Sig role-phrases:
- source supply. Specifies locations or states and the mass available at each. Constitutive origin side. If altered: A route problem without supplied quantity is different.
- target demand. Specifies destinations or states and required mass. Constitutive destination side. If altered: Unmatched demand violates the balanced formulation unless slack is modeled.
- admissible transport plan. Assigns or couples source mass to target mass while respecting constraints. Identity-bearing decision object. If altered: A cost matrix alone is not a transport solution.
- unit cost relation. Prices moving mass from each source to each destination. Constitutive objective input. If altered: Without cost there is feasibility but no minimum-cost transport problem.
- minimum aggregate cost. Ranks plans by total transported cost. Constitutive selection rule. If altered: A heuristic route not shown optimal is only a candidate plan.
What It Is Not¶
- Assignment problem. Are shipments indivisible one-to-one units?
- Vehicle routing. Is route order rather than mass coupling optimized?
- Network flow. Is a fixed graph and edge flow the defining representation?
- Wasserstein distance. Is the optimal value being used as a metric?
Scope of Application¶
Use transport problem when the two mass distributions, feasibility constraints, cost function, and minimization target are explicit.
- Logistics. Allocates shipments to destinations.
- Resource allocation. Matches supply and demand.
- Probability. Couples distributions.
- Economics. Studies allocation under costs.
- Optimal transport geometry. Defines distances through minimum coupling cost.
Clarity¶
Physical travel is not required: source and target may be probability distributions or abstract states. Conversely, an ordinary routing problem is not automatically transport because vehicles and path order may be the decision instead of mass coupling.
Manages Complexity¶
Separating supply, demand, plan, cost, and objective exposes changes such as unbalanced mass, capacity constraints, indivisibility, regularization, and nonunique optima without losing the basic problem.
Abstract Reasoning¶
- Define source and target measures or finite quantities.
- Check that total mass balances or model the mismatch explicitly.
- Write admissible maps or couplings.
- Specify the per-unit cost and aggregate objective.
- Compare feasible plans and state whether splitting is allowed.
Knowledge Transfer¶
Minimum-cost coupling transfers to image matching, probability, and economics, but the source-target mass constraint distinguishes transport from generic optimization. The nearest stopping boundary is explicit: The assignment problem is closest: it is a discrete one-to-one special case with indivisible equal units, while transport allows mass splitting in its broader formulations. The inclusion test remains: A problem is a transport problem when source mass, target mass, admissible couplings, and a transport cost are specified and total cost is minimized subject to balance constraints. The structure no longer applies when the case exits when no source-target mass balance, coupling decision, or aggregate transport-cost objective remains.
Examples¶
Canonical¶
Equal-output mines and equal-demand factories are matched bijectively; each mine–factory pair has a shipment cost and the chosen matching minimizes their sum.
Mapped back: source supply → one unit per mine; target demand → one unit per factory; admissible transport plan → bijection; unit cost relation → c(m,f); minimum aggregate cost → least summed shipment cost.
Applied / In Practice¶
A delivery company chooses the shortest tour visiting customers with one truck; that is vehicle routing, not a transport problem unless a source-demand coupling is also the central decision.
Mapped back: source supply → single depot inventory; target demand → customer visits; admissible transport plan → route order; unit cost relation → road length; minimum aggregate cost → tour distance, not coupling cost.
Structural Tensions¶
T1: Monge determinism vs. Kantorovich splitting. A map preserves source identity while a coupling gives convex flexibility. Diagnostic: May one source divide among destinations?
T2: cost realism vs. mathematical tractability. Rich constraints model logistics better but can obscure the core coupling geometry. Diagnostic: Which constraints change the problem class?
Structural–Framed Character¶
Description turns on source supply, target demand, admissible transport plan, unit cost relation, minimum aggregate cost. Skeletal core. A conserved quantity is coupled between two distributions under a cost-minimizing rule. Domain-bound accent. Mines, factories, measures, couplings, assignments, shipment costs, and linear programs define transport theory. Transfer remains bounded because Why not prime. Constrained minimum-cost coupling is portable; this is a named optimization family. The negative boundary is concrete: Any shipping schedule, vehicle-routing problem, assignment, network flow, logistics plan, matching, resource allocation, or Wasserstein distance is not automatically the transport problem. The transport problem is structural-formal: distributions, feasible couplings, costs, and minima admit exact specification. Its character: minimum-cost reconciliation of source and target mass.
Structural Core vs. Domain Accent¶
Skeletal core. A conserved quantity is coupled between two distributions under a cost-minimizing rule.
Domain-bound accent. Mines, factories, measures, couplings, assignments, shipment costs, and linear programs define transport theory.
Why not prime. Constrained minimum-cost coupling is portable; this is a named optimization family.
Instantiates / Related Primes¶
This entry typically is a kind of Minimum-cost flow problem.
- Optimization. Feasible plans are ranked by total cost.
- Allocation. Supply is assigned to demand.
- No strict parent is asserted.
Relationships to Other Abstractions¶
Current abstraction Transport problem Domain-specific
Parents (1) — more general patterns this builds on
-
Transport problem is a kind of, typical Minimum-cost flow problem Domain-specific
The classical (Hitchcock-Koopmans) transport problem is a bipartite instance of minimum-cost flow: route supply to demand across a capacitated bipartite network while minimizing total transfer cost.Minimum-cost flow problems route a required amount of flow through a capacitated network subject to conservation, minimizing total edge cost. The finite transport problem couples supplies at sources to demands at destinations, respecting supply and demand while minimizing the total cost of the transfer plan, which is exactly a minimum-cost flow instance on a bipartite source-destination graph with no intermediate nodes. The relation is typical rather than strict because the transport problem's Monge and Kantorovich continuous-measure formulations generalize beyond finite graphs into optimal-transport geometry, a case the discrete minimum-cost-flow framework does not itself cover.
Hierarchy path (1) — routes to 1 parentless root
- Transport problem → Minimum-cost flow problem → Optimization
Neighborhood in Abstraction Space¶
Transport problem sits in a moderately populated region (55th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Unclustered & Miscellaneous (2551 abstractions)
Nearest neighbors
- Stowage plan for container ships — 0.86
- Individual-Pieces Set — 0.86
- Draft survey — 0.86
- Fuel Fraction — 0.85
- Business performance management — 0.85
Computed from structural-signature embeddings · 2026-10-08
Not to Be Confused With¶
- Assignment problem. Tell: Are shipments indivisible one-to-one units?
- Vehicle routing. Tell: Is route order rather than mass coupling optimized?
- Network flow. Tell: Is a fixed graph and edge flow the defining representation?
- Wasserstein distance. Tell: Is the optimal value being used as a metric?
References¶
- Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Transportation_theory_(mathematics) (revision 1351524930).
- Preserved source candidate: https://books.google.com/books?id=mqGeSQ6dJycC
- Preserved source candidate: https://books.google.com/books?id=mqGeSQ6dJycC&dq=a.n.+tolstoi+transportation+networks&pg=PA362
- Preserved source candidate: https://books.google.com/books?id=2hDvzITtfdAC
- Preserved source candidate: https://books.google.com/books?id=2hDvzITtfdAC&dq=%22a.n.+tolstoy%22+mathematics&pg=PA831
- Preserved source candidate: https://priorart.ip.com/IPCOM/000128834/
- Preserved source candidate: http://dx.doi.org/10.1561/2200000073
- Preserved source candidate: https://academic.oup.com/gji/article-abstract/205/1/345/2594839
- Preserved source candidate: https://archive.org/details/combinatorialmat0000brua
The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.