Fahrplanerstellung als Periodic-Event-Scheduling (public transport timetabling as periodic-event scheduling)

\(\large (\text{PESP})~~\left\{~~ \begin{align*} & \text{Min.} && \rlap{f(t, y) = \sum_{(i,j)\in A}w_{ij}\cdot(t_j-t_i+T\,y_{ij})} \\ & \text{u. d. N.} && l_{ij} \le t_j-t_i+T\,y_{ij} \le u_{ij} && ((i, j)\in A) \\ & && 0\le t_i \le T-1 && (i\in V)\\ & && 0\le y_{ij}\le 2,~y_{ij}\in\mathbb{Z} && ((i, j)\in A) \end{align*}\right. \)
\(A\)Menge von Beziehungen \((i, j)\) zwischen Ereignissen \(i\) und \(j\) (Pfeilmenge des Constraint-Graphen)
\(l_{ij}\)Zeitlicher Mindestabstand zwischen den Eintrittszeitpunkten der Ereignisse \(i\) und \(j\)
\(T\)Zykluslänge des Fahrplans
\(\ast\)\(t_i\ge 0\)Eintrittszeitpunkt von Ereignis \(i\)
\(u_{ij}\)Zeitlicher Höchstabstand zwischen den Eintrittszeitpunkten der Ereignisse \(i\) und \(j\)
\(V\)Menge von Ereignissen \(i\) (Knotenmenge des Constraint-Graphen)
\(w_{ij}\)Gewicht der Beziehung \((i, j)\) zwischen Ereignissen \(i\) und \(j\) (Pfeilgewicht im Constraint-Graphen)
\(\ast\)\(y_{ij}\in\{0, 1, 2\}\)Ternäre Entscheidungsvariable zur Darstellung von \((t_j-t_i-l_{ij})\bmod{T}\) als \(t_j-t_i-l_{ij}+Ty_{ij}\)

Anwendung auf das Problem der Fahrplanerstellung

  1. Konstruktion des Constraint-Graphen \(G=(V, A, l, u)\)
    • Knotenmenge \(V\):
      • Zwischenhaltestelle \(h\): zwei Knoten \(i_h^a\) und \(i_h^d\) (a: arrival, d: departure)
      • Starthaltestelle \(h\): ein Knoten \(i_h^d\)
      • Endhaltestelle \(h\): ein Knoten \(i_h^a\)
    • Pfeilmenge \(A\):
      • Haltepfeile \((i_h^a, i_h^d)\) von Ankunftsknoten zu zugehörigen Abfahrtsknoten
      • Fahrtpfeile \((i_g^d, i_h^a)\) für Strecken von Haltestellen \(g\) zu nächsten Haltestellen \(h\)
      • Umsteigepfeile \((i_g^a, i_h^d)\) für Haltestellen \(g\), von denen man zu Haltestellen \(h\) umsteigen kann
    • Mindest- und Höchstabstände \(l\), \(u\):
      • Haltepfeil \((i_h^a, i_h^d)\): Mindest- und Höchsthaltezeit \(l_h\), \(u_h\) an Haltestelle \(h\)
      • Fahrtpfeil \((i_g^d, i_h^a)\): Fahrzeit \(t_{gh}\) von Haltestelle \(g\) zu Haltestelle \(h\) (Mindest- = Höchstabstand)
      • Umsteigepfeil \((i_g^a, i_h^d)\): Mindest- und Höchstumsteigezeit von Haltestelle \(g\) zu Haltestelle \(h\)

  2. Wahl der Gewichtungsfaktoren \(w_{ij}\) zu Pfeilen \((i, j)\in A\)
    • Setze \(M:=\sum_h r_h+\sum_{(g, h)}s_{gh}\) mit
      • \(r_h\) als durchschnittlicher Anzahl der an Station \(h\) auf Weiterfahrt wartenden Fahrgäste
      • \(s_{gh}\) als durchschnittlicher Anzahl der pro Fahrt von Haltestelle \(g\) zu Haltestelle \(h\) umsteigenden Fahrgäste
    • Haltepfeile \((i_h^a, i_h^d)\): \(w_{ij}=M+r_h\)
    • Fahrtpfeile \((i_g^d, i_h^a)\): \(w_{ij}=0\)
    • Umsteigepfeile \((i_g^a, i_h^d)\): \(w_{ij}=s_{gh}\)
    3.