An Efficient Approach for Transforming Unbalanced Transportation Problems into Balanced Problems in Order to Find Optimal Solutions

Abstract

In operations research, the transportation problem (TP) is among the earliest and most effective applications of the linear programming problem. Unbalanced transportation problems reflect the reality of supply chain and logistics situations where the available supply of goods may not precisely match the demand at different locations. To deal with an unbalanced transportation problem (UTP), it is essential first to convert it into a balanced transportation problem (BTP) to find an initial basic feasible solution (IBFS) and hence the optimal solution. The present paper is concerned with introducing a new approach to convert an unbalanced transportation problem into a balanced one and as a consequence to obtain optimum total transportation cost. Numerical examples are provided to demonstrate the suggested method.

Share and Cite:

Rashid, A. and Islam, M. (2024) An Efficient Approach for Transforming Unbalanced Transportation Problems into Balanced Problems in Order to Find Optimal Solutions. American Journal of Operations Research, 14, 74-86. doi: 10.4236/ajor.2024.141004.

1. Introduction

The transportation problem (TP) holds a critical role in operations research, offering a systematic approach to optimizing the movement of goods and resources within various industries. It serves as a mathematical model to minimize costs while efficiently transporting items from multiple origins to multiple destinations. The significance of TP lies in its ability to enhance decision-making processes, streamline supply chain management, and improve overall operational efficiency. Unbalanced transportation problems, arising from uneven supply and demand at origins and destinations, present specific challenges. Such imbalances can be caused by variations in production capacities, fluctuating resource availability, or varying demand levels. Effectively addressing these challenges requires the development of conversion methods that transform unbalanced problems into balanced ones, ensuring the application of standard optimization techniques. Optimizing unbalanced transportation problems is crucial in real-world situations such as supply chain management, logistics and distribution, e-commerce and retail, manufacturing operations, international trade, healthcare supply chains, food and perishables industry, automotive industry, energy sector, and government and public services. It helps in planning and executing transportation activities, reducing costs, improving delivery times, and enhancing operational efficiency. In e-commerce and retail, optimizing transportation is essential for timely deliveries, inventory management, and meeting customer expectations. In the energy sector, optimizing transportation is vital for efficient raw material movement and distribution. In this work, we explore an effective approach for finding optimal solutions to unbalanced transportation problems. A constant unit cost (k > 0) for dummy columns or rows can be used to turn an unbalanced transportation problem into a balanced one. This technique has various benefits and real-world applications in operations management. Some of the benefits are: 1) Feasibility and Optimality: The introduction of dummy columns or rows with a positive unit cost ensures that the transportation problem becomes feasible and can be solved using standard linear programming techniques. This facilitates the search for an optimal solution that minimizes transportation costs; 2) Realistic Cost Consideration: Assigning a positive unit cost to dummy elements reflects the actual costs associated with transporting goods from dummy sources or to dummy destinations. This realistic cost consideration provides a more accurate representation of the operational costs involved in the transportation process; 3) Sensitivity Analysis: The positive unit cost allows for sensitivity analysis. Decision-makers can assess how changes in the cost associated with the dummy elements impact the overall solution. This analysis is valuable for understanding the robustness of the optimal solution in response to variations in transportation costs; 4) Resource Allocation: In operations management, where resources are often limited, introducing a positive unit cost for dummy elements helps in optimizing resource allocation. This is particularly relevant when there are additional costs associated with obtaining supplies from alternative sources or delivering products to alternative destinations and 5) Risk Management: Operations often involve uncertainties, and introducing a positive unit cost for dummy elements can account for the costs associated with managing risks. It allows decision-makers to optimize transportation plans while considering the potential costs of alternative sourcing or distribution strategies in the face of disruptions. Some applications are: 1) Supply Chain Optimization: Operations managers can use this approach to optimize supply chain logistics by considering alternative supply sources or distribution channels with associated transportation costs; 2) Inventory Management: Optimizing transportation plans by introducing realistic costs for dummy elements helps in managing inventory more effectively. It allows for better decision-making regarding stock levels and replenishment strategies; 3) Production Planning: In manufacturing, the transportation of raw materials and finished goods often involves imbalances in supply and demand. Converting the transportation problem into a balanced form with realistic costs aids in production planning; 4) Distribution Network Design: Operations managers can use the balanced transportation model to design efficient distribution networks, considering the costs associated with alternative sourcing or delivery points; 5) Service Level Optimization: For industries where service levels vary based on transportation choices, introducing positive unit costs allows for optimizing service levels while considering the associated costs; 6) Cost-effective Transportation Planning: By incorporating realistic costs into transportation planning, operations managers can develop cost-effective and efficient transportation strategies, ultimately improving overall operational efficiency and 7) Facility Location Planning: When deciding on the location of facilities, introducing positive unit costs helps in evaluating transportation costs from potential sourcing or distribution points.

