Entwicklung einer Fahrplanauskunft

[evilboy]

Gesetzt den Fall, ich habe ein Busunternehmen mit vier Linien, die sich teilweise überschneiden.

Und jetzt möchte ich das gerne in ein Programm überführen, das dann
1) einen Reiseplan aufstellt (Von A nach Z: Fahren Sie mit Linie 1 von A nach C, mit Linie 4 von C nach E und mit Linie 2 von E nach Z – Fahrpläne mit konkreten Uhrzeiten lassen wir mal außen vor) und
2) eine ungefähre Angabe in Kilometern und Minuten Fahrzeit zwischen den Stationen (die ich natürlich hinterlegen muss) anzeigt.

Eine ungefähre Vorstellung, wie man das aufstellen müsste, habe ich (welche Linien gibt es am Startort und welche am Zielort, wo überschneiden sie sich – aber wie löst man das bei mehreren Linien?; Hinterlegung der Fahrzeit in min und km zwischen jeweils zwei Stationen).

Aber so wirklich sicher bin ich mir da nicht. Ich erwarte jetzt nicht, dass mir jemand eine Lösung herzaubert. Aber hat jemand ein Stichwort oder einen Literaturhinweis zur Hand, so dass ich mich in die Thematik einarbeiten kann?
Das klassische Travelling-Salesman-Problem ist es ja nicht, da es nicht zwischen allen Orten Direktverbindungen gibt……

[MichaG42]

Hallo evilboy,

