Algorithms in a Nutshell

Transportation

The Transportation problem is simpler than the Transshipment problem because there are no intermediate warehouse nodes. There exists m supply stations s_i, each capable of producing sup(s_i) units of a commodity. There are n demand stations t_j, each demanding dem(t_j) units of the commodity. There is a fixed per-unit cost d(i, j)≥0 associated with transporting a unit over the edge (i, j). The goal is to determine the flow f(i, j) of units from supply stations s_i to demand stations t_j that minimizes the overall transportation cost, TSC, which can be concisely defined as:

Total Shipping Cost (TSC) = Σ i Σ j d(i, j)*f(i, j)

The solution must also satisfy both the total demand for each demand station t_j and the supply capabilities for supply stations s_i.

Solution

We convert the Transportation problem instance into a Transshipment problem instance with no intermediate warehouse nodes.