Vogels approximation method

The Vogels approximation method is a heuristic procedure that is used primarily in distribution logistics, for example to solve a transportation problem. It belongs to the field of mathematically oriented statistics, or Operations Research. The method comes very close to the desired optimum, but the effort involved is considerably higher compared to other mathematical methods.

The central problem in distribution logistics is to transport a good from here to there as cheaply as possible. This involves not only the pure route planning, but also, with regard to operational planning, criteria that affect the establishment of distribution centers and production sites. For example, if a company manufactures a certain product in several plants that is delivered to different locations, then the Vogel approximation method can be used to find out which transport routes would be almost optimal under which conditions.

Vogel’s approximation method in practice

When solving a transportation problem, the Vogel approximation method acts as a basic solution, which then finds a cost-optimized approximate solution using further optimization methods. As mentioned above, the transportation problem is an operations research issue. It deals with finding a cost-minimal (optimal) path that specifies the transportation of uniform objects from several supply locations to several demand locations. The quantities available and to be delivered at the respective locations are given. The corresponding transport costs per unit between all locations are also known. Other heuristic methods that deal with the solution of the transportation problem in operations research are the northwest corner method and the matrix minimum method.

Vogel’s approximation method: the algorithm step by step

The fixed data are the supply and demand locations and their corresponding capacities or demands. The units to be delivered are entered (see also the videos).

1. First, an auxiliary matrix is created with the opportunity costs. These result from the difference between the two smallest values in the respective row and column.

2. Then the row or column with the highest opportunity costs is selected.

3. Then the lowest value from this row or column is selected. In the original matrix, the maximum possible capacities are now assigned to this field.

4. In the original matrix, the relevant column or row is filled with zeros and deleted in the auxiliary matrix as soon as the supply or demand quantity is exhausted.

5. The opportunity costs are recalculated after each pass and the assignment starts over.

6. When all capacities are assigned, the process is complete.

In principle, the idea behind this is that the path that would cause the greatest costs if it were abandoned is taken first. These are represented by the opportunity costs in the auxiliary matrix. Instead of working with the absolute price, the relative increase in costs is considered here.

 

 

Problems and restrictions

When the highest differences are equal to the highest, the algorithm does not specify how to proceed. This problem cannot be solved trivially in relation to the best solution. Furthermore, it is not possible to include existing fixed costs with this method.

Operations Research: Applying the solution

The method dates from a time when computing power was still quite limited. Nowadays, thanks to the complexity of the problem, a great deal of computing power is required to find integer solutions for a large number of locations. As a rule, companies rent the necessary computing power from a data center (HPC). However, the Vogels approximation method can be used to find a good reference, which can greatly speed up the actual optimization. For example, if you want to introduce tugger trains in production logistics, you can use this method to solve the challenge of the corresponding transport problem.

Advantages and disadvantages

Advantages

  • The solution is close to the optimum
  • The calculation time is short because there are no complex matrix operations
  • Permissible integer solutions are found quickly
  • Can be done quickly by hand – if the complexity allows it

Disadvantages

  • The solution is not the optimum
  • The algorithm can hardly include fixed costs and multiple-product cases
  • Additional computing power is needed for complex problems these days

Summary

The transportation problem is a basic logistical problem that can be solved using the Vogel approximation method. This is a heuristic procedure that forms the basis for an approximation solution that comes very close to the optimum. The resulting transportation mix keeps transportation costs to a minimum. Since logistical requirements are constantly changing, this calculation must also be carried out continuously to ensure permanent cost optimization.

Teaser image: Daniel Schwen / CC BY-SA 3.0

If you are interested in topics related to heuristics, then read the article block heuristic.