Algorithms in a Nutshell

Transshipment

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 are w warehouse stations w_k, each capable of receiving and reshipping (known as "transshipping") a maximum max_k units of the commodity at the fixed warehouse processing cost of wp_k per unit. There is a fixed shipping cost of d(i, j) for each unit shipping from supply station s_i to demand stations t_j, a fixed transshipping cost of ts(i, k) for each unit shipped from supply station s_i to warehouse station w_k, and a fixed transshipping cost of ts(k, j) for each unit shipped from warehouse station w_k to demand station t_j. The goal is to determine the flow f(i, j) of units from supply station s_i to demand station t_j that minimizes the overall total cost, which can be concisely defined as:

Total Cost (TC) = Total Shipping Cost (TSC) + Total Transshipping Cost (TTC)

TSC = Σ i Σ j d(i, j)*f(i, j)

TTC = Σ i Σ k ts(i, k)*f(i, k)+ Σ j Σ k ts(j, k)*f(j, k)

The goal is to find integer values for f(i, j)≥0 that ensure that TC is a minimum while meeting all of the supply and demand constraints. Finally, the net flow of units through a warehouse must be zero, to ensure that no units are lost (or added!). The supplies sup(s_i) and demands dem(t_i) are all greater than 0. The shipping costs d(i, j), ts(i, k), and ts(k, j) may be greater than or equal to zero.

Solution

We convert the Transshipment problem instance into ...