FGSV-Nr. FGSV 002/127
Ort online-Konferenz
Datum 13.04.2021
Titel Ein Graphen-basiertes Modell zur Beschreibung von Preissystemen im öffentlichen Nahverkehr
Autoren Ralf Borndörfer, Marika Karbstein, B.Sc. Ricardo Euler
Kategorien HEUREKA
Einleitung

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.

PDF
Volltext

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.

h1 h2 h1 h h2 h für alle h, h1, h2 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(v0) F kann nun der Tarifzustand eines Pfades p = (v0, . . . , vn) 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 = {S0, S1, S2} 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 ((t1, t2), s, h) = 1 ⇐⇒ s = S2 und h 1                                                                         (5)

Ausgehend von einem Startzustand S(v0) = (t1, 0) kann nun der Tarif des Pfades (v1, v2, v3, v4) nachverfolgt werden. Es ergeben sich

•      f (v1) = (t1, 0),

•      f (v1, v2) = Up((t1, 0), (v1, v2)) = (t1, 1), da As (v 1, v 2) = S0,

•      f (v1, v2, v3) = Up((t1, 1), (v2, v3)) = (t1, 2), da As (v 1, v 2) = S1,

•      f (v1, v2, v3, v4) = Up((t1, 2), (v3, v4)) = (t2, 3), da As (v 1, v 2) = S2.

Obwohl schon am Knoten v3 mehr als zwei Kanten überquert wurden, gibt die Übergangsfunktion trotzdem 0 zurück, da nur das Symbol S1 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

Preisaufschläge für die Verwendung spezieller Züge können durch die Verwendung von Tarifsymbolen modelliert werden. Dazu muss es eine Kante im Routinggraphen geben, die den Umstieg in den teureren Zug modelliert (siehe Bild 3). An dieser Kante kann dann das Tarifsymbol aufgesammelt werden. Im Ticketgraphen gibt es für jedes reale Ticket dann ein Ticket mit und eines ohne den Aufschlag. Es wird eine Übergangskante zwischen beiden eingeführt, deren Übergangsbedingung vom Tarifsymbol abhängt.

Bild 3: Der Routinggraph modelliert zwei Linien z1 und z2 an einer Station st . Der Stationsknoten st ist nur mit den Ankunfts- und Abfahrtsknoten der Routen verbunden, sowie mit einem Knoten f u der ein- und ausgehende Fußwege modelliert. Direkte Verbindungen zu anderen Stationen gibt es nicht. Der Ticketgraph auf der rechten Seite modelliert ein Kurzstreckenticket ohne Umstieg (t1), ein normales Ticket (t2), sowie
beide Tickets zuzüglich eines Zuschlages für die Linie z1 (t1z und t2z ). Übergangsbedingungen sind in verkürzter Notation direkt im Ticketgraphen notiert. Das Aufsammeln des Tarifsymbols S1 löst den Wechsel in die Tickets mit Aufschlag aus. Der Monoidzustand wu zählt die Umstiege des Pfades. Jede Kante des Routinggraphen ist mit einem Tarifsymbol und einem Tarifattribut, das Umstiege angibt, annotiert.

2.3.4 Nachtzuschläge

In einigen Verbünden existieren Nachtzuchläge auf Nachtlinien. Die Modellierung dieser Linien wird wie in Abschnitt 2.3.3 beschrieben vorgenommen. Wenn der Zuschlag nicht nur von der Linie, sondern auch von der Tageszeit abhängt, muss die Tageszeit als Tarifattribut eingeführt werden. Der Übergang in ein Ticket mit Zuschlag ist dann nicht nur von dem die Linie markierenden Tarifsymbol, sondern zusätzlich noch von diesem Tarifattribut abhängig. Das Monoid besteht hier aus den natürlichen Zahlen bis 86400 (Sekunden am Tag) und der Addition modulo 86400 (notiert als Z86400). Leider ist die einzige mit Z86400 verträgliche Ordnungsrelation trivial, d.h. h1 h1 h1 = h2. Dies schränkt die Vergleichbarkeit von Tarifzuständen ein. Hier sollte in der praktischen Anwendung mit Heuristiken gearbeitet werden.

