Transportation problem

The transport problem is a question from Operations Research : For the transport of uniform objects from several places of supply to several places of demand , an optimal , i.e. H. to find a cost-minimal plan, whereby the quantities available and to be delivered at the individual locations and the respective transport costs per unit between all locations are known.

As early as 1781 Monge formulated a general transport problem mathematically. The standard case of a linear cost function with respect to the transport quantities is a problem of linear optimization for which special solution algorithms exist in addition to the standard methods such as simplex methods . As one of the first subject areas of Operation Research, the problem was formulated as a mathematical model by Kantorowitsch as early as 1939 . In the 1950s, Dantzig , Charnes and William W. Cooper as well as Ford and Fulkerson developed different solution algorithms.

The classic transport problem without capacity restrictions on the transport routes is a special case of the capacitive transport problem, which defines minimum or maximum transport quantities for routes. Classic and capacitive transport problems are in turn special cases of the (capacitive) reloading problem , in which there are places of supply and demand as well as pure reloading locations. A special case of the transport problem is the assignment problem , in which only one unit is offered or requested at each location.

Mathematical formulation of the classic transport problem

The classic transport problem without capacity restrictions is described by the following data: m supply locations provide quantities of the goods ( ), n demand locations ask for the goods in quantities ( ). The quantities must be greater than or equal to zero, and the total supply must be equal to the total demand (balanced transport problem). If this is not the case in the original problem, a fictitious supply or demand location is to be introduced, which provides the excess demand or takes up the excess supply. Furthermore - for example in a matrix C - the non-negative costs for the transport of a quantity unit from the place of supply to the place of demand are given. Transport costs from or to a fictitious location are set to zero. If nothing can be transported between two locations, the corresponding transport costs are infinite. ${\displaystyle A_{i}}$ ${\displaystyle a_{i}}$ ${\displaystyle i=1,\dotsc ,m}$ ${\displaystyle B_{j}}$ ${\displaystyle b_{j}}$ ${\displaystyle j=1,\dotsc ,n}$ ${\displaystyle c_{ij}}$ ${\displaystyle A_{i}}$ ${\displaystyle B_{j}}$

Formulation as a linear program

In the transport plan describes the transport quantity that is transported from to . The total costs are obtained by multiplying the determined transport quantity for each transport route by the costs for the transport on the respective transport route and adding up these products. What is needed is a transport plan with minimal costs that complies with the restrictions on the quantities available and meets the demand at all places of demand. With the names introduced, the mathematical model of the transport problem results: ${\displaystyle x_{ij}}$ ${\displaystyle A_{i}}$ ${\displaystyle B_{j}}$

Minimize the objective function ${\displaystyle z=\sum _{i=1}^{m}\sum _{j=1}^{n}c_{ij}x_{ij}}$

under the constraints

1. ${\displaystyle \sum _{j=1}^{n}x_{ij}=a_{i}\quad \forall i}$
2. ${\displaystyle \sum _{i=1}^{m}x_{ij}=b_{j}\quad \forall j}$
3. ${\displaystyle x_{ij}\geq 0\quad \forall i\forall j}$

The first secondary condition describes that the supply is to be completely called up at each supply location, while the second specifies for each demand location that the demand is to be fully met. All transport quantities need to be non-negative. Often the whole number of the transport quantities is required, i.e. H. . ${\displaystyle x_{ij}\in \mathbb {N} _{0}}$

If the conditions listed at the beginning ( ) are met and all routes can be used ( ), there is at least one solution to the transport problem. If nothing can be transported between certain locations, the existence of a solution is not guaranteed. ${\displaystyle a_{i}\geq 0,\ b_{j}\geq 0,\ c_{ij}\geq 0{\rm {\ und\ }}\sum a_{i}=\sum b_{j}}$ ${\displaystyle c_{ij}\neq \infty \ \forall i\forall j}$

Formulated as a minimum cost flow problem

→ Main article : Minimum-Cost Flow Problem

With the help of graphs , the problem can also be formulated as a minimum cost flow problem. The aim is to find a minimum cost flow with a given flow value in a graph with edge costs between two nodes . Each location is represented by a node, and an edge is drawn from each supply location to each demand location, the costs of which correspond to the transport costs. In addition, two special nodes and are introduced. Node is connected with all supply locations and with all demand locations, these edges having the cost value 0 and the respective supply or demand quantities of the associated nodes as capacity. Then a cost-minimal flow is determined with the total demand as the flow value from to . The determined flow on the edge between and indicates how much is transported between these two locations. ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle A_{i}}$ ${\displaystyle B_{j}}$

