Transshipment Problem using Modified Neural Network Model

Transshipment Problem using Modified Neural Network Model

N. C. Ashioba

Department of Computer Science Delta State Polytechnic Ogwashi Uku, Delta State, Nigeria.

E. O. Nwachukwu

Department of Computer Science University of Port Harcourt, Rivers State, Nigeria.

Abstract -Transshipment problem is an example of a transportation problem that deals with the shipment of a homogenous product from various supply origins through different transshipment points to various demand destinations with the objective of minimizing the total transshipment cost. Transshipment problem has been solved using the Modified Distribution Method (MODI) where the transshipment problem is converted to an equivalent transportation problem

And the demand constraints: x11+x12+x13+.+x1m=b1 x +x +x +.+x =b

21 22 23 2m 2

21 22 23 2m 2

.

xn-11+x-12+xn-13+.+xn-1m= bn-1 xn1+xn2+xn3++ =bn }

(3)

by classifying the transshipment points as being parts of the supply origins and the demand destinations. The method cannot be used to predict the total cost of shipping a homogenous product from various supply origins through

Where xij 0 for all i, j (4)

+

= . . (5)

different demand destination to a particular demand destination. In this paper we have deployed the Modified

=1

=1

Neural Network model to find the optimal solution of a transshipment problem. The model accepts both normalized and un-normalized data sets as input. The model was simulated using C++ programming language. The result has shown that the Modified Neural Network Model is more efficient and effective to predict the total cost of shipping a homogenous product from various supply origins to a particular demand destination through different transshipment points.

Keyword: Supply points, Demand points, Transshipment points, Neural Network and Transshipment Problem.

I INTRODUCTION

Transportation Problem is a subclass of a linear programming problem that deals with the shipment of a homogenous product from various supply origins, to different demand destinations with the objective of minimizing the total transportation cost in the problem. It can be classified as direct or indirect Transportation Problem [1].

The direct transportation problem deals with the shipment of homogenous product from various supply origins to different demand destinations. The mathematical model for transportation problem is stated as [2]:

Where cij is the cost of transportation of a unit from the ith source to the jth destination, and the quantity xij, to be positive integer or zero, represents the optimal quantity of the product that can be transported from the ith origin to the jth destination.

But instead of direct shipments to destinations, the commodity can be transported to a particular destination through one or more intermediate or trans-shipment points. Each of these points in turn supply to other points. Thus, when the shipments pass from destination to destination and from source to source, we have a trans-shipment problem. Since transshipment problem is a particular case of transportation problem hence to solve transshipment problem, we first convert transshipment problem into equivalent transportation problem and then solve it to obtain optimal solution using MODI method of transportation problem. In a transportation problem, shipments are allowed only between source-sink pairs. In many applications, this assumption is too strong. The mathematical model for the converted transshipment problem is stated as:

+ +

= . (6)

=1 =1

Subject to:

= . (1)

=1 =1

Subject to the supply constraints:

x11+x21+x31+.+xm1=a1

x12+x22+x32+.+xm2=a2

xi1+xi2+.+xii+1-=a

1i 2i i-1i m+ni i

1i 2i i-1i m+ni i

x +x +x +x =

.

x1j+x2+.+xm+nj-= bj

xj1+xj2++ 1++=j}

..(7)

.

x1m-1+x2m-2+x3m-1+..xnm-1= am-1

(2)

+

x1n+x2n+x3n++=nm }

= . . (8)

=1 =+1

These constraints are similar to the constraints of a transportation problem with m + n sources and m = n destination with difference that here there are no and

term and that bj =0 for j = 1,2,3,.,m and ai =0 for

i=m+1, m+2, m+n.

II REVIEW OF RELATED WORKS

grouped in a number of layers [9]. Figure 1 illustrates a single layer neural network with three input elements and three neurons. In the network each element of the input vector p is connected to each neuron input through the weights matrix w.

w ni

Several researchers have solved the Transportation Problem Pi

with various methods to obtain an optimal solution. The

simplex method developed by Dantzig provides an algorithm which consists in moving from one vertex of the region of feasible solution to another in such a way that the value of the objective function at the succeeding vertex is

f Output (a)

ni =wpi

ai =f(ni)

less in a minimization problem. [3] stated that the computational procedure in the simplex method is based on the fundamental property that the optimal solution to a linear programming problem, if it exists, occurs only at one corner point of the feasible region.

1. formulated an OR model for finding an optimal solution for a transportation problem. All the optimal solution algorithms for solving Transshipment Problem need an initial basic feasible solution.

2. uses the following methods in finding the initial feasible solution:

   • North West Corner Method

   • Least cost method

   • Row minima Method

   • Column minima method

   • Vogel Approximation method

     The algorithm deployed the stepping stone and the modified distribution methods (MODI) in testing for optimality of a transshipment problem.

     f

     f

