Geektonight

Transportation Problem: Finding an Optimal Solution

  • Post last modified: 27 July 2022
  • Reading time: 15 mins read
  • Post category: Operations Research

The transportation problem is an important Linear Programming Problem (LPP). This problem depicts the transportation of goods from a group of sources to a group of destinations. The whole process is subject to the availability and demand of the sources as well as destination, respectively in a way, where entire cost of transportation is minimised.

Sometimes, it is known as Hitchcock problem. Generally, transportation costs are involved in such problems but the scope of problems extends well beyond to hide situations that do not have anything to try with these costs.

Table of Content

  • 1.1 Step 1: Obtaining the Initial Feasible Solution
  • 1.2 Step 2: Testing the Optimality
  • 1.3 Step 3: Improving the Solution
  • 2 Stepping Stone Method
  • 3.1 Degeneracy in Transportation Problem
  • 3.2 Unbalanced Transportation Problem
  • 3.3 Alternative Optimal Solutions
  • 3.4 Maximisation Transportation Problem
  • 3.5 Prohibited Routes

The term β€˜transportation’ is related to such problems principally because in studying efficient transportation routes, a special procedure was used which has come to be referred to as the transportation method.

A typical transportation problem is a distribution problem where transfers are made from various sources to different destinations, with known unit costs of transfer for all source-destination combinations, in a manner that the total cost of transfers is the minimum. In this chapter, you will discuss how to improve an optimal solution by stepping stone method and describe the special cases in the transportation problems.

Finding Optimal Solution Using the Stepping Stone Method

A typical transportation problem is like this. Let’s consider that a man- ufacturer of refrigerators runs three plants located at different places called A, B and C. Suppose further that his buyers are located in three regions X, Y and Z where he has got to supply them the products.

So, the need within the three regions as well as production in several plants per unit time period are known and equal in aggregate and further that the cost of one transporting refrigerator from each plant to each of the requirement centres is given and constant.

The manufacturer’s problem is to determine as to how he should route his product from his plants to the marketplaces so that the total cost involved in the transportation is minimized. In other words, he needs to decide on how many refrigerators should be supplied from A to X, Y and Z, how many from B to X, Y and Z and how many from C to X, Y and Z to attain it at the least cost.

The places where the products originate from (the plants in our example) are called the sources or the origins and places where they are to be supplied are the destinations. In this terminology, the trouble of the manufacturer is to decide on how many units are transported from different origins to different destinations in order that the overall transportation cost is the minimum.

The transportation method is an efficient alternative to the simplex method for solving transportation problems.

Step 1: Obtaining the Initial Feasible Solution

To use the transportation method is to get a feasible solution, namely, the one that satisfies the rim requirements (i.e., the requirements of demand and supply). The initial feasible solution may be obtained by various methods.

  • Row Minima Method
  • Column Minima Method
  • North-West Corner (NWC) Rule
  • Least Cost Method (LCM)
  • The Vogel’s Approximation Method (VAM)

Step 2: Testing the Optimality

After obtaining the initial basic feasible solution, the successive step is to check whether it is optimal or not. There are two methods of testing the optimality of a basic feasible solution. One of these is named the stepping-stone method within which the optimality test is applied by calculating the opportunity cost of each empty cell.

The other method is named as the Modified Distribution Method (MODI). It is based on the concept of dual variables that are used to evaluate the empty cell. Using these dual variables, the opportunity cost of each of the empty cell is determined. Thus, while both methods involves determining opportunity costs of empty cells, the methodology employed by them differs.

Both the methods can be used only when the solution is a basic feasible solution so that it has m + n – 1 basic variables. If a basic feasible solution contains less than m + n – 1 non-negative allocation, then the transportation problem is said to be a degenerate one. Incidentally, none of the methods used to find initial solution would yield a solution with greater than m + n – 1 number of occupied cells.

Step 3: Improving the Solution

By applying stepping stone method, if the answer is found to be optimal, then the process terminates because the problem is solved. If the answer is not seen to be optimal, then a revised and improved basic feasible solution is obtained. This can be done by exchanging a non-basic variable for a basic variable.

In simple terms, rearrangement is formed by transferring units from an occupied cell to an empty cell that has the largest opportunity cost, then adjusting the units in other related cells in a way that each one of the rim requirements are satisfied. The solution obtained is again tested for optimality and revised, if necessary. You continue this manner until an optimal solution is finally obtained.

Stepping Stone Method

This is a procedure for determining the potential, if any, of improving upon each of the non-basic variables in terms of the objective function.

To determine this potential, each of the non-basic variables (empty cells) is taken into account one by one. For each such cell, you discover what effect on the overall cost would be if one unit is assigned to the present cell. With this information, then, you come to understand whether the solution is optimal or not.

If not, you improve that solution. This method is derived from the analogy of crossing a pond using stepping stones. It concludes that the whole transportation table is assumed to be a pond and the occupied cells are the stones required to build specific movements inside the pond.

Stepping stone method helps in determining the change in net cost by presenting any of the vacant cells into the solution. The main rule of the stepping stone method is that every increase (or decrease) in supply in one occupied cell must be associated with a decrease (or increase) in supply in another cell. The same rule also holds for demand.

The steps involved in the stepping stone method are as follows:

  • Determine Initial Basic Feasible Solution (IBFS). Make sure the number of occupied cells is exactly equal to m + n βˆ’ 1. 2. Evaluate the cost-effectiveness of shipping goods via transpor- tation routes for the testing of each unoccupied cell. For this, se- lect an unoccupied cell and trace a closed path using the straight route in which at least three occupied cells are used.
  • Assign plus (+) and minus (βˆ’) signs alternatively in the corner cells of the closed path (identified in step 2). The unoccupied cell should be assigned with a plus sign.
  • Add the unit transportation costs associated with each of the cell traced in the closed path. This would give the net change in terms of cost.
  • Repeat steps 2 to 4 until all unoccupied cells are evaluated.
  • Check the sign of each of the net change in the unit transportation costs. If all the net changes calculated are more than or equal to zero, an optimal solution has been attained. If not, then it is possible to advance the current solution and minimise the total transportation cost.
  • Select the vacant cell with the highest negative net cost change and calculate the maximum number of units that can be assigned to this cell. The smallest value with a negative position on the closed path indicates the number of units that can be shipped to the entering cell. Add this number to the unoccupied cell and all other cells on the route having a plus sign and subtract it from the cells marked with a minus sign.
  • Repeat the procedure until we get an optimal solution.

Special Cases in the Transportation Problems

Transportation is all about getting a product from one place to another, put the product on a truck or railcar and you are good to go. Well, not exactly. There’s a bit more that goes into it. It becomes particularly complicated when there are multiple places the product is coming from, and multiple places the product is going to.

Transportation managers must do to some calculations to find the optimum path for getting their product to the customer. Let us look at some common problems a transportation manager might encounter. One common transportation issue has to do with supply and demand.

Some variations that often arise while solving the transportation problem could be as follows:

Degeneracy in Transportation Problem

In a standard transportation problem with m sources of supply and n demand destinations, the test of optimality of any feasible solution requires allocations in m + n – 1 independent cells. Degeneracy occurs whenever the number of individual allocations are but m + n – 1, where m and n are the number of rows and columns of the transportation problem, respectively. Degeneracy in transportation problem can develop in two ways.

  • The basic feasible solution might have been degenerate from the initial stage
  • They may become degenerate at any immediate stage

To resolve degeneracy a little positive number, Ξ” is assigned to at least one or more unoccupied cell that have lowest transportation costs so on make N = m + n – 1 allocations. (Ξ” is an infinitesimally small number almost equal to zero.)

Although there is a great deal of flexibility in choosing the unused square for the Ξ” stone, the general procedure, when using the North West Corner Rule, is to assign it to a square in such how that it maintains an unbroken chain of stone squares. However, where Vogel’s method is used, the Ξ” allocation is carried during a least cost independent cell.

An independent cell during this context means a cell which cannot cause a closed path on such allocation. After this, the test of optimality is applied and if necessary, the solution is improved within the normal way until optimality is reached.

Unbalanced Transportation Problem

When the total supply of all the sources is not equal to the total demand of all destinations, the problem is an unbalanced transportation problem.

Two situations are possible: 1. If supply < demand, a dummy supply variable is introduced in the equation to make it equal to demand 2. If demand < supply, a dummy demand variable is introduced in the equation to make it equal to supply

Then before solving you must balance the demand and supply. The unit transportation cost for the dummy column and dummy row are assigned zero values, because no shipment is really made just in case of a dummy source and dummy destination.

Alternative Optimal Solutions

