Die Tourenberechnung besteht aus zwei nacheinander ablaufenden Phasen. In der Auftragssammlung werden zusammen auf einer Tour erfüllbare Aufträge gesammelt, ohne dass der genaue Start- oder Endzeitpunkt schon fixiert wird. In der Terminierung wird für jede Tour ein Startzeitpunkt so festgelegt, dass die Anzahl der benötigten Routenzuginstanzen minimiert wird.

Auftragssammlung

Input:

Eine Liste L von Transportaufträgen für eine Route geordnet nach frühestem Bereitstellzeitpunkt

Routenverlauf mit Wegstrecken zwischen den Wegpunkten zur Berechnung von Fahrzeiten

Die Routenzugkonfiguration (Schlepper mit Höchstgeschwindigkeit, Kettungsfaktoren)

Output:

Eine Liste R von Touren

Algorithmus:

• Solange L nicht leer
• Erzeuge eine leere Tour T
• Entnehme ersten Auftrag A aus L und füge A zu T hinzu
• Falls T Kapazitätsgrenzen, Schichtpläne oder Anlieferzeitfenster verletzt, notiere Fehlerbedingung für A
• Für jeden Auftrag A in L
  • Falls A zu T hinzugefügt werden kann, ohne Kapazitätsgrenzen, Schichtpläne oder Anlieferzeitfenster zu verletzen
  • Füge A zu T hinzu
  • Entferne A aus L
• Füge T zu R hinzu

Terminierung

Input

Eine Liste F von Touren, mit den frühest- und spätestmöglichen Startzeitpunkten, so dass keine Schichtpläne oder Anlieferzeitfenster verletzt werden. F ist geordnet nach dem frühestmöglichen Startzeitpunkt.

Output

Ein Startzeitpunkt S_T für jede Tour T in F

Eine Routenzuginstanz R_T für jede Tour T in F

Eine Liste B von benötigten Routenzuginstanzen

Algorithmus

• Initialisiere B zu leerer Liste
• Für jede Tour T in F
• Für jede Routenzuginstanz R in B
  • Falls R in der Lage ist T nahtlos an eine andere Tour anzuschließen:
  • R_T = R
  • S_T = Endzeitpunkt der vorherigen Tour
  • Beginne neuen Durchlauf der äußeren Schleife
• Für jede Routenzuginstanz R in B
• Falls R in der Lage ist T mit einer Pause an eine andere Tour anzuschließen:
  • R_T = R
  • S_T = Frühestmöglicher Startzeitpunkt von T
  • Beginne neuen Durchlauf der äußeren Schleife
• Füge neue Routenzuginstanz R zu B hinzu
• R_T = B
• S_T = Frühestmöglicher Startzeitpunkt von T