The transshipment problem is very similar to the transportation problem. It has supply nodes where goods enter the network and demand nodes where goods leave the network. However, it also has *transshipment nodes* where goods neither enter nor leave, but shipments may be assembled or divided before being shipped onwards. The set of all nodes . Unlike the transportation problem, the transshipment problems does not assume there are any arcs present in the network, rather the set of arcs must be defined explicitly. Figure 1 shows an example transshipment network from the American Steel Transshipment Problem.

**Figure 1** The transshipment network from the American Steel Transshipment Problem

In Figure 1 = { Youngstown, Pittsburgh }, = { Albany, Houston, Tempe, Gary }, = { Cincinnati, Kansas City, Chicago }.and = { (Youngstown, Albany), (Youngstown, Cincinnati), (Youngstown, Kansas City), (Youngstown, Chicago), (Pittsburgh, Cincinnati), (Pittsburgh, Kansas City), (Pittsburgh, Chicago), (Pittsburgh, Gary), (Cincinnati, Albany), (Cincinnati, Houston), (Kansas City, Houston), (Kansas City, Tempe), (Chicago, Tempe), (Chicago, Gary) }.

There is a supply of goods at each supply node, a demand for goods at each demand node and a cost for shipping goods along each arc.

In a transshipment problem we need to decide what quantity of goods to deliver along each arc to minimise the total cost of delivering goods.

Transshipment problem are network optimisation problems. Network optimisation problems are solved using mathematical programming. Thus, to formulate a transshipment problem we use the 4 steps for formulating a mathematical programme:

- Identify the Decision Variables
- Formulate the Objective Function
- Formulate the Constraints
- Identify the Data

The decision variables in the transshipment problem are the flow (cf. the transportation problem). The flow may be restricted by a lower bound or upper bound on the flow along the arc .

The objective of the transshipment problem is to minimise the total cost of delivering goods through the network. The cost of shipping a flow of along arc is given by . For the problems we consider here, the cost is linear so . The total cost is so the objective function is

The constraints for the transshipment problem are straightforward:

- Flow out of a supply node is less than the supply available;
- Flow must be conserved at transshipment nodes;
- Flow into a demand node is more than the demand requested.

Given values for supply and demand , we can formulate these constraints:

The transshipment problem formulation is:

The data needed is:

- the set of nodes , split into 3 subsets ;
- the set of arcs ;
- the supply and demand values, ;
- the shipping costs ;
- the bounds on flow .

Transshipment problem formulations can also be expressed in *network form*. The nodes and arcs are drawn explicitly with the shipping cost and flow bounds shown for each arc. To represent the supply (respectively demand) a *source* (*sink*) node is added with new arcs from the source node to the supply nodes (from the demand nodes to the sink node). The bounds on these arcs represent the supply (demand) at the supply (demand) nodes.explicitly. Figure 2 shows the network formulation for the the American Steel Transshipment Problem.

**Figure 2** The network formulation for the American Steel Transshipment Problem

Rather than split the nodes into three disjoint sets with associated constraints, we can redefine the supply and demand constants to allow for one flow conservation constraint for all the nodes. We will show how to do this in a couple of steps. First, we consider all the flow into a node, i.e., the flow from other nodes + the supply at the node. This must be more than the flow out of a node, i.e., the flow to other nodes + the demand at the node, as we cannot create flow out of thin air. Figure 3 shows the new constraint and an example of how flow into a node, 10 (flowing in) + 10 (supply), equals flow out of a node, 20 (flowing out).

**Figure 3** An alternative flow conservation constraint

The allows flow to disappear out of the network at any node, but it will cost money to send flow to any nodes other than the supply node, so the "disappearing flow" should not be present in any optimal flow solution.

Also, both supply and demand will not be present at any node, so we can consider the *net* demand instead of both supply and demand. As long as the *net* flow into a node is greater than the net demand at the node our flow solution is feasible. Figure 4 shows the new constraint and an example of how the net flow into a node, 10 (flowing in) - 20 (flowing out), equals net demand at the node, -10.

**Figure 4** Another alternative flow conservation constraint

Now from the original formulation are replaced by net demand over all the nodes:

The alternative transshipment problem formulation is:

The transshipment problem is often an integer programme as the quantity of goods delivered along the arcs must be integer. However, **if the supply, demand and variable bounds** are integer, then (like the transportation problem) the transshipment problem will have *naturally integer* solutions. This means that any solution found using **linear** programming will have integer values.

To see examples of transshipment problems, check out some of the transshipment problem case studies:

\usepackage{amsmath} Case Study: Submitted: Operations Research Topics: Application Areas: Contents Problem Description Problem Description Return...

Number of topics: 2

-- MichaelOSullivan - 08 Apr 2008

Topic revision: r20 - 2008-04-27 - MichaelOSullivan

Copyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback