A New Algorithm for Fully Interval Integer Transportation Problem

Abstract

In this paper, we propose an optimal diagonal algorithm under a generalized interval arithmetic for solving the problem of complete interval integer transport without converting the crisp equivalent problem .The proposed algorithm is simple to implement and it offers a numerical illustration to demonstrate the efficacy of the proposed process.

Introduction

I. INTRODUCTION

Transport problem (TP) can be described as a special case of linear programming problem and its model is used to determine how many units of goods (raw or finished) are to be transported from each source to different destinations, meet the constraints of supply and demand, while minimizing total transport costs. In a broad sense, the transport problem is used in economic growth, industrial management, passenger and freight modes, etc., and they play a critical role in social economy development.

The transport costs, the availability at the supply points, and the demand point's requirements are the parameters of any transport problem. The model of transport is of the opinion that the choice of routes between supply and demand is determined by the reduction of transport costs in the event of any supply and supply obstacles and the increase of advantages for problems of maximization. Where and when to offer the products to customers, as they want in a cost-, becomes more complicated in today's highly competitive market. Transport models provide a good framework for dealing with this problem. Traditionally, the transportation issue was founded on the premise that the parameters of supply, demand and cost were exactly understood. In real- life cases, however, in general, all parameters of the transport problem are not correct. So it is inevitable to deal with uncertainty and inexactness while handling real world situations. Interval numbers play a major role in dealing with this uncertainty and inexactness. Ganesan et.al have discussed about interval numbers [ 6] [ 7]. In this sense, this paper is formulated as interval numbers with these parameters of the transport problem. When various modes of transport are available, then we must transport goods in a cost-effective manner and also in time from sources to destinations by different means. Several methods are available to solve problems related to interval integer transport. A very few researchers have worked in interval integer number transportation problems. Das et al. [2] by considering the interval as right bound and as the midpoint, solved the interval transportation problem. Pandian et al., [8] solved fully interval integer transportation problems by separation method. Safi et al., [9] by converting the interval fuzzy constraints into multi - objective fuzzy constraints & solved the fixed charge transportation problems. Sengupta et al., [11] proposed a method to solve interval transportation problem by taking into consideration the midpoint and width of the interval in the objective function. S. Purushothkumar et al... [14] Developed a diagonal optimal algorithm to solve the interval integer transportation problems. Many authors [3] [5] [10][12] applied a zero suffix method to solve the transportation problem with crisp values & fuzzy values. All these authors convert the given problem into crisp problem then zero suffix algorithm is applied. The proposed method is based on a zero suffix algorithm. A new ranking technique is employed to rank the fuzzy numbers. The algorithm is illustrated through an example.

II. BASIC DEFINITIONS

1. Definition 1

An interval number A is defined as A= [a, b] ={x / a ≤ x ≤b, x ?? }. Here a, b?? are the   lower and upper bound of the intervals.

2. Definition 2

Arithmetic operations on Interval Numbers [4]

Let A = [a, b] and B =[c , d] are two interval numbers.

Addition: A + B = [a ,b ] + [c , d ] =[a + c  , b + d ].

Subtraction : A + B = [a ,b ] - [c , d ] = [a - d , c – b ].

Multiplication: A * B = [ x, y ] where x = min {ac, ad, bc, bd } and y = max

{ac , ad , bc , bd}.

3. Definition 3

Let A = [a, b] and B = [c, d ] are two interval numbers. Let ? = ????????/2

And cd/2

If ? ≤ ? then A ≤ B. If ? ≥ ? then A ≥ B .

4. Definition 4: Equivalent  interval number : two interval numbers A=[a,b]and B=[c,d] are said to be equivalent if their crisp values [R(A)=R(B)] are equal.

where ij c is the interval unit transportation cost from ith source to the jth destination. The objective is to minimize the total fuzzy transportation cost, in this paper the fuzzy transportation problem is solved by interval version of Vogel’s and MODI method .

5. Definition 5: Fuzzy feasible solution is defined as a set of non-negative assignments that satisfy (in the context corresponding) the row and the column boundaries.

6.  Definition 6: An interval solution to a problem with m sources and n destinations in the transport interval is said to be a simple interval solution if the number of positive allocations is (m+n-1). When the number allocations in a simple interval solution are less than (m+n-1), then the degenerate interval is called the simple feasible solution.

7. Definition 7: An interval feasible solution is said to be optimal if it minimizes the total cost of intervals of transport.

III. INTERVAL INTEGER TRANSPORTATION PROBLEM

IV. ALGORITHM

1. Step 1: Present in the Transportation Table the problem of single interval transport.

2. Step 2: Each and every one interval parameters of the cost of supply, demand and unit transport as to the midpoint and half width of the transport problem. That is in the form of

3. Step 3: Locate the two cells in each row with the least cost and next to the least cost, then find their own separate (penalty) against the corresponding row along the table side.

4. Step 4: Locate the two cells in each column which have the least cost and find their separate (penalty) against the corresponding column under the table next to the least cost.

