Algorithm
Development Kit 1.0

algs.model.network
Class Transshipment

java.lang.Object
  extended by algs.model.network.FlowNetwork<EdgeInfo[][]>
      extended by algs.model.network.FlowNetworkArray
          extended by algs.model.network.Transshipment
Direct Known Subclasses:
Transportation

public class Transshipment
extends FlowNetworkArray

Given a network having sources S, intermediate "warehouse" nodes W, and demanders D, edge capacities c(i,j), edge costs costs[i][j] with m=|S| suppliers and n=|D| demanders, construct a flow, if one exists, which minimizes costs.

Note that w=|W| and there are costs associated with the warehouse nodes as well as potential capacity maxima.

The resulting Flow Network has m + n + 2*w + 2 nodes. Note that the shipping "cost" from the virtual new source and new target are zero. All edges store the shipping cost, in addition to the flow and capacity constraints.

It is assumed that the dimensions of costs matches the respective dimensions of the sup and dem vectors.

If a particular shipment is not possible (or simply not selected) then the cost should be Integer.MAX_VALUE.


Field Summary
 int m
          Number of suppliers.
 int n
          Number of demanders.
 int w
          Number of intermediate warehouses.
 
Fields inherited from class algs.model.network.FlowNetwork
numVertices, sinkIndex, sourceIndex
 
Constructor Summary
Transshipment(int[] sup, int[] dem, int[][] sup_transship, int[] warehouse_costs, int[] warehouse_limits, int[][] dem_transship, int[][] costs)
          Construct an instance of the Transshipment problem.
 
Method Summary
 int getCost()
          Return the computed minimum cost for this solution.
 void output()
          Output the solution grid.
 
Methods inherited from class algs.model.network.FlowNetworkArray
edge, getEdgeStructure, getFlow, getMinCut, populate, toString, validate
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

m

public final int m
Number of suppliers.


w

public final int w
Number of intermediate warehouses.


n

public final int n
Number of demanders.

Constructor Detail

Transshipment

public Transshipment(int[] sup,
                     int[] dem,
                     int[][] sup_transship,
                     int[] warehouse_costs,
                     int[] warehouse_limits,
                     int[][] dem_transship,
                     int[][] costs)
Construct an instance of the Transshipment problem.

Accepts zero warehouse information, in which case this reduces to the Transportation problem.

Parameters:
sup - vector of the supply capability of suppliers
dem - vector of the demand requested by the demanders
sup_transship - vector of shipment costs from suppliers to each warehouse
warehouse_costs - vector of costs just for going through warehouse(s)
warehouse_limits - vector of capacity for going through warehouse
dem_transship - vector of shipment costs from each warehouse to demanders
costs - matrix of cost in shipping from sup[i] to dem[j] without going through any warehouse.
Throws:
java.lang.IllegalArgumentException - if array boundaries are invalid
Method Detail

getCost

public int getCost()
Return the computed minimum cost for this solution.

Overrides:
getCost in class FlowNetworkArray

output

public void output()
Output the solution grid.


Algorithm Development Kit 1.0

This code supports the Algorithms in a Nutshell book, published by O'Reilly Media, Inc. in November 2008. Please visit the book web page to learn of any changes to the code repository or to record a potential defect.