Algorithms in a Nutshell

Transportation | 247

Network Flow

Algorithms

warehouse stationwk, and a fixed transshipping cost ofts(k,j) for each unit

shipped from warehouse stationwkto demand stationtj. The goal is to determine

the flowf(i,j) of units from supply stationsito demand stationtjthat minimizes

the overall total cost, which can be concisely defined as:

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

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

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

The goal is to find integer values forf(i,j)≥0 that ensure thatTCis 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 suppliessup(si) and demandsdem(ti) are all greater than 0. The ship-

ping costsd(i,j),ts(i,k), andts(k,j) may be greater than or equal to zero.

Solution

We convert the Transshipment problem instance into a Minimum Cost Flow

problem instance (as illustrated in Figure 8-8) by constructing a graphG=(V,E)

such that:

V contains n+m+2*w+2 vertices

Each supply stationsimaps to a vertex numberedi. Each warehousewkmaps

to two different vertices, one numberedm+2*k–1 and one numberedm+2*k.

Each demand stationtjmaps to 1+m+2*w+j. Create a new source vertexsrc

(labeled 0) and a new target vertextgt (labeledn+m+2*w+1).

E contains (w+1)*(m+n)+m*n+w edges

The process for constructing edges from the Transshipment problem instance

can be found in theTransshipment class in the code repository.

Once the Minimum Cost Flow solution is available, the transshipment schedule

can be constructed by locating those edges (u,v)∈Ewhosef(u,v)>0. The cost of

the schedule is the sum total off(u,v)*d(u,v) for these edges.

Transportation

The Transportation problem is simpler than the Transshipment problem because

there are no intermediate warehouse nodes. There existsmsupply stationssi, each

capable of producingsup(si) units of a commodity. There arendemand stationstj,

each demandingdem(tj) 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 deter-

mine the flowf(i,j) of units from supply stationssito demand stationstjthat

minimizes the overall transportation cost,TSC, which can be concisely defined as:

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

The solution must also satisfy both the total demand for each demand stationtj

and the supply capabilities for supply stationssi.

Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.

Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use