3. proposed a heuristic algorithm for solving transportation problems with mixed constraints and extend the algorithm to find a more-for-less (MFL) solution, if one exists. The more-for-less (MFL) paradox in a transportation problem occurs when it is possible to ship more total goods for less

   Figure 1: A-layer neural network (source: Jamal, Ibrahim and Salam, 2009)

   The neural network used the learning rule to modify the weights and the biases of the network and the training process for selecting parameters for a given problem. The training procedure used in multilayer perceptron neural network is one of the supervised learning algorithms called the back propagation algorithm. The back propagation algorithm uses the computed output error to adjust the weights so as to minimize the error in its predictions on the training dataset.

   Back propagation neural network requires that all training input data must be normalized between 0 and 1 for training. It cannot be used to train un-normalized input data.

   IV CONCEPTUAL FRAMEWORK OF THE PROPOSED SYSTEM

   Conceptual design of a system is concerned with making a prototype of the proposed system. It provides a description of the proposed system in terms of a set of integrated ideas and concepts about what the system should do, behave and look like. The conceptual framework of the proposed system is illustrated in Figure 2.

   (or equal) total cost, while shipping te same amount or

   more from each origin and to each destination and keeping Pi

   all the shipping costs non-negative.

4. proposed a method, called separation method-based on the zero point to find an optimal solution problem where transportation cost, supply and demand are intervals. They

   w ni

   Output (a)

   ni =wpi

   ai =f(ni)

   developed the separation method without using the midpoint and width of the interval in the objective function of the fully interval transportation problem.

5. proposed a method called zero-suffix method to finding an optimal solution for transportation problem. The proposed method gives an optimal solution without disturbance of degeneracy condition.

This paper deploys a modified neural network model to find the optimal solution of a transshipment problem.

III MATERIALS AND METHOD

Figure 2: Conceptual framework of the proposed system

The proposed system accepts both normalized and un- normalized input data. It normalizes the data using the normalized function (). There are two basic normalization techniques namely max-min normalization and decimal scaling techniques. In this work we use the decimal scaling technique to normalize the data by moving the decimal unit of values of the attributes as shown in equation (9).

Neural Networks are models designed to imitate the human brain through the use of mathematical models. A neural

v 1

v

10 j

……………………………………………..(9)

network consists of a set of artificial neurons (nodes)

where j is the smallest integer such that max |v1|<1.

The Multi-Layer Perceptron Neural Network model analyzes the transshipment problem in two propagations namely the forward and backward propagations. The forward propagation algorithm first computes the total weighted input xj by using the formula in equation (10).

Wnew Wold * * input……………………(17)

where is a constant called the learning rate (=1). The learning rate takes value between 0 and 1.

is the output error calculated by equations (18) and (19).

Inputj x j y j wij ………………………….(10)

