The column sequence method and the row sequence method are heuristic methods from operations research , which are intended to provide a valid initial solution for the transport problem. The optimization algorithm of the transport problem starts from this solution. The costs are already taken into account when calculating the initial ( basic solution ).
Column sequencing algorithm
It begins with the first column and the most cost-effective field is occupied as a maximum. If the column or row restriction is met, the column or row is deleted. If the column restriction has not yet been met, this is initially left unfulfilled given the strict form of the column sequence. This is done for each column - in ascending order of the column number. If a field in the last column is occupied, the first run is completed. Then, in ascending order of the column number, the next cost-effective field is filled to the maximum in all columns in which the column restriction is not yet fulfilled. This continues until all column restrictions are met.
With the relaxed form of the column sequence , if the column restriction is not met in the first field that is filled, the field with the second cheapest costs is used as a maximum. For the untypical case that all column fields have to be selected in order to meet the column restriction, these are selected directly one after the other.
Examples of the column order method
The numbers marked in red correspond to the fields with the lowest cost - including subsequent runs. The number of the occupancy is shown in brackets. The subscript behind the costs reflects the number of occupancy. If this is marked in green, the column restriction is fulfilled.
The following example is for the strict form of the column order :
The costs of the initial solution are:
The following example is for the relaxed form of the column sequence :
The costs of the initial solution are:
Sequence algorithm
The algorithm for the row sequence method is analogous to the algorithm of the column sequence method, except that columns are replaced by rows here.
It begins with the first line and the most cost-effective field is occupied as a maximum. If the column or row restriction is met, the column or row is deleted. If the line restriction has not yet been met, this is initially left unfulfilled given the strict form of the line sequence . This is done for each column - in ascending order of the line number. If a field in the last line is filled, the first run is completed. Then, in ascending order of the line number, the next cost-effective field is filled to the maximum in all lines in which the line restriction is not yet fulfilled. This is continued until all row restrictions are met.
With the relaxed form of the line sequence , if the line restriction is not met for the first field that is filled, the field with the second cheapest costs is used as a maximum. In the untypical case that all line fields have to be selected in order to meet the line restriction, these are selected directly one after the other.
Examples of line sequencing methods
The numbers marked in red correspond to the fields with the lowest cost - including subsequent runs. The number of the occupancy is shown in brackets. The subscript behind the costs reflects the number of occupancy. If this is marked in green, the row restriction is fulfilled.
The following example is for the strict form of the line sequence :
The costs of the initial solution are:
The following example is for the relaxed form of the line sequence :
The costs of the initial solution are:
literature
Tomáš Gál : Basics of Operations Research 2: Graphs and Networks Network Planning Transport Problems Integer Optimization . 3rd edition, Springer, Berlin 1992, p. 307. ISBN 3-540-55294-4 .
