Offensive Security Researcher & Quantum Cryptography Analyst

Transportation Planning Algorithm: Working, Explanation, and Logistics Optimization

Abdul Wahab Junaid
Transportation Planning algorithm and working of this algorithm

Transportation Planning algorithm and working of this algorithm

I want to frame this as the classic logistics question I’d face running a supply chain: I have several factories (supply points), each producing a fixed quantity of goods, and several warehouses or retailers (demand points), each requiring a fixed quantity. Shipping a unit from any given factory to any given warehouse has a known cost. How do I decide how much to ship from each factory to each warehouse so that all supply is used, all demand is met, and total shipping cost is minimized? This is the classical Transportation Problem, a foundational special case of linear programming that I find elegant because its structure allows for algorithms far simpler than general-purpose LP solvers.

History and Background

The problem was first formulated by the French mathematician Gaspard Monge in 1781, in the context of earth-moving (minimizing the cost of transporting soil), which is why the more general modern version of this idea is sometimes called the “Monge–Kantorovich transportation problem.” The modern operations-research treatment came from Frank L. Hitchcock, who formalized the problem mathematically in 1941, and independently from Tjalling Koopmans in 1947, whose work on the topic contributed to his later Nobel Memorial Prize in Economic Sciences (1975). George Dantzig then showed in the late 1940s and 1950s how the simplex method could be specialized into efficient transportation-specific algorithms, such as the Stepping Stone Method and the Modified Distribution (MODI) Method, which avoid needing a full general-purpose LP solver.

Problem Statement

I define it as: given $m$ supply sources with available quantities $a_1, \dots, a_m$, $n$ demand destinations with required quantities $b_1, \dots, b_n$ (with total supply equal to total demand, i.e., $\sum a_i = \sum b_j$, the “balanced” case), and a cost matrix $c_{ij}$ representing the cost of shipping one unit from source $i$ to destination $j$, determine the shipment quantities $x_{ij}$ that minimize total cost while fully satisfying every source’s supply and every destination’s demand.

Core Concepts

How It Works

  1. I confirm the problem is balanced (total supply = total demand); if not, I add a dummy row or column with zero shipping costs.
  2. I find an initial basic feasible solution using a construction heuristic — Vogel’s Approximation Method (VAM) tends to give a good starting point, though the simpler Northwest Corner Rule also works.
  3. I compute dual variables $u_i$ (for each source) and $v_j$ (for each destination) such that $u_i + v_j = c_{ij}$ for every basic (currently used) route, fixing one variable (commonly $u_1 = 0$) to anchor the system.
  4. For every non-basic (unused) route, I compute the opportunity cost $\Delta_{ij} = c_{ij} – (u_i + v_j)$.
  5. If all $\Delta_{ij} \geq 0$, the current solution is optimal, and I stop.
  6. Otherwise, I select the route with the most negative $\Delta_{ij}$, trace a closed loop through currently basic routes to determine how much flow can be shifted onto it, and update the solution accordingly.
  7. I repeat steps 3–6 until no negative $\Delta_{ij}$ remains.

Working Principle

The mechanism is a specialized form of the simplex method, exploiting the transportation problem’s particular structure: its constraint matrix is always totally unimodular, which guarantees that basic feasible solutions are automatically integer-valued whenever supplies and demands are integers — I never need to worry about fractional shipments appearing in an otherwise integer problem. The MODI method’s dual-variable trick lets me evaluate whether any unused route could improve the total cost without having to explicitly recompute the entire solution from scratch, which is what makes it so much faster than applying generic simplex machinery directly.

Mathematical Foundation

I formalize the problem as the linear program:

$$ \min \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij} x_{ij} $$

subject to

$$ \sum_{j=1}^{n} x_{ij} = a_i \quad \forall i, \qquad \sum_{i=1}^{m} x_{ij} = b_j \quad \forall j, \qquad x_{ij} \geq 0 $$

The dual variables satisfy, for every basic variable $x_{ij} > 0$:

$$ u_i + v_j = c_{ij} $$

and the optimality condition for every non-basic route is:

$$ \Delta_{ij} = c_{ij} – u_i – v_j \geq 0 $$

If some $\Delta_{ij} < 0$, I know the solution can still be improved by rerouting flow along a loop that includes that route.

Diagrams

flowchart TD
    Start([Start: supply, demand, cost matrix]) --> Balance{Supply = Demand?}
    Balance -- No --> Dummy[Add dummy source/destination]
    Balance -- Yes --> Initial
    Dummy --> Initial[Build initial feasible solution: VAM/Northwest Corner]
    Initial --> Dual[Compute dual variables u_i, v_j]
    Dual --> Opp[Compute opportunity costs for non-basic routes]
    Opp --> OptCheck{All opportunity costs >= 0?}
    OptCheck -- Yes --> End([Optimal solution found])
    OptCheck -- No --> Loop[Trace closed loop, shift flow, update solution]
    Loop --> Dual

Pseudocode

