In dieser Arbeit wird ein graphenbasiertes Modell zur Einbindung von Preissystemen des öffentlichen Nahverkehrs in Routing-Algorithmen vorgestellt. Jeder Knoten des Graphen repräsentiert einen abstrakten Preiszustand einer Route und ist an einen tatsächlichen Preis gekoppelt. Damit sind sehr einfache und konzise Beschreibungen von Tarifstrukturen möglich, die sich algorithmisch behandeln lassen. Durch das zeitgleiche Tracken eines Pfades im Routinggraphen im Ticketgraphen kann schon während einer Routenberechnung der Preis bestimmt werden. Dies ermöglicht die Berechnung von preisoptimalen Routen. An den Tarifsystemen der Verkehrsverbünde MDV (Mitteldeutscher Verkehrsverbund) und VBB (Verkehrsverbund Berlin- Brandenburg) wird die Konstruktion des Modells detailliert erläutert.

Der Beitrag ist im Volltext verfügbar. Das PDF enthält alle Bilder und Formeln.

1 Einleitung

In Deutschland verlassen sich Millionen Reisende auf Nahverkehrsapplikationen, die sie bei der Wahl der besten Route unterstützen. In der Regel sind diese Applikationen jedoch auf die Fahrtzeit als einziges Optimierungskriterium beschränkt. In den letzten Jahren kam es zu zahlreichen Fortschritten im Bereich der Routing-Algorithmen [1], sodass Suchanfragen mittlerweile in wenigen Millisekunden beantwortet werden können. Dies eröffnet die Frage nach dem Einbeziehen weiterer Optimierungskriterien. Das Ziel ist eine sogenannte Pareto-Menge von Routen zu finden, die verschiedene Kompromisse der Kriterien darstellen, und aus denen vom Nutzer eine persönliche Präferenz ausgewählt werden kann. Naheliegende Kriterien sind z.B. Umstiege, Wartezeiten oder die Kosten einer Reise. Die Berechnung einer günstigsten Reise ist dabei besonders kompliziert, da je nach Anbieter verschiedenste Kriterien in die Preisberechnung einfließen. So bestimmen sich gültige Tickets beispielsweise über Tarifzonen oder -waben, die Anzahl der Umstiege, die gefahrene Distanz, die Anzahl der Halte, Zusatzzahlungen auf bestimmten Linien oder Nachtzuschläge. Hinter der Preisoptimierung verbirgt sich eigentlich also eine multikriterielle Optimierung. Aufgrund dieser Komplexität gab es bisher nur wenige Arbeiten, die sich explizit mit der Preisberechnung befassen. Das sich eine Preisoptimierung aber trotz der Schwierigkeiten lohnen kann, kann in Abbildung 1 beobachtet werden.

Bild 1: Für diese Darstellung wurden kürzeste Wege für alle OD-Paare (Origin-Destination- Paare) im Netz des MDV berechnet. Es wurde dabei nach Fahrtzeit und Umstiegen optimiert. Für jedes OD-Paar wurde so eine Menge optimaler Routen gefunden. Diese Routen durchqueren ggfs. jeweils unterschiedliche Tarifzonen. Die verbundenen Datenpunkte repräsentieren dabei, wie oft eine gewisse Kombination von Tarifzonen für ein OD-Paar gefunden wurde. So gibt es z.B. ungefähr 60.000 OD-Paare, für die es eine Lösung mit vier und eine mit fünf Tarifzonen gibt. Durch eine Routenauswahl nach Preis können sich also durchaus Vorteile für den Kunden ergeben.

In dieser Arbeit wird ein Ansatz vorgestellt, der in der Lage ist, alle im Nahverkehr relevanten Aspekte der Preisberechnung für Einzelfahrten abzubilden und sie in klassische Routing-Algorithmen zu integrieren. Jeder Kante werden dabei Tarifattribute zugeordnet, die den Tarifzustand einer Route beeinflussen. Der Tarifzustand besteht im Wesentlichen aus numerischen Attributen und einem abstrakten Ticket in einem Ticketgraphen. Der Ticketgraph modelliert dabei die Menge aller Tickets und möglichen Übergange zwischen Tickets (Erweiterungen ihres Gültigkeitsbereiches). Der Ansatz kombiniert dabei zwei verschiedene mathematische Ideen: Die Definition des Zustands einer Route über deterministische finite Automaten und der Berechnung kürzester Wege mit Gewichten, die nicht mehr den rationalen Zahlen, sondern strukturärmeren Räumen entstammen.

Literatur Eine Erweiterung des Dijkstra-Algorithmus auf mehrere Optimierungskriterien wird von Hansen [2] und Theune [3] vorgestellt. Der RAPTOR-Algorithmus [4] von Delling et al. optimiert neben der Fahrtzeit implizit auch die Anzahl der Umstiege. So verwenden verwenden Delling et al. [4] die Tarifzonen des Londoner Nahverkehrsnetzes als Optimierungskriterium in einer Beispielanwendung ihres multikriteriellen RAPTOR-Algorithmus. In einem zweiten Schritt werden dann die preisgünstigsten Routen aus den gefundenen Vorschlägen ausgewählt. Dieser Ansatz kann allerdings streckenbezogene Tickets (Kurzstrecke) nicht abbilden. Müller-Hannemann und Schnee [5] nutzen Heuristiken um relationsbasierte Preise des Fernverkehrs auf Kanten des Routinggraphen zu projizieren. Dieser Ansatz scheint vor allem im Fernverkehr sinnvoll. Allerdings kann die Optimalität der gefundenen Routen nicht mehr garantiert werden. Kürzeste Wege unter Nebenbedingungen an finite Automaten/reguläre Sprachen wurden bereits von Barrett et al. [6] untersucht. Allerdings wird hier keine Optimierung auf den Automaten untersucht. Eine Übersicht zur kombinatorischen Optimierung über geordneten algebraischen Strukturen findet sich bei Zimmermann [7]. Später wurden kürzeste Wege mit Gewichten in geordneten Halbringen auch von Mohri [8] untersucht. Diese Veröffentlichung ist eine überarbeitete Fassung des technischen Reports [9] und beschäftigt sich detailliert mit der Modellierung der Preissysteme. Eine mathematische Darstellung der algorithmischen Nutzung der Modelle und entsprechende Optimalitätsbeweise geben die Autoren in [10].

Übersicht In Kapitel 2 wird das Modell der konditionalen Tarifnetzwerke detailliert erläutert. Abschnitt 2.1 erläutert dabei die grundlegenden Ideen ohne Verwendung exakter mathematischer Formulierungen. In Abschnitt 2.2 werden dann die verwendeten Begriffe mathematisch exakt formuliert. Die Anwendung des Modells auf konkrete tarifliche Besonderheiten wird in Abschnitt 2.3 erläutert. In Abschnitt 2.4 wird die Einbindung des Modells in klassische Routingalgorithmen kurz umrissen. Zum Abschluss werden in Kapitel 3 zwei beispielhafte Modellierungen für die Tarifverbünde MDV und VBB präsentiert.

2 Konditionale Tarifnetzwerke

2.1 Das Modell

Wir beschreiben ein Modell, in dem der Preis für eine Route im öV in einem mehrstufigen Prozess berechnet wird: Entlang der Route werden im ersten Schritt Tarifattribute aufgesammelt, die dann genutzt werden, um den Tarifzustand der Teilroute zu ermitteln. Ausgehend von einem Ausgangszustand am Startknoten werden die Attribute bei jedem Übergang über eine Kante im Routinggraphen zur Aktualisierung des Tarifzustandes genutzt, bis am Zielknoten der Endzustand bestimmt ist. Dies ist der Tarifzustand der Route. Mit seiner Hilfe wird dann im letzten Schritt die Preisfunktion ausgewertet, die den richtigen Preis liefert.

Die aufsammelbaren Tarifattribute lassen sich unterteilen in numerische Attribute (z.B. Haltestellenabstände), Mengen (z.B. Tarifzonen), boolsche Werte (z.B. Umstiege) und abstrakte Tarifsymbole (z.B. als Marker für einen Zuschlag auf bestimmten Strecken).

Numerische Attribute, Mengen und boolsche Werte lassen sich im Sinne einer kompakten Darstellung mit Hilfe des mathematischen Begriffs eines positiven, partiell geordneten Monoids beschreiben. Es genügt, sich dieses Monoid als eine Zusammenfassung verschiedener tariflicher Komponenten mit ähnlichen Struktureigenschaften vorzustellen (u.a. Additivität, Vergleichbarkeit der Elemente). Eine genauere Erläuterung des Begriffs folgt in Abschnitt 2.2. Die Tarifattribute, die sich als ein solches Monoid darstellen lassen, nennen wir Monoidattribute.

Der Tarifzustand setzt sich zusammen aus dem Monoidzustand und einem Ticket. Im Monoidzustand werden alle bisher aufgesammelten Monoidattribute aufsummiert. Er ist also vergleichbar mit klassischen Kantengewichten.

Das (abstrakte) Ticket, spielt eine besondere Rolle. Es kodiert typischerweise ein einzelnes Ticket, z.B. Berlin AB oder ein Kurzstreckenticket. Allerdings kann es sinnvoll sein, ein Ticket in mehrere abstrakte Tickets aufzuteilen. Dies ist dann der Fall, wenn im Ticket noch weitere relevante Informationen kodiert werden sollen, die zur Bestimmung der zukünftigen Entwicklung des Tickets benötigt werden. Umgekehrt ist jedoch jedem Ticket ein konkreter Preis zugeordnet. Tickets können im Verlauf einer Route durch einen Tarifübergang ineinander übergehen. So geht z.B. das Ticket ’Berlin AB’ in das Ticket ’Berlin ABC’ über, wenn die Route in den C-Bereich des Berliner Tarifgebiets führt. Tarifübergänge werden durchgeführt, wenn die Route bestimmte Übergangsbedingungen erfüllt. Diese Tarifbedingungen hängen vom Monoidzustand und dem zuletzt gefundenen Tarifsymbol auf der Route ab. Der Monoidzustand stellt dabei additive Informationen zur Bestimmung der Tarifentwicklung zur Verfügung, z.B. die Anzahl von besuchten Zonen, die in vielen Tarifsystemen zur Bestimmung des Preises wichtig ist. So wechselt man in vielen Tarifen ab einer gewissen Anzahl von Haltestellen von einem Kurzstreckentarif in einen Normaltarif. Das Tarifsymbol kodiert hingegen tarifliche Ereignisse auf der Route, z.B. können Umstiege mit einem Tarifsymbol für einen Preisaufschlag markiert werden. Dieses Tarifsymbol wird dabei auf den Umstiegskanten im Routinggraphen notiert.

Auf diese Weise entsteht ein gerichteter Graph, dessen Knoten die Tickets sind, während die Kanten Übergänge zwischen diesen Tickets kodieren. Jeder Übergangskante ist dabei eine Tarifbedingung zugeordnet. Einen so beschrifteten Digraphen nennen wir einen Ticketgraphen. Den Ticketgraphen in Kombination mit den Tarifbedingungen, den Tarifattributen, den Tarifstartzuständen und der Preisfunktion bezeichnen wir als konditionales Tarifnetzwerk (KTN).

Der Zweck des Modells ist es die Berechnung beweisbar preiswertester Routen für Fahrtwünsche eines Kunden zu ermöglichen. Es beschränkt sich dabei auf Einzelfahrscheine, da der Erwerb eines Zeitfahrscheins in der Regel nicht in die indivuelle Entscheidung für eine Route einfließt. Stattdessen handelt es sich um eine Eingangsgröße des Routingproblems, die die tariflichen Optionen bei der Routensuche beeinflusst. Insbesondere bedeutet dies, dass es nicht als sinnvoll erscheint Zeitfahrscheine und Einzelfahrscheine im selben KTN darzustellen. Für Kunden im Besitz eines solchen Fahrscheins muss daher in der Regel ein modifiziertes KTN zur Preisberechnung herangezogen werden.

2.2 Mathematische Formulierung

Das Routingnetzwerk wird durch einen gerichteten Graphen G = (V , A) dargestellt. Kanten repräsentieren entweder elementare Verbindungen von Linien (Verbindung zweier benachbarter Stationen), Fußwege oder Umstiege. Der Ticketgraph wird mit T = (T , E ) bezeichnet, wobei T die Tickets und E die Übergangskanten bezeichnen. Übergangskanten haben ein Ausgangsticket tail (e) und ein Zielticket head (e). Jede Kante a ∈ A im Routinggraph ist einem Tarifattribut A(a) aus dem Raum der Tarifattribute S × H zugeordnet, wobei S eine Menge abstrakter Tarifsymbole und (H, ∗, n, ≤) ein partiell geordnetes, positives Monoid ist. Der Tarifzustand einer Route f wird als Element des Produktraums F = T × H beschrieben, wobei T das Ticket und H wiederum das Monoid ist.

Monoid Ein partiell geordnetes Monoid (H, ∗, n, ≤) ist eine Menge H mit einer Operation ∗, die das Assoziativgesetz erfüllt. Weiterhin gibt es ein neutrales Element n (z.B. 0 in den natürlichen Zahlen, die leere Menge für die Menge der Tarifzonen) mit n ∗ h = h ∗ n = h für alle h in H. Weiterhin soll es eine Ordnungsrelation ≤ auf H geben, die einen Vergleich von Tarifzuständen untereinander erlaubt. Diese kann auch partiell sein, d.h. dass nur eine Teilmenge der Elemente von H unter einander vergleichbar sein müssen. Die Ordnungsrelation muss sich mit ∗ vertragen (Translationsinvarianz), d.h.

