(r19) TransshipmentProblem < OpsRes

Tags: view all tags
%BEGINLATEXPREAMBLE%
\usepackage{amsmath} 
%ENDLATEXPREAMBLE%


---+ The Transshipment Problem 

The transshipment problem is very similar to the [[TransportationProblem][transportation problem]]. It has supply nodes %${\cal S}$% where goods enter the network and demand nodes %${\cal D}$% where goods leave the network. However, it also has _transshipment nodes_ %${\cal T}$% where goods neither enter nor leave, but shipments may be assembled or divided before being shipped onwards. The set of all nodes %${\cal N} = {\cal S} \cup {\cal T} \cup {\cal D}$%. Unlike the transportation problem, the transshipment problems does not assume there are any arcs present in the network, rather the set of arcs %${\cal A} \subseteq {\cal N} \times {\cal N}$% must be defined explicitly. [[#fig1][Figure 1]] shows an example transshipment network from the [[AmericanSteelTransshipmentProblem][American Steel Transshipment Problem]].

<a name="fig1"></a> *Figure 1* The transshipment network from the [[AmericanSteelTransshipmentProblem][American Steel Transshipment Problem]]

<img src="%ATTACHURLPATH%/steel_network.jpg" alt="steel_network.jpg" width='509' height='328' />

In [[#fig1][Figure 1]] %${\cal S}$% = { Youngstown, Pittsburgh }, %${\cal D}$% = { Albany, Houston, Tempe, Gary }, %${\cal T}$% = { Cincinnati, Kansas City, Chicago }.and %${\cal A}$% = { (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.

---++ Formulating the Transshipment Problem

Transshipment problem are network optimisation problems. [[NetworkOptimisation][Network optimisation]] problems are solved using [[MathematicalProgramming][mathematical programming]]. Thus, to formulate a transshipment problem we use the 4 steps for formulating a mathematical programme:
   1 Identify the Decision Variables
   1 Formulate the Objective Function
   1 Formulate the Constraints
   1 Identify the Data

---+++ Identify the Decision Variables

The decision variables in the transshipment problem are the flow %$x_{ij}, (i, j) \in {\cal A}$% (cf. the transportation problem). The flow may be restricted by a lower bound %$l_{ij}$% or upper bound %$u_{ij}$% on the flow along the arc %$(i, j) \in {\cal A}$%.

---+++ Formulate the Objective Function

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 %$x$% along arc %$(i, j)$% is given by %$c_{ij}(x)$%. For the problems we consider here, the cost is linear so %$c_{ij}(x) = c_{ij} x$%. The total cost is %$\sum_{(i, j) \in {\cal A}} c_{ij} x_{ij}$% so the objective function is
%\[ \min \sum_{(i, j) \in {\cal A}} c_{ij} x_{ij} \]%

---+++ Formulate the Constraints

The constraints for the transshipment problem are straightforward:
   1 Flow out of a supply node is less than the supply available;
   2 Flow must be conserved at transshipment nodes;
   3 Flow into a demand node is more than the demand requested.

Given values for supply %$s_i, i \in {\cal S}$% and demand %$d_j, j \in {\cal D}$%, we can formulate these constraints:

   1 %$\displaystyle \sum_{(i, j) \in {\cal A}} x_{ij} \leq s_i, i \in {\cal S}$%
   2 %$\displaystyle \sum_{(i, j) \in {\cal A}} x_{ij} = \sum_{(j, k) \in {\cal A}} x_{jk} , j \in {\cal T}$%
   3 %$\displaystyle \sum_{(i, j) \in {\cal A}} x_{ij} \geq d_j, j \in {\cal D}$%

---+++ Identify the Data

The transshipment problem formulation is:
%\[ \begin{array}{r@{\,}r@{\,}l}
\min & \displaystyle \sum_{(i, j) \in {\cal A}} c_{ij} & x_{ij} \\
\text{subject to} & \displaystyle \sum_{(i, j) \in {\cal A}} & x_{ij} \leq s_i, i \in {\cal S} \\
                         & \displaystyle \sum_{(i, j) \in {\cal A}} & x_{ij} = \displaystyle \sum_{(j, k) \in {\cal A}} x_{jk} , j \in {\cal T} \\
                         & \displaystyle \sum_{(i, j) \in {\cal A}} & x_{ij} \geq d_j, j \in {\cal D} \\
                         & l_{ij} \leq & x_{ij} \leq u_{ij}, (i, j) \in {\cal A}
\end{array}
\]%

The data needed is:
   1 the set of nodes %${\cal N}$%, split into 3 subsets %${\cal S}, {\cal T}, {\cal D}$%;
   2 the set of arcs %{\cal A}$%;
   3 the supply and demand values, %$s_i, i \in {\cal S}, d_j, j \in {\cal D}$%;
   4 the shipping costs %$c_{ij}, (i, j) \in {\cal A}$%;
   5 the bounds on flow %$l_{ij}, u_{ij}, (i, j) \in {\cal A}$%.

---++ Network Formulation

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. [[#fig2][Figure 2]] shows the network formulation for the the [[AmericanSteelTransshipmentProblem][American Steel Transshipment Problem]].

<a name="fig2"></a> *Figure 2* The network formulation for the [[AmericanSteelTransshipmentProblem][American Steel Transshipment Problem]]

<img src="%ATTACHURLPATH%/steel_formulation.jpg" alt="steel_formulation.jpg" width='593' height='280' />

---++ Alternative Formulation

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. [[#fig3][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).

<a name="fig3"></a> *Figure 3* An alternative flow conservation constraint

<img src="%ATTACHURLPATH%/ship_alt1.jpg" alt="ship_alt1.jpg" width='466' height='293' />

The %$\geq$% 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 %$\hat{d}_j, j \in {\cal N}$% 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. [[#fig4][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.

<a name="fig4"></a> *Figure 4* Another alternative flow conservation constraint

<img src="%ATTACHURLPATH%/ship_alt2.jpg" alt="ship_alt2.jpg" width='415' height='298' />

Now %$s_i, i \in {\cal S}, d_j, j \in {\cal D}$% from the original formulation are replaced by net demand over all the nodes:
%\[ \hat{d}_j = \begin{cases} -s_j & j \in {\cal S} \\
d_j & j \in {\cal D} \\
0 & j \in {\cal T} \end{cases}, j \in {\cal N} \]%

The alternative transshipment problem formulation is:
%\[ \begin{array}{r@{\,}r@{\,}l}
\min & \displaystyle \sum_{(i, j) \in {\cal A}} c_{ij} & x_{ij} \\
\text{subject to} & \displaystyle \sum_{(i, j) \in {\cal A}} & x_{ij} - \displaystyle \sum_{(j, k) \in {\cal A}} x_{jk} \geq \hat{d}_j, j \in {\cal N} \\
                         & l_{ij} \leq & x_{ij} \leq u_{ij}, (i, j) \in {\cal A}
\end{array}
\]%

---++ Naturally Integer Solutions

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 [[TransportationProblem][transportation problem]]) the transshipment problem will have _naturally integer_ solutions. This means that any solution found using *linear* programming will have integer values.

---++ Solving the Transshipment Problem with OR Software
   * [[TransshipmentProblemInAMPL][Using AMPL/CPLEX]]

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

%SEARCH{
"[O]perationsResearchTopics.*value\=.*[T]ransshipmentProblem"
type="regex"
casesensitive="on"
nosearch="on"
}%


-- Main.MichaelOSullivan - 08 Apr 2008
Topic revision: r19 - 2008-04-22 - TWikiAdminUser
~~Edit~~
~~Attach~~