Solving the Least Cost Transportation Problem with Python

I ran into the least cost transportation problem again last week, this time when a small manufacturing client needed help cutting their shipping costs. They had three plants shipping to five distribution centers, and every route had a different price per unit. The question was the same one linear programming has been answering for decades: which routes minimize total cost while meeting all supply and demand constraints?

This article walks through solving the least cost transportation problem in Python using NumPy for the matrix operations and SciPy for verified optimal solutions. I will cover the problem setup, the Minimum Cost Method for finding an initial feasible solution, handling unbalanced cases where supply and demand do not match, and interpreting the results.

TLDR

• The least cost transportation problem finds the cheapest way to move goods from suppliers to demand centers while respecting supply limits and demand requirements
• Python’s NumPy handles the matrix operations needed to model and solve this problem
• The Minimum Cost Method gives a fast initial feasible solution by repeatedly allocating along the cheapest available route
• Real-world transportation problems are usually unbalanced, requiring a dummy demand center to absorb the difference between total supply and demand
• The optimal cost for our example problem is Rs 1180, achieved through a specific allocation across three factories and three distribution centers

What is the Least Cost Transportation Problem?

The least cost transportation problem is a classic linear programming problem where the goal is to determine the most economical way to move goods from multiple origins to multiple destinations. Each origin has a limited supply, each destination has a known demand, and each origin-destination pair has an associated cost per unit shipped.

Mathematically, if x_ij represents the quantity shipped from factory i to distribution center j, the objective is to minimize total cost subject to supply constraints at each factory and demand constraints at each center. This special structure enables efficient specialized algorithms that outperform general-purpose linear programming solvers on large instances.

Setting Up the Problem in Python

The example I will work through involves three factories and three distribution centers. NumPy arrays provide a clean way to represent the supply, demand, and cost matrix. Note that .copy() is used throughout to avoid modifying original arrays, as covered in the guide on how to copy a NumPy array in Python. Here are the problem parameters I will use:

• Factory A: 30 units | Factory B: 20 units | Factory C: 50 units (total supply: 100)
• Center D1: 40 units | Center D2: 70 units | Center D3: 30 units (total demand: 140)

Transportation Costs (per unit): A to D1/D2/D3: Rs 6/8/10, B to D1/D2/D3: Rs 9/12/13, C to D1/D2/D3: Rs 14/16/18.

import numpy as np

# Supply from each factory
supply = np.array([30, 20, 50])

# Demand at each distribution center
demand = np.array([40, 70, 30])

# Transportation cost matrix (rows = factories, columns = centers)
costs = np.array([
    [6, 8, 10],
    [9, 12, 13],
    [14, 16, 18]
])

print("Supply:", supply)
print("Demand:", demand)
print("Cost matrix:")
print(costs)

The supply and demand arrays define the constraints, and the cost matrix defines the per-unit shipping cost for each route. This structure maps directly to the mathematical formulation of the transportation problem.

Supply: [30 20 50]
Demand: [40 70 30]
Cost matrix:
[[ 6  8 10]
 [ 9 12 13]
 [14 16 18]]

Total supply is 100 units and total demand is 140 units. Since demand exceeds supply by 40 units, this is an unbalanced transportation problem. The next section covers how to handle this.

Handling Unbalanced Supply and Demand

When total supply does not equal total demand, the standard transportation algorithms need adjustment. The standard approach is to add a dummy row or column with zero transportation costs. When supply is less than demand, I add a dummy demand center that absorbs the unmet demand at zero cost.

<pre class="wp-block-syntaxhighlighter-code">
total_supply = np.sum(supply)
total_demand = np.sum(demand)

print(f"Total supply: {total_supply}")
print(f"Total demand: {total_demand}")
print(f"Shortfall: {int(total_demand - total_supply)} units")

# Add a dummy demand center with zero costs to balance the problem
if total_supply < total_demand:
    dummy_demand = total_demand - total_supply
    demand_balanced = np.append(demand, dummy_demand)
    dummy_costs = np.zeros((costs.shape[0], 1))
    costs_balanced = np.hstack([costs, dummy_costs])
    print(f"Added dummy demand center with {int(dummy_demand)} units at zero cost")
    print(f"Balanced demand: {demand_balanced}")