h₁ ≤ h₂ ⇒ h₁ ∗ h ≤ h₂ ∗ h für alle h, h₁, h₂ in H.                                                  (1)

Schließlich soll n ≤ h für alle h ∈ H gelten (Positivität).

In Abschnitt 2.3 sind mehrere Beispiele für Monoide, die in Preissystemen auftreten können, zu finden. Da Produkte von Monoiden wieder Monoide bilden, können wir alle relevanten Aspekte eines Preissystems, die auf irgendeine Art gezählt werden müssen, mathematisch als ein einziges Monoid modellieren. Dies vereinfacht die Darstellung wesentlich. Damit Tarifattribute sinnvoll in Algorithmen verwendet werden können, dürfen Rundfahrten nicht zu einer Verbesserung der Attribute führen. Genau diese Eigenschaft wird von positiven, partiell geordneten Monoiden erfüllt.

Die Übergangsfunktion Tr : E × S × H −→ {0, 1} modelliert eine Ja/Nein-Antwort, ob sich ein Ticket in T entlang der Kante e ∈ E entwickeln kann. An der Kante werden dabei das im Routinggraph aufgesammelte Tarifsymbol in S und der aktuelle Monoidzustand in (H, ∗, n, ≤) geprüft. Das aktuell gültige Ticket ist als Ursprung tail (e) der Kante e kodiert. Für jeden möglichen Tarifzustand darf es nur eine eindeutige Entwicklungsmöglichkeit geben, das heißt:

Formel siehe PDF

Unter Verwendung der Übergangsfunktion Tr können wir den Updateschritt eines Tickets entlang einer Kante a im Routinggraphen G präzise beschreiben. Wir führen dazu eine Updatefunktion Up : F × A −→ F ein, die jedem Tarifzustand an a einen neuen, aktualisierten Tarifzustand zuweist. Für den Tarifzustand f = (f t , f h) ∈ F , a ∈ A definieren wir ˜f = Up(f , a) durch

Formel siehe PDF

Ausgehend von einem Starttarifzustand S(v₀) ∈ F kann nun der Tarifzustand eines Pfades p = (v₀, . . . , v_n) im Routinggraphen durch das rekursive Anwenden der Updatefunktion auf jede Kante in p bestimmt werden. Ebenso ist jedem Teilpfad von p ein gültiger Tarifzustand zuordenbar. Wir bezeichnen den Tarifzustand eines Pfades p mit f (p). Teilpfade können dann in Routingalgorithmen anhand ihrer Tarifzustände verglichen werden, um einen dominanten Pfad zu ermitteln.

Bild 2: Simpler Routinggraph mit einer Route auf der linken Seite und ein Ticketgraph mit zwei Tickets auf der rechten Seite. Die Kanten des Routinggraphen sind jeweils mit einem Tarifsymbol und einem Tarifattribut aus R annotiert.

Beispiel Abbildung 2 zeigt ein simples Beispiel eines Routinggraphen mit verknüpftem Ticketgraphen. Die Tarifattribute entstammen der Menge der Tarifsymbole S = {S₀, S₁, S₂} und dem Monoid H = (R+, +, 0, ≤), also den positiven, reellen Zahlen mit der normalen Addition und Ordnungsrelation. In diesem Beispiel wird (R+, +, 0, ≤) verwendet um die Anzahl der genutzten elementaren Verbindungen zu zählen. Als Übergangsfunktion wählen wir beispielsweise (hier ist s ∈ S ein Tarifsymbol und h ∈ R)

Tr ((t₁, t₂), s, h) = 1 ⇐⇒ s = S₂ und h ≥ 1                                                                         (5)

Ausgehend von einem Startzustand S(v₀) = (t₁, 0) kann nun der Tarif des Pfades (v₁, v₂, v₃, v₄) nachverfolgt werden. Es ergeben sich

•      f (v₁) = (t₁, 0),

•      f (v₁, v₂) = Up((t₁, 0), (v₁, v₂)) = (t₁, 1), da As (v 1, v 2) = S₀,

•      f (v₁, v₂, v₃) = Up((t₁, 1), (v₂, v₃)) = (t₁, 2), da As (v 1, v 2) = S₁,

•      f (v₁, v₂, v₃, v₄) = Up((t₁, 2), (v₃, v₄)) = (t₂, 3), da As (v 1, v 2) = S₂.

Obwohl schon am Knoten v₃ mehr als zwei Kanten überquert wurden, gibt die Übergangsfunktion trotzdem 0 zurück, da nur das Symbol S₁ aufgesammelt wurde. Auf diese Weise können globale Bedingungen an den Pfad von lokalen Parametern abhängen.