j o j (1 – o j )( k * w jk ………………………..(18)

Where yj is the activity level of the jth unit in the previous layer and wij is the weight of the connection between the ith and the jth unit.

The algorithm uses the activation function to predict the calculated output. The activation function used in a multi- layer perceptron neural network is a sigmoid function which is expressed in equation (11).

k

and

k ok (1 – ok )(Tk ok )…………………………….(19)

The objective function is:

1 m n

f (x)

1 e x j

……………………………………..(11)

Minimize F = cij * xij …. (20)

i=1 j =1

The multi-layer perceptron neural network is trained to solve the transportation problem by using the backward propagation algorithm which determines the output error by using the expression in equation (12).

Error Tk Ok …………………………………….(12)

The overall performance (net error) of the Multi-Layer Perceptron Neural Network is measured by the mean square error (MSE) expressed in equation (13).

V RESULTS ANALYSIS AND DISCUSSION

Table 1 shows a firm that has two factories to ship its products from factories X and Y through two-retail stores A and B to destination C. The Table shows also that number of units available at factories X and Y are 200 and 300 respectively, while those demand at retail stores A and B are 100 and 150 and at the destination the demand is 250.

Table 1: Quantity of goods located at the factories, retail-stores and demand destination

1

1

n

MSE e N p1

2 1 (y

p N j

• d j

)2 …..(13)

The algorithm is successfully finished if the net error is zero (perfect) or approximately zero. Where the net error is not zero, we apply the back propagation algorithm to calculate the back propagation errors and new weight.

The back propagation error in the output neuron is calculated by using the formula in equation (14)

k Errk Ok (1 Ok )(Tk Ok )……………(14)

Where

Ok is the calculated (actual) output expressed in equation (7)

Table 2 shows the transportation cost per unit in naira.

Ok

1

1 e xk

………………………………………….(15)

Table 2: Transportation unit cost in Naira

Ok is the observed (True) output

The back propagation error in the hidden layer is calculated by using the formula

j Errj

Oj (1 Oj ) k * wjk …………….(16)

Where wjk is the weight of the connection from unit j to unit k in the next layer and k is the error of unit k.

The weight adjustment formula in equation (17) is used to adjust the weights to produce new weights which are fed into the input layer.

Applying the Vogel Approximation Method, the initial feasible solution is illustrated n Table 3.

Table 3: Initial solution using VAM

Using the Modified Distribution method, the optimal solution of the transportation problem is shown in Table 4:

Table 4: Optimal solution using MODI

Since opportunity cost corresponding to each unoccupied cell is positive, therefore the total transportation cost is:

= 100 × 7 + 100 × 8 + 50 × 4 + 250 × 0

= 700 + 800 + 200 + 750 = 2450

Applying the Modified Neural Network using C++ simulator, the total transshipment cost is calculated as follows:

Enter the number of input neurones

+++++++++++++++++++++++++++++++ 2

Enter the number of neurones in the hidden layer

+++++++++++++++++++++++++++++++ 2

Enter the number of neurones in the output layer

+++++++++++++++++++++++++++++ 1

INPUT PARAMETERS 200

300

OUTPUT PARAMETERS 250

The weights between the input and the hidden layers are:

++++++++++++++++++++++++++++

input[1].weight[1]=0.00125126 input[1].weight[2]=0.563585 input[2].weight[1]=0.193304 input[2].weight[2]=0.80874

The weights between the hidden and the output layers are:

+++++++++++++++++++++++++++++++++++++++

hidden[1].weight[1]=0.585009 hidden[2].weight[1]=0.479873 The input to hidden layer [1] is: 1 The input to hidden layer [2] is: 1

The output quantity [1] is: 0.743622 the error is 249.256

The diff 0.256378

The error 249.256

The output_hidden error 47.5203 the sum 50.6035

The Input_hidden error 0 The Input_hidden error 0 the sum 50.6035

The Input_hidden error 0 The Input_hidden error 0

The weights between the hidden and the output layers are:

++++++++++++++++++++++++++++++++++++++

hidden[1].weight[1]=48.1053 hidden[2].weight[1]=48.0001

The weights between the input and hidden layers are:

+++++++++++++++++++++++++++++++++

input[1].weight[1]=0.00125126 input[1].weight[2]=0.563585 input[2].weight[1]=0.193304 input[2].weight[2]=0.80874

The input to hidden layer [1] is: 1 The input to hidden layer [2] is: 1 The output quantity [1] is: 1

the error is 249

The unit cost between the input and the hidden layers are:

+++++++++++++++++++++++++++++++++

input[1].cost[1]=7 7

input[1].cost[2]=8 8

input[2].cost[1]=5 5

input[2].cost[2]=4 4

The unit cost between the hidden and the output layers are:

++++++++++++++++++++++++++++++++++++

hidden[1].cost[1]=1 1

hidden[2].cost[1]=4

the sum of neural 18.71893 the sum of neural 2240.106

The total Transportation cost ==248.825 Press any key to continue . . .

V DISCUSSION OF RESULT

The results have shown that the optimal solution of the transshipment problem is obtained using MODI method and the Modified Neural Network Model. The MODI method can be used by the producer to predict the total cost of transportation of a commodity from various supply origins to different demand destinations through various transshipment points while the Modified Neural Network model can be used by the producers or consumers to predict the total cost transportation from various supply origin to a particular demand destination through different transshipment points. Secondly, the results have shown that the optimal solution of a transshipment problem with large constraints and variables can be solved using the Modified Neural Network Model.

1. CONCLUSION

   Transshipment problem is a multilayer perceptron problem with three layers namely input layer as the sources, hidden layers as transshipment points and output layers as the demand destination points. Transshipment problem with very large constraints and variables can best be solved using the Modified Neural Network Model. The model can be used to predict the total cost of shipping a homogenous product from various supply origins through different transshipment points to a particular demand destination.

2. REFERENCES

1. Kotler, P. and Keller, K. L. (2007) Marketing Management (12th edition) New Delhi: Pearson Prentice Hall.

2. Basirzadeh H. (2011) An Approach for Solving Fuzzy Transportation Problem. Applied Mathematical Sciences. Vol. 5 No. 32 pp. 1549- 1566.

3. Gupta K. P. and Hire D. S. (2011) Operations Research. Ram Nagar, New Dehli, S. Chand & company Ltd.

4. Nabendu, S., Tanmoy, S., and Banashri, S. (2010) A study of Transportation Problem for an Essential Item of Southern Part of North Eastern Region of India as an OR Model and use of Object Oriented Programming: International Journal of Computer Science and Network Security Vol. 10 No 4 pp78-86.

5. Sharma J. K. (2010) Operations Research Theory and Applications (4th Edition) India, Macmillan Publisher India Ltd.

6. Veena A, Krzysztof K, and Benjamin L. (2006). Solving Transportation Problems with Mixed Constraints. International Journal of Management Science and Engineering Management Vol. 1 No. 1 pp47-52.

7. Fegade M. R, Jadhav V. A, and Muley A. A. Finding an optima solution of Transportation Problem Using Interval and Trianular Membership Function. European Journal of Scientific Research Vol 60 No 3 (2011) pp 397-403.

8. Sudhakar V. J, Arunsankar N and Karpagam T. A (2012). New Approach for finding an Optimal Solution for Transportation Problem. European Journal of Scientific Research Vol 68 No 2. pp 254-257.

9. Jamal, M. N., Ibrahim, M. E., and Salam, A. N. (2008) Multilayer Perceptron Neural Network (MLPs) For Analyzing the Properties of Jordan Oil Shale: World Applied Sciences Journal 5(5) pp 546-552