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……

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

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

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).

Zitat von NamenLozer:

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

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.

Zitat von BUG:

Zitat von NamenLozer:

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 von BUG:

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

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.

Zitat von NamenLozer:

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.

Zitat von Furtbichler:

Zitat von NamenLozer:

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 von Furtbichler:

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...

Zitat von NamenLozer:

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 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
@evilboy: Hast du den Ansatz verstanden oder hast du Fragen?

EDIT:

Zitat von evilboy:

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