DE60001429T2

DE60001429T2 - Verfahren und Vorrichtung für die Ermittlung von Routen innerhalb eines Verkehrsnetz

Info

Publication number: DE60001429T2
Application number: DE60001429T
Authority: DE
Inventors: Shin Kikuchi; Keisuke Ohnishi
Original assignee: NAVITIME JAPAN CO; Navitime Japan Co Ltd
Current assignee: NAVITIME JAPAN CO; Navitime Japan Co Ltd
Priority date: 1999-03-08
Filing date: 2000-03-08
Publication date: 2003-07-17
Anticipated expiration: 2020-03-09
Also published as: ATE232969T1; EP1035403B1; EP1035403A1; JP2000258184A; US6349261B1; DE60001429D1; JP3750400B2

Description

Gebiet der Erfindung

Die vorliegende Erfindung bezieht sich auf ein Computersystem zum Bestimmen einer Route minimaler Kosten von einem Startort aus bis zu einem Zielort, zwischen denen sich eine Person durch Gehen und Benutzung eines Verkehrs- bzw. Beförderungsmittelnetzes, wie z. B. eines öffentlichen Verkehrs- bzw. Beförderungsmittelnetzes, bewegt.

Beschreibung der verwandten Technik

Eine optimale Route ist in einem komplizierten Verkehrnetz schwierig zu bestimmen. Weiter muss eine Optimierung unter Berücksichtigung von verschiedenen Faktoren, wie z. B. die Zeit und die Kosten, bewirkt werden. Theoretisch kann ein Computer eine optimale Route durch Berechnung, die für alle möglichen Kombinationen ausgeführt wird, bestimmen. Wenn jedoch das Verkehrsnetz kompliziert wird, nimmt die Berechnungszeit selbst dann, wenn ein Hochleistungscomputer verwendet wird, drastisch zu, so dass es unmöglich wird, die Berechnung zu vollenden.
Um ein solches Problem zu vermeiden, dass es unmöglich wird, die Berechnung zu vollenden, sind verschiedene Verfahren vorgeschlagen worden. Ein Markierungs- bzw. Labelbestimmungsverfahren - welches in einem Computer benutzt wird, um eine kürzeste Route innerhalb eines Verkehrsnetzes zu bestimmen - re duziert die Computerverarbeitungszeit und liefert eine schnelle Lösung. Das Markierungs- bzw. Labelbestimmungsverfahren wird manchmal auch nach seinem Erfinder als das Dijkstra-Verfahren bezeichnet. Die japanischen Patentanmeldungen mit den Offenlegungs (kokai)-Nrn. 10-275296 (Navigation Method and System), 10-253376 (Method and System for Determining a Minimum-Cost Route) und 11-44547 (Method and System for Determining a Minimum-Cost Route) offenbaren jede ein Verfahren zum Bestimmen einer Route in einem Verkehrnetz durch Benutzung des Markierungs- bzw. Labelbestimmungsverfahrens.
Ein exemplarisches System, das durch ein Netz repräsentiert wird, wie es in Fig. 1 gezeigt ist, soll beschrieben werden. Jeder der schwarzen Kreise in Fig. 1 entspricht einem speziellen Ort und wird als ein "Knoten" bezeichnet. Eine Linie, die benachbarte Knoten verbindet, welche jeweiligen Orten entsprechen, wird als ein "Verbindungsglied" bezeichnet. Mathematisch wird ein Satz, der die Knoten und Verbindungsglieder enthält, als eine "graphische Darstellung" bezeichnet. Wenn die Verbindungsglieder eine Ausrichtung haben, wird die graphische Darstellung als eine "gerichtete graphische Darstellung" bezeichnet, und wenn die Verbindungsglieder keine Ausrichtung haben, wird die graphische Darstellung als eine "ungerichtete graphische Darstellung" bezeichnet. Die Fig. 1 zeigt eine exemplarische gerichtete graphische Darstellung. Ein Problem der kürzesten Route ist ein Problem des Findens einer kürzesten Route unter Routen zwischen bzw. von einem Startortknoten s und bzw. zu einem Zielortknoten t innerhalb eines Netzes, wie z. B. des oben beschriebenen Netzes.
Hier wird eine kürzeste Route P vom Knoten s zum Knoten t wie folgt repräsentiert.
P = {s, i, j, ..., k, t}
In diesem Fall repräsentiert, wenn die Route P an einem gewissen Knoten in die Routen P1 und P2 geteilt wird, jede der Routen P1 und P2 die kürzeste Route innerhalb eines entsprechenden Satzes. Dieses wird als das Prinzip der Optimalität bezeichnet. Das Markierungs- bzw. Labelbestimmungsverfahren ist ein Algorithmus zum mathematischen Bestimmen der kürzesten Route durch Benutzung des Prinzips. Das heißt, das Markierungs- bzw. Labelbestimmungsverfahren beginnt mit einem leeren Satz. Jeder Knoten wird mit einer temporären Markierung markiert, und die Knoten, welche die kürzeste Route bilden, werden Knoten um Knoten bestimmt, um einen Untersatz der kürzesten Route auszuweiten. Schließlich werden alle die Knoten mit permanenten Markierungen markiert. Auf diese Weise wird die kürzeste Route bestimmt. Das folgende ist ein Algorithmus, der für das Programmieren von Computern verwendet wird.
Wenn ein Satz von allen Knoten, die zwischen dem Knoten s und dem Knoten t vorhanden sind, durch V repräsentiert wird, wird die Länge der kürzesten Route von dem Knoten s zum Knoten j durch d(j) repräsentiert, ein Satz von Knoten für die kürzeste Route (nachstehend als ein "Knotensatz kürzester Route" bezeichnet) wird durch S1 repräsentiert und sein komplementärer Satz wird durch S2 (= V - S) repräsentiert, wobei die kürzeste Route wie folgt bestimmt wird.
(1) Die folgende Initialisierung wird ausgeführt.
S1 ← 0 (leerer Satz), S2 ← V,
d(s) ← 0, d(i) ← ∞
Hier repräsentiert i einen Knoten in dem komplementären Satz S2, und X ← Y repräsentiert eine Operation des Ersetzens von X durch Y.
(2) Wenn S1 = V, dann wird die Berechnung beendet.
(3) Wenn S1 ≠ V, dann wird die Länge der kürzesten Route d(i) ausgewählt, und die Ersetzung v ← i wird bewirkt.
Da die Länge d(v) die Länge der kürzesten Route vom Knoten s zum Knoten v repräsentiert, ist der Knoten v in dem Knotensatz kürzester Route S1 enthalten und wird aus dem komplementären Satz S2 ausgeschlossen.
(4) Für jeden Knoten i, der in dem komplementären Satz S2 enthalten ist und den ein Verbindungsglied, das sich von dem Knoten V (herausgehendes Verbindungsglied) aus erstreckt, als nächstes erreicht, wird die folgende Berechnung ausgeführt.
d'(i) ← d(v) + avi
Wenn d(i) > d'(i), dann
d(i) ← d'(i) und p(i) ← v.
Hier repräsentiert avi die Länge eines Verbindungsglieds vom Knoten v zum Knoten i, und d(i) sowie d'(i) repräsentieren je die Länge einer Route von dem Startort s zum Knoten i. Der Wert d(i) an dieser Stelle repräsentiert die Länge der kürzesten Route, welche durch Knoten innerhalb des Knotensatzes S1 kürzester Route gebildet wird. Es gibt eine Möglichkeit, dass der komplementäre Satz S2 einen Knoten enthält, der eine kürzere Route zur Verfügung stellt. Jedoch würde eine solche kürzere Route während wiederholter Berechnung gefunden werden.
(5) Die Verarbeitung kehrt zum Schritt (2) oben zurück.
Wenn dem auf diese Weise erhaltenen p(i) in umgekehrter Reihenfolge von dem Endknoten t auf der Basis von p(t) gefolgt wird, wird die kürzeste Route von dem Startknoten s aus erhalten. Wenn z. B. der oben beschriebene Algorithmus auf das in Fig. 1 gezeigte Beispiel angewandt wird, wird das folgende erhalten.
d(1) = 0 d(2) = 50 d(3) = 70 d(4) = 65 d(5) = 85
p(2) = 1 p(3) = 2 p(4) = 2 p(5) = 3
Da s = 1 und t = 5, wird der Knoten 3 dahingehend bestimmt, dass er dem Knoten 5 vorhergeht, weil p(5) = 3; der Knoten 2 wird dahingehend bestimmt, dass er dem Knoten 3 vorhergeht, weil p(3) = 2; und der Knoten 1 wird dahingehend bestimmt, dass er dem Knoten 2 vorhergeht, weil p(2) = 1, so dass der Startort s erreicht wird. Das heißt, die kürzeste Route ist 1 → 2 → 3 → 5, und die Länge derselben ist 85 (= d(5)). Weiter hat die Route (1 → 2 → 4) von dem Knoten 1 zum Knoten 4 auch eine Länge d(4) kurzer Route.
Wenn die Bestimmung der Route der Fig. 1 aktuell unter Benutzung des oben beschriebenen Algorithmus simuliert wird, wird gefunden, dass die Berechnung der Länge d'(4) vom Knoten 3 zum Knoten 4 nicht erforderlich ist. Das heißt, das Markierungs- bzw. Labelbestimmungsverfahren beinhaltet eine drastische Reduktion in dem Betrag der Berechnung, verglichen mit einem Fall, in welchem die kürzeste Route durch Benutzung von allen Kombinationen berechnet wird.
Das oben beschriebene Markierungs- bzw. Labelbestimmungsverfahren kann auf die Bestimmung einer Route von einer gewissen Station zu einer Zielstation innerhalb eines öffentlichen Verkehrmittelnetzes angewandt werden. In diesem Fall wird die kürzeste Route unter Berücksichtigung von nicht nur der Entfernung, sondern auch der Zeit und des Fahrpreises bestimmt, welche allgemein als Kosten bezeichnet werden.
Das Markierungs- bzw. Labelbestimmungsverfahren verwirklicht eine Hochgeschwindigkeitsverarbeitung, wenn es unter Benutzung eines Computers ausgeführt wird. Ganz besonders, wenn ein Startort und ein Zielort vorherbestimmt sind, beginnt das Markierungs- bzw. Labelbestimmungsverfahren die Routenbestimmung von dem Startort aus, um sukzessiv Knoten zu finden, welche die Kosten minimieren, und es bestimmt die Route, welche den Zielort mit minimalen Kosten erreicht. Die zu berücksichtigenden Kosten sind Zeit oder Entfernung, und daher wird die "Bewegungs- bzw. Reisezeit" oder die "Bewegungs- bzw. Reisestrecke" berechnet.
In vielen derzeit hergestellten Navigationssystemen wird das Markierungs- bzw. Labelbestimmungsverfahren häufig benutzt, wenn die Routenbestimmung mit einem Ziel des Erreichens von minimalen Kosten ausgeführt wird. Beispiele solcher Bestimmung einer Route minimaler Kosten umfassen ein System zum Bestimmen einer Route minimaler Kosten in einem Eisenbahnnetz und ein System zum Bestimmen einer Route minimaler Kosten in einem Straßennetz.
Aus EP 0 638 887 A2 sind ein Verfahren zum Bestimmen einer Route von einem Startort zu einem Zielort innerhalb eines Verkehrsnetzes gemäß dem Oberbegriff des Anspruchs 1 und ein entsprechendes System gemäß dem Oberbegriff des Anspruchs 6 bekannt. Im Besonderen wird ein Navigationssystem, das auf bzw. in einem Fahrzeug anzubringen ist, offenbart, welches eine Route von einem Startort zu einem Zielort unter der Bedingung von minimalen Kosten bestimmt, indem es ein Straßennetz benutzt, das von Karten- bzw. Landkartendaten her erzeugt worden ist, welche das Verkehrsnetz repräsentieren.
EP 0 763 808 A1 offenbart einen Tourzeit- bzw. -fahrplanprozessor, der einen Tourzeit- bzw. -fahrplan speichert, worin eine Verschiedenheit von Verkehrsmitteln benutzt wird. Der Tourzeit- bzw. -fahrplan kann auf Anforderung hin durch ein Informationszentrum erstellt werden, und der jeweilige Benutzer wird durch den Tourzeit- bzw. -fahrplanprozessor geführt durch Suchen nach und Anzeigen einer bevorzugten Route zu einem Bestimmungsort mittels in dem Zeit- bzw. Fahrplan spezifizierten Transportanlagen bzw. -möglichkeiten unter Benutzung der gut bekannten Dijkstra-Technik.
Jedoch kann kein konventionelles Navigationssystem eine Route bestimmen, längs welcher sich eine Person durch Gehen und Benutzen eines Beförderungs- bzw. Verkehrsmittelnetzes bewegt. Zum Beispiel berücksichtigt ein Navigationssystem, das für ein Eisenbahnnetz entworfen ist, nicht eine Station, zu welcher eine Person von einem Startort aus geht (eine Station, wo die Person in das Eisenbahnnetz eintritt, die nachstehend als eine "Zugangsstation" bezeichnet wird), oder wie lange die Person braucht, um einen Zielort von einer Station aus zu erreichen, wo die Person das Eisenbahnnetz verlässt (nachstehend als eine "Abgangsstation" bezeichnet). Daher beginnt ein solches Navigationssystem die Routenbestimmung, nachdem eine Person die Station, welche dem Startort am nächsten ist, und die Station, die dem Zielort am nächsten ist, bestimmt hat. Daher kann das Navigationssystem nicht garantieren, dass die bestimmte Route, welche Abschnitte enthält, in der die Person geht, die Kosten minimiert, obwohl das System eine Route minimaler Kosten von der Zugangsstation aus bis zu der Abgangs station, die beide durch die Person bestimmt sind, angemessen bestimmen kann.

