and k to l respectively. We further have

$X{1}_{ij}=x{1}_{ij}/\left[\underset{l=1}{\overset{L}{\sum }}{D}_{l}\right],\text{\hspace{0.17em}}X{2}_{jk}=x{2}_{jk}/\left[\underset{l=1}{\overset{L}{\sum }}{D}_{l}\right],\text{\hspace{0.17em}}X{3}_{kl}=x{3}_{kl}/\left[\underset{l=1}{\overset{L}{\sum }}{D}_{l}\right]$

Primal of the problem can be formulated as under ?

2.3. Primal (P)

Minimize:

$\underset{i=1}{\overset{I}{\sum }}\underset{j=1}{\overset{J}{\sum }}C{1}_{ij}X{1}_{ij}+\underset{j=1}{\overset{J}{\sum }}\underset{k=1}{\overset{K}{\sum }}C{2}_{jk}X{2}_{jk}+\underset{k=1}{\overset{K}{\sum }}\underset{l=1}{\overset{L}{\sum }}C{3}_{kl}X{3}_{kl}$ (1)

Subject to:

$\underset{i=1}{\overset{I}{\sum }}\underset{j=1}{\overset{J}{\sum }}X{1}_{ij}=1\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i\in I,j\in J$ (2)

$\underset{j=1}{\overset{J}{\sum }}\underset{k=1}{\overset{K}{\sum }}X{2}_{jk}=1\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall j\in J,k\in K$ (3)

$\underset{k=1}{\overset{K}{\sum }}\underset{l=1}{\overset{L}{\sum }}X{3}_{kl}=1\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall k\in K,l\in L$ (4)

$-\underset{j;\left(i,j\right)\in N}{\sum }X{1}_{ij}\ge -{s}_{i}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i\in I$ (5)

$-\underset{k;\left(k,l\right)\in N}{\sum }X{3}_{kl}\ge -{d}_{l}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall l\in L$ (6)

$\underset{k;\left(j,k\right)\in N}{\sum }X{2}_{jk}-\underset{i;\left(i,j\right)\in N}{\sum }X{1}_{ij}=0\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall j\in J$ (7)

$\underset{l;\left(k,l\right)\in N}{\sum }X{3}_{kl}-\underset{j;\left(j,k\right)\in N}{\sum }X{2}_{jk}=0\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall k\in K$ (8)

$X{1}_{ij},X{2}_{jk},X{3}_{kl}\ge 0\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i\in I,j\in J,k\in K$ and $l\in L$ (9)

In this formulation we assume forward unidirectional flows. Equation (1) minimizes the cost of transportation of units from source nodes to sink nodes while satisfying the supply and demand constraints. Equation (2) ensures that entire supply is transported from supply nodes to meet the demand, which is valid for the balanced problem. Equation (3) and Equation (4) ensures that the entire supply is transported between the layers of transshipment nodes and demand nodes respectively. Equation (5) and Equation (6) are supply and demand constraints respectively. Equation (7) and equation (8) ensures that no inventory is accumulated on any transshipment nodes. Equation (9) is the non-negativity constraint.

2.4. Dual of the Problem (DP)

In this section we present the dual of the problem P. We associate $V1,V2,V3,{U}_{i},{V}_{l},W{1}_{j},W{2}_{k}$ as the dual variables corresponding to (2), (3), (4), (5), (6), (7) and (8) respectively. We first state the dual of the problem as DP and then divide it into two parts as DP1 and DP2 for computational simplicity.

1) DP

Maximize:

$V1+V2+V3-\underset{i\in I}{\sum }{s}_{i}{U}_{i}-\underset{l\in L}{\sum }{d}_{l}{V}_{l}$ (10)

Subject to:

$V1-{U}_{i}-W{1}_{j}\le C{1}_{ij}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i\in I,j\in J$ (11)

$V2+W{1}_{j}-W{2}_{k}\le C{2}_{jk}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall j\in J,k\in K$ (12)