</pre>

Adding the dummy column means the algorithm will allocate unmet demand to the dummy center rather than leaving some real demand unfulfilled. The cost of shipping to the dummy center is zero, so it does not affect the real transportation cost.

Total supply: 100
Total demand: 140
Shortfall: 40 units
Added dummy demand center with 40 units at zero cost
Balanced demand: [40. 70. 30. 40.]

The Minimum Cost Method

The Minimum Cost Method is a greedy heuristic that finds a feasible starting solution for the transportation problem. It works by repeatedly selecting the route with the lowest cost where both the supplier still has inventory and the demand center still has unmet demand, then allocating as much as possible along that route.

<pre class="wp-block-syntaxhighlighter-code">
def minimum_cost_method(supply, demand, costs):
    supply = list(supply.copy())
    demand = list(demand.copy())
    costs = costs.copy()
    n, m = len(supply), len(demand)
    allocation = np.zeros((n, m))
    total_cost = 0

    while sum(supply) > 0 and sum(demand) > 0:
        min_cost = float('inf')
        min_i, min_j = -1, -1

        for i in range(n):
            for j in range(m):
                if supply[i] > 0 and demand[j] > 0 and costs[i, j] < min_cost:
                    min_cost = costs[i, j]
                    min_i, min_j = i, j

        if min_i == -1:
            break

        quantity = min(supply[min_i], demand[min_j])
        allocation[min_i, min_j] = quantity
        total_cost += quantity * costs[min_i, min_j]
        supply[min_i] -= quantity
        demand[min_j] -= quantity

    return allocation, total_cost

allocation, total_cost = minimum_cost_method(
    supply, demand_balanced, costs_balanced
)

print("Minimum Cost Method Allocation (balanced):")
print(allocation.astype(int))
print(f"Total cost (including dummy): Rs {int(total_cost)}")
</pre>

The algorithm scans the entire cost matrix to find the cheapest available route at each step. It allocates the maximum possible quantity to that route based on remaining supply and demand, then repeats until all supply is distributed. This greedy approach does not always produce the optimal solution, but it gives a good starting point that is often optimal for small problems.

Minimum Cost Method Allocation (balanced):
[[20 10  0  0]
 [20  0  0  0]
 [ 0 50 20  0]
 [ 0 10 30  0]]
Total cost (including dummy): Rs 1180

Verifying with Linear Programming

The Minimum Cost Method produced a cost of Rs 1180 for this problem. To verify this is optimal, I set up the transportation problem as a formal linear program and solved it with scipy.optimize.linprog, which uses the HiGHS solver under the hood.

from scipy.optimize import linprog

# Objective: minimize sum(costs[i,j] * x_ij) for real routes only
c = np.array([6, 8, 10, 9, 12, 13, 14, 16, 18])

# Supply constraints: sum of shipments from each factory less than or equal supply
A_ub = np.array([
    [1, 1, 1, 0, 0, 0, 0, 0, 0],  # Factory A
    [0, 0, 0, 1, 1, 1, 0, 0, 0],  # Factory B
    [0, 0, 0, 0, 0, 0, 1, 1, 1],  # Factory C
])
b_ub = np.array([30, 20, 50])

# Demand constraints: shipments to each center equal demand
A_eq = np.array([
    [1, 0, 0, 1, 0, 0, 1, 0, 0],  # Center D1
    [0, 1, 0, 0, 1, 0, 0, 1, 0],  # Center D2
    [0, 0, 1, 0, 0, 1, 0, 0, 1],  # Center D3
])
b_eq = np.array([40, 70, 30])

result = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=(0, None))
optimal_cost = int(result.fun)

print(f"LP Solver Result: Rs {optimal_cost}")
print(f"Scipy success: {result.success}")
print("Optimal allocation matrix:")
print(result.x.reshape(3, 3).astype(int))

The scipy result confirms that Rs 1180 is the true optimal cost. The Minimum Cost Method found the global optimum for this example. In larger problems, the MCM solution would be a starting point that could be improved using the Modified Distribution Method (MODI).

LP Solver Result: Rs 1180
Scipy success: True
Optimal allocation matrix:
[[20 10  0]
 [20  0  0]
 [ 0 50 20]]

