A revised ASM method for solving time transportation problem

Introduction

A special category of linear programming problems, called the Transportation Problem (TP), appears very frequently in practical situations. In modern times, it has become highly important in industries where goods are produced at multiple locations and need to be transported to different destinations. Traditionally, solving a TP involves two main steps. First, an Initial Basic Feasible Solution (IBFS) is obtained using existing methods. After that, the optimal solution is determined by applying the MODI (Modified Distribution) method. Alternatively, the Stepping Stone Method, introduced by Charnes et al. (1953) [1] , can also be used in place of the MODI method. However, these conventional approaches usually require lengthy and complex calculations to reach the optimal solution. To reduce this computational effort, Quddoos et al. (2012) [2] proposed the ASM Method, which is capable of directly providing an optimal solution. This method significantly decreases the amount of calculation required. However, further research revealed that in some cases, the ASM Method does not directly yield the optimal solution. Instead, it produces an IBFS that is very close to the optimal one. This issue is particularly observed in unbalanced transportation problems. These observations led to the need for modifying the existing ASM Method so that it can be effectively applied to all types of classical deterministic transportation problems. In this paper, a revised version of the ASM Method is presented. To demonstrate the effectiveness of the proposed method, six randomly selected numerical examples are solved using the revised method as well as two other existing methods. The comparison shows that the revised method is capable of providing the optimal solution directly in most cases. Even when it does not, it produces the best IBFS. Since a better IBFS reduces the number of iterations required in the MODI method to reach optimality, the revised ASM Method is preferable over methods like VAM and ZSM.

Preliminaries:

In this section some fundamental concepts are reviewed

Transportation Problem

A Transportation Problem is a special type of linear programming problem that deals with finding the most economical way of transporting goods from multiple sources (such as factories, warehouses, or supply centers) to multiple destinations (such as markets, stores, or demand centers). The objective is to minimize the total transportation cost while satisfying the supply available at each source and the demand required at each destination. It assumes that the transportation cost per unit between each source and destination is known. Transportation problems are widely used in logistics, supply chain management, production planning, and distribution systems to optimize resource allocation efficiently.

Mathematical Model of Transportation Problem

Given m origins and n destinations, the transportation problem can be formulated as the following linear programming problem model:

j=1, 2,……….n 𝑥 𝑖𝑗 ≥ 0 for all i and j Where 𝑥 𝑖𝑗 is the amount of units of shipped from origin 𝑖 to destination 𝑗 and 𝑐 𝑖𝑗 is the cost of shipping one unit from origin 𝑖 to destination 𝑗. The amount of supply at origin is ai and the amount of destination 𝑗 is 𝑏 𝑗 . The objective is to determine the unknown 𝑥 𝑖𝑗 that will the total transportation cost while satisfying all the supply and demand constraints.

Time Minimizing Transportation Problem

In a time minimizing transportation problem, the time of transporting goods from m origins to n destinations is minimized, satisfying the certain condition in respect of availability at sources and requirements at the destinations. Thus, the time minimizing transportation problem is: Here 𝑡 𝑖𝑗 is the time of transporting goods from the 𝑖 𝑡ℎ origin, where availability is 𝑎 𝑖 to the 𝑗 𝑡ℎ destination, where the requirement is 𝑏 𝑗 . For any given feasible solution, X = [𝑥 𝑖𝑗 ] satisfying (2.1), the time of transportation is the maximum of 𝑡 𝑖𝑗 's among the cells in which there are positive allocations, i.e., corresponding to the solution X, the time of transportation is

The aim is to minimize the time of transportation. Such problems arise when it is required to transport perishable goods during war days; it is required to transport food and armament in the shortest possible time.

Revised ASM Method: This section presenting the working procedure to solve time transportation model as follows

Step 1: Form the transportation table using the given data. Check whether the problem is balanced.

Step 2: If the problem is unbalanced, one of the following situations will occur: a) When total supply is greater than total demand, add a dummy column to absorb the extra supply. The transportation cost for each cell in this dummy column is taken as M, where M is a very large positive number. b) When total demand is greater than total supply, add a dummy row to fulfill the extra demand. The cost for each cell in this dummy row is also taken as M, where M is a very large positive number.

Step 3: (a) For case (a), first find the smallest element in each row and subtract it from all elements of that row. Then, in the new table, find the smallest element in each column and subtract it from all elements of that column. After this, go to

Step 5. (b) For case (b), first find the smallest element in each column and subtract it from all elements of that column. Then, in the new table, find the smallest element in each row and subtract it from all elements of that row. After this, go to Step 5

Step4: If the problem is already balanced, subtract the smallest element of each row from its respective row. Then, subtract the smallest element of each column from its respective column.