$V3-{V}_{l}+W{2}_{k}\le C{3}_{kl}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall k\in K,l\in L$ (13)

${U}_{i},{V}_{l}\ge 0$ , $V1,V2,V3,W{1}_{j},W{2}_{k}$ unrestricted (14)

2) DP1

Maximize:

$V1+V2-\underset{i\in I}{\sum }{s}_{i}{U}_{i}$ (15)

Subject to:

$V1-{U}_{i}-W{1}_{j}\le C{1}_{ij}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i\in I,j\in J$ (16)

$V2+W{1}_{j}-W{2}_{k}\le C{2}_{jk}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall j\in J,k\in K$ (17)

${U}_{i}\ge 0$ , $V1,V2,W{1}_{j},W{2}_{k}$ unrestricted (18)

3) DP2

Maximize:

$V3-\underset{l\in L}{\sum }{d}_{l}{V}_{l}$ (19)

Subject to:

$V3-{V}_{l}+W{2}_{k}\le C{3}_{kl}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall k\in K,l\in L$ (20)

${V}_{l}\ge 0$ , $V3,W{2}_{k}$ unrestricted (21)

3. Theoretical Results

We start with the development of the heuristic for the dual solution, and then move on to develop heuristic for the primal. Let $S{P}_{il}$ denote the length of shortest path from i to l such that $S{P}_{il}={\lambda }_{ij}+{\lambda }_{jk}+{\lambda }_{kl}$ , such that ${\lambda }_{ij},{\lambda }_{jk},{\lambda }_{kl}$ denotes the length of path from i to j, j to k and k to l in a shortest path $S{P}_{il}$ .

SPS = { $S{P}_{il}$ : $S{P}_{il}$ is the shortest path between i and l} $\forall i\in I,l\in L$

Problem TP

Minimize:

$\underset{i,l}{\sum }{X}_{il}S{P}_{il}$ (22)

Subject to:

$\underset{l\in L}{\sum }{X}_{il}={s}_{i}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i\in I$ (23)

$\underset{i\in I}{\sum }{X}_{il}={d}_{l}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall l\in L$ (24)

${X}_{il}\ge 0\text{\hspace{0.17em}}\text{\hspace{0.17em}}\text{\hspace{0.17em}}\forall i\in I,l\in L$ (25)

Theorem 1: Problem P and Problem TP are equivalent.

Proof: Since all the arcs capacities are unbounded in the transshipment problem, hence optimal flow for a pair of source and sink nodes will always be on $S{P}_{il}$ . This ensures that any further reduction in the objective function value is not possible. Therefore optimal solution to problem TP gives the optimal solution to problem P and hence problem TP and P are equivalent. Hence proved.

4. Solution Procedures

4.1. Description of Heuristic 1 (H1)

We extend this heuristic from our previous article on single stage transshipment Sinha and Sharma  problem to two stage transshipment problem. Unlike heuristic developed for single stage transshipment problem, we will decrease the $W{1}_{j}$ along the shortest path after substituting ${U}_{i}=0\text{\hspace{0.17em}}\forall i\in I$ . We next describe this heuristic in detail.

Step 1: Sort $S{P}_{il}\text{\hspace{0.17em}}\forall i\in I,j\in J$ in the ascending order and select the $S{P}_{il}$ from top of the list.

Step 2: Assign $V1={\lambda }_{ij},V2={\lambda }_{jk},V3={\lambda }_{kl}$ , and $W{1}_{j}={\mathrm{max}}_{j}\left(V1-C{1}_{ij}\right)\text{\hspace{0.17em}}\forall j\in J$

Step 3: $W{2}_{k}={\mathrm{max}}_{j}\left(V2+W{1}_{j}-C{2}_{jk}\right)\text{\hspace{0.17em}}\forall k\in K$