ABRISS DER ERFINDUNG

Im Hinblick auf das Vorstehende ist es ein Ziel der vorliegenden Erfindung, ein Verfahren und ein System zur Verfügung zu stellen, welches für Fälle geeignet ist, in denen eine Person zu einer Zugangsstation eines zu benutzenden Verkehrs- bzw. Beförderungsmittelnetzes geht und wieder von einer Abgangsstation zu einem Zielort geht, und welches beim Bestimmen des Zielorts durch die Person eine Route minimaler Kosten unter Einschluss von Abschnitten, entlang denen die Person geht, bestimmen kann.
Gemäß der vorliegenden Erfindung wird dieses Ziel durch ein Verfahren erreicht, wie es im Anspruch 1 definiert ist, und durch ein System, wie es im Anspruch 5 definiert ist. Die abhängigen Ansprüche definieren bevorzugte und vorteilhafte Ausführungsformen der vorliegenden Erfindung.
Um das obige Ziel zu erreichen, stellt die vorliegende Erfindung ein Verfahren zum Bestimmen einer Route minimaler Kosten von einem Startort zu einem Zielort innerhalb eines Verkehrsnetzes durch Benutzung eines Computers gemäß einem Markierungs- bzw. Labelbestimmungsverfahren zur Verfügung, in welchem Verkehrsnetz Orte als Knoten repräsentiert sind, und eine Route zwischen benachbarten Knoten als ein Verbindungsglied repräsentiert ist. Das Verfahren umfasst:
(1) das Wählen von wenigstens einer Zugangsstation eines zu benutzenden Beförderungs- bzw. Verkehrsmittelnetzes, deren geradlinige Entfernung, gemessen von dem Startort aus, in einen vorbestimmten Bereich fällt, und von wenigstens einer Abgangsstation des Beförderungs- bzw. Verkehrsmittelnetzes, de ren geradlinige Entfernung, gemessen von dem Zielort aus, in den vorbestimmten Bereich fällt, und Bewerten bzw. Berechnen der Kosten einer Gehroute von dem Startort zu der Zugangsstation und der Kosten einer Gehroute von der Abgangsstation zu dem Zielort auf der Basis der jeweiligen geradlinigen Entfernungen, jede berechnet unter Verwendung von geographischen Breiten-/Längendaten; und
(2) das Einbeziehen der Gehrouten als Verbindungsglieder, die bewertete bzw. berechnete Kosten haben, in ein Verkehrsnetz, welches das Beförderungs- bzw. Verkehrsmittelnetz umfasst, um ein umfassendes Verkehrsnetz auszudrücken, um dadurch den Computer zu befähigen, eine Route unter gewünschten Kostenbedingungen gemäß dem Markierungs- bzw. Labelbestimmungsverfahren zu bestimmen.
Weiter kann das folgende Verfahren angewandt werden, welches sich von dem oben beschriebenen Verfahren in der Art und Weise des Bestimmens einer Gehroute unterscheidet.
Das Verfahren umfasst:
(1) das Berechnen der Kosten einer Gehroute von dem Startort bis zu wenigstens einer Zugangsstation eines zu benutzenden Verkehrs- bzw. Beförderungsmittelnetzes und der Kosten einer Gehroute von wenigstens einer Abgangsstation des Verkehrs- bzw. Beförderungsmittelnetzes zu dem Zielort, wobei die mit jeder der Gehrouten verbundenen Kosten in einen bestimmten Kostenbereich fallen, und die Gehrouten durch ein Markierungs- bzw. Labelbestimmungsverfahren bestimmt werden, welches ein Straßennetz benutzt, das aus Karten bzw. Landkartendaten erzeugt ist, die geographische Breiten-/Längeninformation umfassen und welches die Gehrouten unter gewünschten Kostenbedingungen bestimmt; und
(2) das Vereinigen der Gehrouten, die berechnete Kosten haben, als Verbindungsglieder mit einem Verkehrsnetz, welches das Verkehrs- bzw. Beförderungsmittelnetz umfasst bzw. enthält, um ein umfassendes Verkehrsnetz auszudrücken, um dadurch den Computer zu befähigen, eine Route unter gewünschten Kostenbedingungen gemäß dem Markierungs- bzw. Labelbestimmungsverfahren zu bestimmen.
Als nächstes wird ein erster Aspekt der Erfindung beschrieben. Ein Computer wird betrieben, um eine Route minimaler Kosten von einem Startort zu einem Zielort, zwischen denen eine Person von dem Startort zu einer Zugangsstelle (einer Station in dem Fall eines Eisenbahnnetzes) eines Verkehrs- bzw. Beförderungsmittelnetzes geht, das Verkehrs- bzw. Beförderungsmittelnetz bis zu einer Abgangsstelle (einer Station in dem Fall eines Eisenbahnnetzes) des Verkehrs- bzw. Beförderungsmittelnetzes benutzt und von der Abgangsstelle des Verkehrs- bzw. Beförderungsmittelnetzes zu dem Zielort geht, zu bestimmen.
Zunächst soll die Gesamtverarbeitung beschrieben werden
(1) Wenigstens eine Zugangsstation von einem zu benutzenden Beförderungsmittelnetz, deren geradlinige Entfernung, gemessen von dem Startort aus, in einen vorbestimmten Bereich fällt, und wenigstens eine Abgangsstation des Beförderungsmittelnetzes, deren geradlinige Entfernung, gemessen von dem Zielort, in den vorbestimmten Bereich fällt, werden gewählt. Die Kosten einer Gehroute von dem Startort zu der Zugangsstation und die Kosten einer Gehroute von der Abgangsstation zu dem Zielort werden auf der Basis der geradlinigen Entfernung zwischen dem Startort und der Zugangsstation bzw. der geradlinigen Entfernung zwischen der Abgangsstation und dem Zielort werden bewertet bzw. berechnet. Die Gehrouten, die be wertete bzw. berechnete Kosten haben, werden als Verbindungsglieder in ein Verkehrsnetz inkorporiert, welches das Beförderungsmittelnetz umfasst bzw. enthält. Die oben beschriebene Berechnung soll als eine "Gehkostenberechnung auf der Basis geradliniger Entfernung" bezeichnet werden.
(2) Das Verkehrsnetz wird derart dargestellt, dass die Orte als Knoten repräsentiert werden, und eine Route zwischen benachbarten Knoten als ein Verbindungsglied repräsentiert wird. Es wird eine Markierung eingeführt, bestehend aus dem Namen eines Verbindungsglieds, welches den Startknoten und einen speziellen Knoten verbindet, und kumulativen Kosten von dem Startknoten zu dem speziellen Knoten. Während der Anfangswerteinstellung wird der Startknoten mit einer temporären Markierung (*, 0) markiert, und jeder der übrigen Knoten wird mit einer temporären Markierung (Φ, ∞) markiert, worin "*" bedeutet, dass kein Verbindungsglied den Startknoten erreicht. "Φ" bedeutet, dass noch kein Verbindungsglied noch den entsprechenden Knoten erreicht hat, und "∞" bedeutet einen numerischen Wert, der genügend groß innerhalb des Kontexts eines relevanten Problems ist.
(3) Unter den Knoten, die temporäre Markierungen tragen, wird ein Knoten ausgewählt, der das niedrigste Potenzial (d. h. kumulative Kosten) hat. Wenn der ausgewählte Knoten der Zielort ist, wird die Routenbestimmung beendet, und die in (5) unten beschriebene Verarbeitungsroutine wird ausgeführt. Wenn der ausgewählte Knoten nicht der Zielort ist, wird die in (4) beschriebene Verarbeitungsroutine sukzessiv bzw. nachfolgend ausgeführt.
(4) Das Potenzial eines Endknotens, der von dem Knoten aus verbunden ist, welcher das niedrigste Potenzial hat, und welcher eine temporäre Markierung hat, wird berechnet. Wenn das auf diese Weise berechnete Potenzial von dem Endknoten niedriger als das Potenzial ist, welches durch die temporäre Markierung des Endknotens angegeben wird, wird das durch die temporäre Markierung des Endknotens angegebene Potenzial durch das berechnete Potenzial des Endknotens ersetzt. Die temporäre Markierung des Knotens, der das niedrigste Potenzial hat, wird permanent gemacht, und die in (3) oben beschriebene. Verarbeitungsroutine wird ausgeführt.
(5) Den permanenten Markierungen wird nach rückwärts von dem Zielort aus zu dem Startort gefolgt, um eine Route von niedrigstem Potenzial, einschließlich der Gehrouten, zu bestimmen.
Als nächstes soll die "Gehkostenberechnung auf der Basis der geradlinigen Entfernung" für das Bewerten bzw. Berechnen der Gehkosten auf der Basis der geradlinigen Distanz beschrieben werden. Die geradlinige Entfernung von dem Startort zu einer Zugangsstelle eines zu benutzenden Beförderungsmittelnetzes und die geradlinige Entfernung von einer Abgangsstelle des Beförderungsmittelnetzes zu dem Zielort werden unter Verwendung der folgenden Gleichungen berechnet.
cosξ = sinφ1·sinφ2 + cosφ1·cosφ2·(cos(λ1 - λ2) (1)
S = R·ξ (2)
Hier ist S eine geradlinige Entfernung zwischen zwei Orten A und B; R ist ein Krümmungsradius der Erde in der Nähe von Japan (angenähert 6370 km); ξ ist ein Winkel zwischen einer Linie, die sich von dem Zentrum eines Bogens AB zu dem Ort A erstreckt, und einer Linie, die sich von dem Zentrum zu dem Ort B erstreckt; λ1 und φ1 sind die geographische Breite bzw. die geographische Länge von dem Ort A; und λ2 und φ2 sind die geographische Breite bzw. die geographische Länge des Orts B.
Die geographische Breite und die geographische Länge von jedem Ort kann aus Landkartendaten erhalten werden, welche die Information der geographischen Breite/geographischen Länge enthalten. Die geographische Breite und die geographische Länge des gegenwärtigen Orts können durch Benutzung eines GPS (globales Navigationssystem bzw. Satellitennavigationssystem)-Empfängers erhalten werden. Ein Mittel, wie z. B. ein GPS-Empfänger, ist speziell effektiv, wenn der Startort für die Person unbekannt ist, weil die Person in einem nicht vertrauten Gebiet geht. In der vorliegenden Erfindung wird die Gehentfernung zwischen dem Ort A und B so behandelt, als ob sie proportional der geradlinigen Entfernung zwischen denselben ist. Daher kann, wenn die Kosten die Zeit sind, jede von einer benötigten Zeit von dem Startort zu der nächstliegenden Zugangsstelle des Beförderungsmittelnetzes und einer benötigten Zeit von der Abgangsstelle des Beförderungsmittelnetzes zu dem Zielort mittels Teilung der entsprechenden geradlinigen Entfernung durch eine mittlere Gehgeschwindigkeit berechnet werden. Die auf diese Weise erhaltenen Kosten werden in das zu benutzende Verkehrsnetz aufgenommen.
Maximale Kosten werden im voraus in Relation zu der erforderlichen Zeit von dem Startort zu einer Zugangsstelle des Beförderungsmittelnetzes und der erforderlichen Zeit von einer Abgangsstelle des Beförderungsmittelnetzes zu dem Zielort festgelegt, und eine Zugangsstelle (Zugangsstellen) sowie eine Abgangsstelle (Abgangsstellen) des Beförderungsmittelnetzes werden derart ausgewählt, dass die Gehkosten nicht die maximalen Kosten übersteigen. Wenn eine Mehrzahl von Zugangsstellen oder Abgangsstellen ausgewählt wird, wird eine Mehrzahl von Verbindungsgliedern zwischen dem Startort und den jeweiligen Zugangsstellen des Beförderungsmittelnetzes und/oder zwischen den Abgangsstellen des Beförderungsmittelnetzes und dem Zielort gebildet.
Nachdem die Verbindungsglieder in den Gehabschnitten in das Verkehrsnetz aufgenommen worden sind, wird die folgende Routenbestimmungsverarbeitung für das Verkehrsnetz ausgeführt.
(1) Das Verkehrsnetz wird derart dargestellt, dass die Orte als Knoten repräsentiert werden und eine Route zwischen benachbarten Knoten als ein Verbindungsglied repräsentiert wird. Es wird eine Markierung eingeführt, bestehend aus dem Namen eines Verbindungsglieds, das den Startknoten und einen speziellen Knoten verbindet, und kumulativen Kosten von dem Startknoten zu dem speziellen Knoten. Während der Anfangswerteinstellung wird der Startknoten mit einer temporären Markierung (*, 0) markiert, und jeder der übrigen Knoten wird mit einer temporären Markierung (Φ, ∞) markiert, worin "*" bedeutet, dass kein Verbindungsglied den Startknoten erreicht, und "Φ" bedeutet, dass noch kein Verbindungsglied den entsprechenden Knoten erreicht hat, und "∞" bedeutet einen numerischen Wert, der innerhalb des Kontexts eines relevanten Problems genügend groß ist.
(2) Unter den Knoten, die temporäre Markierungen tragen, wird ein Knoten ausgewählt, der das niedrigste Potenzial (d. h. kumulative Kosten) hat. Wenn der ausgewählte Knoten der Zielort ist, wird die Routenbestimmung beendet, und die Endverarbeitungsroutine, die unten in (4) beschrieben ist, wird ausgeführt. Wenn der ausgewählte Knoten nicht der Zielort ist, wird die in (3) beschriebene Verarbeitungsroutine nachfolgend ausgeführt.
(3) Das Potenzial eines Endknotens, der von dem Knoten her verbunden ist, welcher das niedrigste Potenzial hat, und welcher eine temporäre Markierung hat, wird berechnet. Wenn das auf diese Weise berechnete Potenzial des Endknotens niedriger als das Potenzial ist, welches durch die temporäre Markierung des Endknotens angegeben wird, wird der Potenzialwert in der temporären Markierung des Endknotens durch den berechneten Potenzialwert des Endknotens ersetzt. Die temporäre Markierung des Knotens, der das niedrigste Potenzial hat, wird permanent gemacht, und die oben in (2) beschriebene Verarbeitungsroutine wird ausgeführt.
(4) Permanenten Markierungen wird rückwärts von dem Zielort aus zu dem Startort gefolgt, um eine Route von niedrigstem Potenzial zu bestimmen, und zwar einschließlich der Gehrouten.
In der Beschreibung wird das oben beschriebene Markierungs- bzw. Labelbestimmungsverfahren als ein "Potenzialbasismarkierungsbestimmungsverfahren" bezeichnet, um es von dem konventionellen Markierungsbestimmungsverfahren zu unterscheiden.
Als nächstes soll ein zweiter Aspekt der vorliegenden Erfindung beschrieben werden.
Es wird ein Computer betrieben, um eine Route minimaler Kosten von einem Startort zu einem Zielort, zwischen denen eine Person von dem Startort zu einer Zugangsstelle (einer Station in dem Fall eines Eisenbahnnetzes) von einem Beförderungsmittelnetz geht, das Beförderungsmittelnetz bis zu einer Abgangsstelle (einer Station in dem Fall eines Eisenbahnnetzes) von dem Beförderungsmittelnetz benutzt, und von der Abgangsstelle des Beförderungsmittelnetzes zu dem Zielort geht. Das Verfahren umfasst die folgenden Schritte:
(1) Wenigstens eine Zugangsstelle zu einem zu benutzenden Beförderungsmittelnetz, wodurch Kosten innerhalb eines vorbestimmten Bereichs eingegangen werden, und wenigstens eine Abgangsstelle des Beförderungsmittelnetzes, wodurch Kosten in nerhalb des vorbestimmten Bereichs eingegangen werden, werden gewählt. Die Kosten der Route von dem Startort bis zu der Zugangsstelle und die Kosten der Route von der Abgangsstelle des Beförderungsmittelnetzes zu dem Zielort werden aus einer Straßenkarte berechnet. Die Gehrouten, die berechnete Kosten haben, werden als Verbindungsglieder in ein Verkehrsnetz aufgenommen, welches das Beförderungsmittelnetz umfasst. Die oben beschriebene Berechnung soll als eine "Gehkostenberechnung auf Straßenkartenbasis" bezeichnet werden.
(2) Das Verkehrsnetz wird derart dargestellt, dass die Orte als Knoten repräsentiert werden, und eine Route zwischen benachbarten Knoten als ein Verbindungsglied repräsentiert wird. Es wird eine Markierung eingeführt, die aus dem Namen eines Verbindungsglieds, welches den Startknoten und einen speziellen Knoten verbindet, und kumulativen Kosten von dem Startknoten zu dem speziellen Knoten besteht. Während der Anfangswerteinstellung wird der Startknoten mit einer temporären Markierung (*, 0) markiert, und jeder der übrigen Knoten wird mit einer temporären Markierung (Φ, ∞) markiert, worin "*" bedeutet, dass kein Verbindungsglied den Startknoten erreicht, "Φ" bedeutet, dass noch kein Verbindungsglied den entsprechenden Knoten erreicht hat, und "∞" bedeutet einen numerischen Wert, der innerhalb des Kontexts eines relevanten Problems genügend groß ist.
(3) Unter den Knoten, die temporäre Markierungen tragen, wird ein Knoten ausgewählt, der das niedrigste Potenzial (d. h. kumulative Kosten) hat. Wenn der ausgewählte Knoten der Zielort ist, wird die Routenbestimmung beendet, und die Endverarbeitungsroutine, die unten in (5) beschrieben ist, wird ausgeführt. Wenn der ausgewählte Knoten nicht der Zielort ist, wird die Verarbeitungsroutine, die in (4) beschrieben ist, der Reihe nach ausgeführt.
(4) Das Potenzial eines Endknotens, der von dem Knoten aus verbunden ist, welcher das niedrigste Potenzial hat, und welcher eine temporäre Markierung hat, wird berechnet. Wenn das auf diese Weise berechnete Potenzial des Endknotens niedriger als das Potenzial ist, welches durch die temporäre Markierung des Endknotens angegeben wird, wird der Potenzialwert in der temporären Markierung des Endknotens durch den berechneten Potenzialwert des Endknotens ersetzt. Die temporäre Markierung des Knotens, der das niedrigste Potenzial hat, wird permanent gemacht, und die in (3) oben beschriebene Verarbeitungsroutine wird ausgeführt.
(5) Den permanenten Markierungen wird rückwärts von dem Zielort aus zu dem Startort gefolgt, um eine Route des niedrigsten Potenzials zu bestimmen, und zwar einschließlich der Gehrouten.
In dem ersten Aspekt der vorliegenden Erfindung werden die Kosten einer Route von dem Startort zu jeder Zugangsstelle eines Beförderungsmittelnetzes, das benutzt werden soll, und die Kosten einer Route von jeder Abgangsstelle des Beförderungsmittelnetzes zu dem Zielort je auf der Basis der entsprechenden geradlinigen Entfernung berechnet. Im Gegensatz hierzu werden diese Kosten in dem zweiten Aspekt der Erfindung durch Benutzung einer Straßenkarte genau berechnet. Wenn Zugangs- und Abgangsstationen ausfindig gemacht werden, deren Kosten, die durch die "Gehkostenberechnung auf Straßenkartenbasis" berechnet worden sind, in einen festgelegten Kostenbereich fallen, werden eine Gehroute von dem Startort zu der Zugangsstation und eine Gehroute von der Abgangsstation zu dem Zielort in das Verkehrsnetz als Verbindungsglieder aufgenommen.
In der "Gehkostenberechnung auf Straßenkartenbasis" wird das gleiche "Markierungsbestimmungsverfahren auf Potenzialbasis" benutzt, wie es in dem ersten Aspekt benutzt wird. Da das hier verwendete Netz ein Straßennetz ist, wird das "Markierungsbestimmungsverfahren auf Potenzialbasis" nach einigen Modifikationen benutzt.
Durch Verwendung des "Markierungsbestimmungsverfahrens auf Potenzialbasis" wird eine Route minimaler Kosten für das Verkehrsnetz bestimmt, in welches die durch die "Gehkostenberechnung auf Straßenkartenbasis" erhaltenen Verbindungsglieder aufgenommen worden sind.
Als nächstes soll das "Markierungsbestimmungsverfahren auf Potenzialbasis" spezieller beschrieben werden. In dem Markierungsbestimmungsverfahren auf Potenzialbasis wird das Potenzial von jedem Knoten in eine entsprechende Markierung eingeführt. Eine Markierung für jeden Knoten wird wie folgt definiert:
(l, P(v))
worin l ein Verbindungsglied repräsentiert, das benachbarte Knoten verbindet, v repräsentiert einen Knoten, der gegenwärtig betrachtet wird, und p(v) ist das Potenzial des Knotens v. Das Potenzial p(v) repräsentiert die kumulativen Kosten, welche eine Route von dem Startpunkt zu dem Knoten v nach sich zieht.
Eine Route von dem Startort (Startknoten) zu einem Zielort (Zielknoten) kann unter der Bedingung des Minimierens der Kosten bestimmt werden.

Prozess für das Einstellen von Anfangswerten

Der Startknoten s wird mit einer temporären Markierung (*, 0) markiert, und jeder der übrigen Knoten wird mit einer temporären Markierung (Φ, ∞) markiert, worin "*" bedeutet, dass kein Verbindungsglied noch den Startknoten erreicht hat, "Φ" bedeutet, dass noch kein Verbindungsglied den entsprechenden Knoten erreicht hat, und "∞" bedeutet einen numerischen Wert, der innerhalb des Kontexts eines relevanten Problems genügend groß ist.

Prozess für das Ausfindigmachen eines Knotens niedrigsten Potenzials

Unter den Knoten, die temporäre Markierungen tragen, wird ein Knoten ausfindig gemacht, der das niedrigste Potenzial hat, und er wird als der Knoten v niedrigsten Potenzials bezeichnet. Wenn der hier ausfindig gemachte Knoten der Zielknoten (Zielort) ist, wird der Knoten mit einer permanenten Markierung markiert, und die Verarbeitung geht weiter zu dem "Endprozess". In anderen Fällen geht die Verarbeitung weiter zum "Routenbestimmungsprozess".

Routenbestimmungsprozess

Wenn ein Knoten, der mit einem Verbindungsglied a (abgehendes Verbindungsglied a) verbunden ist, das sich von dem Knoten v aus erstreckt, repräsentiert wird durch
δ - la, und
das von dem Startknoten aus akkumulierte Potenzial repräsentiert wird durch
p(v),
dann wird das Potenzial des Knotens δ - la repräsentiert durch
p(v) + d(a).
Wenn p(v) + d(a) kleiner als p (δ - la) ist, welches bereits für den Knoten δ - la gesetzt worden ist, wird
p(v) + d(a) als das neue Potenzial
p (δ - la) benutzt, und
der Knoten wird mit einer temporären Markierung
(a, p (δ - la) markiert.
Nachdem die oben beschriebene Verarbeitung für alle die Verbindungsglieder (abgehende Verbindungsglieder) ausgeführt worden ist, die sich von dem Knoten v aus erstrecken, wird die temporäre Markierung des Knotens v permanent gemacht. Nachfolgend kehrt die Verarbeitung zu dem "Prozess für das Ausfindigmachen eines Knotens niedrigsten Potenzials" zurück.

Endprozess

Knoten, die durch die oben beschriebene Verarbeitung erhalten werden und die je eine permanente Markierung haben, werden in einer verlangten Form ausgegeben.
Als nächstes soll die vorliegende Erfindung in mehr Einzelheiten beschrieben werden. Die Fig. 2 zeigt die Beziehung zwischen Knoten und Verbindungsgliedern. Die hier benutzten Symbole haben die folgenden Bedeutungen:
v: Knoten, der das niedrigste Potenzial unter den Knoten hat, welche temporäre Markierungen tragen;
u: Knoten, der dem Knoten v benachbart ist;
a, b: Verbindungsglieder;
δ - la: Knoten, welchen das Verbindungsglied a erreicht;
δ + la: Knoten, von dem aus sich das Verbindungsglied a erstreckt;
d(a): Kosten, die mit dem Erreichen des Verbindungsglieds a verbunden sind; und
p(v): Potenzial des Knotens v (gibt die kumulativen Kosten von dem Startort aus an (= Σd(ai))).
Gesehen von dem Knoten v aus, ist a ein abgehendes Glied, und b ist ein ankommendes Glied. Gesehen von dem Knoten u aus, ist a ein ankommendes Glied, und b ist ein abgehendes Glied. d(a) sind die Kosten, wie z. B. die Zeit, die Entfernung oder das Geld, welche bzw. welches für die Benutzung des Verbindungsglieds a gebraucht bzw. eingegangen werden. Die zu erhaltenden Ergebnisse variieren in Abhängigkeit von der Art der Kosten. Obwohl im Allgemeinen d(a) = d(b) in einem Fall gilt, wie er in Fig. 2(3) gezeigt ist, gilt in einigen Fällen d(a) ≠ d(b). Das Potenzial p(v) ist eine Summe der Kosten, die sich entlang einer Route von dem Startort 0 bis zu dem Knoten v angesammelt haben.
Eine Markierung des Knotens u (gleich wie δ - la, δ + la), der mit dem Knoten v über das Verbindungsglied a verbunden ist, ist definiert als
(a, p(v) + d(a)) oder
u (a, p(v) + d(a)).
Da p(v) + d(a) gleich p(u) ist, kann die obige Markierung geschrieben werden als
(a, p(u)) oder
u(a, p(u)).
Das heißt, die Markierung des Knotens u wird repräsentiert durch das Verbindungsglied a, welches den Knoten u mit dem Knoten v verbindet, und ein kumulatives Potenzial bis zu dem Knoten u. Eine Markierung, die in der Zukunft geändert werden kann, wird als eine "temporäre Markierung" bezeichnet, und eine Markierung, welche in der Zukunft niemals geändert werden wird, wird als eine "permanente Markierung" bezeichnet, Das heißt, eine permanente Markierung für den Knoten u umfasst einen niedrigsten Wert des bis zu dem Knoten u akkumulierten Potenzials, weil in der vorliegenden Erfindung eine von dem Startknoten ausgehende Route immer bestimmt wird, während Knoten, von denen jeder das niedrigste Potenzial hat, ausgewählt werden. Dieses Konzept soll als nächstes beschrieben werden.
Die Einführung des Konzepts des Knotenpotenzials vereinfacht die Programmbeschreibung und befähigt zu einer Beurteilung darüber, ob die Verarbeitung zu Ende ist. Wie oben beschrieben ist, benutzt die vorliegende Erfindung das Markierungsbe stimmungsverfahren für die Routenbestimmung. Die Fig. 3 zeigt einen Satz S von allen Knoten, wie auch einen Satz S' (schraffierter Teil) von Knoten, welche permanente Markierungen tragen. Um eine Route niedrigsten Potenzials zu finden, wird ein Knoten, der eine Markierung trägt, deren Potenzialwert am niedrigsten ist, aus den Knoten ausfindig gemacht, welche temporäre Markierungen (= S - S') tragen. Hier werden nur abgehende Verbindungsglieder betrachtet, und es wird angenommen, dass der auf diese Weise ausfindig gemachte Knoten der Knoten v ist. Wenn die Knoten u1 und u2 dem Knoten v benachbart sind, werden die Knoten u1 und u2 mit temporären Markierungen wie folgt markiert (hier wird angenommen, dass jeder der Knoten u1 und u2 ein Knoten ist, welcher noch nicht ausfindig gemacht worden ist):
u1: (a1, p(v) + d(a1))
u2: (a2, p(v) + d(a2))
Nachfolgend wird die temporäre Markierung (l, p(v)) des Knotens v permanent gemacht, und der Knoten v wird in den Satz S' von Knoten aufgenommen, die permanente Markierungen tragen. Dass das Potenzial p(v), welches durch die Markierung (l, p(v)) angegeben wird, das niedrigste ist, kann wie folgt nachgewiesen werden.
Es sei angenommen, dass der Knoten w als nächster während des Suchvorgangs zum Ausfindigmachen einer temporären Markierung, die den niedrigsten Potenzialwert hat, gefunden wird, und dass der Knoten w mit den benachbarten Knoten v, u2 und x über Verbindungsglieder b1 bzw. b2 bzw. b3 verbunden ist. In diesem Fall werden die temporären Markierungen für die Knoten v, u2 und x wie folgt bestimmt:
v: (b1, p(w) + d(b1))
u2: (b2, p(w) + d(b2))
x: (b3, p(w) + d(b3))
Das Potenzial p(v) des Knotens v, welches durch die Markierung (l, p(v)) angegeben wird, die permanent gemacht ist, erfüllt die folgende Beziehung.
p(v) ≤ p(w) + d(b1)
Dieses ist deswegen so, weil das Potenzial p(v) während der vorhergehenden Suche ausgewählt wurde, in welcher der Knoten v gefunden wurde, und daher gilt p(v) ≤ p(w). Demgemäß ist, während eine Routenbestimmung, die für den Knoten w ausgeführt wird, die Auswahl des Verbindungsglieds b1, das den Knoten v und den Knoten w verbindet, nicht erforderlich. Dieses bedeutet auch, dass sich die permanente Markierung (1, p(v)) des Knotens v nicht ändern wird. Demgemäß ist nachgewiesen, dass das Potenzial p(v) das niedrigste ist.
Als nächstes wird der Knoten u2 betrachtet. Der Knoten u2 ist bereits markiert worden mit
(a2, p(v) + d(a2)).
Der Potenzialwert dieser Markierung wird mit jenem einer neuen Markierung
(b2, p(w) + d(b2))
verglichen. Wenn p(v) + d(a2) ≤ p(w) + d(b2) ist, bleibt die Markierung des Knotens u2 unverändert, und die folgende Markierung wird aufrecht erhalten.
u2: (a2, p(v) + d(a2))
Wenn p(v) + d(a2) > p(w) + d(b2) ist, dann wird der Knoten u2 mit der folgenden temporären Markierung markiert.
u2: (b2, p(w) + d(b2))
Demgemäß wird durch Ersetzen von temporären Markierungen die Route, welche das niedrigste Potenzial erzeugt, festgesetzt.
Wie aus der obigen Beschreibung zu verstehen ist, wird der entsprechende niedrigste Potenzialwert in jede permanente Markierung eingesetzt, und das Vorhandensein einer temporären Markierung repräsentiert die Möglichkeit einer anderen Route, die das Potenzial weiter vermindert.
Die folgende Programmierungstechnik wird dazu benutzt, die Routenbestimmung von einem Startknoten 0 aus zu beginnen. Das heißt, während der Anfangswerteinstellung wird der Startknoten 0 mit einer temporären Markierung (*, 0) markiert, und jeder der übrigen Knoten wird mit einer temporären Markierung (Φ, ∞) markiert.
Daher prüft der Computer, um zu beurteilen, ob das Ausfindigmachen einer Route minimaler Kosten, die Gehabschnitte enthält, beendet ist, ob "ein Knoten, der dem Zielort entspricht, mit einer permanenten Markierung markiert worden ist". Die oben beschriebene Operation kann mittels eines Programms ausgeführt werden, das die folgenden Schritte umfasst.

Schritt 1

Prozess für das Einstellen von Anfangswerten

Der Startknoten wird mit einer temporären Markierung (*, 0) markiert, und jeder der übrigen Knoten wird mit einer temporären Markierung (Φ, ∞) markiert.

Schritt 2

Prozess für das Ausfindigmachen des Knotens des niedrigsten Potenzials

Unter den Knoten, von denen jeder eine temporäre Markierung trägt, wird ein Knoten von niedrigstem Potenzial ausfindig gemacht und als der Knoten v niedrigsten Potenzials betrachtet. Wenn der ausfindig gemachte Knoten ein Knoten ist, welcher dem Zielort entspricht, geht die Verarbeitung weiter zum Schritt S4 (Endprozess). In anderen Fällen geht die Verarbeitung weiter zum Schritt S3 (Routenbestimmungsprozess).

Schritt 3

Routenbestimmungsprozess

Wenn der Knoten δa benachbart dem Knoten v mit dem Knoten v über das Verbindungsglied a verbunden ist und die Kosten d(δa) mit dem Verbindungsglied a verbunden sind, ist das Potenzial des Knotens δa gleich p(v) + d(a). In dem Fall, in welchem ein Potenzial p(δa) bereits zum Knoten δa gesetzt worden ist, wenn p(v) + d(a) < p(δa) ist, wird p(v) + d(a) als neues Potenzial p(δa) betrachtet, um eine temporäre Markierung (a, p(δa)) zu erzeugen. Nachfolgend wird die temporäre Markierung des Knotens v permanent gemacht. Nachfolgend kehrt die Verarbeitung zum Schritt 2 (Prozess zum Ausfindigmachen des Knotens niedrigsten Potenzials) zurück.

Schritt 4

Endprozess

Permanente Markierungen werden von dem Knoten v aus nach rückwärts verfolgt, um die Route in einer verlangten Form auszugeben.
Die Fig. 4 ist ein Ablaufdiagramm, das die oben beschriebene Verarbeitung zeigt. Der Teil der Verarbeitung, der ein anderer als der Prozess S "Gehkostenberechnung" in Fig. 4 ist, entspricht dem "Markierungsbestimmungsverfahren auf Potenzialbasis". In Fig. 4 repräsentiert p(δa) ein Potenzial, das bereits für den Knoten δa gesetzt worden ist. Wenn das Potenzial p(δa) großer als ein neuerlich berechnetes Potenzial
p(v) + d(a)
ist, wird p(δa) in der Markierung ersetzt durch
p(v) + d(a).
Weiter wird der Verbindungsgliedname in der Markierung ersetzt durch "a" und der Knoten δa wird markiert mit einer neuen temporären Markierung
(a, δa).
Wenn ein benachbarter Knoten gesucht wird, wird die Suchoperation nur für abgehende Verbindungsglieder ausgeführt. Da das Ablaufdiagramm der Fig. 4 eine "TUE WÄHREND"-Konfiguration hat, wird die Markierung des Knotens v mit einer permanenten Markierung in dem Endprozess ausgeführt, in welchem der Knoten niedrigsten Potenzials ausfindig gemacht und als der Knoten v betrachtet wird. Das heißt, in der obigen Beschreibung wird die Markierungsoperation dahingehend beschrieben, dass sie im Schritt 2 ausgeführt wird. Jedoch ist die Markierungsoperation in dem Ablaufdiagramm in die Verarbeitung im Schritt 3 aufgenommen. Dieses ist lediglich eine Sache in Bezug auf die Programmierung, und es ist im Konzept keine fundamentale Differenz vorhanden.
Die in Fig. 4 gezeigte Verarbeitung ist dem ersten und zweiten Aspekt der vorliegenden Erfindung gemeinsam. Daher wird, wenn das aktuelle Verarbeiten gemäß dem ersten Aspekt der vorliegenden Erfindung ausgeführt wird, die "Gehkostenberechnung auf der Basis geradliniger Entfernung" als die "Berechnung der Gehkosten" ausgeführt, und wenn die aktuelle Verarbeitung gemäß dem zweiten Aspekt der vorliegenden Erfindung ausgeführt wird, wird die "Gehkostenberechnung auf Straßenkartenbasis" als die "Berechnung der Gehkosten" ausgeführt. Die Einzelheiten dieser Berechnungen werden in dem Abschnitt "Ausführungsformen der Erfindung" beschrieben.
In der oben beschriebenen Routenbestimmung wird die Verbindungsgliedtabelle, wie sie in Fig. 5 gezeigt ist, erzeugt. Daher kann durch eine Operation des Folgens der Knoten nach rückwärts von dem Zielort aus mit Bezug auf die Verbindungsgliedtabelle, wie sie in Fig. 5 gezeigt ist, und Verbindungsgliednamen, die in den permanenten Markierungen eingesetzt sind, eine Route minimaler Kosten gefunden werden, die sich von dem Startort zu dem Zielort erstreckt, der eine permanente Markierung trägt.

KURZE BESCHREIBUNG DER ZEICHNUNGEN

Fig. 1 ist ein Netzdiagramm, welches speziell ein Verfahren zum Erhalten einer optimalen Lösung durch Benutzung eines konventionellen Markierungs- bzw. Labelbestimmungsverfahrens zeigt;
Fig. 2 ist ein Diagramm mit Bezug auf eine Ausführungsform der vorliegenden Erfindung, das Knoten, Verbindungsglieder, Potenziale und ihre Bezugssymbole zeigt;
Fig. 3 ist ein Diagramm mit Bezug auf die Ausführungsform der vorliegenden Erfindung, das Knoten zeigt, die temporäre Markierungen tragen, sowie einen Knoten, der permanente Markierungen trägt;
Fig. 4 ist ein Ablaufdiagramm mit Bezug auf die Ausführungsform der vorliegenden Erfindung, das die Verarbeitung zum Bestimmen einer Route von einem Startort zu einem Zielort unter der Bedingung des Erreichens minimaler Kosten zeigt;
Fig. 5 ist ein Diagramm mit Bezug auf die Ausführungsform der vorliegenden Erfindung, das eine Verbindungsgliedtabelle zeigt;
Fig. 6 ist ein Diagramm mit Bezug auf die Ausführungsformen der vorliegenden Erfindung, das Untergrundbahnlinien zeigt, die in einem Beispiel verwendet werden, in dem in engerer Wahl stehende Stationen auf der Basis der geradlinigen Entfernung durchsucht werden;
Fig. 7 ist ein Diagramm mit Bezug auf die Ausführungsform der vorliegenden Erfindung, das ein Straßennetz zeigt, welches in einem Beispiel verwendet wird, in dem in engerer Wahl stehende Stationen auf der Basis einer Straßenkarte durchsucht werden; und
Fig. 8 ist ein Diagramm, das mit Bezug auf Effekte der Erfindung dazu benutzt wird, um zusätzlich ein anderes Verfahren des Durch- bzw. Untersuchens von in engerer Wahl stehenden Stationen auf der Basis der geradlinigen Entfernung zu beschreiben.

BESCHREIBUNG DER BEVORZUGTEN AUSFÜHRUNGSFORMEN

Es sollen Ausführungsformen der vorliegenden Erfindung unter Bezugnahme auf die Zeichnungen beschrieben werden.
In den Ausführungsformen wird eine Route minimaler Kosten unter Verwendung einer in Fig. 6 gezeigten Untergrundbahnkarte unter der Annahme bestimmt, dass ein Startort in der Nähe der Stationen Tokyo, Kobashi und Ginza lokalisiert ist, und ein Zielort zwischen den Stationen Mtsukoshimae und Ningyocho lokalisiert ist. In der Ausführungsform 1 werden die Zugangs- und Abgangsstation auf der Basis der geradlinigen Entfernung ausfindig gemacht, und in der Ausführungsform 2 werden die Zugangs- und Abgangsstationen auf der Basis einer Straßenkarte ausfindig gemacht. In jedem der beiden Fälle werden Stationen innerhalb von 10 Gehminuten als in engerer Wahl stehende Zugangs- und Abgangsstation gesucht. In einem aktuellen Programm für die Routenbestimmung wird ein Benutzer darum gebeten, einen Start- und Zielort unter Benutzung von speziellen Ortsnamen festzulegen. Die geographische Breite und die geographische Länge von jedem Ort werden aus Karten- bzw. Landkartendaten abgeleitet, welche im voraus geliefert worden sind. Zur Vereinfachung basiert die folgende Beschreibung auf der Annahme, dass eine Zeit für das Erwarten eines Zuges Null ist und dass jedes Wechseln der Untergrundbahnlinien (angegeben durch gestrichelte Linien) 3 Minuten Gehen erfordert. Weiter bestimmt in den Ausführungsformen die Zeit die Kosten. Das heißt, eine Route, welche eine erforderliche Zeit minimiert, wird gesucht. Daher ist die Einheit des Potenzials, welches unten erörtert werden wird, die Zeit.

Ausführungsform 1

Zunächst wird die "Gehkostenberechnung auf der Basis geradliniger Entfernung" beschrieben. Wenn die von Kartendaten erhaltenen Positionsdaten Koordinaten in einem normalen Koordinatensystem (orthogonales Koordinatensystem) sind, wird eine maximale Gehzeit (10 Minuten) mit einer mittleren Gehgeschwindigkeit multipliziert, um einen Suchbereich zu bestimmen. Wenn die mittlere Gehgeschwindigkeit 4 km/h ist, werden Stationen ausgewählt, die innerhalb eines kreisförmigen Bereichs lokalisiert sind, welcher einen Radius von etwa 700 mm hat und auf einen Startort oder einen Zielort zentriert ist. Die auf diese Weise ausfindig gemachten Stationen werden als zu benutzende, in engerer Wahl stehende Stationen betrachtet. In dem Fall, in dem die Ortsdaten, welche von den Kartendaten erhalten werden, Daten der geographischen Breite/geographischen Länge sind, wird eine Entfernung S zwischen einer in engerer Wahl stehenden Station und einem Start- oder Zielort durch Benutzung der Gleichungen (1) und (2) erhalten, die in dem Abschnitt "ABRISS DER ERFINDUNG" beschrieben sind. Das heißt, wenn die geographische Breite und die geographische Länge des Startorts durch (φ1, λ1) und die geographische Breite und die geographische Länge des Zielorts durch (φ2, λ2) repräsentiert werden, kann die geradlinige Entfernung S wie folgt berechnet werden.
cosξ = sinφ1·sinφ2 + cosφ1·cosφ2·(cos (λ1 - λ2)
S = R·ξ
Daher werden Stationen, die die Bedingung S ≤ 700 erfüllen, in die Routenkarte als Knoten aufgenommen, um mit dem Startort oder dem Zielort verbunden zu werden. Die Kosten eines Verbindungsglieds zwischen einer gewissen Station und dem Startort oder dem Zielort haben einen Wert, der erhalten wird mittels Teilung der geradlinigen Entfernung S durch die mittlere Gehgeschwindigkeit. In dem in Fig. 6 gezeigten Beispiel werden die Kosten eines Verbindungsglieds zwischen dem Startort und der Station Kyobashi als 4 Minuten erhalten, und die Kosten eines Verbindungsglieds zwischen dem Startort und der Station Tokyo werden als 3 Minuten erhalten. Weiter werden die Kosten eines Verbindungsglieds zwischen dem Zielort und der Station Ningyocho als 2 Minuten erhalten, und die Kosten eines Verbindungsglieds zwischen dem Zielort und der Station Mitsukoshimae werden als 3 Minuten erhalten. Diese Werte werden in eine Verbindungsgliedtabelle aufgenommen, die in Fig. 5 gezeigt ist. Nachfolgend wird die folgende Routenbestimmung ausgeführt.

Anfängliche Einstellung

Während der Anfangswerteinstellung wird ein Knoten, der dem Startort entspricht, mit einer temporären Markierung (*, 0 Minuten) markiert, und jeder der anderen Knoten, welche Stationen entsprechen, wird mit einer temporären Markierung (Φ, ∞) markiert, worin "*" bedeutet, dass kein Verbindungsglied den Startknoten erreicht, "Φ" bedeutet, dass noch kein Glied den entsprechenden Knoten erreicht hat, und "∞" bedeutet einen numerischen Wert, der innerhalb des Kontextes eines relevanten Problems genügend groß ist. In dem anfänglichen Zustand wird der dem Startort entsprechende Knoten als der Knoten v betrachtet.

Verarbeitung in der ersten Schleife

Unter den Knoten, die Stationen entsprechen und temporäre Markierungen tragen, wird ein Knoten oder werden Knoten von niedrigstem Potenzial gesucht. In diesem Fall werden Knoten, die der Station Tokyo und der Station Kyobashi entsprechen, mit dem Knoten v verbunden. Da diese Endknoten beide ungesuchte Knoten sind, ist das Potenzial von jedem Endknoten eine kumulative Zeit, gemessen von dem Startort. Daher werden die Knoten, die den Stationen Tokyo und Kyobashi entsprechen, mit den folgenden temporären Markierungen markiert.
Station Tokyo, Marunouchi-Linie: (Startort, 3 Minuten) Station Kyobashi, Ginza-Linie: (Startort, 4 Minuten)
Weiter wird der dem Startort entsprechende Knoten mit der folgenden permanenten Markierung markiert.
Startort: (*, 0 Minuten)
Nachfolgend wird bzw. werden unter den Knoten, die temporäre Markierungen tragen, ein Knoten oder Knoten von niedrigstem Potenzial gesucht. Zu diesem Zeitpunkt hat ein Knoten, welcher der Station Tokyo auf der Marunouchi-Linie entspricht, das niedrigste Potenzial (3 Minuten); dieser Knoten wird als Knoten v betrachtet.

Verarbeitung in der zweiten Schleife

Da der Knoten v an dieser Stelle nicht der Zielort ist, wird die Verarbeitung fortgesetzt.
Verbindungsglieder, die sich von dem Knoten v aus erstrecken, der der Station Tokyo auf der Marunouchi-Linie entspricht, erreichen einen Knoten, welcher der Station Otemachi auf der Marunouchi-Linie entspricht, und einen Knoten, welcher der Station Ginza auf der Marunouchi-Linie entspricht, von denen jeder ein Potenzial 3 + 2 hat; d. h. 5 Minuten. Die auf diese Weise ausfindig gemachten neuen Knoten werden mit temporären Markierungen markiert, und der Knoten, welcher der Station Tokyo entspricht, wird mit einer permanenten Markierung markiert. Demgemäß sind am gegenwärtigen Punkt die folgenden temporären Markierungen vorhanden.
Station Otemachi, Marunouchi Linie:
(Station Tokyo, Marunouchi Linie → Marunouchi-Linie, 5 Minuten)
Station Ginza, Marunouchi-Linie:
(Station Tokyo, Marunouchi-Linie → Marunouchi-Linie, 5 Minuten)
Station Kyobashi, Ginza-Linie: (Startort, 4 Minuten)
Weiter sind die folgenden permanenten Markierungen vorhanden.
Startpunkt: (*, 0 Minuten)
Station Tokyo, Marunouchi-Linie: (Startort, 3 Minuten)
Beim Suchen eines Knotens oder von Knoten des niedrigsten Potenzials unter den Knoten, welche temporäre Markierungen tragen, wird ein Knoten gefunden, welcher der Station Kyobashi auf der Ginza-Linie entspricht, und zwar wegen des Vorhandenseins der Markierung Station Kyobashi, Ginza-Linie: (Startort, 4 Minuten), und der Knoten, welcher der Station Kyobashi entspricht, wird als Knoten v betrachtet.

Verarbeitung in der dritten Schleife

Da der Knoten v an diesem Punkt nicht der Zielort ist, wird die Verarbeitung fortgesetzt.
Verbindungsglieder, die sich von dem Knoten v aus erstrecken, welcher der Station Kyobashi auf der Ginza-Linie entspricht, erreichen einen Knoten, welcher der Station Ginza auf der Ginza-Linie entspricht, und einen Knoten, welcher der Station Nihombashi auf der Ginza-Linie entspricht. In diesem Fall hat der Knoten, welcher der Station Ginza entspricht, ein Potenzial 4 + 1; d. h. 5 Minuten, und der Knoten, welcher der Station Nihonbashi entspricht, hat ein Potenzial 4 + 2; d. h. 6 Minuten. Die auf diese Weise ausfindig gemachten neuen Knoten werden mit temporären Markierungen markiert, und der Knoten, welcher der Station Kyobashi auf der Ginza-Linie entspricht, wird mit einer permanenten Markierung markiert. Demgemäß sind am gegenwärtigen Punkt die folgenden temporären Markierungen vorhanden.
Station Otemachi, Marunouchi-Linie:
(Station Tokyo, Marunouchi-Linie → Marunouchi-Linie, 5 Minuten)
Station Ginza, Marunouchi-Linie:
(Station Tokyo, Marunouchi-Linie → Marunouchi-Linie, 5 Minuten)
Station Ginza, Ginza-Linie:
(Station Kyobashi, Ginza-Linie → Ginza-Linie, 5 Minuten)
Station Nihombashi, Ginza-Linie:
(Station Kyobashi, Ginza-Linie → Ginza-Linie, 6 Minuten)
Weiter sind die folgenden permanenten Markierungen vorhanden.
Startpunkt: (*, 0 Minuten)
Station Tokyo, Marunouchi-Linie: (Startort, 3 Minuten)
Station Kyobashi, Ginza-Linie: (Startort, 4 Minuten)
Nachfolgend wird bzw. werden unter den Knoten, die temporäre Markierungen tragen, ein Knoten oder Knoten von niedrigstem Potenzial gesucht. In diesem Fall werden drei in Frage kommende Knoten (5 Minuten) gefunden. Hier wird der Knoten, welcher der Station Tokyo auf der Marunouchi-Linie entspricht, als Knoten v betrachtet.
Wenn die oben beschriebene Verarbeitung fortgesetzt wird, bis der Knoten v den Zielort erreicht, werden die folgenden permanenten Markierungen erhalten.
Startpunkt: (*, 0 Minuten)
Station Tokyo, Marunouchi-Linie: (Startort, 3 Minuten)
Station Kyobashi, Ginza-Linie: (Startort, 4 Minuten)
Station Otemachi, Marunouchi-Linie:
(Station Tokyo, Marunouchi-Linie → Marunouchi-Linie, 5 Minuten)
Station Ginza, Marunouchi-Linie:
(Station Tokyo, Marunouchi-Linie → Marunouchi-Linie, 5 Minuten)
Station Ginza, Ginza-Linie:
(Station Kyobashi, Ginza-Linie → Ginza-Linie, 5 Minuten)
Station Nihombashi, Ginza-Linie:
(Station Kyobashi, Ginza-Linie → Ginza-Linie, 6 Minuten)
Station Awajicho, Marunouchi-Linie:
(Station Otemachi, Marunouchi-Linie → Marunouchi-Linie, 7 Minuten)
Station Kasumigaseki, Marunouchi-Linie:
(Station Ginza, Marunouchi-Linie → Marunouchi-Linie, 7 Minuten)
Station Shimbashi, Ginza-Linie:
(Station Ginza, Ginza-Linie → Ginza-Linie, 7 Minuten)
Station Mitsukohimae, Ginza-Linie:
(Station Nihombashi, Ginza-Linie → Ginza-Linie, 7 Minuten)
Station Ginza, Hibiya-Linie:
(Station Ginza, Marunouchi-Linie → Gehen, 8 Minuten)
Station Otemachi, Hibiya-Linie:
(Station Otemachi, Hibiya-Linie → Gehen, 8 Minuten)
Station Kandabashi, Ginza-Linie:
(Station Mitsukoshimae, Ginza-Linie → Ginza-Linie, 8 Minuten)
Station Nihombashi, Hibiya-Linie:
(Station Nihombashi, Ginza-Linie → Gehen, 9 Minuten)
Station Nihombashi, Toei-Asakusa-Linie:
(Station Nihombashi, Ginza-Linie → Gehen, 9 Minuten)
Station Hibiya, Hibiya-Linie:
(Station Ginza, Hibiya-Linie → Hibiya-Linie, 9 Minuten)
Station Takaracho, Toei-Asakusa-Linie:
(Station Nihombashi, Toei-Asakusa-Linie → Toei-Asakusa- Linie, 10 Minuten)
Station Higashi-Ginza, Hibiya-Linie:
(Station Ginza, Hibiya-Linie → Hibiya-Linie, 10 Minuten)
Station Kasumigaseki, Hibiya-Linie:
(Station Kasumigaseki, Marunouchi-Linie → Gehen, 10 Minuten)
Station Shimbashi, Toei-Asakusa-Linie:
(Station Shimbashi, Ginza-Linie → Gehen, 10 Minuten)
Station Takebashi, Hibiya-Linie:
(Station Otemachi, Hibiya-Linie → Otemachi, 10 Minuten)
Zielort:
(Station Mitsukoshimae, Ginza-Linie → Gehen, 10 Minuten)
Demgemäß erfordert es 10 Minuten, um den Zielort zu erreichen. Die Route minimaler Kosten von dem Startort zu dem Zielort kann dadurch erhalten werden, dass man den permanenten Markierungen rückwärts von dem Zielort aus folgt. In dem in Fig. 4 gezeigten Ablaufdiagramm kann die Ankunft an dem endgültigen "Zielort: (Station Mitsukoshimae, Ginza-Linie → Ge hen, 10 Minuten)" detektiert werden durch den Vorgang des Markierens des Knotens v entsprechend dem Zielort mit einer permanenten Markierung während des Endprozesses.
Da die Markierung des Zielorts "Zielort: (Station Mitsukoshimae, Ginza-Linie → Gehen, 10 Minuten)" ist, ist ein Verbindungsglied, welches zuerst den Zielort erreicht hat, "Station Mitsukoshimae, Ginza-Linie → Gehen". Ein nachfolgendes Überprüfen der Markierung des Knotens entsprechend der Station Mitsukoshimae, Ginza-Linie zeigt, dass die Markierung (Station Nihombashi, Ginza-Linie → Ginza-Linie, 7 Minuten) ist, Demgemäß findet man, dass die Route so bestimmt ist, dass sie von der Station Nihombashi zur Station Mitsukoshimae auf der Ginza-Linie weitergeht. In einer entsprechenden Art und Weise wird den permanenten Markierungen rückwärts zu dem Startort gefolgt, der die Markierung (*, 0 Minuten) trägt. Demgemäß wird die Route minimaler Kosten bestimmt. In diesem Fall wird die Route minimaler Kosten wie folgt bestimmt.
Startort → Station Kyobashi, Ginza-Linie → Station Nihombashi, Ginza-Linie → Station Mitsukoshimae, Ginza-Linie → Zielort

Ausführungsform 2

In der vorliegenden Ausführungsform wird ein Gehabschnitt durch "Gehkostenberechnung auf Straßenkartenbasis" bestimmt. Wie in der Ausführungsform 1 wird eine Beförderungsmittelnetzkarte, die in Fig. 6 gezeigt ist, benutzt. Daher unterscheidet sich die vorliegende Ausführungsform von der Ausführungsform 1 nur in der Art und Weise des Bestimmens eines Verbindungsglieds von dem Startort zu einer Zugangsstation oder von einer Abgangsstation zu dem Zielort. In der vorliegenden Ausführungsform werden die Gehkosten durch Benutzung eines Straßennetzes berechnet, das in Fig. 7 gezeigt ist. In Fig. 7 ist jeder Schnittpunkt (Knoten) mit einem Kreis bezeichnet; und jede Straßenabzweigung (Verbindungsglied) ist mit einem Pfeil (→) bezeichnet. Eine Zahl in jedem Kreis bezeichnet eine entsprechende Knotennummer, und eine Zahl in jedem Quadrat bzw. Rechteck bezeichnet eine entsprechende Verbindungsgliednummer. Weiter bezeichnet eine bloße Zahl, die an jedem Verbindungsglied angebracht ist, die entsprechenden Kosten, und die Einheit derselben ist eine Minute (Zeit).
Grundsätzlich kann das in Fig. 4 gezeigte "Markierungsbestimmungsverfahren auf Potenzialbasis" für die "Gehkostenberechnung auf Straßenkartenbasis" benutzt werden. Jedoch müssen in diesem Fall die Kosten eines bestimmten Verbindungsglieds zwischen einer gewissen Station und dem Start- oder Zielort in einen festgelegten Kostenbereich fallen. Daher muss, wenn die "Gehkostenberechnung auf Straßenkartenbasis" gemäß dem Ablaufdiagramm der Fig. 4 ausgeführt wird, der Beurteilungsschritt D1 in dem Ablaufdiagramm der Fig. 4 wie folgt modifiziert werden:
p(v) > P
worin p(v) das Potenzial des Knotens v ist und P für die Kosten steht, die für die Gehabschnitte festgelegt worden sind. Weiter wird in den Endprozess E eine Verarbeitung ausgeführt, um Stationen, die permanente Markierungen tragen, in das Untergrundbahnnetz als in engerer Wahl stehende Zugangsstationen oder in engerer Wahl stehende Abgangsstationen aufzunehmen. Natürlich ist die "Berechnung der Gehkosten" in dem ersten Schritt S unnötig.
Wenn das in der oben beschriebenen Art und Weise modifizierte Programm ausgeführt wird, wird eine Mehrzahl von Stationen erhalten, die permanente Markierungen tragen, und Verbindungsglieder, welche den Startort und in engerer Wahl stehende Zugangsstationen verbinden, sowie Verbindungsglieder, welche in engerer Wahl stehende Abgangsstationen und den Zielort verbinden, werden in die Verbindungsgliedtabelle aufgenommen, die in Fig. 5 gezeigt ist. In einem Beispielsfall, in dem der Startort der Knoten 10 in dem Straßennetz ist (bezeichnet durch einen Doppelkreis in Fig. 7), werden die folgenden in engerer Wahl stehenden Zugangsstationen ausfindig gemacht:
Station Tokyo, Marunouchi-Linie 26 (Route: 10 → 1 → 26, Kosten: 11 Minuten)
Station Kyobashi, Ginza-Linie 14 (Route: 10 → 5 → 14, Kosten: 13 Minuten)
Jede der auf diese Weise ausfindig gemachten Routen wird in das Untergrundbahnnetz als ein einzelnes Verbindungsglied aufgenommen. Das heißt die folgenden Verbindungsglieder werden aufgenommen.
Startort → Station Tokyo, Marunouchi-Linie L1, Kosten: 11 Minuten
Startort → Station Kyobashi, Ginza-Linie L2, Kosten: 13 Minuten
Hier repräsentieren L1 und L2 je eine Verbindungsgliednummer, welche in der Verbindungsgliedtabelle nicht benutzt wird.
Die Bestimmung der Routen von in engerer Wahl stehenden Abgangsstationen zu dem Zielort wird in der gleichen Art und Weise ausgeführt wie jene für Routen von dem Startort zu den in engerer Wahl stehenden Zugangsstationen. Obwohl die Rou tenbestimmung für Zugangsstationen für abgehende Verbindungsglieder ausgeführt wird, werden in der Routenbestimmung für Abgangsstationen nur ankommende Verbindungsglieder der Suchoperation unterworfen, welche rückwärts von dem Zielort aus ausgeführt wird. Jedoch wird das Gehen, anders als im Fall des Fahrens, nicht sehr viel durch Einwegstraßen, Verkehrssignale oder Verkehrsstauungen beeinträchtigt. Daher entsteht kein Problem, selbst wenn die Kosten eines abgehenden Verbindungsglieds dahingehend betrachtet werden, dass sie die gleichen wie jene eines ankommenden Verbindungsglieds sind. Nachdem die auf diese Weise bestimmten neuen Verbindungsglieder in das Untergrundbahnnetz aufgenommen worden sind, wird die Routenbestimmung durch das "Markierungsbestimmungsverfahren auf Potenzialbasis" wie in der Ausführungsform 1 ausgeführt.

ERGEBNISSE BZW. ERFOLGE DER ERFINDUNG

Gegenwärtig hat jede größere Stadt ein entwickeltes Verkehrsnetz. Besonders Untergrundbahnnetze sind so kompliziert wie ein Spinnennetz. Wenn eine Person eine Untergrundbahn benutzt, geht die Person häufig von einem Startort zu einer Zugangsstation und von einer Abgangsstation zu einem Zielort. Jedoch bestimmen konventionelle Systeme eine Route zwischen einer festgelegten Zugangs- und Abgangsstation, während sie die Abschnitte ignorieren, in denen die Person geht. Daher haben solche Systeme einen Nachteil insofern, als selbst dann, wenn die Person Stationen festlegt, die dem Start- und Zielort als Zugangs- und Abgangsstation am nächsten sind, keine Garantie besteht, dass eine bestimmte Route die Kosten minimiert, wenn die Gehabschnitte berücksichtigt werden. Im Gegensatz hierzu kann in der vorliegenden Erfindung eine Route minimaler Kosten zuverlässig bestimmt werden, weil der Start- und Zielort direkt festgelegt werden und eine Route bestimmt wird, welche die Gehabschnitte enthält. Demgemäß ist bei der Routenbestimmung gemäß der vorliegenden Erfindung ei ne ausfindig gemachte Zugangs- oder Abgangsstation nicht notwendigerweise die nächstliegende Station (die Station, die dem Start- oder Zielort am nächsten ist). Jedoch besteht die Garantie, dass die Gesamtkosten (im Allgemeinen die Zeit), welche jene Kosten enthalten, die beim Gehen von Abschnitten eingegangen werden, minimiert sind. Eine Person kann eine Routenbestimmung zum Bestimmen einer Route minimaler Kosten ausführen, während sie nächstliegende Stationen innerhalb eines Bereichs festlegt, welcher der Person vertraut ist. Die vorliegende Erfindung ist auch effektiv, wenn eine solche Routenbestimmung in einem Bereich ausgeführt wird, welcher der Person nicht vertraut ist. Außerdem ist, da der Benutzer im Gegensatz zur Zugangs- und Abgangsstation den Start- und Zielort direkt festlegen kann, der Vorgang des Festlegens einfach, wobei die Gesamtkosten genauer berechnet werden können.
Uns begegnet oft eine Situation, in der eine Person uns fragt: "Welche Station ist die günstigste von hier aus?" Die vorliegende Erfindung eliminiert die Notwendigkeit einer solchen Frage, weil der Benutzer den Start- und Zielort festlegen kann, zwischen denen Gehabschnitte vorhanden sind. Weiter kann es die vorliegende Erfindung mit einer Forderung zum Suchen einer nächstliegenden Station (zu Fuß) aufnehmen. In diesem Fall wird die "Gehkostenberechnung auf Straßenkartenbasis unabhängig von anderen Berechnung ausgeführt, um eine Station niedrigsten Potenzials ausfindig zu machen. Demgemäß kann die nächstliegende Station mit Leichtigkeit ausfindig gemacht werden. Die vorliegende Erfindung stellt eine solche Flexibilität zur Verfügung.
In der vorliegenden Erfindung werden zwei Verfahren vorgeschlagen, um in engerer Wahl stehende Zugangsstationen und in engerer Wahl stehende Abgangsstationen zu bestimmen. In dem Verfahren, in dem die "Gehkostenberechnung auf der Basis ge radliniger Entfernung" angewandt wird, werden in engerer Wahl stehende Zugangsstationen und in engerer Wahl stehende Abgangsstationen aufgrund der Annahme ausgewählt, dass die Kosten von jedem Gehabschnitt proportional zu der geradlinigen Entfernung zwischen dem Start- und dem Endpunkt des Abschnitts sind. Im Allgemeinen schneiden sich in einer größeren Stadt die Straßen senkrecht zueinander, und es besteht eine Möglichkeit, dass im schlechtesten Fall ein Fehler erzeugt wird, welcher der geradlinigen Entfernung x entspricht (angenähert 1,4). Wenn z. B. die maximalen Gehkosten dahingehend festgelegt werden, dass sie 10 Minuten sind, können in engere Wahl kommende Stationen herausgezogen werden, die bis zu etwa 14 Minuten erfordern. In einigen Fällen muss dieser Punkt in Betracht gezogen werden, wenn man ein Routenbestimmungsprogramm programmiert. In einem exemplarischen Fall, der in Fig. 8 gezeigt ist, worin eine Person von der Stelle A zu der Stelle B längs einer Route A → D → E → F → G → B geht, was die Person zwingt, eine rechtwinklige Wendung an jeder zwischenliegenden Stelle zu machen, kann die Entfernung (oder können die Kosten) der Route genauer durch Berechnung einer Summe der Längen der beiden Seiten eines rechtwinkligen Dreiecks ABC oder AC + CB erhalten werden. Selbst wenn jedoch eine solche Berechnung nicht angewandt wird, werden die Merkmale der vorliegenden Erfindung, d. h. die Vereinfachung der Programmierung und die Befähigung, die Verarbeitung innerhalb einer verkürzten Zeitdauer zu vollenden, nicht ausgeschaltet. Das wichtige Merkmal hier ist die Fähigkeit des automatischen Bestimmens einer Route einschließlich der Gehabschnitte, ohne einen nicht akzeptierbaren Fehler zu erzeugen.
Mittlerweile ist zu sagen, dass, um genaue Gehkosten zu berechnen, die "Gehkostenberechnung auf Straßenkartenbasis" in der Ausführungsform 2 angewandt wird. Da die Gehkosten durch eine Verarbeitung erhalten werden können, die fast die glei ehe wie jene für das "Markierungsbestimmungsverfahren auf Potenzialbasis" ist, können Teile, die einem Programm für die Berechnung der Gehkosten und einem Programm für das Markierungsbestimmungsverfahren gemeinsam sind, in der Form von Unterprogrammen bzw. Subroutinen programmiert werden, was eine beträchtliche Zunahme in der Größe der Programme verhindert. Obwohl die "Gehkostenberechnung auf Straßenkartenbasis", verglichen mit der "Gehkostenberechnung auf der Basis geradliniger Entfernung" eine längere Verarbeitungszeit erfordert, ist die erstere insofern vorteilhafter, als die erstere die Gehkosten genau berechnen und einem Benutzer eine detaillierte Route innerhalb jedes Gehabschnitts zur Verfügung stellen kann.

Claims

1. Verfahren zum Bestimmen einer Route von einem Startort (s) zu einem Zielort (t) innerhalb eines Verkehrsnetzes mittels Benutzung eines Computers, in welchem Verkehrsnetz die Orte als Knoten (u-x) repräsentiert sind, und eine Route zwischen benachbarten Knoten (u-x) als ein Verbindungsglied (a- c) repräsentiert ist, wobei die Bestimmung gemäß einem Markierungs- bzw. Labelbestimmungsverfahren ausgeführt wird, das ein Straßennetz benutzt, welches von Karten- bzw. Landkartendaten erzeugt worden ist, die geographische Breiten/Längeninformation enthalten, unter den Bedingungen von minimalen Kosten, während die Reise- bzw. Fahrzeit oder die Reise- bzw. Fahrstrecke als Kosten bewertet wird, wobei das Verfahren gekennzeichnet ist durch die folgenden Schritte:

(1) Berechnen der Kosten einer Gehroute von dem Startort (s) bis zu wenigstens einer Zugangsstation eines zu benutzenden Verkehrs- bzw. Beförderungsmittelnetzes, und der Kosten einer Gehroute von wenigstens einer Abgangsstation des Verkehrs- bzw. Beförderungsmittelnetzes zu dem Zielort (t), wobei die Gehrouten durch das Markierungs- bzw. Labelbestimmungsverfahren bestimmt werden; und

(2) Aufnehmen der Gehrouten als Verbindungsglieder (a- c) , welche die berechneten Kosten haben, in das Verkehrsnetz, welches das Verkehrs- bzw. Beförderungsmittelnetz umfasst, um ein umfassendes Verkehrsnetz darzustellen, um dadurch den Computer zu befähigen, eine Route unter gewünschten Kostenbedingungen gemäß dem Markierungs- bzw. Labelbestimmungsverfahren zu bestimmen.

2. Verfahren zum Bestimmen einer Route gemäß Anspruch 1, worin die jede der Gehrouten betreffenden Kosten in einen vorgesehenen bzw. festgelegten Kostenbereich fallen, und worin das Markierungs- bzw. Labelbestimmungsverfahren die Gehrouten unter gewünschten Kostenbedingungen bestimmt.

3. Verfahren zum Bestimmen einer Route gemäß Anspruch 1, worin die wenigstens eine Zugangsstation derart gewählt wird, dass ihre geradlinige Entfernung, gemessen von dem Startort (s) aus, in einen vorbestimmten Bereich fällt, und die wenigstens eine Abgangsstation derart gewählt wird, dass ihre geradlinige Entfernung, gemessen von dem Zielort (t) aus, in den vorbestimmten Bereich fällt, worin die Kosten der Gehroute von dem Startort (s) zu der Zugangsstation und die Kosten der Gehroute von der Abgangsstation zu dem Zielort (t) auf der Basis der jeweiligen geradlinigen Entfernungen berechnet werden.

4. Verfahren zum Bestimmen einer Route gemäß irgendeinem der Ansprüche 1-3, worin das Markierungs- bzw. Labelbestimmungsverfahren Markierungen bzw. Labels benutzt, von denen jede bzw. jedes aus dem Namen eines Verbindungsglieds (a-c) besteht, das einen Startknoten und einen speziellen Knoten verbindet, und ein Potenzial (p), das kumulative Kosten von dem Startknoten bis zu dem speziellen Knoten angibt, und folgendes umfasst:

eine Verarbeitungsroutine (1), in welcher der Startknoten mit einer temporären Markierung (*, 0) markiert wird, und jeder der übrigen Knoten mit einer temporären Markierung (Φ, ∞) während der Anfangswerteinstellung markiert wird, worin "*" bedeutet, dass kein Verbindungsglied den Startknoten erreicht, "Φ" bedeutet, dass kein Verbindungsglied schon den entsprechenden Knoten erreicht hat, und "∞" bedeutet einen numerischen Wert, welcher genügend groß innerhalb des Kontexts eines relevanten Problems ist;

eine Verarbeitungsroutine (2), in welcher unter den Knoten, die temporäre Markierungen tragen, ein Knoten ausgewählt wird, der das niedrigste Potenzial hat, wobei, wenn der ausgewählte Knoten der Zielort (t) ist, die Routenbestimmung beendet wird, und die Verarbeitungsroutine (4) ausgeführt wird, und wenn der ausgewählte Knoten nicht der Zielort (t) ist, die Verarbeitungsroutine (3) sukzessive bzw. nacheinander ausgeführt wird;

eine Verarbeitungsroutine (3), in welcher das Potenzial (p) eines Endknotens, der von dem Knoten her verbunden ist, welcher das niedrigste Potenzial hat, und welcher eine temporäre Markierung hat, berechnet wird, wobei, wenn das auf diese Weise berechnete Potenzial des Endknotens niedriger als das Potenzial ist, welches durch die temporäre Markierung des Endknotens angegeben wird, das durch die temporäre Markierung angegebene Potenzial des Endknotens durch das berechnete Potenzial des Endknotens ersetzt wird, wobei die temporäre Markierung des Knotens, der das niedrigste Potenzial hat, permanent gemacht wird, und die Verarbeitungsroutine (2) ausgeführt wird; und

eine Verarbeitungsroutine (4), in der permanenten Markierungen von dem Zielort (t) aus rückwärts zu dem Startort (s) gefolgt wird, um eine Route des niedrigsten Potenzials, einschließlich der Gehrouten, zu bestimmen.

5. System zum Bestimmen einer Route von einem Startort (s) zu einem Zielort (t) innerhalb eines Verkehrsnetzes mittels Benutzung eines Computers, in welchem Verkehrsnetz die Orte als Knoten (u-x) repräsentiert werden, und eine Route zwischen benachbarten Knoten (u-x) als ein Verbindungsglied (a- c) repräsentiert wird, wobei die Bestimmung gemäß einem Markierungs- bzw. Labelbestimmungsverfahren ausgeführt wird, das ein Straßennetz benutzt, welches von Karten- bzw. Landkarten daten erzeugt worden ist, die geographische Breiten/Längeninformation enthalten, unter den Bedingungen von minimalen Kosten, während die Reise- bzw. Fahrzeit oder die Reise- bzw. Fahrstrecke als Kosten bewertet wird, wobei das System gekennzeichnet ist durch die folgenden Schritte:

(1) Mittel zum Berechnen der Kosten einer Gehroute von dem Startort (s) bis zu wenigstens einer Zugangsstation eines zu benutzenden Verkehrs- bzw. Beförderungsmittelnetzes, und der Kosten einer Gehroute von wenigstens einer Abgangsstation des Verkehrs- bzw. Beförderungsmittelnetzes zu dem Zielort (t) , wobei die Gehrouten durch das Markierungs- bzw. Labelbestimmungsverfahren bestimmt werden; und

(2) Mittel zum Aufnehmen der Gehrouten als Verbindungsglieder (a-c), welche die berechneten Kosten haben, in das Verkehrsnetz, welches das Verkehrs- bzw. Beförderungsmittelnetz umfasst, um ein umfassendes Verkehrsnetz darzustellen, um dadurch den Computer zu befähigen, eine Route unter gewünschten Kostenbedingungen gemäß dem Markierungs- bzw. Labelbestimmungsverfahren zu bestimmen.

6. System zum Bestimmen einer Route gemäß Anspruch 5, worin die jede der Gehrouten betreffenden Kosten in einen festgelegten Kostenbereich fallen, und worin das Markierungs- bzw. Labelbestimmungsverfahren die Gehrouten unter gewünschten Kostenbedingungen bestimmt.

7. System zum Bestimmen einer Route gemäß Anspruch 5, worin die Mittel zum Berechnen der Kosten der Gehrouten zum Wählen der wenigstens einen Zugangsstation derart, dass ihre geradlinige Entfernung, gemessen von dem Startort (s) aus in einen vorbestimmten Bereich fällt, und zum Wählen der wenigstens einen Abgangsstation, derart, dass ihre geradlinige Entfernung, gemessen von dem Zielort (t) aus in den vorbestimmten Bereich fällt, vorgesehen werden, worin die Mittel zum Be rechnen der Kosten der Gehrouten die Kosten der Gehroute von dem Startort (s) aus zu der Zugangsstation und die Kosten der Gehroute von der Abgangsstation bis zu dem Zielort (t) auf der Basis der jeweiligen geradlinigen Entfernungen berechnen.

8. System zum Bestimmen einer Route gemäß irgendeinem der Ansprüche 5-7, worin das Markierungs- bzw. Labelbestimmungsverfahren Markierungen bzw. Labels benutzt, von denen jede bzw. jedes aus dem Namen eines Verbindungsglieds (a-c) besteht, das einen Startknoten und einen speziellen Knoten verbindet, und einem Potenzial (p), das kumulative Kosten von dem Startknoten bis zu dem speziellen Knoten angibt, und folgendes umfasst:

eine Verarbeitungsroutine (1), in welcher der Startknoten mit einer temporären Markierung (*, 0) markiert wird, und jeder der übrigen Knoten mit einer temporären Markierung (Φ ∞) während der Anfangswerteinstellung markiert wird, worin "*" bedeutet, dass kein Verbindungsglied den Startknoten erreicht, "Φ" bedeutet, dass kein Verbindungsglied schon den entsprechenden Knoten erreicht hat, und "∞" einen numerischen Wert bedeutet, welcher genügend groß innerhalb des Kontexts eines relevanten Problems ist;

eine Verarbeitungsroutine (2), in welcher unter den Knoten, die temporäre Markierungen tragen, ein Knoten ausgewählt wird, der das niedrigste Potenzial hat, wobei, wenn der ausgewählte Knoten der Zielort (t) ist, die Routenbestimmung beendet wird, und die Verarbeitungsroutine (4) ausgeführt wird, und wenn der ausgewählte Knoten nicht der Zielort (t) ist, die Verarbeitungsroutine (3) sukzessiv bzw. nacheinander ausgeführt wird;

eine Verarbeitungsroutine (3), in welcher das Potenzial (p) eines Endknotens, der von dem Knoten her verbunden ist, welcher das niedrigste Potenzial hat, und welcher eine temporäre Markierung hat, berechnet wird, wobei, wenn das auf die se Weise berechnete Potenzial des Endknotens niedriger als das Potenzial ist, welches durch die temporäre Markierung des Endknotens angegeben wird, das durch die temporäre Markierung angegebene Potenzial des Endknotens durch das berechnete Potenzial des Endknotens ersetzt wird, wobei die temporäre Markierung des Knotens, der das niedrigste Potenzial hat, permanent gemacht wird, und die Verarbeitungsroutine (2) ausgeführt wird; und

eine Verarbeitungsroutine (4), in der permanenten Markierungen von dem Zielort (t) rückwärts zu dem Startort (s) gefolgt wird, um eine Route des niedrigsten Potenzials, einschließlich der Gehrouten, zu bestimmen.