Nettes Problem. ;-)
Ich weiß jetzt nicht, ob das relevant ist, könnte aber sein. Wie stellt sich denn das "sich überschneiden" dar? Handelt es sich dabei um zentrale Umsteigeknoten (sternförmig: komme von A(Linie 1 außerhalb) fahre nach B(Knoten) - Fahre nach C(Linie 2 - Knoten) - Fahre nach D(Linie 3 - außerhalb) oder stellt es sich eher wie ein Netz dar, mit zahlreichen Möglichkeiten zwischen den Linien ?

Danke, lg Micha

[jfheins]

Also wenn du konkrete Fahrpläe außen vor lässt, ist das relativ einfach: Das Netz lässt sich als Graph auffassen. Ein Knoten sit dann eine Haltestelle, und eine Kante ist eine Transportmöglichkeit (Verbindung) zwischen zwei Haltestellen.

Eine Buslinie würdest du dann erstmal aufteilen, welche Haltestellen mit welchen Kosten verbunden werden. Die Kanten kannst du dann in den Graphen einsortieren.

"Kosten" ist hier übrigens ein etablierter Begriff, meistens haben die Kanten definierte Kosten und es wird dann der günstigste Weg gesucht. Dafür eignet dich der Dijkstra-Algorithmus. Er bekommt zwei Knoten und rechnet dir dann den kürzesten Pfad (= geringste Kosten) aus.

Was zum Lesen gibt es hier: http://de.wikipedia.org/wiki/Graph_(Graphentheorie) bzw. hier: http://de.wikipedia.org/wiki/Dijkstra-Algorithmus oder einfach hier nachfragen ;-)

[Namenloser]

Das, was jfheins gesagt hat, und vielleicht hilft es, wenn du dir bewusst machst, dass Zeit auch eine Dimension ist. Das heißt, eigentlich suchst du eine Route durch eine dreidimensionale (wenn deine Karte zweidimensional ist, wovon ich ausgehe) Punktwolke (die sich als Graph darstellen lässt).

[BUG]

Zitat:

Zitat von NamenLozer (Beitrag 1223414)

Das, was jfheins gesagt hat, und vielleicht hilft es, wenn du dir bewusst machst, dass Zeit auch eine Dimension ist. Das heißt, eigentlich suchst du eine Route durch eine dreidimensionale (wenn deine Karte zweidimensional ist, wovon ich ausgehe) Punktwolke (die sich als Graph darstellen lässt).

Das Ganze kann man vereinfachen. Die Position der Haltestellen ist eigentlich egal, nur die Zeit (und evtl. der Preis) zwischen den Stationen ist interessant.
Die Zeit würde ich auch als Kopien der Haltestellen modellieren.

Für jeden (diskreten) Zeitpunkt, z.B. in Minutenauflösung, gibt es eine Kopie von jeder Haltestelle. Jede Haltestelle hat eine Kante zu ihrer Kopie im nächsten Zeitschritt (eine Zeiteinheit als Kosten).
Außerdem besitzt sie Kanten zu den nächsten Haltestellen in den Linien zu der jeweils geplanten Ankunftszeit. Die Kanten-Kosten sind die Fahrzeiten.
Um den schnellsten Weg zu finden lassen sich dann klassische Algorithmen anwenden (z.B. Dijstra).

Das sollte eine geeignete Basis für weitere Verbesserungen sein, z.B. Duplizierung aller Haltestellenknoten als Ankunfts- und Abreiseknoten, um Unsteigezeiten zu berücksichtigen.

Auch wenn die oben definierte Graphen theoretisch unendlich sind (angenommen die Zeit endet nicht), kann man praktisch annehmen, das niemand mehr als drei Tage auf einer Strecke fährt und damit die Anzahl der Knoten auf gut handhabbare Größen begrenzen :mrgreen:

[Furtbichler]

Nee, das ist ein Minimierungsproblem (shortest Path). Nur das der Graph nicht nur Entfernungen/Preise enthält (und damit Fahrzeiten), sondern auch Wartezeiten.

Ein Weg von A nach B über C mit Umsteigen wird im Graph dann einfach so modelliert.

A=>C1 (Fahrzeit: 5 min)
C1=>C2(Wartezeit: 3 min)
C2=>B (FAhrzeit: 3 min)

vielleicht gibt es auch eine direkte Strecke (A=>B). Die dauert aber, wegen Bauarbeiten, 15min.
A=>B (Fahrzeit: 15min)

Nun kann jeder single-pair shortest-path Algorithmus die optimale Lösung finden. Etwas modifizieren muss man den Algorithmus aber schon, denn die Wartezeit am Punkt 'C' (Übergang C1=>C2) ist nicht notwendigerweise konstant 3 minuten, sondern kann variieren. Vielleicht ist der Anschluss bei Ankunft 15:19 wirklich nur 3 minuten, weil der andere Bus um 15:22 kommt, aber wenn man um 14:19 kommt, dann muss man leider 20min warten, denn der andere Bus kommt leider erst um 14:39.

D.h. die Kostenfunktion 'Zeit(P1,P2)' ist nicht durch eine einfache Matrix dargestellt, sondern berücksichtigt andere Parameter. Mit fällt auf Anhieb ein, das man einfach die Ankunftzeit an C1 als weiteren Parameter nimmt.


Ergo benötigt der Optimierungsalgorithmus ("Finde kürzesten Weg von A->B") neben dem Start- und Endpunkt auch den Zeitpunkt der gewünschten Abfahrt. Sollte sehr einfach umzusetzen sein.

[Namenloser]

Zitat:

Zitat von BUG (Beitrag 1223423)

Zitat:

Zitat von NamenLozer (Beitrag 1223414)

Das, was jfheins gesagt hat, und vielleicht hilft es, wenn du dir bewusst machst, dass Zeit auch eine Dimension ist. Das heißt, eigentlich suchst du eine Route durch eine dreidimensionale (wenn deine Karte zweidimensional ist, wovon ich ausgehe) Punktwolke (die sich als Graph darstellen lässt).

Das Ganze kann man vereinfachen. Die Position der Haltestellen ist eigentlich egal, nur die Zeit (und evtl. der Preis) zwischen den Stationen ist interessant.

Ja, das ist schon richtig, am Ende hat man natürlich einfach einen Graphen mit Kantengewichten. Ich persönlich finde es bloß anschaulicher, wenn man sich vorstellt, dass man kürzeste Wege auf einer zweidimensionalen Karte berechnet und die Kosten zwischen zwei Knoten der geometrischen Distanz entsprechen. In der Praxis muss natürlich der geometrisch kürzeste Weg nicht der schnellste sein, da man z.B. auf der Autobahn schneller fahren kann als auf irgendeiner Landstraße, aber ich finde, wenn man das Prinzip erst mal verstanden hat, kann man es sehr leicht verallgemeinern...

Edit:

Zitat:

Zitat von BUG (Beitrag 1223423)

Auch wenn die oben definierte Graphen theoretisch unendlich sind (angenommen die Zeit endet nicht), kann man praktisch annehmen, das niemand mehr als drei Tage auf einer Strecke fährt und damit die Anzahl der Knoten auf gut handhabbare Größen begrenzen :mrgreen:

Das ist eigentlich gar nicht nötig, es reicht ja, wenn die Knoten „virtuell“ vorhanden sind. Dijkstra guckt sich ja immer nur die unmittelbar adjazenten Knoten an. Man kann diese also generieren, während man den Algorithmus ausführt...

Man muss nur aufpassen, dass es zwischen dem Start- und dem Ziel-Knoten auch wirklich eine Verbindung gibt... sonst würde man in eine Endlosschleife laufen.

[Furtbichler]

Zitat:

Zitat von NamenLozer (Beitrag 1223440)

Man muss nur aufpassen, dass es zwischen dem Start- und dem Ziel-Knoten auch wirklich eine Verbindung gibt... sonst würde man in eine Endlosschleife laufen.

Nö. Dann gibt es einfach keine Lösung.

Bei der Graphentraversierung markiert man die besuchten Knoten, dann passiert das nicht.

[Namenloser]

Zitat:

Zitat von Furtbichler (Beitrag 1223443)

Zitat:

Zitat von NamenLozer (Beitrag 1223440)

Man muss nur aufpassen, dass es zwischen dem Start- und dem Ziel-Knoten auch wirklich eine Verbindung gibt... sonst würde man in eine Endlosschleife laufen.

Nö. Dann gibt es einfach keine Lösung.

Man will aber trotzdem nicht, dass das ganze System abschmiert, bloß weil der User eine Route berechnen will, die nicht existiert.

Zitat:

Zitat von Furtbichler (Beitrag 1223443)

Bei der Graphentraversierung markiert man die besuchten Knoten, dann passiert das nicht.

Hier ist der Graph aber unendlich und man findet (in zeitlicher Dimension) an jedem Knoten einen weiteren Knoten, der nicht zum Ziel führt.

Jedes Stehen eines Busses an einer Haltestelle ist eigentlich ein Knoten. Man kann sich dann an jedem Knoten jeweils dafür entscheiden, ob man mit dem Bus zur nächsten Haltestelle (1. adjazenter Knoten) fährt, oder ob man auf den nächsten Bus wartet (2. adjazenter Knoten). Nun kann man aber beliebig lange an der Haltestelle stehen und darauf warten, dass ein Bus kommt, der einen in Richtung des Ziels bringt. Wenn ein solcher aber niemals kommt, dann sitzt man bei einer naiven Implementierung in einer Endlosschleife...

[BUG]

Zitat:

Zitat von NamenLozer (Beitrag 1223440)

Man muss nur aufpassen, dass es zwischen dem Start- und dem Ziel-Knoten auch wirklich eine Verbindung gibt... sonst würde man in eine Endlosschleife laufen.

Stimmt, das könnte man vorher einfach prüfen (oder evtl. sogar vor berechnet haben).
Wenn man eventuell über den Basis-Dijstra hinaus will, wäre es schon schön, wenn der Graph endlich ist :mrgreen: Aber für so kleine Probleme sollte wohl nicht nötig sein.

Ich glaube, alles Prinzipielle zu in dieser Modellierung wurde mittlerweile genannt und wir fangen jetzt an, uns im Kreis zu drehen und über Details/Optimierungen zu streiten :wink:
@evilboy: Hast du den Ansatz verstanden oder hast du Fragen?

EDIT:

Zitat:

Zitat von evilboy (Beitrag 1223400)

Fahrpläne mit konkreten Uhrzeiten lassen wir mal außen vor

Der Fall ist einfacher zu modellieren, bringt dem Fahrgast aber nicht wirklich viel, wenn der er zwar die kürzeste Fahrzeit hat, aber zwischen-drin einen halben Tag warten muss :mrgreen:

[evilboy]

Zitat:

Zitat von BUG (Beitrag 1223450)

Ich glaube, alles Prinzipielle zu in dieser Modellierung wurde mittlerweile genannt und wir fangen jetzt an, uns im Kreis zu drehen und über Details/Optimierungen zu streiten :wink:
@evilboy: Hast du den Ansatz verstanden oder hast du Fragen?

Ja, erst mal vielen Dank an alle für die hilfreichen Infos!
Ich mach mich jetzt mal dran, das Liniennetz umzusetzen :) Und ja, es gibt keine isolierten Linien, so dass man von jeder Haltestelle zu jeder Haltestelle kommt und das Problem schon mal nicht auftritt…