2.3.5 Neutrale Zonen

Manche Tarifverbünde, wie z.B. der MDV, definieren neutrale Zonen. Diese werden einer der umliegenden Tarifzonen zugeschlagen, wenn diese durchfahren wird. Auf diese Weise müssen in Grenzregionen von Tarifzonen für kurze Fahrten nicht zwei volle Zonen bezahlt werden. Es gibt zwei Ideen hiermit umzugehen.

∙ Für jede neutrale Zone wird ein Ticket in T angelegt. Alle Stationen in einer Zone erhalten ein eindeutiges, die Zone repräsentierendes Tarifsymbol. Wird im Routinggraphen ein anderes Tarifsymbol aufgesammelt, bedeutet dies, dass die neutrale Zone verlassen wurde. Wenn ein Symbol aufgesammelt wurde, das keine neutrale Zone repräsentiert, wird in ein Zonenticket gewechselt. Die dabei gefundene Tarifzone wird auch rückwirkend für die neutrale Zone gültig. Wird direkt eine andere neutrale Zone betreten, ist nicht eindeutig klar, welche Tarifzonen nun gültig sind. Deswegen erfolgt ein Übergang in ein Ticket, dass die Kombination beider neutraler Zonen repräsentiert. Sobald nun eine nicht neutrale Zone gefunden wird, kann wieder in ein entsprechendes Zonenticket gewechselt werden.

∙ Dieser Ansatz ist simpler und bildet neutrale Zonen nicht direkt im konditionalen Tarifnetzwerk ab. Stattdessen werden an jeder Station im Routinggraphen, die in einer neutralen Zone liegt, mehrere optionale Tarifattribute angelegt, die die verschiedenen wählbaren Tarifzonen repräsentieren. Ein Routingalgorithmus muss die Suche an dieser Stelle aufspalten und beide Optionen verfolgen.

2.4 Integration in Kürzeste-Wege-Algorithmen

Das Konzept KTN kann zur Berechnung von preisgünstigsten Routen in multikriterielle Kürzeste-Wege-Algorithmen wie Dijkstra’s Algorithmus und RAPTOR integriert werden. In diesem Abschnitt soll das Vorgehen dabei kurz erläutert werden. Eine mathematische präzise Darstellung, sowie die erforderlichen mathematischen Beweise, übersteigen den Rahmen dieses Beitrages. Interessierte Leser*Innen seien dafür auf [10] verwiesen.

Seien p1 und p2 Pfade von einer Station s zu einer Station t (s, t -Pfade) und seien f (p1) und f (p2) die jeweiligen Tarifzustände. Wir benötigen einen Operator f um einen Vergleich der Form f (p1) f f (p2) anstellen zu können.

Dijkstra-artige Routing-Algorithmen basieren auf der sukzessiven Verlängerung lokal optimaler Teilpfade zu einem optimalen s, t -Pfad (Pfad von Start s zum Ziel t ). Damit dieser Ansatz funktioniert, muss der verwendete Vergleichsoperator für Pfade die Bedingung der Subpfad-Optimalität erfüllen. Vergleicht man z.B. die Fahrtzeit, so ist die bekannte Größer-gleich-Relation in den rationalen Zahlen.

Subpfad-Optimalität Sei p = (s = v0, . . . , vn = t ) ein optimaler s, t -Pfad in G. Dann ist jeder Teilpfad (s, . . . , vi ), i n ebenfalls optimal.

Zielfunktionen wie z.B. Fahrtzeit 2 oder Distanz erfüllen diese Bedingung.

Ein Tarifzustand f (p) besteht aus einem Ticket f t (p1) und einem Monoidzustand f h(p1). Die Vergleiche erfolgen dabei anhand der Ordnungsrelation h des Monoids und entlang von Pfaden im Ticketgraphen. D.h es gilt f (p1) f (p2) genau dann, wenn f h(p1) h f h(p2) und ein f t (p1), f t (p2)-Pfad in T existiert. Gilt weder f (p1) f (p2) noch f (p1) f (p2), so sind beide Pfade unvergleichbar. Die Unvergleichbarkeit von Pfaden führt dazu, dass nicht mehr ein einziger optimaler Pfad gefunden wird, sondern eine Menge von Pareto-optimalen, untereinander unvergleichbaren Pfaden.