${U}_{i}={\mathrm{max}}_{j}\left(V1-W{1}_{j}-C{1}_{ij}\right)\text{\hspace{0.17em}}\forall i\in I$

${V}_{l}={\mathrm{max}}_{k}\left(V3+W{2}_{k}-C{3}_{kl}\right)\text{\hspace{0.17em}}\forall l\in L$

Step 4: Evaluate DP = DP1 + DP2 and retain the best solution.

Step 5: Repeat step 3 by decreasing value of $W{1}_{j}$ in steps $\forall j\in J$ .

Step 6: Goto step 1 and repeat the entire process for all $S{P}_{il}$ from the sorted list.

Result 1: Computational complexity of the algorithm is O (n2).

Proof: Complexity of this algorithm is dominated by the step 1 which can be solved in O (n2) time.

4.2. Description of Heuristic 2 (H2)

In the previous algorithm, we tinkered with value of $W{1}_{j}$ along $S{P}_{il}$ $\forall l\in L$ . There is no reason as to why we cannot tinker with the values of ${U}_{i},{V}_{k},W{2}_{k}$ along $S{P}_{il}$ . We define $\left(C{1}_{ij}-V1+{U}_{i}+W{1}_{j}\right)$ , $\left(C{2}_{jk}-V2+W{2}_{k}-W{1}_{j}\right)$ and $\left(C{3}_{kl}-V3+{V}_{l}-W{2}_{k}\right)$ as source slack, transshipment slack and sink slack respectively ( $S1,S2,S3$ ). Next we describe this heuristic in detail.

Step 0: Sort values of $S{P}_{il}$ in SPS in ascending order and set $S{P}_{il}^{*}={\left(S{P}_{il}\right)}_{\mathrm{min}}$ , $j=1$ .

Step 1: Set $W{1}_{j}={\mathrm{max}}_{j}\left(V1-C{1}_{ij}\right),V1={\lambda }_{ij}^{*},V2={\lambda }_{jk}^{*},V3={\lambda }_{kl}^{*}$ such that ${\lambda }_{ij}^{*},{\lambda }_{jk}^{*},{\lambda }_{kl}^{*}$ belongs to $S{P}_{il}^{*}$ $\forall j\in J$ .

Step 2: Compute max_value of DP1 and DP2 by increasing value of ${U}_{i},{V}_{l},W{2}_{k}$ and retain the maximum value of (DP1 + DP2).

Step 3: Decrease the value of $W{1}_{j}$ in steps and repeat the step 2.

Step 4: $j=j+1$ , If $j>J$ , then goto step 5 else goto step 1.

Step 5: Stop

Result 2: Heuristic 2 runs in O (n3) time.

Proof: Complexity of the heuristic is dominated by step 2 which can be completed in O (n3) steps.

4.3. Description of Heuristic 2 (H2)

We refer Sharma and Prasad  for developing a heuristic to get a good primal solution after having yielded a good dual solution. This is due to the structural similarity between the two problems. Solution to dual problem DP can be expressed as $DP,V1,V2,V3,U=\left\{{U}_{i}\text{\hspace{0.17em}}\forall i\in \left(1,I\right)\right\},V=\left\{{V}_{l}\text{\hspace{0.17em}}\forall l=\left(i,L\right)\right\}$ . Slack $S1,S2,S3$ is defined as following:

$S1=|C{1}_{ij}-V1+{U}_{i}+W{1}_{j}|$ , $S2=|C{2}_{jk}-V2-W{1}_{j}+W{2}_{k}|$ , $S3=|C{3}_{kl}-V3+{V}_{l}-W{2}_{k}|$ $\forall i\in \left(1,I\right),j\in \left(1,J\right),k\in \left(1,K\right)$ . If $S1=0,S2=0$ and $S3=0$ , then $X{1}_{ij}\ge 0$ , $X{2}_{jk}\ge 0$ add $X{3}_{kl}\ge 0$ . In other words primal variables for the arc $\left(i,j\right),\left(j,k\right),\left(k,l\right)$ (i.e. $X{1}_{ij},X{2}_{jk},X{3}_{kl}$ ) can assume positive value if the corresponding dual slacks for these arcs are zero. This is known as complementary slackness condition. We utilize this condition to devise a method to extract good primal solution from an existing dual solution. Let $S{P}_{il}$ denote the total slack for a shortest path between node i and node l i.e.