Zitat:

Zitat von BUG (Beitrag 1223450)

EDIT:

Zitat:

Zitat von evilboy (Beitrag 1223400)

Fahrpläne mit konkreten Uhrzeiten lassen wir mal außen vor

Der Fall ist einfacher zu modellieren, bringt dem Fahrgast aber nicht wirklich viel, wenn der er zwar die kürzeste Fahrzeit hat, aber zwischen-drin einen halben Tag warten muss :mrgreen:

Klar, das Ganze sollte erst mal nur ein Anschauungsmodell werden :)
Es gibt Apps wie Tube 2 für Windows Mobile (ja, das alte Windows Mobile), die genau so funktioniert haben und mangels echtem Fahrplan immer einen Pauschalwert für Umstiege (5-10 Minuten) veranschlagt haben…

[Furtbichler]

Zitat:

Zitat von NamenLozer (Beitrag 1223445)

Hier ist der Graph aber unendlich und man findet (in zeitlicher Dimension) an jedem Knoten einen weiteren Knoten, der nicht zum Ziel führt.

Hmmm..... Nein.

Der Graph enthält alle Bus/Bahnlinien. Die Kosten einer Fahrt sind je Kante konstant (wenn man Baustellen, Staus etc. mal ignoriert). Die Wartezeiten an den Knoten beim Umsteigen sind abhängig von der Ankunftszeit, die jedoch beim Traversieren des Knotens bekannt ist, denn man sucht ja immer den kürzesten Weg bei Abfahrt zu einem bestimmten Zeitpunkt.