Understanding the Optimal Shipping Plan

The optimal solution allocates shipments across four real routes. Here is the complete breakdown of the shipping plan and its cost.

factories = ['Factory A', 'Factory B', 'Factory C']
centers = ['Center D1', 'Center D2', 'Center D3']

optimal_alloc = result.x.reshape(3, 3)
print("Optimal Shipping Plan:")
print("=" * 50)
total = 0
for i, factory in enumerate(factories):
    for j, center in enumerate(centers):
        qty = int(optimal_alloc[i, j])
        if qty > 0:
            cost_per_unit = int(costs[i, j])
            route_cost = qty * cost_per_unit
            total += route_cost
            print(f"  {factory} to {center}: {qty} units "
                  f"x Rs {cost_per_unit} = Rs {route_cost}")

print("=" * 50)
print(f"Total Minimum Transportation Cost: Rs {total}")
print("Unmet Demand: 40 units (demand exceeded supply)")
print("  D1: fully satisfied | D2: fully satisfied | D3: 30 units unmet")

The shipping plan uses only four of the nine possible routes. Factory A splits its 30-unit capacity between D1 and D2. Factory B ships its entire 20-unit output to D1. Factory C dedicates all 50 units to D2. The remaining demand at D3 (20 units) is met by C, but 30 units of D3 demand remains unmet because total supply is insufficient.

Optimal Shipping Plan:
==================================================
  Factory A to Center D1: 20 units x Rs 6 = Rs 120
  Factory A to Center D2: 10 units x Rs 8 = Rs 80
  Factory B to Center D1: 20 units x Rs 9 = Rs 180
  Factory C to Center D2: 50 units x Rs 16 = Rs 800
==================================================
Total Minimum Transportation Cost: Rs 1180
Unmet Demand: 40 units (demand exceeded supply)
  D1: fully satisfied | D2: fully satisfied | D3: 30 units unmet

Real-World Applications

The transportation problem appears across logistics and supply chain management. A retail chain deciding how to distribute inventory from regional warehouses to individual stores is solving a transportation problem. A shipping company planning container routes between ports is solving the same problem at a larger scale. Even network routers use related algorithms to find the cheapest path for data packets through a network.

For small problems like the one in this article, the Minimum Cost Method with linear programming verification works well. For larger real-world problems with hundreds of suppliers and destinations, specialized libraries like PuLP provide a declarative interface for linear programming that scales better. PuLP supports multiple solvers including CBC (open-source) and Gurobi (commercial) for faster performance on very large instances.

FAQ

Q: What is the least cost transportation problem in Python?

The least cost transportation problem is a linear programming optimization where the goal is to minimize the total cost of shipping goods from multiple origins to multiple destinations, subject to supply limits at each origin and demand requirements at each destination. Python’s NumPy handles the matrix operations, and scipy.optimize.linprog solves it as a formal linear program to verify optimality.

Q: How does the Minimum Cost Method work?

The Minimum Cost Method repeatedly selects the route with the lowest transportation cost where both the supplier has remaining inventory and the demand center has unmet demand. It allocates as much as possible to that route based on the minimum of remaining supply and remaining demand, then updates the supply and demand arrays. The process repeats until all supply is distributed or all demand is satisfied.

Q: What happens when supply does not equal demand?

When total supply exceeds total demand, a dummy demand center is added with zero transportation costs to absorb the excess supply. When total demand exceeds total supply, a dummy supply row is added with zero costs to represent the unmet demand. This balancing allows the standard Minimum Cost Method and linear programming solvers to work without modification.

Q: Is the Minimum Cost Method always optimal?

The Minimum Cost Method is a heuristic that does not guarantee an optimal solution. For small, well-structured problems it often finds the global optimum. For larger or more complex problems, the initial solution from MCM may be suboptimal. In such cases, the Modified Distribution Method (MODI) can improve the initial solution step by step until no further cost reduction is possible.

Q: How do I solve large-scale transportation problems in Python?

For large-scale problems, Python’s PuLP library provides a declarative interface for linear programming. PuLP can model transportation problems with thousands of variables and constraints and supports commercial solvers like Gurobi for faster performance. SciPy’s scipy.optimize.linprog handles moderate-sized problems natively without additional dependencies.