Efficient Heuristic Based Methods for Two-Stage Transshipment Problem

Priyank Sinha, Renduchintala Raghavendra Kumar Sharma

Industrial and Management Engineering Department, IIT Kanpur, Kanpur, India.

DOI: 10.4236/ajor.2018.84016                

Abstract

In this article, we propose efficient methods for solving two stage transshipment problems. Transshipment problem is the special case of Minimum cost flow problem in which arc capacities are infinite. We start by proposing a novel problem formulation for a two stage transshipment problem. Later, special structure of our problem formulation is utilized to devise two dual based heuristics solutions with computational complexity of O (n²), and O (n³) respectively. These methods are motivated by the methods developed by Sharma and Saxena [1], Sinha and Sharma [2]. Our methods differ in the initialization and the subsequent variation of the dual variables associated with the transshipment nodes along the shortest path. Lastly, a method is proposed to extract a very good primal solution from the given dual solutions with a computational complexity of O (n²). Efficacy of these methods is demonstrated by our numerical analysis on 200 random problems.

Keywords

Two Stage Transshipment Problem, Min Cost Flow, Transportation Problem, Dual, Primal

1. Introduction

Minimum cost flow problem can be described as a preparation of minimum cost plan for the transportation of certain number of units from source to sink to satisfy the demand at each sink. One or more layers of transshipment nodes are present between the sources and sinks, which act as buffer. Weintraub [3] is attributed with the development of one of the first primal based algorithms to solve minimum cost flow problem with convex costs. A variant of negative cycle algorithm is used which aims to identify most negative cycle and subsequently induces it iteratively into the feasible flow. Plotkin and Tardos [4] later proposed a polynomial time algorithm for min cost flow with computational complexity of O (m⁴). Pseudo flow is maintained by the algorithm such that it satisfies the complimentary slackness conditions while performing flow augmentation from the nodes with positive excess to nodes with negative excess. Algorithm is terminated when all the excesses are reduced to zero. Ahuja et al. [5] has employed advanced data structures to solve primal simplex algorithm for min-cost flow. They have further documented that transshipment problem can be solved by enhanced capacity scaling algorithm in O (n log (n) S (n, m)) time, where n and m are the number of nodes and number of arcs in a network respectively. S (n, m) refers to running time of shortest path problem with n nodes and m arcs. Enhanced capacity scaling algorithm and repeated capacity scaling algorithm runs in O (n³ log (n)) and O (n² log (n) S (n, m)) time respectively (Ahuja et al. [5] ). Further cost scaling algorithm can be used to solve min cost flow problem in O (n³ log (n)). Hence, best primal based approach solves the transshipment problem with the time complexity of O (n³ log (n)). Recently Juman and Hoque [6] have proposed an efficient heuristic with O (n³) running time to solve uncapacitated balanced transportation problem. Performance of this heuristic is better than Vogel’s Approximation Method (VAM), which is one of the most popular primal based methods to obtain a very good initial basic feasible solution.

Next, we review some popular dual based procedures to solve min cost flow problem. Busakar and Gowan [7] are attributed for developing successive shortest path algorithm. It successively identifies the least cost paths between the source and sink and allocates the maximum capacity on the residual network while maintaining the dual feasibility. Algorithm terminates when residual network contains no admissible path between the source and the sink or when the flow is maximal (primal feasibility is achieved). First polynomial time algorithm to solve min cost flow problem was proposed by Edmonds and Karp [8] . It is a specific implementation of Ford-Fulkerson algorithm in which breadth first search is used to find the shortest path in intermediate stages. Computational complexity of the algorithm is O ((n + m) log U). Helgason and Kennington [9] has used linear programming formulation of the network flow problem to analyze dual simplex method. Plotkin and Tardos [4] had proposed an efficient pivoting strategy with complexity of O (m²n) for the dual simplex method proposed by Orlin [10] . This reduces the number of pivoting steps required for dual simplex method. According to Ali et al. [11] , efficient execution of each pivot in dual based methods requires less number of iterations when compared with primal based algorithm. However, each pivot operation may require higher computational effort.

Our approach in this article to solve two stage transshipment problems is different from the approaches discussed above. We pose the two stage transshipment problem differently and exploit the special structure of the problem to devise two computationally attractive dual based procedures with the computational complexity of O (n²) and O (n³) respectively. We also propose a method (with computational complexity of O (n²)) to extract good primal solution from an existing dual solution. These methods are motivated by Sharma and Saxena [1] , and Sinha and Sharma [2] . Solution proposed by these methods can be used as an initial basic feasible solution to get an advanced start for the exact methods proposed by Orlin [10] , Plotkin and Tardos [4] , and Ali et al. [11] . Next we give problem formulation for two stage transshipment problem.

2. Problem Formulation

We next present the mathematical formulation of the primal problem and dual problem respectively.

2.1. Constants of the Problem

$D_l$ refers to the absolute demand at the l^th demand node, while $d_l$ is the demand at market l as a fraction of total market demand. Hence we have

$d_l=D_l/\left[{\displaystyle \underset{l=1}{\overset{L}{\sum }}{D}_l}\right]$ and ${\displaystyle \underset{l=1}{\overset{L}{\sum }}{d}_l}=1$ ,

where L is the total number of demand nodes. Similarly $S_i$ refers to to absolute number of units available for transportation at the source node i and

