# Optimization Techniques for Design Problems in Selected Areas in WSNs: A Tutorial
## 4 Network Flow Programming Models
### Special Classes of NFPs
#### 4.2.3 Transshipment Problem  
A transportation problem allows only shipments that go directly from a supply point to a demand point. In many situations, shipments may be allowed between supply points or demand points. Sometimes there may also be points, called transshipment points, through which goods can be transshipped on their journey from a supply node to a demand node. Basically a transshipment node differs from a supply or demand node in that it can both receive and send goods. This type of shipping problems is known as transshipment problems, for which the optimal solution can be obtained by solving a transportation problem.  
In general we say that there are \(m\) pure supply points, \(n\) pure demand points, and \(p\) transshipment points. For an NFP model, a pure supply point would have only leaving arcs whereas a pure demand point would have only entering arcs. We let \(s_{T}\) be the total supply available for the problem i.e., \(s_{T}=\sum_{i=1}^{m+p}s_{i}\), and we let \(t_{k}\) be the net stock position at transshipment node \(k\) for \(k=1,...,p\). If stock is supplied at node \(k\), then \(t_{k}\) is positive, and if stock is demanded at node \(k\), then \(t_{k}\) is negative. In the example in Figure 6, \(m=n=p=3\), with \(s_{T}=17\). The basic steps for solving a transshipment problem would be:  
Figure 6a illustrates the graph of an example of a transshipment problem. It can be noticed that the transshipment problem has an NFP model that is not bipartite. However, a transshipment problem can be transformed into a balanced transportation problem yielding an associated NFP model that is bipartite, whose tableau is illustrated in Figure 6b.  
1. If necessary, put the problem into balanced form by adding either a dummy supply point to meet the excess demand or a dummy demand point to absorb the excess supply. Shipments to or from the dummy node will have zero shipping cost.
2. Construct a transportation tableau with \(m+p\) rows, one for each supply point and transshipment point, and \(n+p\) columns, one for each demand point and transshipment point. Each pure supply point \(i\) will have a supply equal to its original value \(s_{i}\). and each pure demand point \(j\) will have a demand equal to its original value \(d_{i}\). Each transshipment point will have a supply equal to \(s_{k}=t_{k}+s_{T}\) and a demand equal to \(d_{k}=s_{T}\).
3. A large cost \(M\) is assigned to shipments that are not permissible. A shipment is allowed from a transshipment point to itself and assigned a unit transportation cost of zero i.e., include \(x_{kk}\) in the model and set \(c_{kk}\) equal to zero for \(k=1,...,p\). The transformed model for the example is shown in Figure 6b.
4. Obviously, the transportation simplex can then be used to solve the problem.  
**Example for a Possible Application to WSN**: This kind of problem can be used to model a WSN sensor network where the source nodes are the ones that do the sensing of the required phenomena  
Figure 6: An illustrative example of a simple transportation problem. (**a**) NFP model of a transshipment problem; (**b**) Tableau of a transshipment problem.  
and the demand points are the sink nodes, as earlier explained for the classic transportation problem. The transshipment nodes can be relaying sensors that receive and forward the transmission from one sensor node to another as in Figure 6. The objective can be the minimization the of overall delay where the cost \(c_{ij}\) of of each arc represents the amount of delay per unit throughput, i.e., \((s^{2}/b)\), and the decision variable \(x_{ij}\) represents the flow in bps, The demand constraints represent the target throughput each sink node should receive. The objective function is the sum of the delays \(c_{ij}x_{ij}\) on all arcs.