An alternate optimal solution is additionally called as an alternate optima, which is when a linear / integer programming problem has more than one optimal solution. Typically, an optimal solution may be a solution to a problem which satisfies the set of constraints of the problem and, therefore, the objective function which is to maximise or minimise. It is possible for a transportation problem to possess multiple optimal solutions.

This happens when one or more of the development indices zero within the optimal solution, which suggests that it’s possible to style routes with an equivalent total shipping cost. The alternate optimal solution is often found by shipping the foremost to the present unused square employing a stepping-stone path. Within the world, alternate optimal solutions provide management with greater flexibility in selecting and using resources.

Maximisation Transportation Problem

The main motive of transportation model is used to minimise transportation cost. However, it also can be used to get a solution with the objective of maximising the overall value or returns. Since the criterion of optimality is maximisation, the converse of the rule for minimisation will be used. The rule is: a solution is optimal if all – opportunity costs dij for the unoccupied cell are zero or negative.

Hence, how does all this help the business overall? If a business’ objective is to maximise profits, then finding the answer to transportation problems allows the companies to use the results from the matrixes to maximise their objective and obtain the foremost profit they will. Profit is often calculated by using this easy formula.

Profit = Selling price – Production cost – Transportation cost

If the objective of a transportation problem is to maximise profit, a minor change is required in the transportation algorithm. Now, the optimal solution is reached when all the development indices are negative or zero. The cell with the most important positive improvement index is chosen to be filled by employing a stepping-stone path. This new solution is evaluated and therefore the process continues until there are not any positive improvement indices.

Prohibited Routes

At times there is transportation problems during which one among the sources is unable to ship to at least one or more of the destinations. When this happens, the problem is claimed to have an unacceptable or prohibited route.

In a minimisation problem, such a prohibited route is assigned a really high cost to prevent this route from ever getting used within the optimal solution. In a maximisation problem, the very high cost utilised in minimisation problems is given a negative sign, turning it into an awfully bad profit.

Sometimes there could also be situations, where it is unacceptable to use certain routes during a transportation problem. For example, road construction, bad road conditions, strike, unexpected floods, local traffic rules, etc.

Such restrictions (or prohibitions) will be handled within the transportation problem by assigning a very high cost (say M or [infinity]) to the prohibited routes to make sure that routes will not be included within the optimal solution then the matter is solved within the usual manner.

You Might Also Like

Project network analysis methods, simulation in operation research, transportation problem: initial basic feasible solution, project evaluation and review technique (pert), project network analysis with critical path method, operation research models and modelling, what is operations research (or) definition, concept, characteristics, tools, advantages, limitations, applications and uses, linear programming: simplex method, duality in linear programming, linear programming: graphic solution, replacement models in operation research, what is linear programming assumptions, properties, advantages, disadvantages, leave a reply cancel reply.

You must be logged in to post a comment.

World's Best Online Courses at One Place

We’ve spent the time in finding, so you can spend your time in learning

Digital Marketing

Personal growth.

how to solve transportation problem using stepping stone method

Development

how to solve transportation problem using stepping stone method

Stepping Stone | Transportation Problem | Transportation Model

As we discussed in MODI method that, to understand these methods which will be used to get optimum solution to transportation problem , we need to get knowledge of optimality test first.

Jump to Stepping Stone Method or Modified Distribution Method (MODI) for optimizing solution to transportation problem .

Optimality Test :

β†’ Optimality test is carried to check whether the basic feasible solution (BFS) obtained by any of different methods ( Vogel's Approximation Method (VAM) , Least Cost Method or North West Corner Method | Method to Solve Transportation Problem | Transportation Model ) is optimum or not!

β†’ This test is done only after fulfilling two requirements as follows:

a) Total number of non-negative allocation is (m+n-1). b) These allocations are in independent cells. where, m = no. of rows & n = no. of columns

β†’ There are two different methods used for checking whether the solution to transportation problem is optimal or not.

Stepping Stone Method Modified Distribution Method (MODI)

Stepping Stone Method:

β†’ In basic feasible solution (BFS) , there will be unallocated cells. In this method, for checking the optimality of the solution obtained, we arbitrarily select any of the unoccupied cells and then we allocate units to that unit, and subsequently we deduct from other cells in the matrix, such that supply and demand are not altered.

β†’ If net change in cost comes out negative, then we conclude that the new allocated cell can improve the BFS and the present solution has opportunity for improvement.

β†’ If net change in cost comes out positive for that allocated cell , then the present solution is optimal.

β†’ In this method, this procedure is carried out for all vacant cells. If any of unallocated cell gives net change in cost as negative, then from that cell we can improve the present solution.

Let us now understand how one can apply Stepping Stone Method. We will understand it using a numerical as follows:

Applying Stepping Stone Method - Numerical

Question : check optimality of the basic feasible solution given below by using stepping stone method..

how to solve transportation problem using stepping stone method

Note that all the explanation is provided in β€œCYAN” colour. You have to write in examination the only thing which are given in this regular colour under each steps (if any), else you can directly solve matrix of the problem as explained here.

β†’ Here in the given numerical the unoccupied/unallocated cells are: PA, PB, QB & RC.

how to solve transportation problem using stepping stone method

β†’ Draw the closed loop (as shown above) from cell PA (unallocated cell) and complete the loop by using allocated cells .

β†’ Closed loop as following will be formed :

PA β†’ PC β†’ QC β†’ QA

β†’ Mark (+) & (-) sign alternatively at each corner, starting from the original unallocated cell as shown above.

β†’ Find the net change in the cost: For PA cell; net change in cost will be;

β†’ Similarly, repeat the procedure for all unallocated cells.

how to solve transportation problem using stepping stone method

Rules to create closed loops : Start a loop from unallocated cell and then use allocated cells to complete the loop. Only horizontal and vertical movements are allowed and for once at a time. Diagonal movements are not allowed. Only two cells should be used in a specific row or column while creating a loop.

β†’ For explanation purpose we are showing extra step here, illustrating allocation of cell PB.

You can show all allocations in the same matrix in the examination, but add the table as shown below. Use different lines for different loops, so that you and supervisor both can easily distinguish between loops. Tips for drawing lines for loops : β†’ Use ball-point pen and pencil to get two different lines. β†’ If you have black pen then, draw one loop with black colour. β†’ Upon limitation to colour pens and pencil, you can use different line patterns as straight line, dashed lines, curvy lines, centre lines, etc.

how to solve transportation problem using stepping stone method

Note that :

In Stepping Stone method, if the net cost change are/is:

(i) β‰₯ 0 \ge 0 β‰₯ 0 β†’ then the current basic feasible solution (BFS) is optimal and stop the procedure.

(ii) < 0 < 0 < 0 β†’ then the current basic feasible solution (BFS) is not optimal and further improvement is possible.

β†’ As here all the net cost change are positive (+) or β‰₯ 0 \ge 0 β‰₯ 0 , the present solution is optimal.

Limitations of Stepping Stone Method :

β†’ In Stepping Stone Method method there are 'm' rows and 'n' columns, so the total number of unoccupied cell will be equal to m β‹… n βˆ’ ( m + n βˆ’ 1 ) mβ‹…nβˆ’(m+nβˆ’1) m β‹… n βˆ’ ( m + n βˆ’ 1 ) .

β†’ Thus, total number of loops increases, which increases calculation and it will be more time consuming.

Check optimality of same problem using Modified Distribution Method (MODI) .

Suggested Notes:

Unbalanced Transportation Problem Numerical

Unbalanced Transportation Problem Numerical

Modified Distribution Method (MODI) | Transportation Problem | Transportation Model

Modified Distribution Method (MODI) | Transportation Problem | Transportation Model

Vogel’s Approximation Method (VAM) | Method to Solve Transportation Problem | Transportation Model

Vogel’s Approximation Method (VAM) | Method to Solve Transportation Problem | Transportation Model

Transportation Model - Introduction

Transportation Model - Introduction

North West Corner Method | Method to Solve Transportation Problem | Transportation Model

North West Corner Method | Method to Solve Transportation Problem | Transportation Model

Least Cost Method | Method to Solve Transportation Problem | Transportation Model

Least Cost Method | Method to Solve Transportation Problem | Transportation Model