5. Step 5: The supreme price is set. If it is along the table side, make full assignment to the cell in that row with minimal costs. If it is under the table, at least allow the cell in that column to be allocated in full. Proceed in the same manner until the completion of all duties.

6. Step 6: Where penalties are equal for two rows / columns or more. Consider the modification among the first and the third minimum values in element-wise terms. Identify their average and assign the minimum cost for them. This step provides the initial response,

7. Step 7: Write this assigned costs on the top of the column of original assignment problem.  Let ??Cij , Dij ??? be the assigned cost for column. Subtract  assignment matrix from each entry of cost matrix, the corresponding column ??Cij , Dij????

8. Step 8: Create a rectangle such that one corner contains negative fuzzy penalty and the other two corners in the same row and column are assigned to the allocated cost values. Calculate the number of unallocated diagonal extreme cells, say. Locate all of them. Identify the most negative and share the diagonals assigned to the cell. Continue the process until all negative penalties are resolved.

V. NUMERICAL EXAMPLE

1. Example: Consider the following question of interval transport addressed by M.K.Purushothkumar, M.Ananathanarayan, S.Dhanasekar[1].

Table-1. Interval Transportation table

Express all the interval parameters ã =[a1,a2] in terms of midpoint and width as

Table-2. Interval Transportation table

Locate the two cells in each row with the least cost and next to the least cost, then find their own separate (penalty) against the corresponding row along the table side. Similarly locate the two cells in each column which have the least cost and find their separate (penalty) against the corresponding column under the table next to the least cost.

Table-3. Interval Transportation table

Apply the proposed algorithm then we get the initial solution is

Table-4. Interval Transportation table

Table-5. Interval Transportation table

r13 ? 0 , r33 ? 0 , r34 ? 0 , r42 ? 0 , r43 ? 0 , r44 ? 0

Out of all unassigned cells r43 ? 0 . We replace the allocation ?2,3? in the third column to ?4,3? and the allocation

?4,1? in the first column to ?2,1? .

Table-6. Interval Transportation table

Create a rectangle such that one corner contains negative fuzzy penalty and the other two corners in the same row and column are assigned to the allocated cost values. Calculate the number of unallocated diagonal extreme cells, say. Locate all of them. Identify the most negative and share the diagonals assigned to the cell. Continue the process until all negative penalties are resolved.

Table-7. Interval Transportation table

r11 ? 0 , r34 ? 0 , r41 ? 0 , r42 ? 0 , r44 ? 0 , therefore the optimal assignment are The optimal Solution is given by

Table-8. Interval Transportation table

The transportation cost is given by

= ?18,1? + ?6, 2? + ?55,1? + ?68,1.5? + ?6,1? + ?21,1?

= ?174, 2?

= [172,176]

VI. COMPARISION

M.K.Purushothkumaretal.,[2]       M.K.Purushothkumaretal.,[1]      Developed method

(Zero suffix algorithm)                   ( Diagonal optimal algorithm)

[92,335]                                            [82,349]                                 [172,176]

Conclusion

An algorithm is proposed for solving interval integer transportation problem by using zero suffix algorithm. This algorithm is effective and easy to understand. Numerical examples are illustrated and obtained results are compared with the available method. The comparison shows that the solution is better than the available method. In this paper we proposed using an efficient diagonal algorithm to solve the transportation of integer intervals. Algorithm is powerful and easy to understand. Even to solve any problem of transportation of integer intervals this method is useful.

References

[1] Akilbasha, P.Pandian and G.Natarajan, An innovative exact method for solving fully interval integer transportation problems, Informatics in Medicine Unlocked, 11, (2018), 95?99. [2] Chanas S., Delgado M., Verdegay J.L, Vila M.A., Interval and fuzzy extensions of classical transportation problems, Transportation Planning Technology, 17, 1993. [3] J.W. Chinneck and K. Ramadan, Linear programming with interval coefficients, Journal of the Operational Research Society, 51, (2000), 209 ? 220. [4] S. K. Das, A. Goswami and S.S. Alam, Multiobjective transportation problem with interval cost, source and destination parameters, European Journal of Operational Research, 117 (1999), 100 ? 112. [5] W. Chinneck and K. Ramadan , Linear programming with interval coefficients, Journal of the Operational Research Society, volume 51 , pages 209 – 220, 2000. [6] S.K. Das, A. Goswami and S.S. Alam ,Multiobjective transportation problem with interval cost,source and destination parameters, European Journal of Operational Research, volume 117,pages 100 – 112,1999. [7] M. R. Fegade, V. A. Jadhav and A. A. Mulley, Solving fuzzy transportation problem by zero su?x method and robust ranking technology, IOSR Journal of Engineering, 2(7) (2012), 3639. [8] Ishibuchi, H., Tanaka, H., Multiobjective programming in optimization of the interval objective function. European Journal of Operational Research, volume 48, pages 219– 225, 1990.

Copyright

Copyright © 2022 Shalini Chandran, Sumitha R. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.