Transportation theory (mathematics)
The transportation problem is a question from the Operations Research: For transporting uniform objects of several supply to several demand locations is an ideal, that is to find cost- minimal plan, the existing and, where quantities to be delivered at the individual sites and the respective transportation costs are known per unit between all locations.
Already in 1781 formulated a general Monge transportation problem mathematically. In the standard case of a relative to the transport quantities linear cost function is a linear programming problem, for in addition to standard methods such as simplex method, there exist some solution algorithms. One of the first topics of Operation Research, the problem was formulated in 1939 by Kantorovich as a mathematical model. In the 1950s developed Dantzig, Charnes and William W. Cooper and Ford and Fulkerson different solution algorithms.
The classical transportation problem without capacity constraints on the transport paths is a special case of the capacitated transportation problem, which specifies paths for minimum or maximum transport volumes. Classic and capacitated transportation problem in turn are special cases of the ( capacitated ) Umladeproblems, in which there are pure transfer points in addition to supply and demand locations. A special case of the transportation problem, the assignment problem, in which at each place offered or asked for only one unit.
- 3.1 Exact method
- 3.2 Opening heuristics
- 3.3 improvement process
Mathematical formulation of the classical transportation problem
The classical transportation problem without capacity constraints is described by the following data: m offer sites provide quantities of the goods ( ) ready n demand places ask the estate in the amounts to (). The amounts must be greater than or equal to zero, also the total supply of aggregate demand must be equal ( balanced transportation problem ). If this is not in the original problem of the case, a fictitious quotation, or Nachfrageort is introduced, which provides the excess demand, and absorbs the excess supply. Furthermore - as in a matrix C - where the non-negative cost of transporting a quantity unit of the Angebotsort Nachfrageort. Transportation costs to or from a fictional place are set to zero. Can not be transported between two locations, the corresponding transport costs are infinite.
Formulation as a linear program
In the transportation plan describes the transport quantity that is transported from to. The total cost arising by the determined transport quantity is multiplied for each transport with the cost of transportation on the particular transport and these products summed. Wanted is a transport plan with minimum cost which complies with the limitations of the available quantities and meets the demand at all demand locations. With the imported identifiers is then obtained by the mathematical model of the transport problem:
The first constraint describes the range of each Angebotsort to be fully accessed, while the second specifies for each Nachfrageort that the demand is to be met in full. All transport volumes must be non-negative. Often, the integrality of transport volumes is required, ie.
If the conditions listed at the beginning () met and that all paths are usable (), then there exists at least one solution for the transportation problem. Can not be transported between some places, the existence of a solution is not assured.
Formulation as min -cost flow problem
With the help of graphs the problem can be formulated as a min -cost flow problem. It comes with edge cost between two nodes in a graph to find a minimum cost flow with a given flow value. Every place is here represented by a node and each of Angebotsort to each Nachfrageort an edge is drawn, the costs of meeting the transportation costs. In addition, two special nodes and introduced. Node is connected to all locations and offer all types of demand, these edges 0 and capacity as the cost value have the relevant offer or demand quantities of the corresponding node. Subsequently, a minimum cost flow is determined by the total demand as a flow value from to. The calculated flow on the edge between and indicates how much is transported between these two places.
Example
A beverage producer has received a one-time contract to supply 30 tank loads of a special drink, which at the production Hamburg (16 charges ) and Paris (14 charges ) is in stock. According to the contract to be delivered 15 cargoes to Lisbon, 5 and 10 to Barcelona to Florence. Then the transport costs were roughly determined per tank charge in the calculation. The following table summarizes the data situation together:
Since the sufficient conditions for the existence of a solution are given, there exists at least one transport plan for this transportation problem. Is now sought an optimal solution to the following linear optimization problem:
Here, for example, refers to the amount of Paris () should be transported to Lisbon ().
Solution method
Exact method
In the above presented formulation as a linear program, the problem for example with the simplex method to solve optimally. If the supply and demand quantities are integers and a feasible solution exists, always delivers the simplex method for this particular problem an integer solution, as due to the complete unimodularity of the constraint matrix every corner of the corresponding polyhedron is an integer. For this problem, instead of the general simplex method, the network simplex method can be used, a faster variant, which is especially suitable for min -cost flow problems.
Alternatively, the problem with any combinatorial, that is not based on linear programming to be solved algorithm for finding a minimum cost flows.
Opening heuristics
Several iterative methods search only with the help of a simple opening of an admissible heuristic starting solution (also called basic solution ) and then try to improve them by an improvement heuristic. The following procedure are commonly used as the opening heuristic (according to expenditure order):
- North -west corner method
- Matrix minimum method (also ranking method, ascending index method or column minimum method)
- Vogelsche approximation method (VAM, VAV)
In most cases, the relatively complex Vogelsche approximation method performs relatively quick an optimal solution. In data processing, the North -West corner method is often preferred because it is easier to program and the number of iterations required is not significant.
Improvement process
From a certificated take-off solution can be constructed iteratively an optimal solution. As the method used for example in question
- The Stepping Stone Method ( springboard method)
- The MODI method, also called potential method.
For both methods, individual cells of the table are checked to what extent their change brings about an improvement in the cost situation. In this case, the change is propagated to other cells. These changes can be described as a closed circuit. There are often modified cells until no further improvement is possible and the optimum has been reached. The MODI method results in a finite number of steps to an optimal solution if the above conditions are met. With it, the optimal solution is generally found more quickly than with the Stepping Stone method.