 Open Access
 Total Downloads : 529
 Authors : N. C. Ashioba, E. O. Nwachukwu
 Paper ID : IJERTV5IS020025
 Volume & Issue : Volume 05, Issue 02 (February 2016)
 Published (First Online): 04022016
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
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
.
xn11+x12+xn13+.+xn1m= bn1 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 unnormalized 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 transshipment 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 transshipment 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 sourcesink 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 i1i m+ni i
1i 2i i1i m+ni i
x +x +x +x =
.
x1j+x2+.+xm+nj= bj
xj1+xj2++ 1++=j}
..(7)
.
x1m1+x2m2+x3m1+..xnm1= am1
(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.

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.

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


proposed a heuristic algorithm for solving transportation problems with mixed constraints and extend the algorithm to find a moreforless (MFL) solution, if one exists. The moreforless (MFL) paradox in a transportation problem occurs when it is possible to ship more total goods for less
Figure 1: Alayer 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 unnormalized 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 nonnegative.

proposed a method, called separation methodbased 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.

proposed a method called zerosuffix 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 maxmin 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 MultiLayer 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 multilayer 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 MultiLayer 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 tworetail 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, retailstores and demand destination
1
1
n
MSE e N p1
2 1 (y
p N j

d j
Factories 
quantity 

X 
200 

Y 
300 

Retail stores 

A 
100 

B 
150 

Demand destination 

C 
250 

Factories 
quantity 

X 
200 

Y 
300 

Retail stores 

A 
100 

B 
150 

Demand destination 

C 
250 

)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
Factory 
Retail store 

X 
Y 
A 
B 
C 

factory 
X 
0 
8 
7 
8 
9 
Y 
6 
0 
5 
4 
3 

Retail store 
A 
7 
2 
0 
5 
1 
B 
1 
5 
1 
0 
4 

C 
8 
9 
7 
8 
0 
Factory 
Retail store 

X 
Y 
A 
B 
C 

factory 
X 
0 
8 
7 
8 
9 
Y 
6 
0 
5 
4 
3 

Retail store 
A 
7 
2 
0 
5 
1 
B 
1 
5 
1 
0 
4 

C 
8 
9 
7 
8 
0 
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
X 
Y 
A 
B 
C 
supply 

X 
0 
8 
7 
100 
9 
200 

0 
8 

Y 
6 
0 
5 
50 
25 
300 

0 
4 
3 

A 
7 
2 
0 0 
5 
1 
0 

B 
1 
5 
1 
0 0 
4 
0 

C 
8 
9 
7 
8 
0 0 
0 

Demand 
0 
0 
100 
150 
250 
500 
Using the Modified Distribution method, the optimal solution of the transportation problem is shown in Table 4:
Table 4: Optimal solution using MODI
X 
Y 
A 
B 
C 
supply 
ui 

X 
0 
8 
7 
100 
100 
200 
4 

8 
9 

Y 
6 
0 
50 
250 
0 

0 
5 
4 
3 
300 

A 
7 
2 
0 0 
5 
1 
0 
3 

B 
1 
5 
1 
0 
4 
0 
4 

0 

C 
8 
9 
7 
8 
0 0 
0 
3 

Demand 
0 
0 
100 
150 
250 
500 

vj 
4 
0 
3 
4 
3 
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.

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.

REFERENCES

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

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

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

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 pp7886.

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

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 pp4752.

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 397403.

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 254257.

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 546552