Wenn mann also z.B. am Zentralbahnhof umsteigen will, dann gibt es immer genau eine nächste Verbindung zu einem Ort X (ICE und Bummelzug sind zwei unterschiedliche Verbindungen!). Die übernächste ist irrelevant, denn dann ist man garantiert länger unterwegs. Deswegen kann man (zumindest bei der Bahn) auch angeben, wie lange man mindestens am Umsteigebahnhof warten will. Denn dann wird ggf. nicht die nächste Verbindung genommen, sondern die Übernächste.

Der Graph also endlich, aber die Kantengewichtung unvollständig und wird erst während des Suchvorganges dynamisch ermittelt. Eine Fahrtzeit kann zum Zeitpunkt X 10 Minuten sein, aber zum Zeitpunkt Y (Berufsverkehr) auch 50 Minuten. Die Wartezeit kann mal 5, mal 10 Minuten sein (gleiches Ziel). Das ist aber kein Showstopper.

Zitat:

Zitat von evilboy (Beitrag 1223451)

Fahrpläne mit konkreten Uhrzeiten lassen wir mal außen vor

Würde ich nicht machen, denn deine Lösung ist dann eine ganz andere.

Implementiere einen Optimierungsalgorithmus deiner Wahl (Djikstra wurde bereits genannt) und modelliere dabei Haltestellen und Umsteigeaktionen als einzelne Knoten. Die Verbindungen zwischen den Knoten sind Fahrt- bzw. Umsteigezeiten. Für beides schreibst Du jeweils eine Funktion

