3 Verbindungssuche mit Hilfe des Netzplanes
 
In den vorangegangenen Kapiteln wurde gezeigt, wie das fahrplanmäßige Angebot an Verbindungen und Teilverbindungen mit Hilfe von Netzplänen dargestellt werden kann. Da Netzpläne aber auch Graphen sind, können nun Standardalgorithmen darauf angewendet werden. Da das Ziel die Suche optimaler Verbindungen ist, liegt das Hauptaugenmerk auf der Suche kürzester Wege innerhalb des Netzplanes.

Wie bereits erwähnt, ist der Begriff kürzest hier sehr weit gefaßt. Es ist der Weg in einem bewerteten Graphen gesucht, der unter den gegebenen Voraussetzungen mit den geringsten Aufwendungen auskommt. In dieser Arbeit handelt es sich bei dem bewerteten Graph in den meisten Fällen um den fahrplanrepräsentierenden Netzplan. Generell stellt sich bei der Suche nach kürzesten Wegen die Frage, wie mit mehreren gleichwertigen kürzesten Wegen zu verfahren ist bzw. wie diese ermittelt werden. Dies ist aber ein allgemeines Problem der Wegesuche in Graphen und wird hier nicht behandelt.
Bei dieser Gelegenheit sei nochmals auf die einschlägige Literatur zur Graphentheorie verwiesen, z.B. TURAU (1996).

Dieses Kapitel befaßt sich nun mit den unterschiedlichen Möglichkeiten, den Begriff optimale Verbindung im Falle fahrplangebundener Verkehrsmittel zu interpretieren und auszulegen. Auch wenn dabei, wie auch bisher schon, von Bahnhöfen und Zügen die Rede ist, so gelten die Aussagen natürlich auch für andere fahrplangebundene Verkehrsmittel.

Allgemeine Anmerkungen

Auch in den Fällen, wo die Optimierung nicht anhand der aufzuwendenden Zeit erfolgen soll, spielen zeitliche Aspekte eine wichtige Rolle: In aller Regel sind Vorgaben hinsichtlich Abfahrts- und Ankunftszeit zu berücksichtigen.

Bei allen Optimierungsvarianten ist es denkbar, daß bestimmte Verbindungen und Teilverbindungen aufgrund einschränkender Vorgaben durch den Verbindungssuchenden nicht verfügbar sind. Bei der Verbindungssuche müssen diese daher unberücksichtigt bleiben (z.B. durch Ausblenden aus dem Netzplan). Beispiele für nicht verfügbare Teilverbindungen sind:

3.1 Zeitoptimale Verbindungen

Das naheliegendste Kriterium zur Verbindungssuche ist die aufzuwendende Zeit. Alleine oder in Verbindung mit anderen wird dieses Kriterium wohl auch am häufigsten zum Einsatz kommen.

3.1.1 Kürzeste Fahrzeit

Es soll die Verbindung gesucht werden, die eine möglichst kurze Fahrzeit ermöglicht. Zeiten am Abfahrts- und am Ankunftsbahnhof werden nicht berücksichtigt. Es gehen nur Wartezeiten auf den Zwischenbahnhöfen in die Gesamtbewertung der Verbindung mit ein. Da dadurch lediglich die schnellste überhaupt innerhalb des gültigen Fahrplans vorhandene Verbindung vom angegebenen Start- zum angegebenen Zielort gesucht wird, ist dieses Kriterium alleine nicht sehr sinnvoll.

3.1.2 Frühestmögliche Ankunftszeit Ausgehend von einer bestimmten frühestmöglichen Abfahrtszeit soll die Verbindung gesucht werden, die eine möglichst frühe Ankunft ermöglicht. Die Zeit von der frühestmöglichen bis zur tatsächlichen Abfahrtszeit geht in diesem Fall als Wartezeit am Abfahrtsort in die Gesamtbewertung der Verbindung mit ein. Diese Situation ergibt sich häufig bei der Rückfahrt am Ende einer Veranstaltung oder bei Anschlußfahrten (z.B. nach einem Flug).


Frühestmögliche Ankunftszeit

Die beiden dick gezeichneten Verbindungen sind im Hinblick auf die Forderung gleichwertig, obwohl die Fahrzeiten unterschiedlich sind. Sie bieten beide, ausgehend von einer Abfahrtszeit ab 10:00 Uhr, die frühestmögliche Ankunfszeit, nämlich 15:02 Uhr.

3.1.3 Kürzeste Fahrzeit innerhalb eines Abfahrtszeitbereiches

Durch Einschränken des zulässigen Abfahrtszeitbereiches kann die schnellste Verbindung unter all denjenigen Verbindungen gesucht werden, die innerhalb einer bestimmten Zeitspanne abfahren. Wartezeiten am Abfahrts- und am Ankunftsbahnhof werden für die Bewertung nicht berücksichtigt. Diese Situation ergibt sich beispielsweise bei einer Fahrt, die irgendwann am Vormittag beginnen und möglichst kurz dauern soll.


Schnellste Verbindung im Abfahrtszeitbereich