$S{P}_{il}={\mathrm{min}}_{j,k}\left(\underset{i,j}{\sum }S1+\underset{j,k}{\sum }S2+\underset{k,l}{\sum }S3\right)$ .

We further define deviation number as $D{N}_{il}=S{P}_{il}*{X}_{il}$ . According to complimentary slackness condition, for a primal optimal solution, we have

$\underset{i\in I}{\sum }\underset{l\in L}{\sum }D{N}_{il}=0$ .

If $S{P}_{il}=0$ , positive flow can be allocated to the corresponding path without violating the complimentary slackness property. Further, positive flow cannot be allocated to the path with $S{P}_{il}>0$ . As we are working with good dual solution (and not optimal dual solution), we may have to send positive flow along a path even if corresponding $S{P}_{il}>0$ . But the heuristic described below, tries to minimize $D{N}_{il}$ and hope to keep complementary slackness violations as low as possible to get good primal solution. If algorithm terminates with

$\underset{i\in I}{\sum }\underset{l\in L}{\sum }D{N}_{il}=0$ ,

then we have the optimal primal solution. $D{N}_{il}$ is similar to Kilter number (Clasen  ) for solving general min-cost-flow problem.

We find shortest path from every source node “i” to every sink node “l” using these slacks as weights, and then make the allocations according to shortest path available. Detailed heuristic is described as under:

Step 0: ${X}_{ij}={X}_{jk}={X}_{kl}=0,\forall i\in I,j\in J,k\in K,l\in L$

Step 1: Compute ${S}_{il}={\mathrm{min}}_{j,k}\left[S{1}_{ij}+S{2}_{jk}+S{3}_{kl}\right]$ . Let min be at ${j}^{*}$ and ${k}^{*}$ $\forall i\in I,j\in J,k\in < /mo>K,l\in L$ .

$\begin{array}{l}S{1}_{ij}=|C{1}_{ij}-V1+{U}_{i}+W{1}_{j}|,\\ S{2}_{jk}=|C{2}_{jk}-V2-W{1}_{j}+W{2}_{k}|,\\ S{3}_{kl}=|C{3}_{kl}-V3+{V}_{l}-W{3}_{k}|\end{array}$

Step 2: Sort all ${S}_{il}$ in increasing order.

Step 3: Choose ${S}_{il}$ from the top of the list such that ${d}_{l}>0$ and ${s}_{i}>0$ and goto step 4, if all Sil are processed then goto step 5

Step 4: ${X}_{i{j}^{*}}={X}_{{j}^{*}}{}_{{k}^{*}}={X}_{{k}^{*}}{}_{l}=\mathrm{min}\left({s}_{i},{d}_{l}\right)={a}^{*},{s}_{i}={s}_{i}-{a}^{*},{d}_{l}={d}_{l}-{a}^{*}$ , remove ${S}_{il}$ from the list then goto step 3.

Step 5: Stop.

Result 3: Computational complexity of the algorithm is O (n2).

Proof: Complexity of this algorithm is dominated by the step 2 which can be solved in O (n2) time.

5. Numerical Analysis and Conclusions

In this section, we discuss the efficacy of our methods by implementing them on large size randomly generated problems. 200 problems of the size 200 × 200 ×

Table 1. Numerical analysis.