In Sonderfällen müssen auch einige Pfade mit f (p1) f (p2) als unvergleichbar betrachtet werden, um algorithmischen Optimalität zu erhalten. Diese können durch unvorteilhafte Strukturen im Tarifsystem hervorgerufen werden. Insbesondere muss sichergestellt werden, dass f (p1) f (p2) Up(f (p1), a) Up(f (p2), a) für alle a A

gilt. In [10] erörtern die Autoren die mathematischen Details dieser Einschränkungen. Der Vergleichsoperator f erfüllt nun eine abgeschwächte Form der Subpfad-Optimalität.

Schwache Subpfad-Optimalität Sei p ein Pareto-optimaler s, t -Pfad in G. Dann existiert ein (evtl. von p1 verschiedener Pfad) Pareto-optimaler s, t -Pfad p11 = (s = v0, . . . , vn = t ), sodass jeder Teilpfad (v0, . . . , vi ), i n optimal ist.

Diese Eigenschaft ist zwar schwächer, ermöglicht es aber dennoch ausschließlich optimale Teilpfade zu untersuchen und dennoch die vollständige Pareto-Menge zu finden. Dies ermöglicht ein optimales preissensitives Routing unter Verwendung klassischer Routing-Algorithmen.

3 Zwei Beispiele in Deutschland

Im vorhergehenden Kapitel wurde das KTN-Modell theoretisch dargestellt. Wir werden nun die praktische Anwendbarkeit des Modells an zwei Tarifverbünden in Deutschland exemplarisch nachweisen.

3.1 Mitteldeutscher Verkehrsverbund (MDV)

Fachliche Beschreibung des Tarifsystems Der Tarif des Mitteldeutschen Verkehrsverbundes ist ein Zonentarif. Es gibt dabei sechs Preisstufen und einen Maximaltarif. Die Städte Halle und Leipzig bilden eigene Zonen mit vom Zonentarif abweichenden Kosten. Sobald mehr als eine Zone durchquert wird, werden sie jedoch nicht mehr unterschieden. Zusätzlich gibt es zwei Stadtverkehrstarife für kleinere Städte. Beim Verlassen der Stadt greift wieder der Zonentarif. Die Städte zählen dabei nicht als eigene Zonen, sondern werden den umliegenden Zonen zugeschlagen. Für verschiedene Tickets gelten verschiedene zeitliche Gültigkeiten. Wir gehen jedoch davon aus, dass die Zeit ausreicht um alle Routen dieses Preismodus tatsächlich zu fahren, d.h. dass Gültigkeiten nicht in die Preisberechnung mit einbezogen werden müssen. Eine Besonderheit sind neutrale Zonen. Je nach Verlauf der Route werden diese einer benachbarten Zone zugeschlagen. Außerdem gibt es in Leipzig und Halle Kurzstreckentarife, die von der Anzahl der Umstiege und der Anzahl der besuchten Haltestellen (max. vier) abhängen. Kurzstreckentarife in den Landkreisen berücksichtigen dagegen die zurückgelegte Distanz.

Bild 4: Ticketgraph für den MDV.

