The objective of the line blocking is to determine the number of required vehicles for a given timetable and simultaneously minimize the resulting costs. This section describes line blocking without vehicle interchange. Alternatively, you can calculate line blocking with vehicle interchange (Line blocking description with vehicle interchange).
The solution algorithm for the line blocking procedure is based on the formulation of a graph flow problem. The procedure includes the following steps.
1. Decomposition of the problem into independent subproblems (partitioning)
2. For each subproblem, construction of a graph, where line blocking is represented as a one good flow problem (graph construction)
3. Determination of the minimum cost flow in the graph (solution of the flow problem)
4. Decomposition of the flow in the graph into chains and aggregation to blocks (decomposition)
