Transportation, Assignment and Transshipment Models

Introduction

Operations managers routinely decide how much product should move from several supply points to several demand points, which employee should perform which job, and how goods should pass through intermediate distribution facilities. These decisions share a common structure: scarce resources must be allocated across alternative routes or activities while minimizing cost or maximizing contribution.

Transportation, assignment and transshipment models are network-based linear programming models. They are especially valuable because their structure permits efficient algorithms, clear managerial interpretation and sensitivity analysis. Although frequently associated with physical distribution, the models also apply to production planning, workforce allocation, telecommunications, energy transmission, hospital scheduling and project resource allocation.

A transportation model determines quantities shipped from origins to destinations. An assignment model is a special case in which each origin and destination has unit capacity and each assignment is indivisible. A transshipment model extends the transportation structure by allowing flow through intermediate nodes.

Learning Objectives

After studying this chapter, the reader should be able to:

1. Formulate transportation, assignment and transshipment problems mathematically.
2. Distinguish balanced, unbalanced, degenerate, infeasible and prohibited-route models.
3. Construct initial transportation solutions and improve them using the stepping-stone or MODI method.
4. Solve assignment problems using reduction procedures and the Hungarian algorithm.
5. Model transshipment systems with intermediate facilities and capacity restrictions.
6. Interpret shadow prices, reduced costs, unused capacity and alternative optima.
7. Evaluate operational, strategic, ethical and technological implications of network decisions.

1. Transportation Models

1.1 Basic structure and terminology

A transportation problem has a set of origins, such as factories or suppliers, and a set of destinations, such as warehouses, stores or customers. Each origin has a known supply, each destination has a known demand, and shipping one unit from origin i to destination j has a known unit cost.

Let:

• m = number of origins;
• n = number of destinations;
• sᵢ = supply available at origin i;
• dⱼ = demand required at destination j;
• cᵢⱼ = unit transportation cost from origin i to destination j;
• xᵢⱼ = quantity shipped from origin i to destination j.

The standard cost-minimization model is:

subject to origin supply constraints:

and destination demand constraints:

with:

The model assumes that costs are linear, shipment quantities are divisible, costs are known or represented by suitable estimates, and shipment decisions for one route do not alter the unit cost of another route. If all supply is used and all demand is met, the inequalities may be written as equalities.

A transportation problem is balanced when total supply equals total demand:

If supply exceeds demand, a dummy destination absorbs the surplus. If demand exceeds supply, a dummy origin represents unmet demand or an outside supplier. Dummy costs must reflect the managerial meaning of the imbalance. A zero dummy cost may be appropriate for unused capacity, but a penalty cost is more appropriate when unmet demand represents lost sales or service failure.

1.2 A compact transportation example

A firm has two plants and three warehouses. Plant P1 can supply 40 units and P2 can supply 60 units. Warehouse W1 requires 20 units, W2 requires 50 units and W3 requires 30 units. Unit shipping costs are:

The problem is balanced. A feasible allocation is:

Its cost is:

This allocation is feasible, but feasibility does not establish optimality. Another allocation may satisfy every supply and demand constraint at lower total cost.

1.3 Constructing an initial basic feasible solution

An initial basic feasible solution is the starting point for transportation optimization. Three common methods are:

1. Northwest-corner method: allocate as much as possible beginning at the upper-left cell, moving right or downward when a supply or demand is exhausted. It is simple but ignores costs.
2. Least-cost method: allocate as much as possible to the currently least-cost available cell. It normally provides a better starting solution than the northwest-corner method.
3. Vogel’s approximation method: calculate a penalty for each row and column as the difference between its two smallest costs. Allocate in the row or column with the largest penalty, using its least-cost cell. This often produces a strong starting solution.

A nondegenerate basic feasible solution for an m × n transportation table normally contains m + n − 1 positive allocations. If fewer than m + n − 1 occupied cells exist, the solution is degenerate. A very small quantity, commonly denoted ε, may be placed in an appropriate empty cell for computational purposes, provided it does not create a closed loop with existing basic cells. The ε is a bookkeeping device, not a real shipment.

1.4 Optimality testing: the MODI method

The modified distribution method, or MODI method, tests a basic feasible solution efficiently. For every occupied cell, determine row potentials uᵢ and column potentials vⱼ satisfying:

Set one potential arbitrarily, usually u₁ = 0, and calculate the remaining potentials from the occupied cells. For each unoccupied cell, calculate its reduced cost:

For a minimization problem, the current solution is optimal if every unoccupied cell has Δᵢⱼ ≥ 0. A negative value indicates that introducing one unit into that route can reduce total cost, subject to adjustment around a closed loop.

To improve the solution, select an unoccupied cell with a negative reduced cost. Construct a closed path that alternates plus and minus signs, beginning with a plus sign in the entering cell. The smallest allocation in the minus positions is the maximum amount that can be moved around the loop. Add this amount to plus cells and subtract it from minus cells. Recalculate the potentials and reduced costs.

The reduced cost also has managerial meaning. Under the model assumptions, a negative value indicates an economically attractive route not currently used. A zero reduced cost indicates a possible alternative optimum: shifting flow along the relevant loop may produce another optimal plan with the same total cost.

1.5 Prohibited routes and capacity restrictions

A route may be unavailable because of regulatory restrictions, incompatible infrastructure, security concerns or excessive risk. A prohibited route should not simply be assigned a very large cost unless the numerical method and scale make that safe. The best practice is to exclude the variable or explicitly mark the cell as prohibited.

Route capacity can be represented by:

where kᵢⱼ is the maximum quantity that can use route i,j. Fixed charges, economies of scale, vehicle indivisibility and delivery time windows may require mixed-integer programming rather than a basic transportation model.

The transportation model also supports supply limits, minimum shipment requirements, multiple products and service-level constraints. However, adding product compatibility, nonlinear rates or inventory timing may destroy the simple transportation structure.

2. Assignment Models

2.1 Concept and formulation

An assignment problem allocates n agents to n tasks, with exactly one agent assigned to each task and exactly one task assigned to each agent. Agents may be workers, machines, vehicles or sales territories; tasks may be jobs, routes, projects or customer accounts.

Let cᵢⱼ be the cost of assigning agent i to task j, and let xᵢⱼ equal 1 if the assignment is made and 0 otherwise. The binary model is:

subject to:

The assignment model is a special transportation model with unit supply at every origin and unit demand at every destination. Its constraint matrix has a strong integrality property, so solving the corresponding linear programming relaxation produces integral optimal solutions under the standard one-to-one structure.

If the numbers of agents and tasks differ, add dummy agents or tasks. A dummy cost should represent the consequence of an unfilled task, an idle agent or outsourcing. For maximization, convert benefits to costs, for example by subtracting each benefit from a sufficiently large constant, or solve the equivalent maximum assignment algorithmically.

2.2 Hungarian algorithm

The Hungarian algorithm solves a square assignment problem through row and column reductions and systematic selection of independent zeros.

1. Subtract the smallest element in each row from every element in that row.
2. Subtract the smallest element in each column from every element in that column.
3. Cover all zeros with the minimum number of horizontal and vertical lines.
4. If the number of lines equals n, select independent zeros to obtain an optimal assignment.
5. If fewer than n lines are needed, subtract the smallest uncovered value from every uncovered element and add it at intersections of covering lines. Repeat the covering and adjustment process.

Row and column reductions preserve the identity of the optimal assignment because they subtract constants from every feasible solution’s row or column total. The algorithm is particularly attractive for large one-to-one matching problems, although modern solvers may use equivalent network optimization methods.

2.3 Worked assignment example

Four technicians must be assigned to four jobs. The estimated completion times are:

A feasible assignment is T1–J2, T2–J3, T3–J1 and T4–J4, with total time:

To establish optimality, the Hungarian procedure is applied. Row minima are 2, 3, 1 and 4. After row reduction, column minima are then subtracted. The resulting zero pattern permits the independent selection T1–J2, T2–J3, T3–J1 and T4–J4. Therefore the minimum total completion time is 14 units, provided the time estimates and one-job-per-technician assumptions are valid.

The managerial interpretation is not that each technician should always perform the mathematically fastest task in isolation. The model recognizes opportunity cost: assigning one technician to a task prevents that technician from performing another task.

3. Transshipment Models

3.1 Why transshipment is needed

A pure transportation model permits shipments directly from origins to destinations. In many supply networks, goods can move through consolidation centers, ports, cross-docks, regional warehouses or intermediate processing facilities. A transshipment model represents these intermediate nodes explicitly.

A network contains nodes and directed arcs. Each node may be:

• a supply node, with net positive availability;
• a demand node, with net negative requirement;
• a transshipment node, where inflow is balanced by outflow, subject to storage or processing rules.

Let xᵢⱼ be flow on arc i,j, cᵢⱼ its unit cost and bᵢ the net supply at node i. A minimum-cost flow formulation is:

subject to flow conservation:

and arc capacities:

Here, uᵢⱼ is the capacity of arc i,j. A supply node has positive bᵢ, a demand node has negative bᵢ, and a pure transshipment node has bᵢ = 0. If a node can store inventory, the conservation equation must be modified to include inventory changes.

3.2 Transformation into a transportation table

Some transshipment problems can be converted into transportation form by treating each node as both a potential origin and destination. Artificially large costs or prohibited cells prevent nonsensical flows, such as a demand node shipping more product after receiving it. Network-flow formulations are usually clearer and computationally more efficient, especially when there are many nodes and arcs.

A transshipment model differs from a transportation model in an important managerial respect: the best direct route may not be the best network route. A shipment through an intermediate node may have a higher number of handling activities but lower total transport cost, better consolidation or greater service reliability.

3.3 Capacity and operational constraints

Intermediate facilities may have limits on throughput:

where hᵢ is the processing capacity of node i. If a facility must maintain flow balance, both inbound and outbound flows are linked. Inbound and outbound capacities may be represented separately when dock capacity, storage capacity and transport capacity differ.

Time-dependent transshipment requires a time-expanded network. Each physical facility is represented at multiple time points, with arcs for movement and holding inventory. This structure supports appointment windows, perishability and service deadlines, but increases model size.

4. Solution Interpretation and Sensitivity Analysis

A solver output is not a managerial recommendation until it has been interpreted. The analyst should examine:

• quantities on every active route;
• unused supply and unmet demand;
• route capacity utilization;
• total cost and cost per delivered unit;
• bottleneck facilities;
• alternative optimal solutions;
• sensitivity to demand, supply and cost changes;
• practical feasibility, including lead time and quality requirements.

Dual values, also called shadow prices, estimate the marginal change in the objective value caused by relaxing a binding constraint, within the allowable sensitivity range. For example, a demand shadow price can indicate the incremental cost of requiring one additional unit at a destination. A high positive marginal cost may justify local sourcing, facility expansion or demand-management action.

Shadow prices should not be interpreted outside their valid range. If a demand increase changes the basis or causes a capacity constraint to become active, the original marginal value may no longer apply. Similarly, a route’s reduced cost is meaningful only relative to the current model and its assumptions.

Multiple optima and robustness

If an unused route has zero reduced cost in an optimal minimization solution, an alternative optimal allocation may exist. This is strategically useful when managers value resilience, supplier diversification or lower carbon exposure. A single cost-minimizing solution may be fragile if it depends on one supplier, one port or one carrier.

Robust planning can add scenario analysis, capacity buffers, disruption constraints or penalties for concentration. The resulting solution may have a slightly higher expected cost but materially lower operational risk.

5. Applied Case: Regional Medical-Device Distribution

The following is an illustrative case based on a realistic operational setting.

Background

MedSupply distributes sterile medical devices from two plants to three regional hospitals. Plant A has capacity of 70 cartons per week and Plant B has capacity of 50 cartons. Hospital H1 requires 30 cartons, H2 requires 50 and H3 requires 40. Shipping costs per carton are:

The network is balanced. However, H3 requires a validated cold-chain route, and Plant A–H3 is not approved. Therefore that route is prohibited. In addition, Plant B–H1 has a maximum capacity of 20 cartons because of carrier limitations.

Problem formulation

The decision variables are shipments from each plant to each hospital. The objective is to minimize weekly distribution cost, subject to plant capacities, hospital demands, the H3 route prohibition and the Plant B–H1 capacity.

A feasible plan is:

Its cost is:

Consider whether using Plant B for H1 could improve the solution. Each unit shifted from Plant A–H1 to Plant B–H1 changes cost from 4 to 5, an increase of 1. Plant A’s released capacity must then serve H2, where its cost is 6 instead of Plant B’s current H2 cost of 4. A simple exchange therefore increases cost further. Because Plant B has the lowest cost for H3 and its H1 capacity is limited, the capacity should generally be reserved for the most valuable use after considering the complete network. Solving the constrained model confirms that the displayed plan is optimal under the stated costs and route restrictions.

Outcome and managerial interpretation

The plan uses all plant capacity, meets every hospital requirement and respects regulatory restrictions. Plant B’s H3 lane is fully utilized, making that lane a potential bottleneck. Management should not conclude automatically that Plant B must be expanded: the value of expansion depends on the shadow price of its capacity and on whether additional H3 demand, carrier disruption or validation requirements are expected.