Modellierung als KTN Die meisten Fahrten werden von den Zonentickets Z1, . . ., Z6 erfasst. Die Stadttarife Halle und Leipzig werden durch die Tickets H und L dargestellt. Alle anderen Stadttarife werden in den Tickets T 1 und T 2 zusammengefasst. Alle Stationen in diesen Stadtzonen erhalten H, L, T1 oder T2 als Tarifsymbol. Alle anderen Stationen erhalten das Symbol Z . Sobald das Symbol Z gefunden wird, wird der Übergang in ein Zonenticket eingeleitet. Der Kurzstreckentarif teilt sich auf in die Tickets K , KH (Halle) und KL (Leipzig). In Abbildung 4 ist der komplette Ticketgraph dargestellt. Zusätzlich zum Ticket müssen an Pfaden im Routinggraphen die Tarifattribute überquerte Zonen hz , Haltestellenabstände hs, Entfernungskilometer hd und Umstiege ht mitgeführt werden. In den Städten Halle und Leipzig kann eine Kurzstrecke bis zu vier Haltestellen in Tram oder Bus umfassen, während in den Landkreisen eine Gesamtstreckenlänge von 4 km den Ausschlag gibt. Diese Einschränkungen werden von Bedingungen an die Tarifattribute hs und hd erfasst. Zusätzlich löst eine Verletzung der Bedingung ht < 1 den Übergang in ein normales Ticket aus. Es ist aus den Tarifdokumenten nicht ersichtlich, welche der Bedingungen greift, wenn eine (potentielle) Kurzstrecke Stationen in Halle/Leipzig und den Landkreisen umfasst. In der obigen Abbildung gehen wir davon aus, dass die Anzahl an Haltestellen das gültige Maß ist. Abhängig davon, welcher Knoten mittels einer Kurzstrecke erreicht wird, ist der Wechsel in einen anderen Kurzstreckentarif wie auch das Verlassen des Kurzstreckentarifes möglich.Wenn beim Erreichen eines Knotens im Routinggraphen mehr als sechs Zonen durchquert wurden, ist die Bedingung hz > 6 erfüllt und der Maximaltarif M greift. Eine Übersicht über die vorhandenen Tarifattribute ist in Tabelle 1 dargestellt.

Die Übergangsbedingungen zwischen den Tickets sind im Folgenden formalisiert. Der Bezeichner h = (hz , hs, hd , ht ) H fasst alle Monoidattribute zusammen.

Formel siehe PDF

3.2 Berlin/Brandenburg (VBB)

Das KTN des VBB ist deutlich komplizierter als das des MDV und umfasst 41 Tickets und 141 mögliche Tarifübergänge. Aufgrund dessen beschränkt sich diese Darstellung auf eine knappe Zusammenfassung des Preissystems und der verwendeten Tickets. Auf eine Auflistung aller Tarifbedingungen und Tarifsymbole wird verzichtet.

Fachliche Beschreibung des Tarifsystems Das Gebiet des Verbundes Berlin/Brandenburg ist in Waben unterteilt. Abhängig von der Anzahl durchquerter Waben wird eine Preisstufe ausgewählt. Ab fünf Waben zählen nicht mehr die Waben, sondern die Entfernung in Kilometern in einem Entfernungstarif mit elf Preisstufen. Zusätzlich sind die Tarifgebiete der Städte Cottbus, Brandenburg, Frankfurt, Potsdam und Berlin in von den Waben unabhängige Zonen A,B und C unterteilt. Es können für diese Städte entweder AB-, BC- oder ABC-Tickets erworben werden. Darüber hinaus gibt es für kleinere Städte drei verschiedene Stadtverkehrstarife. Es gibt mehrere Kurzstreckentarife, die in der Regel nur auf einzelne Verkehrsunternehmen oder -mittel bezogen sind. In Berlin können Kurzstrecken entweder nur im Bus, oder in S- und U-Bahn gefahren werden. Umstiege sind erlaubt, allerdings nur im jeweiligen Netz. Der Kurzstreckentarif des Unternehmens Havelbus Verkehrsgesellschaft mbH (HVG) hingegen erlaubt keine Umstiege und kein Einfahren in den Tarifbereich Potsdam AB. Der Kurzstreckentarif des Unternehmens Oberhavel Verkehrsgesellschaft mbH (OVG) erlaubt ebenfalls keine Umstiege. Das Kurzstreckenticket Potsdam ermöglicht Kurzstrecken im Tarifgebiet Potsdam ABC und teilweise auch in Berlin B (nur Potsdamer Verkehrsbetriebe (ViP)). Umstiege zwischen den Netzen der verschiedenen Betreiber (ViP, HVG und regiobus Potsdam) sind untersagt, Umstiege innerhalb dieser Netze allerdings erlaubt.