Delphi-Quellcode:

Function FahrtZeit (Von, Bis : TKnoten, Ankunftszeit : TDateTime) : Integer;
Function WarteZeit (Von, Bis : TKnoten, Ankunftszeit : TDateTime) : Integer;

[BUG]

Zitat:

Zitat von Furtbichler (Beitrag 1223463)

Der Graph also endlich, aber die Kantengewichtung unvollständig und wird erst während des Suchvorganges dynamisch ermittelt. Eine Fahrtzeit kann zum Zeitpunkt X 10 Minuten sein, aber zum Zeitpunkt Y (Berufsverkehr) auch 50 Minuten. Die Wartezeit kann mal 5, mal 10 Minuten sein (gleiches Ziel).

Jetzt habe ich es verstanden, schöne Idee :thumb:
Man müsste nochmal genau am Algorithmus nachvollziehen, ob es da keine Probleme gibt. Da die Gesamtfahrzeit nie größer werden kann, wenn man früher als über einen anderen Weg zu einem Knoten kommt, könnte es mit Dijkstra klappen. Das passt ja ziemlich gut zu den Invarianten.

[Namenloser]

Zitat:

Zitat von Furtbichler (Beitrag 1223463)

Wenn mann also z.B. am Zentralbahnhof umsteigen will, dann gibt es immer genau eine nächste Verbindung zu einem Ort X (ICE und Bummelzug sind zwei unterschiedliche Verbindungen!). Die übernächste ist irrelevant, denn dann ist man garantiert länger unterwegs.

Hmm, aber es könnte doch sein, dass zuerst ein Zug kommt, der zwar in die richtige Richtung fährt, aber zwischendurch an zig Haltestellen hält („Bummelzug“), und 10 Minuten später eine wesentlich schnellere Direktverbindung kommt, mit der man schneller ankommt, obwohl man vorher länger gewartet hat. Hab jetzt nicht ganz verstanden, wie das bei dir berücksichtigt wird...

Vielleicht wolltest du darauf hinaus, dass man nur so lange wartet, bis man alle Linien, die überhaupt über die aktuellen Haltestelle fahren, einmal durch hat? Das wäre dann im Falle von Zug- oder Busverbindungen auch mein Ansatz gewesen, um das Problem zu lösen. Aber da ich nicht wusste, ob es evilboy wirklich um Zug-/Busfahrpläne geht oder ob er das Szenario nur zur Veranschaulichung gewählt hat, wollte ich es erst mal möglichst allgemein lassen. Hätte ja z.B. sei können, dass der „Fahrplan“ nicht konstant ist...

Er wollte ja auch nur einen Denkanstoß; mir fallen zu Zug-/Bahnrouten noch einige andere Details ein... z.B. sollte jede Haltestelle nur einmal in einer Route vorkommen, weil es sonst sein könnte, dass eine Route ausgegeben wird, bei der man irgendwo einmal im Kreis fährt, weil das genau so lange dauert, wie wenn man an der Haltestelle gewartet hätte...

Wie BUG schon schrieb:

Zitat:

Zitat von BUG (Beitrag 1223450)

Ich glaube, alles Prinzipielle zu in dieser Modellierung wurde mittlerweile genannt und wir fangen jetzt an, uns im Kreis zu drehen und über Details/Optimierungen zu streiten :wink:

[Furtbichler]

Zitat:

Zitat von NamenLozer (Beitrag 1223577)

Hmm, aber es könnte doch sein, dass zuerst ein Zug kommt, der zwar in die richtige Richtung fährt, aber zwischendurch an zig Haltestellen hält („Bummelzug“),

Das ist eine Verbindung. Der gleiche Bummelzug später wird ignoriert. Ein anderer Zug in die gleiche Richtung ist eine andere Verbindung => berücksichtigen.

Zitat:

sollte jede Haltestelle nur einmal in einer Route vorkommen, weil es sonst sein könnte, dass eine Route ausgegeben wird, bei der man irgendwo einmal im Kreis fährt, weil das genau so lange dauert, wie wenn man an der Haltestelle gewartet hätte...

Dafür sind die Algorithmen gedacht. Die sorgen schon dafür, dass das nicht passiert. Die besuchten Knoten werden nicht noch einmal besucht.

Ausnahme: Eine Kantengewichtung ist negativ, wenn man z.B. mit einem Warp-Antrieb fährt, vergeht die Zeit rückwärts. Dann würde der Djikstra-Algorithmus passen. Wenn man also Busse hat, die ankommen, bevor sie abgefahren sind, muss man den Bellman-Ford Algorithmus verwenden. ;-)

Du hast noch nicht verstanden, wie diese shortest-path Algorithmen funktionieren.

Aber wenn 'Die Bahn' so einen Algorithmus umgesetzt hat, *kann* es nicht schwer sein.

[Namenloser]

Zitat:

Zitat von Furtbichler (Beitrag 1223589)

Zitat:

sollte jede Haltestelle nur einmal in einer Route vorkommen, weil es sonst sein könnte, dass eine Route ausgegeben wird, bei der man irgendwo einmal im Kreis fährt, weil das genau so lange dauert, wie wenn man an der Haltestelle gewartet hätte...

Dafür sind die Algorithmen gedacht. Die sorgen schon dafür, dass das nicht passiert. Die besuchten Knoten werden nicht noch einmal besucht.

Ich weiß schon wie der Dijkstra-Algorithmus funktioniert, ich habe vor einer Woche noch eine Klausur unter anderem darüber (und über Bellman-Ford auch) geschrieben. ;)

Nur ist Haltestelle hier ja nicht das gleiche wie Knoten. Zu jeder Haltestelle gibt es mehrere Knoten wegen der Zeit-Dimension...

[Furtbichler]

Zitat:

Zitat von NamenLozer (Beitrag 1223594)

Ich weiß schon wie der Dijkstra-Algorithmus funktioniert, ich habe vor einer Woche noch eine Klausur unter anderem darüber (und über Bellman-Ford auch) geschrieben. ;)

Dann weißt Du ja mehr als ich :oops:

Zitat:

Nur ist Haltestelle hier ja nicht das gleiche wie Knoten. Zu jeder Haltestelle gibt es mehrere Knoten wegen der Zeit-Dimension...

Nein. Lies meinen Ansatz genau. Eine Fahrt von A->B dauert 5 Minuten, Umsteigen bei B dauert 10 Minuten. Ergo ist fahren und umsteigen ein und dasselbe: Ein Übergang von A nach B, der X Minuten dauert.

Also:
Fahrplan:
Bus 1 fährt von A-10->B-20->C
Bus 2 fährt von B-10->C

Wenn A an B ankommt, fährt #2 3 minuten später ab.
Ich führe einen neuen Knoten ein (B1)
Bus 2 fährt dann nicht von B ab, sondern von B1 -> C (10 Minuten)
Eine neue Kante: Umsteigen von B->B1 (3 minuten).

Also hast Du wieder einen simplen gerichteten Graphen. Nix mit Dimension. Nur eben die Funktion, die die Fahrt/Wartezeit von A nach B ausrechnet, benötigt die Ankunftszeit bei 'A'.

Bei uns wäre das also:
Abfahrt bei A um 15:10 nach B.
Ankunft bei B um 15:20

Bus #2 fährt um 15:23 ab
also bekommt die Kante B->B1 den Wert 3 (Minuten)

Wenn wir bei A um 15:00 losfahren würden, kämen wir bei B um 15:10 an.
Dann bekommt die Kante B->B1 den Wert 13 (Minuten)

verstanden?

[Namenloser]