200 × 200 are solved. Heuristic methods on these problems are implemented in C++. Optimal solution was obtained from problem implementation in CPLEX in GAMS. We compare the number of iterations and the duality gap for these problems in Table 1. As shown, our methods are capable of reducing the computational effort (number of iterations) significantly while not compromising much on duality gap. Heuristic solutions by H1 and H2 are capable of achieving on an average 96% and 98% closeness to optimal solution. Computational complexity of these methods has already been discussed. We later intend to extend this work to general case of Minimum cost flow problem with finite arc capacities.

Cite this paper
Sinha, P. and Sharma, R. (2018) Efficient Heuristic Based Methods for Two-Stage Transshipment Problem. American Journal of Operations Research, 8, 281-293. doi: 10.4236/ajor.2018.84016.
References
   Sharma, R.R.K. and Saxena, A. (2002) Dual Based Procedures for the Special Case of Transshipment Problem. Operation Research, 39, 177-188.

   Sinha, P. and Sharma, R.R.K. (2016) Dual Based Procedures for Un-Capacitated Minimum Cost Flow Problem. American Journal of Operations Research, 6, 468-479.
https://doi.org/10.4236/ajor.2016.66043

   Weintraub, A. (1974) A Primal Algorithm to Solve Network Flow Problems with Convex Costs. Management Science, 21, 87-97.
https://doi.org/10.1287/mnsc.21.1.87

   Plotkin, S.A. and Tardos, E. (1990) Improved Dual Network Simplex. Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, San Francisco, 367-376.
http://delivery.acm.org/10.1145/330000/320222/p367-plotkin.pdf?ip=14.139.38.9&id=320222&acc=ACTIVE%20SERVICE&key=045416E F4DDA69D9%2E6454B2DFDB9CC807%2E4D4702B0C3E38B35%2E4 D4702B0C3E38B35&__acm__=1526448927_7f6da1e85e11c5cff23e4cbeb14d250d

   Ahuja, R.K. (1993) Network Flows. Ph.D. Thesis, Technische Hochshule Darmstadt, Darmstadt.
https://volyubemw.updog.co/dm9seXViZW13MDEzNjE3NTQ5WA.pdf

   Juman, Z.A.M.S. and Hoque, M.A. (2015) An Efficient Heuristic to Obtain a Better Initial Feasible Solution to the Transportation Problem. Applied Soft Computing, 34, 813-826.
https://doi.org/10.1016/j.asoc.2015.05.009

   Busaker, R.G. and Gowen, P.J. (1961) A Procedure for Determining Minimal-Cost Flow Network Patterns. Tech. Rep. ORO-15, Operational Research Office, Johns Hopkins University, Baltimore.

   Edmonds, J. and Karp, R.M. (1972) Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems. Association for Computing Machinery Journal, 19, 248-264.
https://doi.org/10.1145/321694.321699

   Helgason, R.V. and Kennington, J.L. (1977) An Efficient Procedure for Implementing a Dual Simplex Network Flow Algorithm. AIIE Transactions, 9, 63-68.
https://doi.org/10.1080/05695557708975122

   Orlin, J.B. (1984) Genuinely Polynomial Simplex and Non-Simplex Algorithms for Minimum Cost Problems. Technical Report 1615-84, Sloan School of Management, MIT, Cambridge.
https://dspace.mit.edu/bitstream/handle/1721.1/48015/genuinelypolynom00orli.pdf?sequence=1

   Ali, A.I., Padman, R. and Thiagarajan, H. (1989) Dual Algorithms for Pure Network Problems. Operations Research, 37, 159-171.
https://doi.org/10.1287/opre.37.1.159

   Sharma, R.R.K. and Prasad, S. (2003) Obtaining a Good Primal Solution to the Uncapacitated Transportation Problem. European Journal of Operational Research, 144, 560-564.
https://doi.org/10.1016/S0377-2217(01)00396-4

   Clasen, R.J. (1968) The Numerical Solution of Network Problems Using the Out-of-Kilter Algorithm. No. RM-5456-PR. RAND CORP Santa Monica.