The approximation method according to Vogel is a heuristic procedure that is mainly used in distribution logistics, for example to solve a transport problem. It belongs to the field of mathematically oriented statistics, also called operations research. The method comes very close to the desired optimum, but the effort required is much higher compared to other mathematical methods.

The central problem in distribution logistics is to transport a good from A to B as cheaply as possible. This is not only a matter of pure route planning but also of criteria relating to the establishment of distribution centres and production sites in terms of operational planning. If, for example, a company manufactures a certain product in several plants that is delivered to different locations, then Vogel’s 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 transport problem, Vogel’s approximation method acts as a basic solution, which then finds a cost-optimised approximate solution with further optimisation methods. The transport problem is, as mentioned above, a question from Operations Research. It is concerned with finding a cost-minimised (optimal) route that specifies the transport 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 transport problem in Operations Research are the north-west 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 and requirements. The units to be supplied are entered (see also the videos).

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

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

3. Then the lowest value in that 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 in with zeros and deleted from the auxiliary matrix as soon as the supply or demand quantity is exhausted.

5. The opportunity costs are recalculated after each round, and the allocation process starts all over again

6. When all capacities are allocated, the procedure is completed.

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

Problems and limitations

If there are differences of the same magnitude, which in a particular case are also the highest, the algorithm does not specify how to proceed. This problem cannot be solved trivially in terms of the best solution either. Furthermore, it is not possible to include existing fixed costs in this method.

Operations Research: Application of the solution

The method dates back to times when computing power was still quite limited. Nowadays, if you are looking for integral solutions in a large number of places, you need a lot of computing power, thanks to the complexity of the problem. As a rule, companies rent the required power from a computer centre (HPC). With Vogel’s approximation method, however, a good reference can already be found, which under certain circumstances can speed up the actual optimisation enormously. For example, if you want to introduce route 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 computing time is low because there are no complex matrix operations.
  • Valid integer solutions are quickly found.
  • Quickly done 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.
  • Nowadays, additional computing power is required for complex problems.

Summary

The transport problem is a basic logistical problem that can be solved by Vogel’s approximation method. This is a heuristic procedure that forms the basis for an approximate solution that comes very close to the optimum. The resulting transport mix keeps transport costs to a minimum. Since logistical requirements are constantly changing, this calculation must also be performed continuously to ensure permanent cost optimisation.

Teaser picture: Daniel Schwen / CC BY-SA 3.0

You are interested in topics related to heuristics; then read the article Block Heuristics.

Also available in Deutsch (German)