example

A beverage producer has received a one-off order for the delivery of 30 tank loads of a special beverage that is in stock at the Hamburg (16 loads) and Paris (14 loads) production facilities . According to the order, 15 loads are to be delivered to Lisbon , 5 to Barcelona and 10 to Florence . In the calculation, the transport costs per tank load were then roughly determined. The following table summarizes the data situation:

Distance and transport costs per tank load (TL)

from, to	Lisbon ${\displaystyle (B_{1})}$	Barcelona ${\displaystyle (B_{2})}$	Florence ${\displaystyle (B_{3})}$	offer
Hamburg ( ) ${\displaystyle A_{1}}$	2800 km	1800 km	1400 km	16 tsp
	6 T €	4 T €	3 T €
Paris ( ) ${\displaystyle A_{2}}$	1900 km	1100 km	1100 km	14 tsp
	3 T €	2 T €	2 T €
demand	15 tsp	5 tsp	10 tsp	30 tsp

Since there are sufficient conditions for the existence of a solution, there is at least one transportation plan for this transportation problem. We are now looking for an optimal solution to the following linear optimization problem:

Minimize

${\displaystyle z=6x_{11}+4x_{12}+3x_{13}+3x_{21}+2x_{22}+2x_{23}}$

under the constraints

1. offer
   • ${\displaystyle x_{11}+x_{12}+x_{13}=16}$
   • ${\displaystyle x_{21}+x_{22}+x_{23}=14}$
2. demand
   • ${\displaystyle x_{11}+x_{21}=15}$
   • ${\displaystyle x_{12}+x_{22}=5}$
   • ${\displaystyle x_{13}+x_{23}=10}$
3. No negative transports
   • ${\displaystyle x_{ij}\geq 0}$

Here, for example, denotes the amount that is to be transported from Paris ( ) to Lisbon ( ). ${\displaystyle x_{21}}$ ${\displaystyle A_{2}}$ ${\displaystyle B_{1}}$

Solution method

Exact procedures

In the formulation presented above as a linear program , the problem can be optimally solved, for example, with the simplex method . If the supply and demand quantities are integer and a permissible solution exists, the simplex method always delivers an integer solution for this special problem, since every corner of the associated polyhedron is integer due to the total unimodularity of the constraint matrix . Instead of the general simplex method, the network simplex method can also be used for this problem , a faster variant that is especially suitable for min-cost flow problems.

Alternatively, the problem can also be solved with any combinatorial algorithm, that is not based on linear optimization, for finding cost-minimal flows.

Opening heuristics

Several iterative procedures first look for a permissible initial solution (also called basic solution ) with the help of a simple opening heuristic and then try to improve it with an improvement heuristic. The following procedures are usually used as the opening heuristic (in ascending order according to the effort):

• North-west corner method
• Row and column sequencing methods
• Row-column succession
• Matrix minimum method (also ranking method , ascending index method or column minimum method )
• Vogel's approximation method (VAM, VAV)
• Frequency method

In most cases, the relatively complex Vogelsche approximation method produces an optimal solution relatively quickly. In data processing, the north-west corner method is often preferred because it is easier to program and the number of iterations required is negligible.

Improvement process

An optimal solution can be determined iteratively from a permissible initial solution. Examples of methods are possible

• the cycle method (stepping stone method)
• the MODI method , also known as the potential method .

With both methods, individual cells in the table are checked to determine to what extent their changes lead to an improvement in the cost situation. The change is then propagated to other cells. These changes can be described as a closed loop. Cells are changed until no further improvement is possible and the optimum has been reached. The MODI method leads in a finite number of steps to an optimal solution if the above conditions are met. With it, the optimal solution is generally found faster than with the cycle method.

See also

• Optimal transportation
• Backpack problem

swell

1. ↑ G. Monge. Mémoire on the theory of déblais et de remblais. Histoire de l'Académie des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année. 1781, pp. 666-704.
2. ↑ W. Domschke. Transport: Fundamentals, linear transport and reloading problems 2007, pp. 106-108.
3. ↑ Winkler Heiko: Goods distribution planning: A contribution to the theory of industrial company distribution of goods (German Edition), 1977, Gabler, S 160. web

Web links

• Fernuni Hagen : The transport problem in business administration
• Transport problem : Transport problem in JavaScript