Possible strategic actions include qualifying Plant A–H3, negotiating additional cold-chain capacity, establishing a third approved carrier and holding emergency inventory. These actions may raise fixed or holding costs but improve resilience.

Learning points

1. A prohibited route is a structural constraint, not merely an unattractive cost.
2. A capacity restriction can change which low-cost route is strategically valuable.
3. Feasibility, optimality and resilience are different managerial criteria.
4. Regulatory compliance must be embedded in the model rather than checked only after optimization.
5. The optimal solution should be stress-tested against disruption and demand scenarios.

6. Technology, AI and Governance

Enterprise resource planning, transportation-management systems and cloud optimization platforms can solve large network models rapidly. Data pipelines may provide demand forecasts, carrier rates, facility capacities, delivery times and emissions factors. Artificial intelligence can support demand prediction, anomaly detection and scenario generation, but optimization remains necessary to select a feasible allocation under explicit constraints.

Managers should distinguish prediction from prescription. A machine-learning forecast estimates likely demand; a transportation or transshipment model decides how resources should be allocated given that forecast. Poor data, biased service assumptions or omitted constraints can produce an apparently optimal but operationally harmful solution.

Important governance practices include:

• maintain an auditable record of costs, capacities and prohibited routes;
• validate that recommendations satisfy safety, labor and regulatory rules;
• monitor model drift as rates, demand and network conditions change;
• protect commercially sensitive supplier and customer data;
• preserve human review for exceptional, high-impact decisions;
• assess environmental effects, including emissions and empty miles.

Sustainability can be integrated by adding emissions as a constraint, using a weighted objective, or examining cost–emissions trade-offs. A weighted objective such as cost plus a monetary carbon value requires a defensible conversion factor and sensitivity analysis; otherwise, the result may imply false precision.

7. Limitations and Best Practices

These models are powerful abstractions, but they do not automatically capture every operational reality. Common limitations include:

• linear costs when actual tariffs contain quantity breaks;
• deterministic demand when demand is uncertain;
• divisible shipments when vehicles and pallets are discrete;
• static networks when lead times and inventory evolve over time;
• average costs that hide service, quality or risk differences;
• omission of labor, contractual or regulatory constraints.

Best practice is to begin with a transparent base model, validate it with operations personnel, add material constraints incrementally and compare the solution with actual practice. Scenario analysis should test demand variation, route failure, capacity loss, rate changes and new facilities. If integer decisions, fixed charges or nonlinearities are important, use mixed-integer or nonlinear optimization rather than forcing the problem into an unsuitable transportation format.

Chapter Summary

Transportation models allocate quantities from origins to destinations at minimum cost or maximum contribution. Their formulation consists of an objective function, supply constraints, demand constraints and non-negativity restrictions. Balanced and unbalanced problems are handled differently, and dummy nodes represent surplus capacity, unmet demand or outsourcing.

Initial feasible solutions may be obtained through the northwest-corner, least-cost or Vogel methods. The MODI method uses potentials and reduced costs to test optimality and identify improving routes. Degeneracy, prohibited routes and capacity restrictions require careful treatment.

Assignment models are one-to-one transportation models. Binary variables represent whether an agent performs a task, and the Hungarian algorithm solves the standard square problem efficiently. Transshipment models extend the network by permitting flow through intermediate nodes and enforcing flow conservation and arc capacities.

Managerial analysis must go beyond total cost. Shadow prices, reduced costs, bottlenecks, alternative optima, resilience, regulatory compliance and environmental impact all influence the quality of a decision. Optimization technology and AI can improve data and scenario analysis, but governance, model validation and professional judgment remain essential.

Key Terms

Transportation model: A network model allocating supply from origins to destinations.

Origin: A node that provides supply.

Destination: A node that receives demand.

Supply constraint: A restriction limiting quantity shipped from an origin.

Demand constraint: A requirement specifying quantity delivered to a destination.

Balanced transportation problem: A problem in which total supply equals total demand.

Dummy origin or destination: An artificial node used to balance an unbalanced model.

Basic feasible solution: A feasible solution with the number of basic allocations required by the model structure.

Degeneracy: A basic solution containing fewer than the required number of positive allocations.

MODI method: A transportation optimality method using row and column potentials.

Reduced cost: The net cost effect of introducing a currently unused route.

Prohibited route: An origin–destination connection that cannot be used.

Assignment model: A one-to-one allocation model with binary decision variables.

Hungarian algorithm: A systematic method for solving assignment problems.