Mithilfe der nun formal eingeführten Begrifflichkeiten können wir das Konzept eines konditionalen Tarifnetzwerkes (KTN) mathematisch präzise notieren.

Konditionales Tarifnetzwerk Sei G = (V , A) ein Routingnetzwerk und folgendes gegeben:

1. der Raum der Tarifattribute S × H als Produkt der Tarifsymbole S und eines partiell geordneten, positiven Monoids (H, ∗, 0, ≤),

2. Tickets T ,

3. ein kreisfreier Ticketgraph T = (T , E ) mit Übergangsfunktion Tr : E × S × H −→ {0, 1},

4. Tarifattribute für die Kanten des Routinggraphen: A(a) ∈ S × H    ∀ a ∈ A,

5. Startzustände für alle Knoten S(v ) ∈ T × H     ∀ v ∈ V und

6. eine Preisfunktion π : T −→ Q₊.

Das Tuple (T , H, A, S, S, Tr , π) heißt konditionales Tarifnetzwerk für G = (V , A). Die Preisfunktion π weist am Ende jedem (abstrakten) Ticket wieder seinen Preis zu. Die Preise dürfen dabei entlang eines gerichteten Pfades in T nicht fallen.

2.3 Modellierung spezifischer Aspekte

In diesem Abschnitt wird nachgewiesen, dass sich typische Elemente von Nahverkehrspreissystemen mit den Mitteln eines konditionalen Tarifnetzwerkes darstellen lassen.

2.3.1 Tarifzonen und -waben

Die meisten größeren Tarifverbünde setzen tarifzonenbasierte Preissysteme ein. Es gibt dabei Preisstufen, die in einer Tabelle mit der Anzahl durchfahrener Zonen verknüpft sind. Bei der Bestimmung der Anzahl der durchfahrenen Zonen kann das Problem auftreten, dass eine Zone mehrfach durchfahren wird. In diesem Fall ist es nicht korrekt, als Tarifattribut die Anzahl der besuchten Zonen mitzuführen und diese Zahl jeweils beim Übertritt von einer Zone in eine benachbarte zu erhöhen. Man muss sich stattdessen für jede einzelne Zone merken, ob sie schon besucht wurde oder nicht.

Das Problem kann mithilfe der Modellierung im KTN behoben werden. Dabei wird jede Preisstufe zu einem Ticket. Zwischen zwei Tickets wird immer dann eine Kante eingeführt, wenn durch das Aufsammeln von Zonen von der ersten Preisstufe ohne Zwischenschritt in die nächste übergegangen werden kann. Die Übergangsbedingungen an diesen Kanten sind dabei untere Schranken aus dem Monoid (2Z , ∪, ∅, ⊆), wobei Z die Menge aller Tarifzonen bezeichnet und 2Z die Menge aller möglichen Teilmengen von Z . Als Operation wird die Mengenvereinigung ∪ verwendet, als Ordnungsrelation die Teilmengenrelation ⊆. In der Praxis können Teilmengen platzsparend als Bitfeld implementiert werden.

2.3.2 Kurzstrecke

Kurstrecken können ebenfalls in einem KTN modelliert werden. Jedes Kurzstreckenticket wird dabei als ein Ticket angelegt. Eine odere mehrere Kanten stellen die Übergänge in einen Normaltarif dar. In der Regel hängen Kurzstreckenregelungen von der Haltestellendistanz und dem Vorliegen von Umstiegen ab. Diese beiden Eigenschaften können als Monoidattribute modelliert werden. Die Haltestellendistanz wird dabei im Monoid (N, +, 0, ≤) abgebildet, also den normalen arithmetischen Operationen über den natürlichen Zahlen. Ob ein Umstieg vorliegt kann im Monoid ({0, 1}, or , 0, ≤) abgebildet werden. Der Wert 0 oder 1 gibt an, ob ein Umstieg in der Route enthalten ist. Die Werte werden mit der logischen oder-Operation (or ) verknüpft und es gilt die Ordnungsrelation 0 ≤ 1. Kanten, die Umstiege modellieren, erhalten dann den Wert 1, alle anderen den Wert 0. Dies setzt die Verwendung eines Graphenmodells (für G) voraus, bei dem eine Station in mehrere Routen, Umstiegs- und Fußwegknoten aufgeteilt wird. Diese Modellierung wird von Disser et al. [11] detailliert erläutert. Ein Beispiel findet sich in Bild 3.

2.3.3 Preisaufschläge für besondere Linien