Step5: In the reduced table, each row and column will have at least one zero. For every zero, count how many other zeros are present in its row and column (excluding that zero itself). Write this count as a subscript for that zero. Repeat this for all zeros.

Step6: Select the zero having the smallest subscript value and allocate the maximum possible quantity to that cell. If there is a tie, choose the zero whose corresponding row and column have the highest total sum of elements, and then allocate the maximum possible quantity.

Step7: After allocation, remove the row (or column) where the supply is fully used up (or demand is completely satisfied). If both a row and a column are satisfied at the same time, remove only one of them. Assign zero supply (or demand) to the remaining row (or column) for further steps.

Step 8: Check whether each row and column in the reduced table still contains at least one zero.

Otherwise, move to Step 9.

Step 9: Repeat Steps 5 to 8 until all supplies are used up and all demands are fulfilled.

Step 10. Determine 𝑇 𝑗 for this basic feasible solution and cross out all the non-basic cells for which 𝑡 𝑖𝑗 ≥ 𝑇 𝑗 .

Step 11. Construct a loop for the basic cells corresponding to 𝑇 𝑗 in such a way that when the values at the corner cells are shifted around, the value at this cell tends towards zero and no variable becomes zero. If no such closed path can be formed, the solution under test is optimal, otherwise move on to the next step.

Step 12. Go to Step 10 and repeat the procedure until an optimum basic feasible solution is attained.

Numerical Example

In this consider two numerical problem i.e balanced and unbalanced for oil corporation has got three refiners 𝑆 1, 𝑆 2, 𝑎𝑛𝑑 𝑆 3, and it has to send petrol to four different depots 𝐷 1, 𝐷 2, 𝐷 3, and 𝐷 4, . The time of Shipping petrol from each refinery to each depot is given below. The supply of the depots and the Demand petrol as the refineries are also given.

Find the minimum time of shipping of petrol Now identified the smallest element of each column and subtract it from all elements of that column and found that following table as follows.

Balanaced Transportation Problem

We allocate 𝑆 2 𝐷 3 The final table is given below: Now, above mentioned table we cannot found any closed path to reduce the total transportation time of all the shipment form 𝑇 1 = 4 hours. Hence our feasible plan already presents in optimal stage. Thus, all the shipments of this problem can be made in within 4 hours According to step 1, we founded that sum of demand is not equal to the sum of supply i.e.

Unbalanced Transportation Problem

Since, transportation problem is unbalanced. Because in this problem sun of supply is greater then, sum of demand i.e.

Now, according step 2 we introduce a dummy row 𝑆 4 to convert unbalanced into a balanced problem. According to step 3, identified the smallest element from each row and subtract it from all element of that row and obtained the following table as follows Now, above mentioned table we cannot found any closed path to reduce the total transportation time of all the shipment form 𝑇 1 = 7 hours. Hence our feasible plan already presents in optimal stage. Thus, all the shipments of this problem can be made in within 7 hours.

Conclusion

This study introduced a revised ASM method for solving Time Transportation Problems arising in petroleum transportation and distribution systems. The method was successfully applied to two different cases of an oil corporation: a balanced transportation problem and an unbalanced transportation problem. The primary objective was to minimize the total shipping time of petrol while satisfying supply and demand requirements. The numerical investigations revealed that the revised ASM method provides an efficient and straightforward approach for obtaining optimal solutions to time transportation problems. The method requires fewer computational steps and produces reliable allocations for both balanced and unbalanced cases. Furthermore, the proposed approach effectively minimizes transportation time, thereby enhancing operational efficiency and improving distribution planning.

The results demonstrate that the revised ASM method is a practical and powerful optimization technique for logistics management in the petroleum industry. The methodology can be extended to other real-life transportation and distribution problems where time minimization is a critical factor. Future research may focus on incorporating fuzzy parameters, multiple objectives, and uncertainty in transportation networks to further enhance the applicability of the proposed method.

References

1. Charnes A, Cooper WW, Henderson A. An Introduction to Linear Programming. New York: Wiley; 1953.
2. Quddoos A, Javaid S, Khalid MM. A new method for finding an optimal solution for TPs. International Journal on Computer Science and Engineering. 2012;04:12711274.
3. Sharma JK. Operations Research: Theory and Applications. New Delhi: Macmillan India Ltd.; 2003.
4. Sudhakar VJ, Arunsankar N, Karpagam T. A new approach for finding an optimal solution for TPs. European Journal of Scientific Research. 2012;68:254257.
5. Swarup K, Gupta PK, Mohan M. Operations Research: Tracts in Operations Research. New Delhi: Sultan Chand & Sons; 2002.