Die Umlaufbildung hat das Ziel, für einen vorgegebenen Fahrplan die Anzahl der erforderlichen Fahrzeuge zu ermitteln, wobei die dadurch entstehenden Kosten minimiert werden sollen. Dieser Abschnitt beschreibt die Umlaufbildung ohne Fahrzeugaustausch. Alternativ können Sie auch eine Umlaufbildung mit Fahrzeugaustausch rechnen (Verfahrensbeschreibung der Umlaufbildung mit Fahrzeugaustausch).
Der Lösungsalgorithmus für die Umlaufbildung beruht auf der Formulierung eines Graphenflussproblems. Das Verfahren gliedert sich in die folgenden Schritte.
1. Zerlegung des Problems in unabhängige Teilprobleme (Partitionierung)
2. Konstruktion eines Graphen für jedes der Teilprobleme, in dem die Umlaufbildung als Ein-Gut-Flussproblem repräsentiert wird (Graphenaufbau)
3. Bestimmung des kostenminimalen Flusses im Graphen (Lösung des Flussproblems)
4. Zerlegen des Flusses im Graphen zu Ketten und Zusammenfassung zu Umläufen (Dekomposition)
