O'Reilly logo

Algorithms in a Nutshell by Gary Pollice, Stanley Selkow, George T. Heineman

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Transshipment

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.

Solution

We convert the Transshipment problem instance into ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required