function TransportationProblem(supply[1..m], demand[1..n], cost[1..m][1..n]):
    if sum(supply) != sum(demand):
        add dummy source or destination with zero cost to balance

    x = InitialFeasibleSolution(supply, demand, cost)  // e.g., Vogel's Approximation

    loop:
        (u, v) = ComputeDualVariables(x, cost)  // u_i + v_j = cost[i][j] for basic cells

        bestDelta = 0
        bestCell = none
        for each non-basic cell (i, j):
            delta = cost[i][j] - (u[i] + v[j])
            if delta < bestDelta:
                bestDelta = delta
                bestCell = (i, j)

        if bestCell == none:
            return x  // optimal

        loop_path = FindClosedLoop(x, bestCell)
        theta = min shipment among the "minus" corners of loop_path
        update x by adding theta along "plus" corners and subtracting along "minus" corners

    return x

Step-by-Step Example

Using the diagram above: Source 1 supplies 20, Source 2 supplies 30 (total 50). Destination 1 needs 15, Destination 2 needs 25, Destination 3 needs 10 (total 50) — balanced.

Costs: S1-D1=4, S1-D2=6, S1-D3=9, S2-D1=8, S2-D2=5, S2-D3=3.

Using the Least Cost Method for an initial solution:

Initial solution: S1-D1=15, S1-D2=5, S2-D2=20, S2-D3=10. Cost = 15(4) + 5(6) + 20(5) + 10(3) = 60 + 30 + 100 + 30 = 220.

Checking optimality with MODI: setting $u_1=0$, from S1-D1: $v_1 = 4$. From S1-D2: $v_2 = 6$. From S2-D2: $u_2 + 6 = 5 \Rightarrow u_2 = -1$. From S2-D3: $-1 + v_3 = 3 \Rightarrow v_3 = 4$.

Checking non-basic cell S1-D3: $\Delta = 9 – (0+4) = 5 \geq 0$. Checking S2-D1: $\Delta = 8 – (-1+4) = 5 \geq 0$. All opportunity costs are non-negative, so this initial solution is already optimal.

Final optimal cost: 220.

Time Complexity

Finding an initial feasible solution via Vogel’s Approximation Method takes roughly $O(m \cdot n \cdot \min(m,n))$ in a straightforward implementation. Each iteration of the MODI optimality-improvement loop takes $O(mn)$ to compute dual variables and opportunity costs, and $O(m+n)$ to trace a closed loop; the number of iterations needed is typically small in practice but can be bounded by $O(mn)$ in the worst case, giving an overall worst-case complexity around $O(m^2n^2)$, though in practice it converges much faster, similar to how simplex behaves in practice despite worse theoretical worst-case bounds.

Space Complexity

I need $O(mn)$ space to store the cost matrix and the current shipment solution matrix, plus $O(m+n)$ for the dual variable arrays — overall space is $O(mn)$, dominated by the cost and allocation matrices.

Correctness Analysis

Correctness follows from linear programming duality theory: the MODI method is a specialization of the simplex method applied to the transportation problem’s particular constraint structure. The optimality condition — all opportunity costs $\Delta_{ij} \geq 0$ — is exactly the complementary slackness / dual feasibility condition from LP duality theory, which guarantees that once satisfied, the current solution is provably optimal, not merely locally good. The total unimodularity of the transportation constraint matrix additionally guarantees that every basic feasible solution found along the way is integer-valued whenever supplies and demands are integers, so the method never needs separate integer-programming machinery to get whole-unit shipments.

Advantages

Disadvantages

Applications

Implementation in C

#include <stdio.h>

#define M 2  // number of sources
#define N 3  // number of destinations

int main() {
    int supply[M] = {20, 30};
    int demand[N] = {15, 25, 10};
    int cost[M][N] = {
        {4, 6, 9},
        {8, 5, 3}
    };
    int allocation[M][N] = {0};

    int s[M], d[N];
    for (int i = 0; i < M; i++) s[i] = supply[i];
    for (int j = 0; j < N; j++) d[j] = demand[j];

    // Least Cost Method for initial feasible solution
    int visited[M][N] = {0};
    int totalCost = 0;

    for (int step = 0; step < M + N - 1; step++) {
        int minCost = 1000000, mi = -1, mj = -1;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (!visited[i][j] && s[i] > 0 && d[j] > 0 && cost[i][j] < minCost) {
                    minCost = cost[i][j];
                    mi = i;
                    mj = j;
                }
            }
        }
        if (mi == -1) break;

        int qty = (s[mi] < d[mj]) ? s[mi] : d[mj];
        allocation[mi][mj] = qty;
        totalCost += qty * cost[mi][mj];
        s[mi] -= qty;
        d[mj] -= qty;

        if (s[mi] == 0) {
            for (int j = 0; j < N; j++) visited[mi][j] = 1;
        }
        if (d[mj] == 0) {
            for (int i = 0; i < M; i++) visited[i][mj] = 1;
        }
    }

    printf("Allocation matrix:\n");
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++)
            printf("%d\t", allocation[i][j]);
        printf("\n");
    }
    printf("Total transportation cost: %d\n", totalCost);

    return 0;
}

Sample Input and Output

Input: the supply, demand, and cost matrix defined above.

Output:

Allocation matrix:
15	5	0
0	20	10
Total transportation cost: 220

This matches my manual walkthrough — the Least Cost Method already produces the optimal solution here, with total cost 220.

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version