Transshipment node: An intermediate node through which flow passes.

Flow conservation: The requirement that node inflow and outflow satisfy the node’s net supply or demand.

Arc capacity: The maximum flow permitted on a network connection.

Shadow price: The marginal value of relaxing a binding constraint within a valid range.

Alternative optimum: A different solution having the same optimal objective value.

Network resilience: The ability of a distribution system to continue operating under disruption.

Review Questions

Short Answer Questions

1. What distinguishes a balanced transportation problem from an unbalanced problem?
2. Why is an assignment model considered a special transportation model?
3. What does a negative reduced cost indicate in a cost-minimization transportation problem?
4. Define a transshipment node and state its usual flow condition.
5. Why might a dummy destination require a penalty cost rather than a zero cost?

Long Answer Questions

1. Formulate the general transportation model and explain the meaning and units of every variable and constraint.
2. Compare the northwest-corner, least-cost and Vogel approximation methods as procedures for generating initial solutions.
3. Explain the MODI method, including the calculation and interpretation of row potentials, column potentials and reduced costs.
4. Describe the Hungarian algorithm and explain why row and column reductions preserve the optimal assignment.
5. Discuss the limitations of transportation and transshipment models in representing real supply-chain decisions.

Analytical / Application Questions

1. A company has three plants, four markets, route capacities and one prohibited lane. Design a transportation model and specify how you would test whether the resulting plan is robust to a 20% increase in demand at one market.
2. Four nurses must be assigned to four wards using a matrix of predicted labor hours. Explain how you would solve the problem, interpret the result and address an additional requirement that one nurse cannot work in one ward.
3. A distribution network contains two factories, one cross-dock and three customers. Develop a transshipment formulation with cross-dock throughput capacity, then explain which shadow price would be most useful in evaluating an expansion decision.

Multiple Choice Questions with Answers

Question 1

In a balanced transportation problem, which equality holds?

A. Total supply is greater than total demand

B. Total demand is greater than total supply

C. Total supply equals total demand

D. Every route has equal cost

Correct Answer: C. Total supply equals total demand

Question 2

For a minimization transportation problem, what does a negative MODI reduced cost for an unused route indicate?

A. The current solution is necessarily optimal

B. Introducing the route may reduce total cost

C. The route must be prohibited

D. Demand at the destination is zero

Correct Answer: B. Introducing the route may reduce total cost

Question 3

A nondegenerate basic feasible solution for an m × n transportation table normally contains how many positive basic allocations?

A. m + n

B. m × n

C. m + n − 1

D. m − n − 1

Correct Answer: C. m + n − 1

Question 4

Which algorithm is specifically designed for the standard one-to-one assignment problem?

A. Hungarian algorithm

B. Northwest-corner algorithm

C. PERT algorithm

D. Simple exponential smoothing

Correct Answer: A. Hungarian algorithm

Question 5

In an assignment model, what does xᵢⱼ = 1 normally mean?

A. Agent i is assigned to task j

B. Task j is cancelled

C. Agent i performs every task

D. The cost of task j is zero

Correct Answer: A. Agent i is assigned to task j

Question 6

What is the usual flow condition at a pure transshipment node?

A. Outflow must be zero

B. Inflow equals outflow, subject to model rules

C. Inflow must exceed outflow by total demand

D. Only one incoming arc may exist

Correct Answer: B. Inflow equals outflow, subject to model rules

Question 7

What is the appropriate modeling treatment for a route that is not legally permitted?

A. Always assign it a zero cost

B. Exclude or explicitly prohibit the route

C. Double its demand

D. Treat it as a dummy destination

Correct Answer: B. Exclude or explicitly prohibit the route

Question 8

In the illustrative technician assignment, what was the total time of the stated assignment?

A. 12 units

B. 14 units

C. 16 units

D. 18 units

Correct Answer: B. 14 units

Question 9

What does a shadow price estimate within its allowable sensitivity range?

A. The total number of routes

B. The marginal objective-value change from relaxing a constraint

C. The average cost of all products

D. The number of dummy nodes required

Correct Answer: B. The marginal objective-value change from relaxing a constraint

Question 10

Which situation most clearly indicates that a basic transportation model may be inadequate?

A. All costs are linear and shipments are divisible

B. Supply and demand are known and route capacities are fixed

C. Vehicle activation involves fixed charges and binary decisions

D. There are several origins and destinations

Correct Answer: C. Vehicle activation involves fixed charges and binary decisions