Der Bereich der zulässigen Abfahrten wurde hier nun auf 10:00 Uhr bis 12:00 Uhr festgelegt. Die schnellste Verbindung in diesem Bereich ist die der Züge D und E.

3.1.4 Ankunftsbezogene Verbindungssuche

Bisher lag die Betonung auf der frühestmöglichen Abfahrtszeit oder einem in Frage kommenden Abfahrtszeitbereich. Die Suche verläuft dabei vom Abfahrts- zum Ankunftsort. Natürlich kann aber genausogut eine spätestzulässige Ankunftszeit oder ein in Frage kommender Ankunftszeitbereich zugrundegelegt werden. Die genannten Sachverhalte kehren sich dann entsprechend um. So verläuft dann beispielsweise die Suche vom Ankunftsort rückwärts zum Abfahrtsort.

Spätestmögliche Abfahrtszeit

Ausgehend von einer bestimmten spätestzulässigen Ankunftsszeit soll die Verbindung gesucht werden, die eine möglichst späte Abfahrt ermöglicht. Die Zeit von der tatsächlichen bis zur spätestzulässigen Ankunftszeit geht in diesem Fall als Wartezeit am Ankunftsort in die Gesamtbewertung der Verbindung mit ein. Diese Situation ergibt sich häufig bei der Anfahrt zu einer Veranstaltung oder bei Zubringerfahrten.

Kürzeste Fahrzeit innerhalb eines Ankunftszeitbereiches

Durch Einschränken des zulässigen Ankunftszeitbereiches kann die kürzeste Verbindung unter all denjenigen Verbindungen gesucht werden, die innerhalb einer bestimmten Zeitspanne ankommen. Wartezeiten am Abfahrts- und am Ankunftsbahnhof werden für die Bewertung nicht berücksichtigt. Diese Situation ergibt sich beispielsweise bei einer Fahrt, die irgendwann am Nachmittag enden und möglichst kurz dauern soll.

3.2 Entfernungsoptimale Verbindungen

Es könnte die Verbindung gesucht werden, die mit der kürzesten Fahrtstrecke auskommt. Aufwendungen am Abfahrts- und am Ankunftsbahnhof sowie auf den Zwischenbahnhöfen fallen nicht an, da ja hier keine Strecken zurückgelegt werden (Fußwege bleiben unberücksichtigt). Da dadurch lediglich die kürzeste überhaupt innerhalb des gültigen Fahrplans vorhandene Verbindung vom angegebenen Start- zum angegebenen Zielort gesucht wird, ist dieses Kriterium alleine nicht sehr sinnvoll. Wie bei den bereits besprochenen zeitoptimalen Verbindungen sind folgende Varianten denkbar: Auch die Suche nach entfernungsoptimalen Verbindungen muß anhand des fahrplanabbildenden Netzplanes erfolgen, ein Graph, der nur das Verkehrsnetz darstellt, reicht nicht aus. Damit wäre es nur möglich, die kürzeste im baulich vorhandenen Netz denkbare Verbindung zu ermitteln. Ob aber eine solche Verbindung überhaupt oder im fraglichen Zeitraum von den Verkehrsträgern angeboten wird, ist wiederum nur aus dem Fahrplan und somit dem Netzplan ersichtlich.

Generell dürfte aber die Suche nach den entfernungsmäßig kürzesten Verbindungen für den Fahrgast kaum von Interesse sein, da sie für ihn keinen direkten Vorteil verspricht. Natürlich hat die zurückzulegende Entfernung Einfluß auf Fahrzeit und Kosten. Es ist aber aus Sicht des Fahrgastes sicherlich sinnvoller, die Verbindung direkt nach diesen Kriterien zu ermitteln.

3.3 Kostenoptimale Verbindungen

Es soll die billigste Verbindung gesucht werden. Aufwendungen am Abfahrts- und am Ankunftsbahnhof sowie auf den Zwischenbahnhöfen fallen nicht an (Kosten für einen Imbiß während der Wartezeit bleiben natürlich unberücksichtigt). Da dadurch lediglich die billigste überhaupt innerhalb des gültigen Fahrplans vorhandene Verbindung vom angegebenen Start- zum angegebenen Zielort gesucht wird, ist dieses Kriterium alleine nicht sehr sinnvoll. Folgende einschränkende Varianten sind denkbar: Die Suche nach kostenoptimalen Verbindungen muß natürlich auch anhand eines Netzplanes erfolgen, da auf ein- und derselben Strecke Verbindungen mit unterschiedlichen Tarifen existieren. Damit aber nicht genug: Selbst für eine bestimmte Verbindung existieren verschiedene Preismodelle. Je nach der konkreten Anwendbarkeit der einzelnen Tarife ergeben sich für unterschiedliche Gegebenheiten daher unterschiedliche Verbindungen. Aus dem fahrplanabbildenden Netzplan entsteht ein Netzplan für die Fahrtkosten:


Billigste Verbindung