$s_i=S_i/\left[{\displaystyle \underset{l=1}{\overset{L}{\sum }}{D}_l}\right]$ . If the problem is balanced, then we have ${\displaystyle \underset{i=1}{\overset{I}{\sum }}{s}_i}={\displaystyle \underset{l=1}{\overset{L}{\sum }}{d}_l}$ , I is the total number of supply nodes. $C{1}_{ij},C{2}_{jk},C{3}_{kl}$ is the cost of transporting ${\displaystyle \underset{l=1}{\overset{L}{\sum }}{D}_l}$ units from node i to j, j to k and k to l respectively.

2.2. Decision Variables

$x{1}_{ij},x{2}_{jk},x{3}_{kl}$ is the absolute number of units transported from node i to j, j to k and k to l respectively. We further have

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

Primal of the problem can be formulated as under ?

2.3. Primal (P)

Minimize:

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

Subject to:

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

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

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

$-{\displaystyle \underset{j;\left(i,j\right)\in N}{\sum }X{1}_{ij}}\ge -s_i\forall i\in I$ (5)

$-{\displaystyle \underset{k;\left(k,l\right)\in N}{\sum }X{3}_{kl}}\ge -d_l\forall l\in L$ (6)

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

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

$X{1}_{ij},X{2}_{jk},X{3}_{kl}\ge 0\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-{\displaystyle \underset{i\in I}{\sum }{s}_i}{U}_i-{\displaystyle \underset{l\in L}{\sum }{d}_l}{V}_l$ (10)

Subject to:

$V1-U_i-W{1}_j\le C{1}_{ij}\forall i\in I,j\in J$ (11)

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

$V3-V_l+W{2}_k\le C{3}_{kl}\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-{\displaystyle \underset{i\in I}{\sum }{s}_i}{U}_i$ (15)

Subject to:

$V1-U_i-W{1}_j\le C{1}_{ij}\forall i\in I,j\in J$ (16)

$V2+W{1}_j-W{2}_k\le C{2}_{jk}\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-{\displaystyle \underset{l\in L}{\sum }{d}_l}{V}_l$ (19)

Subject to:

$V3-V_l+W{2}_k\le C{3}_{kl}\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:

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

Subject to:

${\displaystyle \underset{l\in L}{\sum }{X}_{il}=s_i}\forall i\in I$ (23)

${\displaystyle \underset{i\in I}{\sum }{X}_{il}}=d_l\forall l\in L$ (24)

$X_{il}\ge 0\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 [2] 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\forall i\in I$ . We next describe this heuristic in detail.

Step 1: Sort $S{P}_{il}\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={\max }_j\left(V1-C{1}_{ij}\right)\forall j\in J$

Step 3: $W{2}_k={\max }_j\left(V2+W{1}_j-C{2}_{jk}\right)\forall k\in K$

$U_i={\max }_j\left(V1-W{1}_j-C{1}_{ij}\right)\forall i\in I$

$V_l={\max }_k\left(V3+W{2}_k-C{3}_{kl}\right)\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 (n²).

Proof: Complexity of this algorithm is dominated by the step 1 which can be solved in O (n²) 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)}_{\min }$ , $j=1$ .

Step 1: Set $W{1}_j={\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 (n³) time.

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

4.3. Description of Heuristic 2 (H2)

We refer Sharma and Prasad [12] 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\forall i\in \left(1,I\right)\right\},V=\left\{V_l\forall l=\left(i,L\right)\right\}$ . Slack $S1,S2,S3$ is defined as following:

$S1=\left|C{1}_{ij}-V1+U_i+W{1}_j\right|$ , $S2=\left|C{2}_{jk}-V2-W{1}_j+W{2}_k\right|$ , $S3=\left|C{3}_{kl}-V3+V_l-W{2}_k\right|$ $\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}={\min }_{j,k}\left({\displaystyle \underset{i,j}{\sum }S1+}{\displaystyle \underset{j,k}{\sum }S2+{\displaystyle \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

${\displaystyle \underset{i\in I}{\sum }{\displaystyle \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

${\displaystyle \underset{i\in I}{\sum }{\displaystyle \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 [13] ) 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}={\min }_{j,k}\left[S{1}_{ij}+S{2}_{jk}+S{3}_{kl}\right]$ . Let min be at $j^{*}$ and $k^{*}$ .

$\begin{array}{l}S{1}_{ij}=\left|C{1}_{ij}-V1+U_i+W{1}_j\right|,\\ S{2}_{jk}=\left|C{2}_{jk}-V2-W{1}_j+W{2}_k\right|,\\ S{3}_{kl}=\left|C{3}_{kl}-V3+V_l-W{3}_k\right|\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 S_il are processed then goto step 5

Step 4: $X_{i{j}^{*}}=X_{j^{*}}{}_{k^{*}}=X_{k^{*}}{}_l=\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 (n²).

Proof: Complexity of this algorithm is dominated by the step 2 which can be solved in O (n²) 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.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Sharma, R.R.K. and Saxena, A. (2002) Dual Based Procedures for the Special Case of Transshipment Problem. Operation Research, 39, 177-188.
[2]	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
[3]	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
[4]	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
[5]	Ahuja, R.K. (1993) Network Flows. Ph.D. Thesis, Technische Hochshule Darmstadt, Darmstadt. https://volyubemw.updog.co/dm9seXViZW13MDEzNjE3NTQ5WA.pdf
[6]	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
[7]	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.
[8]	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
[9]	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
[10]	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
[11]	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
[12]	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
[13]	Clasen, R.J. (1968) The Numerical Solution of Network Problems Using the Out-of-Kilter Algorithm. No. RM-5456-PR. RAND CORP Santa Monica. http://www.dtic.mil/docs/citations/AD0667528