Dein Algorithmus ist im Prinzip derselbe wie meiner, nur du hast es etwas anders dargestellt als ich. Was du machst, ist halt kein reiner Dijkstra-Algorithmus, weil bei Dijkstra die Kantengewichte fest sind. Was du also eigentlich machst, wenn du das Gewicht einer Kante „dynamisch berechnest“, ist, dass du einen neuen Knoten im Graphen erzeugst (der vorher nie berührt wurde, deshalb hätte er auch genau so gut schon immer da sein können. Man könnte auch sagen, du „entdeckst“ den Knoten), der über eine Kante mit genau diesem Gewicht mit dem aktuellen Knoten verbunden ist. Wenn du also bei dir „einen“ Knoten markierst, markierst du in Wirklichkeit eine ganze Knotenmenge... Das ist dann das gleiche, wie wenn ich sage „Man muss sicherstellen, dass eine bestimmte Haltestelle nur einmal angefahren wird“.

[Furtbichler]

Also ich kann den Djikstra-Algorithmus nehmen (glaube ich zumindest). Ausgehend vom Startknoten weiß ich genau, wie lange ich zur nächsten Station oder zum nächsten Umsteigen brauche. Diese Kanten sind also fest und werden nicht mehr verändert.

Interessantes Problem, jedenfalls.

[Namenloser]

Zitat:

Zitat von Furtbichler (Beitrag 1223601)

Diese Kanten sind also fest und werden nicht mehr verändert.

Aber deine Wartezeiten hängen ja von der Uhrzeit ab und damit von deinem zurückgelegten Pfad. Die Kantengewichte in einem Graphen sind aber unabhängig vom Pfad.

Der Graph, den du dir mit deinem Dijkstra anschaust, ist eigentlich ein Teilgraph. Das funktioniert mit Dijkstra, aber z.B. mit Bellman-Ford würde es nicht funktionieren, weil dort alle Knoten/Kanten bekannt sein müssen. Zugegeben, bei mir wäre es ohne einen Quantencomputer allerdings auch ein bisschen schwierig, weil es ja unendlich Knoten gibt, aber man könnte den Graphen ja zumindest zeitlich beschränken, wie von BUG zuerst vorgeschlagen. Dann kann man sogar mit zeitreisenden Bussen umgehen ;)

Edit: Jetzt krieg ich fast schon Lust, das zu implementieren, die Idee von einem Zeitreisen-Busunternehmen hat irgendwie was :)

[Der schöne Günther]

Also in der Praxis scheint die Not da auch erfinderisch zu machen. Mein Nahverkehrsunternehmen hat keine Hemmungen mich mit der Bahn von 2 bis 5 Uhr im Kreis fahren zu lassen bis endlich morgens wieder der erste Bus in das Zieldorf fährt.

Graphentheorie war nie mein Fall, mich würde vor allem die tatsächliche Kostenfunktion am Schluss interessieren: Wahrscheinlichkeit von Verspätungen, Wartezeit, Zeit zum Umsteigen...

[Nintendo]

Hmmm,

ich habe grad so mitgelesen hier und da stößt mir ein Problem auf. Es soll also hier die kürzeste Verbindung zwischen zwei Punkten gesucht werden, weil diese die geringsten Kosten verursacht.

Für den Fahrgast stimmt das ja auch. Wenn ich von Dresden nach Hamburg will, hätte ich am liebsten einen Zug, der in Dresden startet und erst in Hamburg wieder hält. Aber diese Rechnung ist ohne die DB gemacht. Diese will auf dieser Strecke außer mir noch andere Fahrgäste befördern und da ist die Strecke mit den geringsten Kosten diejenige, auf der die meisten Fahrgäste einsteigen. Möglicherweise ist für die DB ein Regionalzug deshalb billiger, weil der an jedem Bahnhof hält und so zumindest potentiell viel mehr Fahrgäste einsteigen, als in einen ICE, der nur an den größeren Bahnhöfen hält.

Zur Vereinfachung lasse ich mal die wirklichen Gegebenheiten an den kleineren Bahnhöfen aussen vor, da es da sein kann, das keiner in oder aussteigt, aber im Wochenmittel eben doch einige ein und aussteigen.