Die Züge A und B bieten für Berechtigte des Tarifes T1 50% Ermäßigung, für die Züge C und D besteht diese Möglichkeit nicht. Zug B kommt am Umsteigebahnhof später an als Zug A und erreicht daher Zug C nicht mehr. Zug D kann sowohl für Zug A als auch für Zug B als Anschluß dienen. Die billgste Verbindung für einen Fahrgast ohne T1-Berechtigung besteht aus den Teilverbindungen der Züge B und D. Sie ist dick eingezeichnet. T1-Berechtigte würden am billigsten über A und C fahren.

Bisher wurde ein linearer Tarif angenommen. Oft können aber die Kosten für eine Verbindung, die aus mehreren Teilverbindungen besteht, nicht einfach durch Aufaddieren der Kosten dieser Teilverbindungen ermittelt werden. Meist sind entfernungsunabhängige Pauschalangebote die Ursache:


Pauschaltarif

Zusätzlich zu den beiden herkömmlichen Tarifen T1 und T2 steht für den gesamten betrachteten Personenkreis und den konkreten Zeitraum der Tarif T3 zur Verfügung, der für die gesamte aus A und B bestehende Verbindung gilt. Fahrgäste ohne T1-Berechtugung fahren damit am günstigsten mit den Zügen A und B. T1-Berechtigte hingegen benutzen besser die Züge A und C.

Auch von der Anzahl der Reisenden kann der Fahrpreis pro Person und damit die billigste Verbindung abhängen, etwa durch Gruppentarife.

Gruppentarif

Neben dem Normaltarif T2 steht für Gruppen bis zu fünf Personen zusätzlich der Tarif TG zur Verfügung, der aber in Zug A nicht gültig ist. Dieser Tarif darf auch mit weniger Personen genutzt werden, ist aber immer voll zu bezahlen. Ab drei Personen lohnt sich in diesem Fall unterwegs das Umsteigen in Zug B.

3.4 Umsteigeoptimale Verbindungen

Es soll die Verbindung gesucht werden, die mit den wenigsten Umsteigevorgängen auskommt. Da dadurch lediglich die umsteigeärmste überhaupt innerhalb des gültigen Fahrplans vorhandene Verbindung vom angegebenen Start- zum angegebenen Zielort gesucht wird, ist dieses Kriterium alleine nicht sehr sinnvoll. Wiederum sind einige Varianten denkbar: Natürlich muß auch die Suche nach umsteigeoptimalen Verbindungen anhand des fahrplanabbildenden Netzplanes erfolgen.
 

3.5 Hierarchische Suche

Als Erweiterung lassen sich mehrere der genannten Kriterien nacheinander anwenden. Die Menge der den Kriterien entsprechenden Verbindungen wird dadurch nach und nach reduziert.

3.5.1 Einige Beispiele

Kürzeste Fahrzeit bei frühestmöglicher Ankunftszeit

Eine Möglichkeit besteht darin, ausgehend von der frühestmöglichen Abfahrtszeit erst die Verbindung mit der frühestmöglichen Ankunftszeit zu suchen und im Falle mehrerer Treffer, also Verbindungen mit gleicher Ankunftszeit, die schnellste davon herauszusuchen.


Frühestmögliche Ankunftszeit, davon kürzeste Fahrzeit

Aus den beiden möglichen Varianten mit gleicher Ankunftszeit (15:02 Uhr) wurde nun die schnellere, also diejenige mit der bei der gegebenen Ankunftszeit spätestmöglichen Abfahrtszeit, herausgesucht.

Kürzeste Fahrzeit bei spätestmöglicher Abfahrtszeit

Als Umkehrung des vorigen Beispiels gibt es folgende Möglichkeit: Ausgehend von der spätestzulässigen Ankunftszeit wird erst die Verbindung mit der spätestmöglichen Abfahrtszeit gesucht und im Falle mehrerer Treffer, also Verbindungen mit gleicher Abfahrtszeit, die schnellste davon herausgesucht.

Billigste Verbindung bei frühestmöglicher Ankunftszeit

Eine weitere denkbare Kombination sieht so aus: Ausgehend von der frühestmöglichen Abfahrtszeit wird erst die Verbindung mit der frühestmöglichen Ankunftszeit gesucht und im Falle mehrerer Treffer, also Verbindungen mit gleicher Ankunftszeit, die billigste davon herausgesucht.


Frühestmögliche Ankunftszeit, davon billigste Verbindung

Aus den beiden möglichen Varianten mit gleicher Ankunftszeit (15:02 Uhr) wurde nun die billigere herausgesucht.

3.5.2 Problem der hierarchischen Suche

Bei der geschilderten Vorgehensweise ist zu beachten, daß eben eine streng hierarchische Auswahl stattfindet: Im ersten Schritt wird nur das wichtigste Kriterium beachtet, im zweiten Schritt das zweitwichtigste und so fort. Dabei kann es naturgemäß passieren, daß wesentliche Sachverhalte nicht entsprechend gewürdigt werden. Wenn beispielsweise unter den schnellsten Verbindungen die billgste gesucht wird, so wird eine noch so billige Verbindung nicht gefunden, wenn sie auch nur eine Minute mehr benötigt als die schnellste Verbindung.