There exists m supply stations si, each capable of producing sup(si) units of a commodity. There are n demand stations tj, each demanding dem(tj) units of the commodity. There are w warehouse stations wk, each capable of receiving and reshipping (known as "transshipping") a maximum maxk units of the commodity at the fixed warehouse processing cost of wpk per unit. There is a fixed shipping cost of d(i, j) for each unit shipping from supply station si to demand stations tj, a fixed transshipping cost of ts(i, k) for each unit shipped from supply station si to warehouse station wk, and a fixed transshipping cost of ts(k, j) for each unit shipped from warehouse station wk to demand station tj. The goal is to determine the flow f(i, j) of units from supply station si to demand station tj 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(si) and demands dem(ti) 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.
We convert the Transshipment problem instance into ...