Tie in selecting row and column (Vogel's Approximation Method - VAM) | Numerical | Solving Transportation Problem | Transportation Model

Tie in selecting row and column (Vogel's Approximation Method - VAM) | Numerical | Solving Transportation Problem | Transportation Model

Assignment Model | Linear Programming Problem (LPP) | Introduction

Assignment Model | Linear Programming Problem (LPP) | Introduction

Critical Path Method [CPM] - Steps and Introduction | Network Analysis | Operation Research

Critical Path Method [CPM] - Steps and Introduction | Network Analysis | Operation Research

Crashing Special Case - Multiple (Parallel) Critical Paths

Crashing Special Case - Multiple (Parallel) Critical Paths

Crashing Special Case - Indirect cost less than Crash Cost

Crashing Special Case - Indirect cost less than Crash Cost

Basics of Program Evaluation and Review Technique (PERT)

Basics of Program Evaluation and Review Technique (PERT)

Numerical on PERT (Program Evaluation and Review Technique)

Numerical on PERT (Program Evaluation and Review Technique)

Network Analysis - Dealing with Network Construction Basics

Network Analysis - Dealing with Network Construction Basics

Construct a project network with predecessor relationship | Operation Research | Numerical

Construct a project network with predecessor relationship | Operation Research | Numerical

Graphical Method | Methods to solve LPP | Linear Programming

Graphical Method | Methods to solve LPP | Linear Programming

Basics of Linear Programming

Basics of Linear Programming

Linear Programming Problem (LPP) Formulation with Numericals

Linear Programming Problem (LPP) Formulation with Numericals

google logo small

All comments that you add will await moderation. We'll publish all comments that are topic related, and adhere to our Code of Conduct .

Want to tell us something privately? Contact Us

Post comment

Education Lessons logo

Education Lessons

Stay in touch, [notes] operation research, [notes] dynamics of machinery, [notes] maths, [notes] science, [notes] computer aided design.

how to solve transportation problem using stepping stone method

1. Algorithm & Example-1

how to solve transportation problem using stepping stone method

Stepping Stone Method

After computing an initial basic feasible solution, we must now proceed to determine whether the solution so obtained is optimal or not.

Now, we will discuss about the methods used for finding an optimal solution. The Stepping Stone Method is for finding the optimal solution of a transportation problem.

Steps in Stepping Stone Method: Transportation Problem

1. Determine an initial basic feasible solution using any one of the following:

  • North West Corner Rule
  • Matrix Minimum Method
  • Vogel Approximation Method

2. Make sure that the number of occupied cells is exactly equal to m+n-1, where m is the number of rows and n is the number of columns.

3. Select an unoccupied cell. Beginning at this cell, trace a closed path, starting from the selected unoccupied cell until finally returning to that same unoccupied cell.

The cells at the turning points are called "Stepping Stones" on the path.

4. Assign plus (+) and minus (-) signs alternatively on each corner cell of the closed path just traced, beginning with the plus sign at unoccupied cell to be evaluated.

5. Add the unit transportation costs associated with each of the cell traced in the closed path. This will give net change in terms of cost.

6. Repeat steps 3 to 5 until all unoccupied cells are evaluated.

7. Check the sign of each of the net change in the unit transportation costs. If all the net changes computed are greater than or equal to zero, an optimal solution has been reached. If not, it is possible to improve the current solution and decrease the total transportation cost, so move to step 8..

8. Select the unoccupied cell having the most negative net cost change and determine the maximum number of units that can be assigned to this cell. The smallest value with a negative position on the closed path indicates the number of units that can be shipped to the entering cell. Add this number to the unoccupied cell and to all other cells on the path marked with a plus sign. Subtract this number from cells on the closed path marked with a minus sign.

Example-1, Example-2

For clarity of exposition, consider the following transportation problem .

Example 1: Stepping Stone Method

A company has three factories A, B, and C with production capacity 700, 400, and 600 units per week respectively. These units are to be shipped to four depots D, E, F, and G with requirement of 400, 450, 350, and 500 units per week respectively. The transportation costs (in Rs.) per unit between factories and depots are given below:

The decision problem is to minimize the total transportation cost for all factory-depot shipping patterns.

An initial basic feasible solution is obtained by Matrix Minimum Method and is shown below in table 1.

Use Horizontal Scrollbar to View Full Table Calculation.

Here, m + n - 1 = 6. So the solution is not degenerate.

Initial basic feasible solution

6 X 450 + 6 X 250 + 3 X 50 + 2 X 350 + 3 X 350 + 5 X 250 = 7350

The cell AD (4) is empty so allocate one unit to it. Now draw a closed path from AD. The result of allocating one unit along with the necessary adjustments in the adjacent cells is indicated in table 2.

Please note that the right angle turn in this path is permitted only at occupied cells and at the original unoccupied cell.

The increase in the transportation cost per unit quantity of reallocation is +4 – 6 + 5 – 3 = 0.

This indicates that every unit allocated to route AD will neither increase nor decrease the transportation cost. Thus, such a reallocation is unnecessary.

Choose another unoccupied cell. The cell BE is empty so allocate one unit to it. Now draw a closed path from BE as shown below in table 3.

The increase in the transportation cost per unit quantity of reallocation is +5 – 6 + 6 – 5 + 3 – 3 = 0

This indicates that every unit allocated to route BE will neither increase nor decrease the transportation cost. Thus, such a reallocation is unnecessary.

We must evaluate all such unoccupied cells in this manner by finding closed paths and calculating the net cost change as shown below.

On small screens, scroll horizontally to view full calculation

Since all the values of unoccupied cells are greater than or equal to zero, the solution obtained is optimal .

Minimum transportation cost is: 6 X 450 + 6 X 250 + 3 X 50 + 2 X 350 + 3 X 350 + 5 X 250 = Rs. 7350

Share This Article

Operations Research Simplified Back Next

Goal programming Linear programming Simplex Method Assignment Problem

easycalculation.com

Stepping Stone Method Calculator

Stepping stone method is one of the method used to find the optimal solution for the transportation problem. This method is designed on the analogy of crossing the pond using the stepping stone. We need to work on step by step procedure to solve the transportation problem. The cells at the turning points are referred to as stepping stones. Use the below online stepping stone method calculator to find the each level of iteration and total minimum cost based on the given inputs.

Solve Transportation Problem using Stepping Stone Method

You can find the minimum cost of the transportation problem using this stepping stone method calculator based on the supply and demand constraints. It is used to check the optimality of the initial feasible solution in terms of the objective function.

Related Calculators:

  • Job Sequencing Problem
  • Inventory Control Model
  • Minimum Transportation Cost Calculator Using North West Corner Method
  • Vogel Approximation Method
  • Neonatal Mortality Rate Calculator
  • Barlows Formula Calculator

Calculators and Converters

  • Calculators
  • Operations Research

Top Calculators

Popular calculators.

  • Derivative Calculator
  • Inverse of Matrix Calculator
  • Compound Interest Calculator
  • Pregnancy Calculator Online

Top Categories

  • Skip to main content
  • Skip to primary sidebar

business-jargons-site-logo

Business Jargons

A Business Encyclopedia

Stepping Stone Method

Definition: The Stepping Stone Method is used to check the optimality of the initial feasible solution determined by using any of the method Viz. North-West Corner, Least Cost Method or Vogel’s Approximation Method. Thus, the stepping stone method is a procedure for finding the potential of any non-basic variables (empty cells) in terms of the objective function.

Through Stepping stone method, we determine that what effect on the transportation cost would be in case one unit is assigned to the empty cell. With the help of this method, we come to know whether the solution is optimal or not.

The series of steps are involved in checking the optimality of the initial feasible solution using the stepping stone method:

  • The prerequisite condition to solve for the optimality is to ensure that the number of occupied cells is exactly equal to m+n-1, where β€˜m’ is the number of rows, while β€˜n’ is equal to the number of columns.
  • In a closed loop, cells are selected in a sequence such that one cell is unused/unoccupied, and all other cells are used/occupied.
  • A pair of Consecutive used cells lies either in the same row or the same column.
  • No three consecutive occupied cells can either be in the same row or column.
  • The first and last cells in the closed loop lies either in the same row or column.
  • Only horizontal and vertical movement is allowed.
  • Once the loop is created, assign β€œ+” or β€œβ€“β€œ sign alternatively on each corner cell of the loop, but begin with the β€œ+” sign for the unoccupied cell.
  • Repeat these steps again until all the unoccupied cells get evaluated.
  • Now, if all the computed changes are positive or are equal to or greater than zero, then the optimal solution has been reached.
  • But in case, if any, value comes to be negative, then there is a scope to reduce the transportation cost further. Then, select that unoccupied cell which has the most negative change and assign as many units as possible. Subtract the unit that added to the unoccupied cell from the other cells with a negative sign in a loop, to balance the demand and supply requirements.

Example, suppose the following matrix shows the initial feasible solution and stepping stone method is adopted to check its optimality:

STM-1

Related terms:

  • Modified Distribution Method
  • Transportation Method of Linear programming
  • Least Cost Method
  • Vogel’s Approximation Method
  • Simplex Method

Reader Interactions

June 14, 2018 at 8:34 pm

Great stuff

Dr. Gerhard Keller says

June 16, 2018 at 12:09 am

Dr Kemas Fachruddin says

September 27, 2019 at 8:26 am

Very Good and helpful for students

Aarif Hussain says

October 2, 2019 at 2:30 am

Best explanation

Humera says

March 9, 2020 at 7:12 pm

Good explanation. Thank you

peter ogot says

September 9, 2020 at 3:25 pm

please may i get a pdf on the illustration of assignment problem, transportation algorithm, simplex algorithm, and any other related units of operations research. my email is below and thanks! the steps are very clear. i have learnt

Kishan says

December 2, 2020 at 2:52 pm

Thank you for your this contribution.

February 27, 2021 at 11:18 pm

January 19, 2023 at 2:00 am

Arfeen says

December 13, 2023 at 5:19 pm

Thank you.Useful.

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

  • Practice Mathematical Algorithm
  • Mathematical Algorithms
  • Pythagorean Triplet
  • Fibonacci Number
  • Euclidean Algorithm
  • LCM of Array
  • GCD of Array
  • Binomial Coefficient
  • Catalan Numbers
  • Sieve of Eratosthenes
  • Euler Totient Function
  • Modular Exponentiation
  • Modular Multiplicative Inverse
  • Stein's Algorithm
  • Juggler Sequence
  • Chinese Remainder Theorem
  • Quiz on Fibonacci Numbers

Related Articles

  • Solve Coding Problems
  • Adjoint and Inverse of a Matrix
  • Count numbers from a given range that can be visited moving any number of steps from the range [L, R]
  • Trapezoidal Rule for Approximate Value of Definite Integral
  • Kaprekar Constant
  • Bakhshali Approximation for computing square roots
  • Check if Array can be generated where no element is Geometric mean of neighbours
  • Sequence with sum K and minimum sum of absolute differences between consecutive elements
  • Program to convert Number in characters
  • Check whether a number can be represented by the product of two squares
  • Find the minimum value of m that satisfies ax + by = m and all values after m also satisfy
  • Find the larger exponential among two exponentials
  • Multiples of 3 or 7
  • Program to check if N is a Nonagonal Number
  • Multiply N complex numbers given as strings
  • Calculate Pi using Nilkantha's series
  • Sum of N terms in the expansion of Arcsin(x)
  • Digital Root (repeated digital sum) of square of an integer using Digital root of the given integer
  • Check if a number is multiple of 5 without using / and % operators
  • Maximum Square Side length with M 1x1 and N 2x2 tiles

Transportation Problem | Set 6 (MODI Method – UV Method)

There are two phases to solve the transportation problem. In the first phase, the initial basic feasible solution has to be found and the second phase involves optimization of the initial basic feasible solution that was obtained in the first phase. There are three methods for finding an initial basic feasible solution,

  • NorthWest Corner Method
  • Least Cost Cell Method
  • Vogel’s Approximation Method

This article will discuss how to optimize the initial basic feasible solution through an explained example. Consider the below transportation problem.

how to solve transportation problem using stepping stone method

Check whether the problem is balanced or not. If the total sum of all the supply from sources

is equal to the total sum of all the demands for destinations

then the transportation problem is a balanced transportation problem.

how to solve transportation problem using stepping stone method

If the problem is not unbalanced then the concept of a dummy row or a dummy column to transform the unbalanced problem to balanced can be followed as discussed in

Finding the initial basic feasible solution. Any of the three aforementioned methods can be used to find the initial basic feasible solution. Here,

will be used. And according to the NorthWest Corner Method this is the final initial basic feasible solution:

how to solve transportation problem using stepping stone method

Now, the total cost of transportation will be

(200 * 3) + (50 * 1) + (250 * 6) + (100 * 5) + (250 * 3) + (150 * 2) = 3700

U-V method to optimize the initial basic feasible solution. The following is the initial basic feasible solution:

how to solve transportation problem using stepping stone method

– For U-V method the values

have to be found for the rows and the columns respectively. As there are three rows so three

values have to be found i.e.

for the first row,

for the second row and

for the third row. Similarly, for four columns four

. Check the image below:

how to solve transportation problem using stepping stone method

There is a separate formula to find

is the cost value only for the allocated cell. Read more about it

. Before applying the above formula we need to check whether

m + n – 1 is equal to the total number of allocated cells

or not where

is the total number of rows and

is the total number of columns. In this case m = 3, n = 4 and total number of allocated cells is 6 so m + n – 1 = 6. The case when m + n – 1 is not equal to the total number of allocated cells will be discussed in the later posts. Now to find the value for u and v we assign any of the three u or any of the four v as 0. Let we assign

in this case. Then using the above formula we will get

). Similarly, we have got the value for

so we get the value for

which implies

. From the value of

. See the image below:

how to solve transportation problem using stepping stone method

Now, compute penalties using the formula

only for unallocated cells. We have two unallocated cells in the first row, two in the second row and two in the third row. Lets compute this one by one.

  • For C 13 , P 13 = 0 + 0 – 7 = -7 (here C 13 = 7 , u 1 = 0 and v 3 = 0 )
  • For C 14 , P 14 = 0 + (-1) -4 = -5
  • For C 21 , P 21 = 5 + 3 – 2 = 6
  • For C 24 , P 24 = 5 + (-1) – 9 = -5
  • For C 31 , P 31 = 3 + 3 – 8 = -2
  • For C 32 , P 32 = 3 + 1 – 3 = 1

If we get all the penalties value as zero or negative values that mean the optimality is reached and this answer is the final answer. But if we get any positive value means we need to proceed with the sum in the next step. Now find the maximum positive penalty. Here the maximum value is 6 which corresponds to

cell. Now this cell is new basic cell. This cell will also be included in the solution.

how to solve transportation problem using stepping stone method

The rule for drawing closed-path or loop.

Starting from the new basic cell draw a closed-path in such a way that the right angle turn is done only at the allocated cell or at the new basic cell. See the below images:

how to solve transportation problem using stepping stone method

Assign alternate plus-minus sign to all the cells with right angle turn (or the corner) in the loop with plus sign assigned at the new basic cell.

how to solve transportation problem using stepping stone method

Consider the cells with a negative sign. Compare the allocated value (i.e. 200 and 250 in this case) and select the minimum (i.e. select 200 in this case). Now subtract 200 from the cells with a minus sign and add 200 to the cells with a plus sign. And draw a new iteration. The work of the loop is over and the new solution looks as shown below.

how to solve transportation problem using stepping stone method

Check the total number of allocated cells is equal to (m + n – 1). Again find u values and v values using the formula

is the cost value only for allocated cell. Assign

then we get

. Similarly, we will get following values for

how to solve transportation problem using stepping stone method

Find the penalties for all the unallocated cells using the formula

  • For C 11 , P 11 = 0 + (-3) – 3 = -6
  • For C 13 , P 13 = 0 + 0 – 7 = -7
  • For C 14 , P 14 = 0 + (-1) – 4 = -5
  • For C 31 , P 31 = 0 + (-3) – 8 = -11

There is one positive value i.e. 1 for

. Now this cell becomes new basic cell.

how to solve transportation problem using stepping stone method

Now draw a loop starting from the new basic cell. Assign alternate plus and minus sign with new basic cell assigned as a plus sign.

how to solve transportation problem using stepping stone method

Select the minimum value from allocated values to the cell with a minus sign. Subtract this value from the cell with a minus sign and add to the cell with a plus sign. Now the solution looks as shown in the image below:

how to solve transportation problem using stepping stone method

Check if the total number of allocated cells is equal to (m + n – 1). Find u and v values as above.

how to solve transportation problem using stepping stone method

Now again find the penalties for the unallocated cells as above.

  • For P 11 = 0 + (-2) – 3 = -5
  • For P 13 = 0 + 1 – 7 = -6
  • For P 14 = 0 + 0 – 4 = -4
  • For P 22 = 4 + 1 – 6 = -1
  • For P 24 = 4 + 0 – 9 = -5
  • For P 31 = 2 + (-2) – 8 = -8

All the penalty values are negative values. So the optimality is reached. Now, find the total cost i.e.

(250 * 1) + (200 * 2) + (150 * 5) + (50 * 3) + (200 * 3) + (150 * 2) = 2450

Please Login to comment...

author

  • Mathematical
  • sumitlovanshi

Improve your Coding Skills with Practice

 alt=

What kind of Experience do you want to share?

Operations Management: Sustainability and Supply Chain Management, Twelfth Edition by Jay Heizer, Barry Render, Chuck Munson

Get full access to Operations Management: Sustainability and Supply Chain Management, Twelfth Edition and 60K+ other titles, with a free 10-day trial of O'Reilly.

There are also live events, courses curated by job role, and more.

The Stepping-Stone Method

The stepping-stone method will help us move from an initial feasible solution to an optimal solution. It is used to evaluate the cost effectiveness of shipping goods via transportation routes not currently in the solution. When applying it, we test each unused cell, or square, in the transportation table by asking: What would happen to total shipping costs if one unit of the product (for example, one bathtub) was tentatively shipped on an unused route? We conduct the test as follows:

Select any unused square to evaluate. ...

Get Operations Management: Sustainability and Supply Chain Management, Twelfth Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Don’t leave empty-handed

Get Mark Richards’s Software Architecture Patterns ebook to better understand how to design componentsβ€”and how they should interact.

It’s yours, free.

Cover of Software Architecture Patterns

Check it out now on O’Reilly

Dive in for free with a 10-day trial of the O’Reilly learning platformβ€”then explore all the other resources our members count on to build skills and solve problems every day.

how to solve transportation problem using stepping stone method

Least-looping stepping-stone-based ASM approach for transportation and triangular intuitionistic fuzzy transportation problems

  • Original Article
  • Open access
  • Published: 26 July 2021
  • VolumeΒ 7 ,Β pages 2885–2894, ( 2021 )

Cite this article

You have full access to this open access article

  • Kedar Nath Das 1 ,
  • Rajeev Das 1 &
  • Debi Prasanna Acharjya 2 Β 

1555 Accesses

2 Citations

Explore all metrics

Transportation problem (TP) is a popular branch of Linear Programming Problem in the field of Transportation engineering. Over the years, attempts have been made in finding improved approaches to solve the TPs. Recently, in Quddoos et al. (Int J Comput Sci Eng (IJCSE) 4(7): 1271–1274, 2012), an efficient approach, namely ASM, is proposed for solving crisp TPs. However, it is found that ASM fails to provide better optimal solution in some cases. Therefore, a new and efficient ASM appoach is proposed in this paper to enhance the inherent mechanism of the existing ASM method to solve both crisp TPs and Triangular Intuitionistic Fuzzy Transportation Problems (TIFTPs). A least-looping stepping-stone method has been employed as one of the key factors to improve the solution quality, which is an improved version of the existing stepping-stone method (Roy and Hossain in, Operation research Titus Publication, 2015). Unlike stepping stone method, least-looping stepping-stone method only deals with few selected non-basic cells under some prescribed conditions and hence minimizes the computational burden. Therefore, the framework of the proposed method (namely LS-ASM) is a combination of ASM (Quddoos et al. 2012) and least-looping stepping-stone approach. To validate the performance of LS-ASM, a set of six case studies and a real-world problem (those include both crisp TPs and TIFTPs) have been solved. The statistical results obtained by LS-ASM have been well compared with the existing popular modified distribution (MODI) method and the original ASM method, as well. The statistical results confirm the superiority of the LS-ASM over other compared algorithms with a less computationl effort.

Similar content being viewed by others

how to solve transportation problem using stepping stone method

Fuzzy Approximate Optimal Solution of the Fuzzy Transportation Problems (FTP) Under Interval Form Using Monte Carlo Approach

A new approach for solving fully intuitionistic fuzzy transportation problems.

Ali Ebrahimnejad & Jose Luis Verdegay

how to solve transportation problem using stepping stone method

A Fuzzy Logic-Based Approach to Solve Interval Multi-objective Non-linear Transportation Problem: Suggested Modifications

Avoid common mistakes on your manuscript.

Introduction

A constrained optimization problem consists of an objective function along with some constraints. If all of them are linear, then it is known as a Linear Programming Problem (LPP). The popular Transportation Problem (TP) is a particular case of LPP. The objective is to minimize the cost of dispensing products from β€˜ m ’ number of suppliers to β€˜ n ’ number of different stations. The LPP formulation of the TP is originally developed by Hitchcock [ 1 ] in the year 1941, as follows.

Mathematical formulation of TP [ 1 ]

Consider a TP with β€˜ m ’ sources and β€˜ n ’ destinations, where \(p_{ij}\) is the unit transportation cost from i th source to j th destination. Let \(S_{i}\) be the supply quantity available at i th source and \(D_{j}\) be the demand quantity of j th destination. The goal of the objective function is to minimize the total transportation cost ( Z ), subject to the commodity \(q_{ij}\) is shipped that met the demand. The mathematical formulation of a balanced TP (where \( \sum\nolimits_{i = 1}^{m} {S_{i} }\)  =  \(\sum\nolimits_{j = 1}^{n} {D_{i} }\) ) is given by

The first two set of constraints fortify that the total quantities shipped from the source β€˜ i ’ must not exceed its supply and the total quantity shipped to the β€˜ j th’ destination must be greater than or equal to its demand, respectively. The third set of constraints assures that quantity of commodity \(q_{ij}\) must be non-negative.

Real-world distribution problems are uncertain in nature because of the changes taking place in the parameters. Zadeh [ 2 ] developed the fuzzy set theory to deal with indistinct data computationally in making decisions and succeeded in its applications in different areas. The application of fuzzy set theory landed in the optimization field after the spearheading research carried out by Bellman and Zadeh [ 3 ]. Nonetheless, there are uncertainties with hesitation due to numerous factors like need for better communication, inaccuracy in data, comprehension of markets, unawareness of customers, etc. Likewise, the costs are still hanging with uncertainties with hesitation because of different components like diversity in rates of fuels, congested driving conditions, climatic conditions, and so on. In such circumstances, the decision-makers fail to foresee transportation cost precisely. Therefore, to deal with these uncertain data, Atanassov [ 4 ] proposed the Intuitionistic Fuzzy Set (IFS) which is validated to be more accurate than the fuzzy set theory proposed by Zadeh [ 2 ]. Afterward, quite ample number of successful approaches have been presented in the literature to solve TPs and IFTPs and the range of application has been steadily widened. It is now considered as one of the important tools in business and industry. Several sorts of methods have been proposed for finding the optimal solution. ASM [ 5 ] is one of such recent methods which has been applied to solve TPs and IFTPs, as well. The authors of ASM method solved a real-valued TP and then compared its result to that of MODI method. They concluded ASM to be a quick and effective approach. In the year 2012, Mohammad Kamrul Hasan [ 15 ] proposed that direct methods (including ASM method) for finding optimal solution of a TP do not reflect optimal solution continuously. Murugesan [ 17 ] admitted and perceived Hasan’s claim by verifying the ASM method for several benchmark problems. However, in the mean time, Abdul Quddoos et al. [ 16 ] experienced a few problems for which the ASM method does not happen to provide the optimal solution, but executes well enough to provide a best IBFS, which appears to be close to the optimal solution. To resolve this issue, Abdul Quddoos et al. [ 16 ] forwarded a revised approach to the ASM method where MODI method was combined with the existing ASM method. This approach gives the optimal solution directly for most of the problems, and if not, it gives the best IBFS. Later, the claim was established by Murugesan et al. [ 18 , 19 , 20 , 21 , 22 , 23 ] in which they tested on 30 balanced and 20 unbalanced benchmark TPs. Over the years, it can be seen that several approaches have been mentioned in the literature for the improvement of ASM method. However, the concept of stepping stone was never used with ASM method in the past research. Therefore, an effort is made in this manuscript to improve the efficiency of the original ASM by a crucial modification in it. The authors developed a new approach, namely, the least-looping stepping-stone approach, and hybridized it with ASM to increase the robustness of the original ASM.

The manuscript is systemized as follows: Section " Motivation " presents the motivation of the proposed method; Section β€œ Proposed LS-ASM Method ” introduces the proposed algorithm alongwith six case studies and a real-life problem. Section Results and Discussion includes the comparative analysis of results. The conclusion part of this paper is produced in Section Conclusion , which comprises some of the future opportunities, as well.

To solve TPs, a number of suitable approaches have been presented in the literature. Most of these approaches attempted to calculate the Initial Basic Feasible Solution (IBFS) before employing its different steps. In 2012, a popular method, namely ASM, was proposed [ 5 ] to solve the classical TP without finding the IBFS. In fact, it was a direct approach basically named after the first letters of the authors’ names Abdul Quddoos, Shakeel Javaid, and M.M. Khalid. However, later in [ 8 , 11 ], it is seen that ASM failed to get to the optimal cost for some of the TPs. To validate this fact, two case studies of Crisp TPs are explained below.

Case study-1:

Table 1 considers a balanced TP which is solved by ASM Method in Table 2 with total transportation cost =  7 × 5 + 5 × 5 + 9 × 20 + 3 × 25 + 3 × 20 + 2 × 5 + 3 × 10 = 415.

Case study - 2:

Table 3 considers a balanced TP which is solved by ASM method in Table 4 with total transportation cost =  13 × 80 + 15 × 200 + 22 × 50 + 11 × 280 + 19 × 220 + 11 × 180 = 14,380 .

It is worth noting that using each of the techniques like Vogel’s Approximation Method (VAM)-MODI [ 9 ], North-West Corner Method (NWCM)-MODI [ 9 ], Row Minima method (RMM)-MODI [ 9 ], and Column Minima Method (CMM)-MODI [ 9 ], the optimal solutions found are 410 and 14,180 for case studies-1 and 2, respectively. It motivated the authors to investigate more key factors of ASM, which needed to be substantially modified to enhance its robustness. Least-looping stepping-stone approach has been employed in the working mechanism of ASM to improve the robustness of ASM. This method is exempted from checking the optimality criteria for all the non-basic cells. Instead, it checks for some selected loops and calculates the net cost change values. Therefore, it helps to minimize the computational time as compared to stepping-stone approach. This new approach is proven to be more attactive due to easy implementation and minimum calculation, as compared to the classical approaches. To validate the better performance of the proposed method in all sort of TPs, two problems on balanced TPs, two problems on TIFTPs, two problems on unbalanced TPs, and one real-life problem have been considered. The working mechanism of the proposed approach has been explained in details in the following section.

Proposed LS-ASM Method

Least-looping stepping-stone method.

The stepping-stone Method [ 14 ] emerged from the idea of crossing a pond making use of stepping stones. The entire cost matrix is considered as a pond and the basic cells are the stones required for certain sequential movement within the pond. In other words, it is an iterative approach to reach the optimal solution from an IBFS. Each iteration includes the formation of closed loops* for each of the non-basic cells in the cost matrix. This helps in determining whether the current iteration has all the best routes. If not, then the only penalty imposed is to perform additional iterations.

However in this paper, the stepping-stone Method is suitably modified for its up gradation. Unlike ASM, LS-ASM considers only few selected non-basic cells for forming closed loops in its working mechanism (algorithm) presented below. First two iterations of least-looping stepping-stone are combined with ASM to reach the optimal solution. This new method is named as β€˜Least-looping stepping-stone based ASM Method’ ( LS-ASM Method) . Even after this hybridization, the proposed method proves out to be an easy and time-saving approach. In the later part of this paper, LS-ASM has been compared with other mentioned approaches.

LS-ASM algorithm

Consider the given TP and construct its transportation table.

If the transportation table is not balanced, then balance it by adding suitable dummy rows/columns. Else, proceed.

Subtract each row minima from the corresponding row costs and each column minima from the corresponding column costs.

Select a zero appearing in the cost matrix and count the total sum of the number of zeros (precluding the selected zero) in that corresponding row and column. Let us name it as sum-zero. Find the sum-zero for each of the existing zeros in the cost matrix.

Choose a cell with the cost zero for which the sum-zero is minimum. Supply maximum possible unit to that zero cell. If tie occurs for some zeros in step 3, then take that zero cell for which total sum of all the costs of respective row and column is maximum and assign maximum possible unit to that cell.

Block the row/column where the supply or the demand is met.

Now, if the reduced cost matrix does not have at least one zero in each row and each column, then go to step 2; otherwise continue step 3 to step 5 until all the demands and supplies are met.

Write the resulting table with both basic and non-basic cells.

For each non-basic cell in the resulting table, trace closed loops * back to the original non-basic cell. Choose only those closed loops * where either or both costs of the adjacent two basic cells of a non-basic cell are greater than the costs of the corresponding non-basic cells .

For each selected closed loop * by Step 8, assign (+) and (βˆ’) sign alternatively on each corner, starting from the original non-basic cell. Choose the minimum allocated value of all the negative positions (βˆ’) on the closed loop * . Allocate this value to the selected non-basic cell, so that the non-basic cell becomes basic cell. Add this value to other basic cells with (+) sign and subtract this value from other basic cells with (βˆ’) sign.

Calculate the sum of the transportation costs of each cell followed in the closed loop *. This sum value is termed as Net Cost Change. Redo this for all other selected closed loops * .

If all the net cost change values are non-negative, an optimal value is attained. Then terminate. Else, select the non-basic cell having negative net cost change value and draw a closed loop.

Choose the minimum allocated value of all the negative positions (βˆ’) on the closed loop. Allocate this value to the selected non-basic cell, so that the non-basic cell becomes basic cell. Add this value to other basic cells with (+) sign and subtract this value from other basic cells with (βˆ’) sign.

Repeat the steps 8–11 (viz., steps of Least-looping stepping-stone Method ) once again and the optimal solution will be obtained with all the values of net cost change non-negative for non-basic cells.

Evaluate the transportation cost and stop.

* Closed loop is a sequence of cells that forms a look in the transportation table with the following conditions.

Any two consecutive cells lie either in the similar row/column.

No three successive cells lie either in the similar row/column.

The starting and ending cell of a sequence lies in the similar row/column.

No cell shows up more than once in a sequence.

Only horizontal and vertical moves are permitted and can change directions at used cells.

To have a quick reference of closed loops * in LS-ASM, two illustrations are presented in Figs.Β  1 and 2 .

figure 1

One form of closed loop *

figure 2

Another form of closed loop *

To have a quick reference of the work sequence in LS-ASM, the flow diagram also is presented in Fig.Β  3 .

figure 3

Flowchart for LS-ASM

Case studies

In this section, an attempt is made to justify the efficiency of the proposed LS-ASM method in solving TPs. Hence, a set of varieties of TPs are being considered both from crisp and fuzzy environment. Keeping in view the above fact, the TPs of the following categories have been solved by LS-ASM.

Balanced TPs in crisp environment (case studies-1 and 2)

Balanced TPs in intuitionistic fuzzy environment (case studies-3 and 4)

Unbalanced TPs in crisp environment (case studies-5 and 6)

A real-life problem in intuitionistic fuzzy environment (separately discussed in Section β€œ Real-Life IFTP ”).

Now, the detailed descriptions of the above TPs are dicussed below under individual case studies.

Balanced TPs

The first case study is already considered in Sect.Β  2 . Assuming the optimal table by ASM, clearly the non-basic cells are \({S}_{1}{D}_{4}\) , \({S}_{2}{D}_{1}\) , \({S}_{2}{D}_{3}\) , \({S}_{2}{D}_{4}\) , \({S}_{3}{D}_{2}\) , \({S}_{3}{D}_{3}\) , \({S}_{3}{D}_{4}\) , \({S}_{4}{D}_{2}\) , and \({S}_{4}{D}_{3}\) .

In Table 5 , it is observed from the loop that \({S}_{1}{D}_{1}\) and \({S}_{4}{D}_{4}\) are adjacent to \({S}_{1}{D}_{4}\) . Now, the cost values of \({S}_{1}{D}_{1}\) and \({S}_{4}{D}_{4}\) (7 and 3, respectively) are less than the cost value of \({S}_{1}{D}_{4}\) (i.e., 11). Therefore, this closed loop is not considered to evaluate the net cost change value. Other closed loops can be constructed and checked in the similar way for the other non-basic cells.

Now, apply Step 12 of the LS-ASM algorithm to the non-basic cell \({S}_{2}{D}_{1}\) having the only negative net cost change value (Refer to Table 6 ). It is seen that in the closed loop of Table 7 out of both the negative positions, 5 < 25. Therefore, 5 is added to the non-basic cell \({S}_{2}{D}_{1}\) and basic cell \({S}_{1}{D}_{2}\) , whereas it is subtracted from the allocated values of the basic cells \({S}_{1}{D}_{1}\) and \({S}_{2}{D}_{2}\) . Now, \({S}_{2}{D}_{1}\) becomes a basic cell. Since, it can be checked that all the net cost change values of the non-basic cells are positive in the next iteration. Finally, the optimal solution has been reached. The optimal table of the TP is demonstrated in Table 8 .

Thus, the total transportation cost according to LS-ASM Method =  5 × 10 + 9 × 20 + 4 × 5 + 3 × 20 + 3 × 20 + 2 × 5 + 3 × 10 = 410.

Case study-2 :

The case study-2 has already been considered in Sect.Β  2 . Proceeding in the similar way as done for case study-1, the optimal transportation cost by LS-ASM is obtained as 14,180 . Two more case studies with the implementation of LS-ASM for TIFTPs are described following case studies.

Case study-3 :

Table 10 uses the ranking function [ 6 ] to convert the Triangular Intuitionistic Fuzzy cost values to real values. In Table 11 , the total transportation cost according to the LS-ASM Method =  1 × 4 + 4 × 1 + 7 × 5 + 8 × 1 + 2 × 7 + 6 × 3 + 5 × 7 = 118.

Case study-4 :

Table 13 uses the ranking function [ 6 ] to convert the Triangular Intuitionistic Fuzzy cost values to real values. In Table 14 , the total transportation cost according to the LS-ASM Method =  (243.33 × 3500 + 3721.21 × 1000 + 406.833 × 1500 + 1050 × 2000 + 2209.259 × 1500 + 5621.21 × 500) = 13,406,940.5.

Unbalanced TPs

In this sub-section, two unbalanced TPs are considered as follows to solve by LS-ASM Method.

Case study-5 :

Table 15 considers an unbalanced TP which is solved by LS-ASM in Table 16 with total transportation cost =  25 × 125 + 15 × 450 + 0 × 300 + 10 × 350 + 20 × 225 = 17,875.

Case study-6 :

Table 17 considers an unbalanced TP which is solved by LS-ASM Method in Table 18 with total transportation cost =  10 × 1 + 6 × 60 + 4 × 10 + 6 × 10 + 3 × 15 + 0 × 40 = 515.

Real-life IFTP

To realize the effectiveness of LS-ASM in real-life problem, a TIFTP from Kumar et al. [ 6 ] has been considered here in this section. The problem comprises of an umbrella company where the company manager wishes to transport umbrellas from three different factories to three different retail stores. The dataset for the transporation table is mentioned in Table 19 (see Table 20 ).

Table 21 gives the optimal solution table for the real-life TIFTP solved by LS-ASM with total transportation cost =  9.75 × 7.125 + 12.375 × 4.625 + 17 × 10.25 + 8.75 × 8.75 + 14.75 × 1.25 = 349.2656.

Results and discussion

The techniques LS-ASM, ASM, VAM-MODI are being programmed in C +  + . The code is compiled and executed on Intel(R) Core (TM) i5-7500 CPU (3.40Β GHz) processor using Dev C +  + 5.11 compiler. The number of least-looping stepping-stone iterations required to reach optimality in each of the problems of Table 22 is 1. The optimal transportation costs of all the methods are compared in Table 22 . The bold letters represent the improved optimal solution reached by that particular method for the corresponding case study and real-life TIFTP.

The results of REDI [ 12 ] and Algorithm of [ 13 ] are directly taken from their respective papers. From Table 22 , it is observed that the LS-ASM code executes successfully reaching the optimal solution. For the first two case studies, LS-ASM gives better optimal results than ASM [ 5 ] method, whereas for case study-3 and case study-4, it executes with same optimal results as other methods. A similar argument has been carried out for the case studies-5 and 6 for unbalanced TPs and also for the real-life TIFTP considered in Section 3.4. Though the optimal solutions could not beat its near competitors namely, ASM and VAM-MODI, it has been able to obtain equally good results as that of others. Like balanced TPs, the LS-ASM consumes less time in case of unbalanced TPs too as compared to VAM-MODI over an average of 50 independent runs.

A fair comparison of these methods is done under the fixed platform and each algorithm is allowed to execute for 50 independent runs. The computational times of all the methods are compared in Table 23 . Furthermore, the bold letters represent the least time required (in s.) for each individual case study and real-life TIFTP.

It is worth noting that LS-ASM consumes less computational time as compared to VAM-MODI method. Moreover, though LS-ASM takes bit more time than ASM for solving the problems in hand, but in return, LS-ASM provides better optimal solution than ASM as reported in Table 22 .

The manuscript proposes an improved stepping-stone approach (namely least-looping stepping-stone method), which has been synergized with a popular ASM approach. The newly framed approach thus established is named as LS-ASM. Unlike ASM, LS-ASM employs a least number of closed loops on non-basic cells. The proposed algorithm is allowed to solve both TPs (balanced and unbalanced) and a real-life TIFTP. Both the optimal solution obtained and the computational time consumed are being compared separately for LS-ASM with its near competitors like ASM and VAM-MODI. Since LS-ASM utilizes less time than the popular VAM-MODI in solving the TPs and TIFTP, it can be treated as an efficient method. On the other hand, LS-ASM provides equally competent with VAM-MODI. Thus, the efficiency of the LS-ASM over VAM-MODI is well established. Furthermore, though LS-ASM is a hybrid version of ASM, it is quite obvious that LS-ASM takes more executional time. However, due to its inherent characteristics of using the closed loops as minimum number of times as possible during simulation, the reachability of finding the optimal solution becomes faster. As a result, the performance of LS-ASM is either equally good or better than its original version, namely ASM. As a whole, it can be concluded that LS-ASM outperforms its near competitors in solving balanced, unbalanced, and TIFTP,Β as well. As a future scope of research, further improvement of LS-ASM can also be made with an effective modification in its existing algorithmic steps, so that the transportation cost will be further minimized and/or the computational time will be further reduced. Also, it can be efficiently applied on several other unbalanced real-world TPs and IFTPs.

Hitchcock FL (1941) The distribution of a product from several sources to numerous localities. J Math Phys 20:224–230

Article Β  MathSciNet Β  Google Scholar Β 

Zadeh LA (1965) Fuzzy sets. Inf Control 8:338–353

Article Β  Google Scholar Β 

Bellman R, Zadeh LA (1970) Decision making in Fuzzy environment. Manag Sci 17(B):141–164

Atanassov KT (1986) Intuitionistic fuzzy sets. Fuzzy Sets Syst 20:87–96

Quddoos A, Javaid S, Khalid MM (2012) A new method for finding an optimal solution for transportation problems. Int J Comput Sci Eng (IJCSE) 4(7):1271–1274

Google Scholar Β 

Kumar PS, Hussain RJ (2016) Computationally simple approach for solving fully intuitionistic fuzzy real life transportation problems. Int J Syst Assur Eng Manag 7(Suppl. 1):90–101

Singh SK, Yadav SP (2014) A new approach for solving intuitionistic fuzzy transportation problem of type-2. Springer Science + Business Media, New York

Ahmed MM, Khan AR, Sharif Uddin MD, Ahmed F (2016) A new approach to solve transportation problems. Open J Optim 5:22–30

Murthy PR (2007) Operation research. New Age International (P) Limited, New Delhi

Antony RJP, Savarimuthu SJ, Pathinathan T (2014) Method for solving the transportation problem using triangular intuitionistic fuzzy number. Int J Comput Algorithm 3:590–605

Chhibber D, Bisht DCS, Srivastava PK (2019) Ranking approach based on incenter in triangle of centroids to solve type-1 and type-2 fuzzy transportation problem. In: AIP Conference Proceedings 2061: 020022

Aramuthakannan S, Kandasamy PR (2016) Application of revised distribution method for finding optimal solution of unbalanced transportation problem. PARIPEX-Indian J Res 5(1):39–42

Halawa MIA, Maatuk AM, Idrees HS, Ali EM (2016) An optimal solution for transportation problem using computing modelling. In: International Conference on Engineering and MIS (ICEMIS), p 1–5. IEEE

Roy GC, Hossain E (2015) Operation research. Titus Publication

Hasan MK (2012) Direct methods for finding optimal solution of a transportation problem are not always reliable. Int Ref J Eng Sci (IRJES) 1(2):46–52

Shakeel AQ, Khalid MM (2016) A revised version of ASM method for solving transportation problem. Int J Agric Stat Sci 12(Supplement 1):267–272

Murugesan R (2019) A note on: direct methods for finding optimal solution of a transportation problem are not always reliable. Int Ref J Eng Sci (IRJES) 8(3):39–48

MathSciNet Β  Google Scholar Β 

Murugesan R, Esakkiammal T (2019) Revised version of ASM method–the best one for finding an IBFS for transportation problems. In: International Conference on recent advances in pure and applied mathematics (ICRAPAM–2019)

Murugesan R, Esakkiammal T (2020) Revised version of ASM method-the best one for finding an IBFS for transportation problems. Adv Math Sci J 8(3):493–510

Murugesan R, Esakkiammal T (2019) A comparative study on ASM method with harmonic mean approach in transportation problems. In: International Conference on mathematical analysis and computing (ICMAC–2019), Organized by the Department of Mathematics, SSN College of Engineering, Kalavakkam, Chennai, Tamil Nadu, India

Murugesan R, Esakkiammal T (2019) A comparative study on ASM method with MDMA method in balanced transportation problems. In: International Conference on operations research and decision systems (ICORDS-2019), organized by the Indian Institute of Management, Visakhapatnam, Andhra Bank School of Business, Andhra University Campus, Visakhapatnam

Murugesan R, Esakkiammal T (2019) A comparative study on ASM method with MDMA method in transportation problems. Int J Comput Appl Math (IJCAM) (accepted)

Murugesan R, Esakkiammal T (2020) A comparative study on ASM Method with VAM and ATM methods in transportation problems. In: International Conference on innovations in graphs and its alliances in digital era (ICIGA-2020), Organized by Department of Mathematics, University of Kerala, Kariavattom, Thiruvananthapuram, Kerala, p 27

Download references

Author information

Authors and affiliations.

Department of Mathematics, National Institute of Technology Silchar, Silchar, India

Kedar Nath DasΒ &Β Rajeev Das

School of Computer Science and Engineering, VIT-Vellore, Vellore, India

Debi Prasanna Acharjya

You can also search for this author in PubMed Β  Google Scholar

Corresponding author

Correspondence to Rajeev Das .

Ethics declarations

Conflict of interest statement.

On behalf of all authors, the corresponding author states that there is no conflict of interest.

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ .

Reprints and permissions

About this article

Das, K.N., Das, R. & Acharjya, D.P. Least-looping stepping-stone-based ASM approach for transportation and triangular intuitionistic fuzzy transportation problems. Complex Intell. Syst. 7 , 2885–2894 (2021). https://doi.org/10.1007/s40747-021-00472-0

Download citation

Received : 02 December 2020

Accepted : 10 July 2021

Published : 26 July 2021

Issue Date : December 2021

DOI : https://doi.org/10.1007/s40747-021-00472-0

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

  • Transportation problem
  • Triangular intuitionistic fuzzy number
  • Stepping-stone method
  • Optimal solution
  • Find a journal
  • Publish with us
  • Track your research

IMAGES

  1. Stepping Stone Method for Transportation Problem

    how to solve transportation problem using stepping stone method

  2. STEPPING STONE METHOD Optimal Solution Transportation Problem

    how to solve transportation problem using stepping stone method

  3. Transportation Problem- Stepping Stone Method

    how to solve transportation problem using stepping stone method

  4. LEARN A FEW STEPS TO SOLVE A TRANSPORTATION PROBLEM BY NWC +SSM

    how to solve transportation problem using stepping stone method

  5. STEPPING STONE METHOD

    how to solve transportation problem using stepping stone method

  6. Transportation Problem- Stepping Stone Method

    how to solve transportation problem using stepping stone method

VIDEO

  1. Transportation Problems in Operations Research: Stepping Stone Method

  2. 7- Stepping stone method

  3. Transportation Problem part-3 Stepping Stone method by Dr. Mohammad Rashid Hussain

  4. Transportation problems/Stepping Stone Method with Epsilon/Operation Research/B Com-6th sem/P U Chd

  5. Operations Research Course

  6. Transportation Problem Session 12

COMMENTS

  1. Transportation Problem

    www.EdDansereau.com/transportation.htmlTransportation Video 5 of 7Example 2Two examples of the Linear Programming Transportation Problem are given. The first...

  2. Transportation Problem: Finding an Optimal Solution

    1.1 Step 1: Obtaining the Initial Feasible Solution 1.2 Step 2: Testing the Optimality 1.3 Step 3: Improving the Solution 2 Stepping Stone Method 3 Special Cases in the Transportation Problems 3.1 Degeneracy in Transportation Problem 3.2 Unbalanced Transportation Problem 3.3 Alternative Optimal Solutions 3.4 Maximisation Transportation Problem

  3. Stepping Stone Method Examples, Transportation Problem

    Solution. We compute an initial basic feasible solution of the problem by Matrix Minimum Method as shown in table 1. Table 1 Here, m + n - 1 = 5. So the solution is not degenerate. Initial basic feasible solution 1 X 10 + 7 X 13 + 3 X 12 + 6 X 2 + 3 X 18 = 203 The cell AD (2) is empty so allocate one unit to it. Now draw a closed path. Table 2

  4. Stepping Stone

    Watch video As we discussed in MODI method that, to understand these methods which will be used to get optimum solution to transportation problem, we need to get knowledge of optimality test first. Jump to Stepping Stone Method or Modified Distribution Method (MODI) for optimizing solution to transportation problem. Optimality Test :

  5. transportation problem using stepping stone method (optimal solution

    1. Algorithm & Example-1 Algorithm Example-1 Find Solution using Voggel's Approximation method, also find optimal solution using stepping stone method Solution: TOTAL number of supply constraints : 3 TOTAL number of demand constraints : 4 Problem Table is Table-1 The maximum penalty, 22, occurs in column D2.

  6. Stepping stone method in transportation problem

    This video explains how to apply stepping stone method for finding an optional solution in transportation problem.Finding an initial basic feasible solution ...

  7. Stepping Stone Method

    The Stepping Stone Method is for finding the optimal solution of a transportation problem. Steps in Stepping Stone Method: Transportation Problem The algorithm is as follows: 1. Determine an initial basic feasible solution using any one of the following: North West Corner Rule Matrix Minimum Method Vogel Approximation Method 2.

  8. Solving the Transportation Problem

    October 23, 2020 Solving the Transportation Problem Algorithms & Functions Minimizing the cost of transporting products from production and storage locations to demand centers is an essential part of maintaining profitability for companies who deal with product distribution.

  9. PDF Transportation problem using Stepping Stone method and its Applications

    The algorithm is as follows: Determine an initial basic feasible solution using any one of the following: North-West Corner Rule Matrix minima Method Vogel's approximation method. Make sure that the number of occupied cells is exactly equal to m+n-1, where m is the number of rows and n is the number of columns.

  10. L2: Solving a Transportation Problem || Stepping Stone Method

    This lecture covers two main concepts, how to resolve degeneracy and Testing optimality of the feasible solution in a Transportation Problem Using the Stepping Stone Method. Show more...

  11. Transportation Problem Solutions

    πŸ’° The Stepping Stone Method can be used to allocate resources in transportation problems by finding the minimum value between two cells and adjusting accordingly. πŸ’° The cost of transportation can be calculated by multiplying the number of units allocated by the unit cost for each route. Browse more

  12. Stepping Stone Method Calculator

    We need to work on step by step procedure to solve the transportation problem. The cells at the turning points are referred to as stepping stones. Use the below online stepping stone method calculator to find the each level of iteration and total minimum cost based on the given inputs. Solve Transportation Problem using Stepping Stone Method

  13. Stepping Stone Method

    Subtract the unit that added to the unoccupied cell from the other cells with a negative sign in a loop, to balance the demand and supply requirements. Example, suppose the following matrix shows the initial feasible solution and stepping stone method is adopted to check its optimality:

  14. Transportation Problem

    Step 1: Check whether the problem is balanced or not. If the total sum of all the supply from sources O1 , O2 , and O3 is equal to the total sum of all the demands for destinations D1 , D2 , D3 and D4 then the transportation problem is a balanced transportation problem. Note:

  15. Stepping-Stone Method

    Stepping-Stone Method. A procedure for solving a transportation problem based on a simplification of the simplex method as applied to the constraint structure that defines a transportation problem. It starts with an initial basic feasible solution and then evaluates, for every nonbasic variable, whether an improved solution can be obtained by ...

  16. How to solve transportation problems using the stepping stone method

    Can't seem to figure out how to use the stepping stone method in solving? Here is a short tutorial on how to use it in linear programing!

  17. The Stepping-Stone Method

    Stepping-stone method. An iterative technique for moving from an initial feasible solution to an optimal solution in the transportation method. LO C.2 Solve a problem with the stepping-stone method. Select any unused square to evaluate. ...

  18. PDF A New Method to Solve Transportation Problem

    Step is. 1: balanced or the balance transportation. column. Then find the maximum value among Step 2: or Find the harmonic to next step. or by adding Table 1: Consider the following transportation problem. row and each. Step 3: Allocate the minimum supply or demand at the Step 4: of minimum of the related.

  19. Solving Transportation problem with North West corner rule & Stepping

    This code has been designed to solve the transportation problem with North-West corner rule . In case of degeneracy problem, it can resolve with the corrective degeneracy method. If user have some questions please contact me on 1. facebook : warut boonphakdee 2. email: [email protected]

  20. How to Solve Transportation Problem With Stepping Stone Method in Or? #

    0:00 / 20:27 HOW TO SOLVE TRANSPORTATION PROBLEM WITH STEPPING STONE METHOD IN OR? #G N SATISH KUMAR My Easy Statistics 24.6K subscribers Subscribe 84K views 4 years ago Operations Research...

  21. Least-looping stepping-stone-based ASM approach for transportation and

    A least-looping stepping-stone method has been employed as one of the key factors to improve the solution quality, which is an improved version of the existing stepping-stone method (Roy and Hossain in, Operation research Titus Publication, 2015). ... (2016) A revised version of ASM method for solving transportation problem. Int J Agric Stat ...

  22. Transportation Problem

    Transportation Problem | Using Steeping Stone Method | Stepping Stone Method | Simple Steps by JOLLY | STEPPING STONE METHOD OF TRANSPORTATION PROBLEMThis vi...