Product transportation from a set of sources (plants, factories, etc.) to a set of destinations (warehouses, store centers, etc.) is a special sort of linear programming issue where supply and demand are taken into consideration at each location. To ensure that every warehouse’s needs are satisfied and every plant runs to its full potential, the transportation challenge seeks to reduce the overall cost of delivering items from plants to warehouses. Original research on the fundamental transportation problem was done by Hitchcock [1] , while Dantzig [2] later found efficient solutions based on the simple method. There are two steps involved in solving the transportation scenario. An elementary, workable solution is found in the first stage. The literature provides a number of heuristic techniques [3] [4] for doing this, including Vogel’s Approximation Method, the Least Cost Method, and the North-West Corner Method. Modified Distribution (MODI) Method or Stepping Stone Method is used to optimize the first solution in the second phase. While the previously mentioned heuristics produce a solid initial solution for balanced transportation problems, they frequently produce a subpar initial answer for imbalanced difficulties. In practical scenarios, however, the issues with transportation might not always be evenly distributed. It is rare to find effective solutions for these kinds of issues in the literature. To address unbalanced transportation challenges, Goyal [5] suggested a modified version of Vogel’s Approximation Method (VAM), which Ramakrishnan [6] enhanced. Another solution to unbalanced transportation problems using VAM was proposed by Balakrishnan [7] . This unbalanced transportation problem was given, and Kulkarni and Datar [8] came up with a new way to change it and a solution algorithm. When tackling transportation and assignment problems that aim to maximise profit while minimising costs, Abdur Rashid [9] looked into a number of heuristic calculations. VAM is an alternative method for solving the unbalanced transportation problem, as proposed by D.K. Ghosh and Y. Zaveri [10] . Studies on imbalanced transportation issues have also been conducted by Kadhirvel and Balamurugan [11] , N. Girmay and T. Sharma [12] , Shimshak et al. [13] , Anuradha et al. [14] , Muruganandam and Srinivasan [15] , Selim Reza, A.K.M., et al. [16] . Rashid [17] contributed a theorem in the context of resolving transportation issues. Ahmed et al. [18] introduced an incessant allocation method to analyze and minimize transportation costs. Gupta and Hira [19] studied to find optimal solutions to transportation problems. Amaliah et al. [20] introduced a heuristic method to find the initial basic feasible solution to the transportation problem (TP). Rashid and Amirul [21] used two reliable techniques to find the optimal solutions to transportation problems, using variations in costs.

The existing literature on unbalanced transportation problems (UTP) often relies on using zero unit cost for dummy columns or rows for optimal solutions. However, these conventional methods have limitations. Our proposed model breaks from this tradition by endorsing the use of non-zero unit costs (i.e., any constants) for dummy columns or rows, offering an innovative perspective on transforming UTP into a balanced transportation problem. The main objectives of the study are: 1) to develop an effective technique to transform an unbalanced transportation problem into a balanced transportation problem; 2) to apply a new scheme to obtain the optimal transportation cost for unbalanced transportation problems; and 3) to provide numerical illustrations to analyze the effect of variation in parameter values on the total transportation cost of unbalanced problems. While traditional methods have strengths, their reliance on zero unit costs may oversimplify real-world logistics, potentially leading to suboptimal solutions. Our proposed approach aims to address these limitations and introduce a paradigm shift in treating UTP. In our proposed model, we advocate transforming UTP into a balanced transportation problem by using non-zero unit costs for dummy columns or rows. This unique approach introduces flexibility not present in traditional methods, considering a broader range of factors and providing a more realistic representation of the complex dynamics in supply chain management.

This paper is organized as follows: Section 2: Mathematical formulations of TP; Section 3: An effective procedure for transforming UTP into BTP; Section 4: A proposed algorithm for finding optimal solution of unbalanced transportation problem (UTP); Section 5: Numerical illustrations; Section 6: Discussion of results; and the last section: The conclusion of the paper.

2. Mathematical Formulation of TP

Let us consider m sources that contain different quantities of the commodity that must be transported to n locations to satisfy demand. Particularly, source i contains an amount a i and destination j has a need of amount b j . The cost of transporting the goods from source i to destination j has a unit cost c i j . Finding a transportation strategy that satisfies all objectives and reduces overall shipping costs is the challenge. The comparable linear programming is as follows if the variables x i j reflect the volume of the commodity sent from source i to destination j:

Minimize z = i = 1 m j = 1 n c i j x i j .

Subject to

j = 1 n x i j = a i , i = 1 , 2 , , m i = 1 m x i j = b j , j = 1 , 2 , , n x i j 0 , i , j . .

It is assumed that the system is balanced in the sense that total supply equals total demand.

That is, i = 1 m a i = j = 1 n b j where a i 0 and b j 0 .

But in real life business situations, the supply may be greater than the demand or the demand may be greater than the supply. These situations are known as unbalanced transportation problems.

3. Effective Procedure for Transforming UTP into BTP

An unbalanced transportation problem (UTP) occurs when the total supply of goods does not equal the total demand. To find an optimal solution for an unbalanced transportation problem using the effective procedure for transforming UTP into BTP (Balanced Transportation Problem), introduce dummy sources or destinations to balance the problem. These dummy sources or destinations represent the difference between total supply and total demand.

Case I: Total supply is higher than total demand

When the available supply at sources is greater than the requirements of the destinations, i.e.

i = 1 m a i > j = 1 n b j .

In this case, the transportation problem’s linear programming model will be unable to find a feasible solution. We add a fictional (imaginary) demand point with a value equal to the surplus supply in order to build a balanced model. Consequently, the transportation tableau gains a dummy column. However, each cell of the dummy column has any cost of (k) units. In tabular representation (Table 1):

Where, b n + 1 = i = 1 m a i j = 1 n b j and c i , n + 1 = k for i = 1 , 2 , , m .

Thus, the objective function of the proposed balanced transportation problem is as follows:

Minimize, Z = i = 1 m j = 1 n + 1 c i j x i j .

Table 1. Balanced transportation problem using dummy column.

Therefore, the total cost of the unbalanced transportation problem (UTP) can be obtained as follows:

Minimize, Z * = Z i = 1 m k x i , n + 1 .

Subject to

j = 1 n + 1 x i j = a i , i = 1 , 2 , , m i = 1 m x i j = b j , j = 1 , 2 , , n + 1 x i j 0 , i , j . .

Case II: Total demand is higher than total supply.

In situations where the total requirements of the destinations exceed the total supply of sources, i.e.,

i = 1 m a i < j = 1 n b j ,

the issue can then be resolved by creating an imaginary supply point that has an amount equal to the excess demand. Consequently, the transportation tableau gains a dummy row. Each cell of the dummy row has any cost of (k) units.

In tabular form (Table 2):

Where a m + 1 = j = 1 n b j i = 1 m a i and c m + 1 , j = k for j = 1 , 2 , , n .

Thus, the objective function of the proposed balanced transportation problem is as follows:

Minimize, Z = i = 1 m + 1 j = 1 n c i j x i j .

Therefore, the total cost of the unbalanced transportation problem (UTP) can be obtained as follows:

Minimize, Z * = Z j = 1 n k x m + 1 , j .

Subject to

Table 2. Balanced transportation problem using dummy row.

j = 1 n x i j = a i , i = 1 , 2 , , m , m + 1 i = 1 m + 1 x i j = b j , j = 1 , 2 , , n x i j 0 , i , j . .

It is remarkable that the dummy cells in the transportation tableau are comparable to slack variables, which have zero c i j values in the objective function and do not change the initial solution.

4. Proposed Algorithm for Finding Optimal Solution of UTP

In this part, we outline an effective approach for making an unbalanced transportation problem into a balanced one for finding optimal solution.

The steps in the suggested procedure are as follows:

5. Numerical Illustrations

Example 5.1: In locations A, B, and C, a company operates three facilities that provide goods to warehouses in D, E, F, G, and H. 900, 1200, and 1800 units per month are the plant’s various capacity levels. The number of units needed each month for the warehouse is 300, 350, 500, 650, and 400. Below is a breakdown of shipping prices per unit. In order to reduce the company’s overall transportation costs, an optimal distribution must be identified (Table 3).

Here total capacity = 3900 units, total requirement = 2200 units. So introduce a dummy warehouse having all transportation costs equal to a constant quantity, say 127 and having the warehouse requirement equal to (3900 − 2200) = 1700 units. The modified balanced transportation matrix is shown below (Table 4).

Using Least Cost Method [4] the following allocations are obtained (Table 5).

After being checked by MODI method, it is observed that the solution obtained in Table 5 is optimal one. In this scenario, the optimal solution of the modified cost matrix coincides with the initial solution.

Hence the optimal solution is

x 11 = 250 , x 14 = 650 , x 21 = 50 , x 23 = 500 , x 25 = 400 , x 26 ( Dummy ) = 250 , x 32 = 350 , x 36 ( Dummy ) = 1450 .

