Solve the transportation problem in Python

The transportation problem is a staple: you have supplies at several sources, demands at several destinations, and a per-unit shipping cost for each source–destination pair. You want the shipping plan that meets every demand at minimum total cost. With quicopt it is a short linear program (LP) in Python.

The naive approach

The classic hand methods — northwest-corner, least-cost, Vogel's approximation — produce a feasible plan, but not necessarily the cheapest, and they are fiddly to code. Since the problem is linear, solve it for the exact optimum instead.

Model it as an LP

A continuous variable x[i][j] is the amount shipped from source i to destination j. Supply and demand rows must balance, and the objective sums the shipping cost:

from ortools.math_opt.python import mathopt
from quicopt import Client

# Ship units from supplies to demands at minimum total cost (balanced).
supply = [20.0, 30.0, 25.0]
demand = [15.0, 25.0, 20.0, 15.0]
cost = [[8, 6, 10, 9], [9, 12, 13, 7], [14, 9, 16, 5]]
S, D = len(supply), len(demand)

model = mathopt.Model(name="transportation")
x = [[model.add_variable(lb=0.0, name=f"x_{i}_{j}") for j in range(D)] for i in range(S)]
for i in range(S):
    model.add_linear_constraint(sum(x[i][j] for j in range(D)) == supply[i])
for j in range(D):
    model.add_linear_constraint(sum(x[i][j] for i in range(S)) == demand[j])
model.minimize(sum(cost[i][j] * x[i][j] for i in range(S) for j in range(D)))

client = Client("https://try.quicoptapi.pgi.fz-juelich.de")
print(client.solve(model).display)

├── status:     optimal
├── feasible:   true
├── objective:  635.0
├── x:          x_0_0=0, x_0_1=15, x_0_2=5, x_0_3=0, x_1_0=15, x_1_1=0, …  (12 variables)
└── solve_time: 0.0023 s

What you get

status: optimal means the plan is proven minimum-cost — total cost 635, found in a couple of milliseconds. The transportation problem is totally unimodular, so the LP already returns whole-unit shipments without needing integer variables.

The same model scales from a 3×4 grid to thousands of routes — you change the data, not the method.

Next

• The problem class behind this: Linear programming (LP)
• A runnable model for every supported class: Examples
• Set up the client and solve your first model: Getting started

Reference: F. L. Hitchcock, The Distribution of a Product from Several Sources to Numerous Localities, Journal of Mathematics and Physics, 1941.