Modellierung als KTN Der Wabentarif wird durch die Tickets W2 (maximal zwei Waben), W3, W4, W5 und WM (Übergang in Entfernungstarif) modelliert. Der Entfernungstarif wird ebenfalls durch ein Ticket für jede Preisstufe dargestellt. In Abbildung 5 sind zur Vereinfachung der Darstellung all diese im Knoten E zusammengefasst. Die Preise der Stadtverkehre Frankfurt, Cottbus und Brandenburg sind identisch, deswegen können ihre ABC-Tarife von den gleichen Tickets repräsentiert werden. Die Tickets r A, r B,r C, r AB, r BC, r ABC dienen zur Beschreibung dieser Preise. Die Übergänge zwischen den Tickets hängen von den an den Stationen aufzusammelnden Tarifsymbolen A, B und C ab. Es ist zu beachten dass die Tickets r A, r B und r C keinem realen Ticket entsprechen, jedoch trotzdem notwendig sind. Dies liegt daran, dass bei Teilrouten, die nur durch eine Zone führen, noch nicht entschieden ist, ob sie im späteren Verlauf auch durch eine weitere führen (und ob also AB oder BC anzuwenden ist). Entsprechende Tickets werden auch für Berlin und Potsdam eingeführt. Hier gibt es jedoch die Besonderheit, dass Potsdam AB komplett in Berlin ABC liegt, der C-Bereich Potsdam aber Gebiete enthält, die nicht im C-Bereich Berlin enthalten sind. Um Tarifübergänge korrekt abbilden zu können, müssen deswegen im Modell die Tickets pA (Potsdam A), pB, pAB, pCmB (Potsdam C mit Berlin) und pCoB (Potsdam C ohne Berlin), pBCmB, pBCoB, pABCmB, pABCoB für Potsdam und bA, bB, bC, bAB, bBC, bABC für Berlin angelegt werden. Die A- und B-Zonen aller Städte stellen eigene Tarifwaben dar, ihre C-Bereiche zerfallen allerdings in verschiedene Waben. Teilweise ist es bei Routen im C-Bereich daher günstiger den Wabenpreis zu zahlen, anstatt ein BC-Ticket zu erwerben. Werden genügend Waben durchfahren, ist das BC-Ticket wieder günstiger. In C-Bereichen gültige Tickets müssen daher kodieren, dass die Route ausschließlich im C-Bereich stattfindet und welcher Preis anzuwenden ist. Neben den bisher genannten Tickets werden daher zusätzlich noch die Tickets pCoB2, pCmB2, r C2 bC2, bC3 und bC4 eingeführt. Diese erhalten den Preis von zwei, drei oder vier Waben, während den Tickets pCoB, pCmB, r C und bC die Preise eines BC-Tickets zugeordnet werden. Die Tickets T1, T2 und T4 markieren die verschiedenen Stadtverkehrstarife für Kleinstädte. Stationen in diesen Städten erhalten ein Tarifsymbol, dass die Zugehörigkeit zum Stadtverkehrstarif markiert. Da T1 und T2 teurer sind als ein Kurzstreckenticket, können diese nur in den Wabentarif übergehen. Das Ticket T4 hat einen geringeren Preis als die Kurzstreckentickets. Damit kann es auch auf Kurzstrecken eingesetzt werden und geht erst beim Verlassen der Stadtzone in ein Kurzstreckenticket über. Dementsprechend wird eine Übergangskante zu den Tickets KH und KO eingeführt.

Bild 5: Ticketgraph für den VBB.

Tabelle 2: Tarifattribute im KTN des MDV