The optimum total transportation cost for BTP is

5 × 250 + 4 × 650 + 7 × 50 + 13 × 500 + 8 × 400 + 127 × 250 + 6 × 350 + 127 × 1450 = 231900

Total cost for UTP ( TC ) = Total cost for BTP k × demandatdummydestination = 231900 127 × 1700 = 16000 .

Table 3. Cost matrix of UTP.

Table 4. Modified cost matrix for BTP using dummy column.

By inserting zero-unit costs in the dummy column, the same optimal result is also attained (Table 6).

Example 5.2: Consider the following frequent unbalanced transportation problem when total demand is higher than total supply (Table 7).

Here the total supply is 1025 units while the total demand is 1250 units. Creating a dummy row (source) for an amount = (1250 − 1025) = 225 units, with all cost elements equal to any constant quantity, say 150, we obtain the balanced transportation problem as follows (Table 8).

Implementing Vogel’s approximation method [4] , we obtain the following allocations (Table 9).

Applying Modified distribution (MODI) method in Table 9, the optimal allocations are as follows (Table 10).

Table 5. Initial solution of modified cost matrix.

Table 6. Effect of different values of k for optimal solutions of UTP.

Table 7. Cost matrix of UTP.

Table 8. Modified cost matrix for BTP using dummy row.

Table 9. Initial solution of modified cost matrix.

Table 10. Optimal solution of modified cost matrix.

Hence the optimal solution is:

x 11 = 225 , x 14 = 100 , x 22 = 80 , x 23 = 320 , x 32 = 300 , x 41 ( Dummy ) = 5 , x 42 ( Dummy ) = 220 .

The optimum total transportation cost for BTP is

4 × 225 + 3 × 100 + 8 × 80 + 6 × 320 + 6 × 300 + 150 × 5 + 150 × 220 = 39310

TotalcostforUTP = TotalcostforBTP k × supplyatdummysource = 39310 150 × 225 = 5560 .

In traditional approach, if we construct the given unbalanced transportation problem into balanced one by adding a dummy source with zero-unit costs, the same optimal solution is also obtained (Table 11).

6. Results and Discussions

Analyzing the effect of optimal solution variations in the constant unit cost for dummy elements in an unbalanced transportation problem is essential for effective decision-making and resource management. Unbalanced transportation problems often arise in real-world scenarios where supply and demand do not align perfectly. By understanding how the optimal solution responds to changes in the unit cost for dummy elements, organizations gain insights into the robustness and sensitivity of their transportation plans. This analysis allows for the identification of critical cost points, helping organizations to strategically allocate resources and make informed decisions. It aids in risk management by providing an understanding of how variations in transportation costs might impact the overall budget and profitability. We observed from Table 6 that when we changed the values of parameter k in the dummy column, the optimal solution, x 11 = 250 , x 14 = 650 , x 21 = 50 , x 23 = 500 , x 25 = 400 , x 26 ( Dummy ) = 250 , x 32 = 350 , x 36 ( Dummy ) = 1450 and total transportation cost (TC) = 16,000 remained unchanged. And also, we observed that from Table 11, when we changed the values of parameters k of dummy row, the optimal solution x 11 = 225 , x 14 = 100 , x 22 = 80 , x 23 = 320 , x 32 = 300 , x 41 ( Dummy ) = 5 , x 42 ( Dummy ) = 220 , and total transportation cost (TC) = 5560, remained unchanged. Furthermore, such analysis supports the continuous improvement of transportation strategies, enabling organizations to adapt to evolving market conditions and align their operations with broader organizational objectives. Ultimately, a thorough examination of the effect of optimal solution variations in the face of changing costs ensures that transportation plans remain resilient, cost-effective, and well-aligned with the dynamic needs of the organization.

Table 11. Effect of different values of k for optimal solutions of UTP.

7. Conclusion