So gibt es auf jeden Fall zwei Sichtweisen:

- Fahrgast will auf dem schnellsten Weg ans Ziel kommen.
- Busunternehmen möchte auf der Strecke möglichst viele Fahrgäste kostenpflichtig befördern und muss deshalb eine Strecke wählen, auf der viele einsteigen. Das ist nicht zwingend die kürzeste Strecke zwischen A und B.


.

[Furtbichler]

Zitat:

Zitat von Der schöne Günther (Beitrag 1223607)

Mein Nahverkehrsunternehmen hat keine Hemmungen mich mit der Bahn von 2 bis 5 Uhr im Kreis fahren zu lassen bis endlich morgens wieder der erste Bus in das Zieldorf fährt.

Das ist der Unterschied zwischen Graphen-Theorie und Praxis.

[jobo]

Zitat:

Zitat von Nintendo (Beitrag 1223610)

So gibt es auf jeden Fall zwei Sichtweisen:
- Fahrgast will auf dem schnellsten Weg ans Ziel kommen.
- Busunternehmen möchte auf der Strecke möglichst viele Fahrgäste kostenpflichtig befördern und muss deshalb eine Strecke wählen, auf der viele einsteigen. Das ist nicht zwingend die kürzeste Strecke zwischen A und B.
.

Die neue Sichtweise entspricht aber wohl nicht der Anforderung des TE. Dieser Anwendungsfall kommt ggF. bei der Planung einer neuen Verkehrsverbindung ins Spiel (Geschieht vermutlich alle 20 Jahre einmal- Abschaffung von Linien ist dagegen relativ einfach).
Hier gäbe es die spannende Aufgabe herauszufinden, wo die Leute mit Bus/Bahn hinfahren würden, wenn sie denn könnten, also Feldforschung oder Auswertung der Verkehrsüberwachungsdaten und Mautsysteme.
Oder man fragt Prof.Dr.Dudenhöffer, der weiß das ja alles.

[jobo]

Zitat:

Zitat von Der schöne Günther (Beitrag 1223607)

Mein Nahverkehrsunternehmen hat keine Hemmungen mich mit der Bahn von 2 bis 5 Uhr im Kreis fahren zu lassen bis endlich morgens wieder der erste Bus in das Zieldorf fährt.

3h im Kreis entspricht nach gängiger Praxis minimal ca 10 km Fußweg, es ist also anzunehmen, dass Du etwas außerhalb wohnst, sonst müsste das System ja Fußweg vorschlagen. :)

[Furtbichler]

Zitat:

Zitat von jobo (Beitrag 1223626)

3h im Kreis entspricht nach gängiger Praxis minimal ca 10 km Fußweg

Ein ICE fährt 300km/h, also währen das 900km Kreisumfang, oder ein Kreis mit dem Durchmesser von 286km. Da wir jedoch nicht wissen, wo der schöne Günther wohnt (obwohl sich das durch Recherche "Kreischender Frauenmob" durchaus herausfinden ließe), ist es müßig, darüber nachzudenken, ob er, anstatt im Kreis zu fahren, nicht doch einfach nach Hause hätte laufen können. Vielleicht macht es Spaß, 3 Stunden im ICE zu sitzen und sich zu überlegen, warum man das eigentlich mit sich machen lässt.

Mir fällt dabei ein Bekannter ein, der -als er noch als DJ arbeitete- morgens nach Hause wollte, nur um im Bus einzuschlafen und vom Busfahrer an der Endhaltestelle geweckt zu werden. Er fuhr also zurück, nur um wieder einzuschlafen und dann an der anderen Endhaltestelle wieder geweckt zu werden. Ein lustiges Schauspiel, das sich 5x wiederholte. Jedenfalls war er irgendwann fit genug, seine Haltestelle im Wachzustand zu erreichen und auszusteigen.

So, ich glaube, wir sollten uns wieder den Optimierungsproblemen zuwenden ;-)