Die Kurstreckentarife werden durch KP (Potsdam), KH (HVG im Havelland), KO (OVG), KSB (S- und U-Bahn in Berlin) und KBB (Bus in Berlin) dargestellt. Die Tarifübergänge der Kurzstreckentickets hängen davon ab, ob ein Umstieg vorliegt (Tarifattribut ht ), sowie von den Haltestellenabständen (hs) und ggfs. dem Verkehrsunternehmen des nächsten Transportmittels (bei erlaubten Umstieg). Um diese Bedingungen an das Verkehrsunternehmen abzubilden, wird ein Tarifsymbol für jedes Verkehrsunternehmen eingeführt. Umstiegskanten im Routinggraphen können dann mit diesen Symbolen annotiert werden. Zusätzlich zu den schon genannten Tarifattributen müssen für die Waben- und Entfernungstarife auch die Tarifattribute Entfernungskilometer hd und überquerte Waben hz betrachtet werden. Die Tarifattribute (ohne Tarifsymbole) sind in Tabelle 2 zusammengefasst.

4 Ausblick

Im Rahmen dieses Beitrags wurde ein mathematisches Modell zur exakten Abbildung der Tarife von Nahverkehrsverbünden vorgestellt. Auch kilometerbasierte Preise des Regionalverkehrs (z.B. innerhalb des VBB) lassen sich in dem Modell erfassen. Es ist damit gelungen ein konsistentes Modell zu formulieren, das preisoptimierte Routensuche im öffentlichen Nahverkehr ermöglicht. Um zu einer vollständig multimodalen und preisoptimierten Routensuche zu gelangen, wird in weiteren Veröffentlichungen zu untersuchen sein, wie die Kombination verschiedener Tarifprodukte unterschiedlicher, sich überlappender Tarifverbünde in das Modell integriert werden kann. Auch die Integration der Relationspreise des Fernverkehrs und der Systeme Sharing-Anbietern bleiben spannende Forschungsthemen.

Literatur

[1] H. Bast, D. Delling, A. V. Goldberg, M. Müller-Hannemann, T. Pajor, P. Sanders, D. Wagner, R. F. Werneck (2016). Route Planning in Transportation Networks. In Algorithm Engineering - Selected Results and Surveys, Volume 9220 in Lecture Notes in Computer Science, S. 19–80. Springer.

[2] P. Hansen (1980). Bicriterion Path Problems. Lecture Notes in Economics and Mathematical Systems, 177.

[3] D. Theune (1995). Robuste und effiziente Methoden zur Lösung von Wegproblemen. Vieweg+Teubner Verlag.

[4] D. Delling, T. Pajor, R. F. Werneck (2015). Round-Based Public Transit Routing. Transportation Science, 49(3):591–604.

[5] M. Müller-Hannemann, M. Schnee (2005). Paying less for train connections with MOTIS. In Proceedings of the 5th Workshop on Algorithmic Methods and Models for Optimization of Railways, Volume 2 in OpenAccess Series in Informatics, S. 657.

[6] C. Barrett, R. Jacob, M. Marathe (2000). Formal-Language-Constrained Path Problems. SIAM J. Comput., 30(3):809–837.

[7] U. Zimmermann (1981). Linear and combinatorial optimization in ordered algebraic structures, Volume 10 in Annaly of discrete mathematics. North-Holland.

[8] M. Mohri (2002). Semiring Frameworks and Algorithms for Shortest-distance Problems. J. Autom. Lang. Comb., 7(3):321–350.

[9] R. Borndörfer, R. Euler, M. Karbstein, F. Mett (2018). Ein mathematisches Modell zur Beschreibung von Preissystemen im öV. Technischer Report 18-47, ZIB, Takustr. 7, 14195 Berlin.

[10] R. Euler, R. Borndörfer (2019). A Graph- and Monoid-Based Framework for PriceSensitive Routing in Local Public Transportation Networks. In V. Cacchiani, A. Marchetti-Spaccamela, Hrsg., 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019), Volume 75 in OpenAccess Series in Informatics (OASIcs), S. 12:1–12:15, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.

[11] Y. Disser, M. Müller-Hannemann, M. Schnee (2008). Multi-criteria Shortest Paths in Time-dependent Train Networks. In C. C. McGeoch, Hrsg., Proceedings of the 7th International Conference on Experimental Algorithms, WEA’08, S. 347–361, Berl