In this paper, we have developed an efficient approach to make an unbalanced transportation problem into a balanced one thereby obtaining optimum total transportation cost. Numerous examples are solved using TORA optimization software to show the validity of the proposed method. It has been observed that the proposed method provides the same optimal solution for an unbalanced transportation problem as that obtained by the traditional method available in the literature. Hence, we conclude that the approach proposed herein can be an important tool for decision-makers who are dealing with transportation problems of unbalanced in nature. The advantages and applications of converting an unbalanced transportation problem into a balanced one with a positive unit cost for dummy elements in operations management are numerous. This approach enables more realistic modeling, facilitates optimization, and supports decision-making in areas such as supply chain management, inventory management, production planning, and distribution network design. This approach can also be extended for profit maximization in an unbalanced transportation problem.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1] Hitchcock, F.L. (1941) The Distribution of a Product from Several Sources to Numerous Localities. Journal of Mathematical Physics, 20, 224-230.
https://doi.org/10.1002/sapm1941201224
[2] Dantzig, G.B. (1963) Linear Programming and Extensions. Princeton University Press, Princeton.
https://doi.org/10.7249/R366
[3] Taha, H.A. (2004) Operations Research: An Introduction. Prentice Hall of India, New Delhi.
[4] Kasana, H.S. and Kumar, K.D. (2005) Introductory Operations Research: Theory and Applications. Springer International, New Delhi.
[5] Goyal, S.K. (1984) Improving VAM for Unbalanced Transportation Problems. Journal of Operational Research Society, 35, 1113-1114.
https://doi.org/10.1057/jors.1984.217
[6] Ramakrishnan, C.S. (1988) An Improvement to Goyal’s Modified VAM for the Unbalanced Transportation Problem. Journal of Operational Research Society, 39, 609-610.
https://doi.org/10.1057/jors.1988.101
[7] Balakrishnan, N. (1990) Modified Vogel’s Approximation Method for the Unbalanced Transportation Problem. Applied Mathematics Letters, 3, 9-11.
https://doi.org/10.1016/0893-9659(90)90003-T
[8] Kulkarni, S.S. and Dattar, H.G. (2010) On Solution to Modified Unbalanced Transportation Problem. Bulletin of the Marathwada Mathematical Society, 11, 20-26.
[9] Rashid, A. (2015) Development of Effective Algorithmic Heuristics for Solving Transportation and Assignment Problems. Ph.D. Thesis, Department of Mathematics, Jahangirnagar University, Jahangirnagar.
[10] Ghosh, D.K. and Zaveri, Y. (2013) Another Approach for Solving Unbalanced Transportation Problem Using Vogel’s Approximation Method. International Journal of Research in Commerce, IT & Management, 3, 45-48.
[11] Kadhirvel, K. and Balamurugan, K. (2013) Method for Solving Unbalanced Transportation Problem Using Trapezoidal Fuzzy Numbers. International Journal of Engineering Research and Applications, 3, 2591-2596.
[12] Girmay, N. and Sharma, T. (2013) Balance an Unbalanced Transportation Problem by a Heuristic Approach. International Journal of Mathematics and Its Applications, 1, 12-18.
[13] Shimshak, D.G., Kashlik, J.A. and Barclay, T.D. (1981) A Modification of Vogel’s Approximation Method through the Use of the Heuristics. INFOR: Information Systems and Operational Research, 19, 259-263.
https://doi.org/10.1080/03155986.1981.11731827
[14] Anuradha, D., Pandian, P. and Natarajan, G. (2012) Solving Unbalanced Transportation Problems with Budgetary Constraints. Journal of Physical Sciences, 16, 85-92.
[15] Muruganandam, S. and Srinivasan, R. (2016) A New Approach for Solving Unbalanced Fuzzy Transportation Problem. Asian Journal of Research in Social Sciences and Humanities, 6, 673-680.
https://doi.org/10.5958/2249-7315.2016.00143.X
[16] Selim Reza, A.K.M., Jalal Uddin Jamali, A.R.M. and Biswas, B. (2019) A Modified Algorithm for Solving Unbalanced Transportation Problems. Journal of Engineering Science, 10, 93-101.
[17] Rashid, A. (2016) Development of a Simple Theorem in Solving Transportation Problems. Journal of Physical Sciences, 21, 23-28.
[18] Ahmed, M.M., Khan, A.R., Ahmed, F. and Uddin, Md.S. (2016) Incessant Allocation Method for Solving Transportation Problems. American Journal of Operations Research, 6, 236-244.
https://doi.org/10.4236/ajor.2016.63024
[19] Gupta, P.K. and Hira, D.S. (2005) Problems in Operations Research. S. Chand & Company Ltd, New Delhi.
[20] Amaliah, B., Fatichah, C. and Suryani, E. (2022) A New Heuristic Method of Finding the Initial Basic Feasible Solution to Solve the Transportation Problem. Journal of King Saud University—Computer and Information Sciences, 34, 2298-2307.
https://doi.org/10.1016/j.jksuci.2020.07.007
[21] Rashid, A. and Islam, Md.A. (2023) Analysis of the Impact of Optimal Solutions to the Transportation Problems for Variations in Cost Using Two Reliable Approaches. American Journal of Computational Mathematics, 13, 607-618.
https://doi.org/10.4236/ajcm.2023.134033

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.