Transportation Problem
Ship from many sources to many destinations at the lowest total cost. The transportation problem finds how much to send along each route from supply points to demand points, minimizing shipping cost while respecting every supply and demand.
Solve Transportation Problem →What is the Transportation Problem?
The transportation problem is the task of determining the least-cost way to ship a product from several supply sources (such as factories or warehouses) to several demand destinations (such as stores or customers), given the supply at each source, the demand at each destination, and the shipping cost per unit on every route.
It is one of the classic special cases of linear programming. Its structure, sources with supplies, destinations with demands, and a cost for each route, is so regular that specialized methods (such as the stepping-stone or MODI method) can solve it more efficiently than a general LP, though the LP formulation is equally valid.
A transportation problem is balanced when total supply equals total demand. When they differ, a dummy source or destination is added to absorb the surplus supply or unmet demand at zero cost, restoring balance so the standard methods apply. The solution specifies exactly how many units to ship on each route to minimize total transportation cost.
In plain terms: You have several factories with stock and several stores that need it, and shipping costs differ by route. The transportation problem works out how much to send from each factory to each store so everyone's supply and demand is satisfied at the lowest total shipping cost.
Key Points
Sources and Destinations
Supply points with available quantities and demand points with required quantities, connected by per-unit shipping costs.
Balance
Balanced when total supply equals total demand; otherwise a dummy source or destination restores balance at zero cost.
Special LP
A structured special case of linear programming, solvable by dedicated methods such as stepping-stone or MODI.
Key Formulas
Understanding the Solution
The solution is a shipping plan, how many units travel on each source-to-destination route, and the resulting minimum total cost. Only a subset of routes will carry flow in an optimal basic solution; many routes will be unused, which is normal.
The transportation structure also yields useful sensitivity information. The methods reveal which routes are on the margin of becoming attractive and how the solution would change if costs, supplies or demands shifted, valuable for planning under changing conditions.
Assumptions & Validation
Known Supplies & Demands
Supply at each source and demand at each destination are known.
If violated: Estimate supplies and demands accurately.
Known Route Costs
The per-unit shipping cost on each route is known.
If violated: Provide all route costs; prohibited routes get a very high cost.
Linear Costs
Shipping cost is proportional to units shipped.
If violated: For nonlinear or fixed-charge costs, use extended models.
⚠️ Check assumptions first
The transportation model assumes shipping cost is proportional to the quantity shipped and that supplies, demands and route costs are known. It must be balanced, with total supply equal to total demand, which is achieved by adding a dummy source or destination when they differ. If costs include fixed charges for opening a route, or are nonlinear, the basic model does not apply and a fixed-charge or nonlinear extension is needed.
When NOT to Use Transportation Problem
One-to-One Assignment
When each source supplies one unit to one destination, the assignment problem and Hungarian method apply.
Routing Between Stops
To sequence deliveries along routes, use vehicle routing, not point-to-point shipping.
Capacitated Multi-Stage Flow
For flow through a multi-stage capacitated network, use network-flow models.
Industry Applications
Distribution Planning
Plan least-cost shipments from warehouses to stores or regions.
Production Allocation
Allocate production across plants to meet regional demand at least cost.
Sourcing Decisions
Decide which sources should supply which markets.
Logistics Cost Reduction
Minimize total freight cost across a supply-demand network.
Frequently Asked Questions
What is the transportation problem?
The transportation problem is the task of finding the least-cost way to ship a product from several supply sources to several demand destinations, given each source's supply, each destination's demand, and the per-unit shipping cost on every route. The solution specifies how many units to send on each route to satisfy all demands from the available supplies at minimum total transportation cost.
How is the transportation problem related to linear programming?
The transportation problem is a classic special case of linear programming, with a particularly regular structure of supply constraints, demand constraints and route costs. Because of this structure, specialized methods such as the stepping-stone and MODI methods can solve it more efficiently than a general linear program, although formulating and solving it as a linear program is equally valid and gives the same optimal shipping plan.
What does it mean for a transportation problem to be balanced?
A transportation problem is balanced when total supply across all sources equals total demand across all destinations. Balance is required for the standard solution methods. When supply and demand differ, a dummy source or destination is added with zero shipping cost to absorb the surplus supply or the unmet demand, restoring balance. The dummy flows represent unused supply or unfilled demand and carry no real cost.
What is a dummy source or destination?
A dummy source or destination is an artificial supply or demand point added to balance a transportation problem when total supply and total demand are unequal. It is given zero shipping cost on all its routes. A dummy destination absorbs excess supply, while a dummy source covers excess demand. In the solution, flow to or from the dummy indicates supply left unused or demand left unmet, at no real cost.
How is the transportation problem different from the assignment problem?
The assignment problem is a special case of the transportation problem in which every source has a supply of exactly one and every destination a demand of exactly one, producing a one-to-one matching. The general transportation problem allows sources and destinations to have any supplies and demands, so a source can serve several destinations and vice versa. The assignment problem's special structure allows the dedicated Hungarian method.
Why do some routes carry no flow in the solution?
In an optimal transportation solution, only a subset of the possible routes carries flow, while many routes are unused. This is a normal property of the problem's structure: an optimal basic solution uses only as many routes as needed to satisfy all constraints, typically one fewer than the number of sources plus destinations. Unused routes are simply those that are not cost-effective in the optimal plan.
Ship at the Lowest Total Cost
Solve the transportation problem for a least-cost shipping plan. Free during Beta.
Solve Transportation Problem →