DE69421563T2

DE69421563T2 - Ermittlung einer empfohlenen Route in einem Führungsgerät

Info

Publication number: DE69421563T2
Application number: DE69421563T
Authority: DE
Inventors: Makoto Fushimi; Yoshiki Ueyama; Takeshi Yagyu
Original assignee: Matsushita Electric Industrial Co Ltd
Current assignee: Panasonic Corp
Priority date: 1993-05-12
Filing date: 1994-05-11
Publication date: 2000-04-06
Anticipated expiration: 2014-05-12
Also published as: EP0624860B1; JP3027899B2; KR0141443B1; JPH06323863A; EP0624860A1; US5475598A; DE69421563D1

Description

1. Erfindungsfeld

Die vorliegende Erfindung betrifft eine Führungsvorrichtung mit einer Routenempfehlung, um ein Fahrzeug effizient von einem bestimmten Punkt zu einem anderen Punkt zu führen, indem automatisch eine empfohlene Route zwischen den Punkten ausgewählt und eine Führung entlang derselben vorgesehen wird.

2. Stand der Technik

Aus "Motorola Technical Developments", volume 13, July 1991, Shaumburg, Illinois, USA pp. 58-59 ist ein Routenplanungssystem mit durch den Benutzer auswählbaren Präferenzen bekannt, welches verschiedene Algorithmen für das Durchlaufen einer digitalen Wiedergabe des Straßennetzwerks zwischen zwei Punkten verwendet, um die günstigste Route zwischen diesen zwei Punkten zu ermitteln. Der Routenplanungsalgorithmus kann ein bestimmtes Straßensegment, eine Straße oder einen Bereich spezifizieren, der bevorzugt verwendet wird und der in der Route enthalten sein sollte, auch wenn daraus eine aufwendigere Route resultieren sollte.
Aus der japanischen Patentanmeldung Hei 5-6238 ist ein System des oben genannten Typs bekannt, in dem als Einrichtung zum Setzen der Position ein Hauptschnittpunkt mit der kürzesten Distanz zu dem durch den Benutzer ausgewählten Punkt als Abfahrtpunkt oder Zielpunkt ausgewählt wird oder in dem der Benutzer zwischen verschiedenen vorgeschlagenen Punkten auswählen kann.
Wenn jedoch der Suchstartpunkt oder der Suchendpunkt einfach an einem Schnittpunkt gesetzt wird, der die kürzeste Distanz zu dem Abfahrtpunkt oder dem Zielpunkt aufweist, dann besteht die Möglichkeit, daß eine Route von einem Punkt zu einem Punkt deduziert wird, welche nicht den Absichten des Benutzers entspricht. Ein derartiges Beispiel ist indem Diagramm von Fig. 15(a) gezeigt, das ein beispielhaftes Straßennetz (auf der Zielseite) darstellt, in welchem eine gewünschte Route nicht durch ein herkömmliches Verfahren zum Setzen der Position erhalten werden kann; und Fig. 15(b) ist ein Diagramm, welches ein Beispiel einer ausgewählte Route zeigt, die durch das herkömmliche Verfahren zum Setzen der Position bestimmt wurde. In Fig. 15(a) ist der Abfahrtpunkt in der Richtung von P(S) gelegen, wobei der Benutzer zu dem durch den schraffierten Bereich angegebenen Punkt fahren möchte und die Position bei Punkt P(U) setzt. Es soll angenommen werden, daß zu diesem Zeitpunkt die Distanzen vom Punkt P(U) zu den Schnittpunkten N0, N1, N2 die folgende Beziehung aufweisen:
P(U)-N0-Distanz < P(U)-N2-Distanz < P(U)-N1-Distanz
Wenn unter diesen Umständen angenommen wird, daß der Suchendpunkt der dem Punkt P(U) nächste Schnittpunkt soll, dann wird der Schnittpunkt N0 als der Suchendpunkt ausgewählt, so daß die in Fig. 15(b) gezeigte Route ausgewählt wird. Das bedeutet, daß eine Route ausgewählt werden kann, welche an der Vorderseite des Zielpunktes vorbei und dann zur Rückseite desselben führt. Neben dem Setzen der Position läßt das Verfahren den Benutzer einen Schnittpunkt aus mehreren vorgeschlagenen Schnittpunkten auswählen, wobei der Benutzer jedoch nicht immer mit der Geometrie der Nachbarschaft der Eingabeposition vertraut sein kann, so daß die tatsächliche Eingabeprozedur verkompliziert wird. Es ist deshalb eine erste Aufgabe, keine falsche, etwa am Ziel vorbeiführende Route auszuwählen, ohne daß dafür eine neue Eingabeoperation erforderlich gemacht wird.
Nach der Erfüllung der ersten Aufgabe besteht eine zweite Aufgabe darin, einen Schnittpunkt nahe der gesetzten Position auszuwählen.
Es ist eine dritte Aufgabe, zu verhindern, daß ein Suchstartpunkt oder ein Suchendpunkt an einem Schnittpunkt gesetzt wird, der von der Straße nahe der durch den Benutzer gesetzten Position entfernt ist.
Nach der Erfüllung der dritten Aufgabe besteht eine vierte Aufgabe darin, eine Route für das Führen in der effizientesten Richtung auszuwählen, um den Zielpunkt zu erreichen.

Zusammenfassung der Erfindung

Um die Probleme zu lösen, ist eine erste Einrichtung der vorliegenden Erfindung eine Suchstart-/Suchendpunkt-Setzeinrichtung zum Auswählen einer Vielzahl von Schnittpunkten als Suchstartpunkt oder Suchendpunkt aus der Positionsinformation des durch die Positionssetzeinrichtung gesetzten Abfahrtpunkts und Zielpunkts.
Eine zweite Einrichtung fügt zu der Suchstart-/Suchendpunkt-Setzeinrichtung in der ersten Einrichtung den Prozeß des Setzens von Anfangskosten beim Start der Suche oder von Zusatzkosten beim Erreichen des Suchendpunktes in Abhängigkeit von der Distanz zwischen dem durch die Positionssetzeinrichtung gesetzten Abfahrtspunkt oder Zielpunkt und dem durch die Suchstart-/Suchendpunkt-Setzeinrichtung gesetzten Suchstartpunkt oder Suchendpunkt hinzu.
Eine dritte Einrichtung ist die Suchstart-/Suchendpunkt-Setzeinrichtung zum Auswählen von einer oder mehrere Straßen aus der Positionsinformation des durch die Positionssetzeinrichtung gesetzten Abfahrtspunktes oder Zielpunktes sowie von einem Schnittpunkt aus den Schnittpunkten an beiden Enden, der in Übereinstimmung mit der Verkehrsregelungsinformation erreicht werden kann.
Eine vierte Einrichtung fügt zu der Suchstart-/Suchendpunkt-Setzeinrichtung in der dritten Einrichtung den Prozeß des Findens des nächsten Punktes auf jeder Straße vom dem durch die Positionssetzeinrichtung gesetzten Abfahrtspunkt oder Zielpunkt und des Setzens von Anfangskosten beim Start der Suche oder von Zusatzkosten beim Erreichen des Suchendpunkts mit der Summe aus den Kosten in Abhängigkeit von der Distanz vom Abfahrtspunkt oder Zielpunkt zum nächsten Punkt und aus den Kosten in Abhängigkeit von der Distanz zwischen diesem Punkt und dem Schnittpunkt an beiden Enden der Straße hinzu.
In Übereinstimmung mit der ersten Einrichtung der vorliegenden Erfindung werden mehrere Schnittpunkt in der Nachbarschaft im Suchstartpunkt oder Suchendpunkt aus der Positionsinformation des durch die Positionssetzeinrichtung in der Suchstartpunkt-/Suchendpunkt- Setzeinrichtung eingegebenen Abfahrtpunktes oder Zielpunktes gesetzt, wird ein Suchstartpunkt an der Richtungsseite des Zielpunktes in der Nähe des Abfahrtpunktes erstellt und wird ein Suchendpunkt in der Richtung des Abfahrtpunktes in der Nähe des Zielpunktes gesetzt, was es ermöglicht, die Auswahl einer Route zu verhindern, welche hinter dem Zielpunkt startet oder über das Ziel hinausgeht.
In Übereinstimmung mit der zweiten Einrichtung werden nach der Erfüllung der durch die erste Einrichtung realisierten Funktion Anfangskosten beim Start der Suche oder Zusatzkosten beim Erreichen des Suchendpunktes in Abhängigkeit von der Distanz vom Abfahrtspunkt oder Zielpunkt aufgestellt, so daß hohe Kosten mit einem sehr weit entfernten Suchstartpunkt oder Suchendpunkt verbunden werden, wodurch verhindert werden kann, daß der Routenstartpunkt oder Routenendpunkt weit von der Position des Abfahrtpunktes oder Zielpunktes entfernt ist.
In Übereinstimmung mit der dritten Einrichtung werden eine oder mehrere Straßen in der Nachbarschaft aus der Positionsinformation des durch die Positionssetzeinrichtung in der Suchstart-/Suchendpunkt-Setzeinrichtung eingegebenen Abfahrtpunktes oder Zielpunktes ausgewählt, und alle Schnittpunkte aus den Schnittpunkten an beiden Enden, die in Übereinstimmung mit der Verkehrsregelungsinformation erreicht werden können, werden in dem Suchstartpunkt oder Suchendpunkt gesetzt, wodurch verhindert werden kann, daß der Suchstartpunkt oder der Suchendpunkt an Schnittpunkten von anderen Straßen gesetzt wird, auch wenn die dem durch den Benutzer gesetzten Abfahrtspunkt oder Zielpunkt nächste Straße eine lange Verbindung ist und kein Schnittpunkt in der Nähe liegt.
In Übereinstimmung mit der vierten Einrichtung werden nach der Erfüllung der durch die dritte Einrichtung realisierten Funktion Punkte auf jeder Straße bestimmt, die dem Abfahrtspunkt oder Zielpunkt am nächsten liegen, und sind durch das Setzen von Anfangskosten beim Start der Suche oder von Zusatzkosten beim Erreichen des Suchendpunktes mit der Summe aus den Kosten in Abhängigkeit von der Distanz zwischen dem nächsten Punkt und dem Abfahrtspunkt oder Zielpunkt und aus den Kosten in Abhängigkeit von der Distanz zwischen diesem Punkt und dem Schnittpunkt an beiden Enden der Straße hohe Kosten mit einem ungeeigneten Suchstartpunkt und Suchendpunkt für das Gelangen vom Abfahrtspunkt zum Zielpunkt verbunden, wodurch die Auswahl einer geeigneten Route vom Abfahrtspunkt zum Zielpunkt ermöglicht wird.

Kurzbeschreibung der Zeichnungen:

Fig. 1 ist ein Blockdiagramm einer Führungsvorrichtung mit Routenempfehlung, welches die erste bis vierte Ausführungsformen der vorliegenden Erfindung zeigt.
Fig. 2(a) ist ein Diagramm, welches ein Beispiel eines Straßennetzes in der ersten Ausführungsform der vorliegenden Erfindung zeigt.
Fig. 2(b) ist ein Diagramm, welches ein Beispiel der Knoteninformationsdaten in dem Straßennetzwerk in der ersten Ausführungsform der vorliegenden Erfindung zeigt.
Fig. 2(c) ist ein Diagramm, welches ein Beispiel der Verbindungsinformationsdaten in dem Straßennetzwerk in der ersten Ausführungsform der vorliegenden Erfindung zeigt.
Fig. 3 ist ein Flußdiagramm, welches den gesamten Betrieb der Führungsvorrichtung mit Routenempfehlung in der ersten bis vierten Ausführungsform der vorliegenden Erfindung zeigt.
Fig. 4 ist ein Flußdiagramm des Prozesses zum Setzen der Position in der ersten Ausführungsform der vorliegenden Erfindung.
Fig. 5 ist ein Flußdiagramm des Prozesses zum Suchen der Route in der ersten bis vierten Ausführungsform der vorliegenden Erfindung.
Fig. 6(a), (b), (c) sind ein Flußdiagramm des Suchprozesses auf der Abfahrtsseite in der ersten bis vierten Ausführungsform der vorliegenden Erfindung.
Fig. 7(a), (b), (c) sind ein Flußdiagramm des Suchprozesses auf der Zielseite in der ersten bis vierten Ausführungsform der vorliegenden Erfindung.
Fig. 8(a) ist ein Diagramm, welches ein Beispiel des Straßennetzes in der zweiten Ausführungsform der vorliegenden Erfindung zeigt.
Fig. 8(b) ist ein Diagramm, welches ein Beispiel der Knoteninformationsdaten in dem Straßennetzwerk in der zweiten Ausführungsform der vorliegenden Erfindung zeigt.
Fig. 9 ist ein Flußdiagramm eines Prozesses zum Setzen der Position in der zweiten Ausführungsform der vorliegenden Erfindung.
Fig. 10(a) ist ein Diagramm, welches ein Beispiel zum Setzen von anderen Anfangskosten als in der zweiten bis vierten Ausführungsform der vorliegenden Erfindung zeigt (1).
Fig. 10(b) ist ein Diagramm, welches ein Beispiel zum Setzen von anderen Anfangskosten als in der zweiten bis vierten Ausführungsform der vorliegenden Erfindung zeigt (2).
Fig. 11 (a) ist ein Diagramm, welches ein Beispiel eines Straßennetzes in der dritten Ausführungsform der vorliegenden Erfindung zeigt.
Fig. 11 (b) ist ein Diagramm, welches ein Beispiel der Knoteninformationsdaten in dem Straßennetzwerk in der dritten Ausführungsform der vorliegenden Erfindung zeigt.
Fig. 11 (c) ist ein Diagramm, welches ein Beispiel der Verbindungsinformationsdaten in dem Straßennetzwerk in der dritten Ausführungsform der vorliegenden Erfindung zeigt.
Fig. 12(a), (b) sind ein Flußdiagramm des Prozesses zum Setzen der Position in der dritten Ausführungsform der vorliegenden Erfindung.
Fig. 13(a) ist ein Diagramm, welches ein Beispiel des Straßennetzes in der vierten Ausführungsform der vorliegenden Erfindung zeigt.
Fig. 13(b) ist ein Diagramm, welches ein Beispiel der Knoteninformationsdaten in dem Straßennetzwerk in der vierten Ausführungsform der vorliegenden Erfindung zeigt.
Fig. 13(c) ist ein Diagramm, welches ein Beispiel der Verbindungsinformationsdaten in dem Straßennetzwerk in der vierten Ausführungsform der vorliegenden Erfindung zeigt.
Fig. 14(a), (b) sind ein Flußdiagramm des Prozesses zum Setzen der Position in der vierten Ausführungsform der vorliegenden Erfindung.
Fig. 15(a) ist ein Diagramm, welches ein Beispiel (auf der Zielseite) des Straßennetzwerkes zeigt, in welchem die gewünschte Route nicht in dem herkömmlichen Verfahren zum Setzen der Position bestimmt werden kann.
Fig. 15(b) ist ein Diagramm, welches ein Beispiel der durch das herkömmliche Verfahren zum Setzen der Position bestimmten Route zeigt.

Ausführliche Beschreibung der bevorzugten Ausführungsformen

Im folgenden werden bevorzugte Ausführungsformen der vorliegenden Erfindung mit Bezug auf die beigefügten Zeichnungen ausführlich beschrieben.
Fig. 1 ist ein Blockdiagramm einer Führungsvorrichtung mit Routenempfehlung in Übereinstimmung mit einer ersten Ausführungsform der vorliegenden Erfindung. In Fig. 1 gibt das Bezugszeichen 101 eine Straßennetzwerk-Aufzeichnungseinrichtung zum Aufzeichnen von Information zu einem Straßennetzwerk einschließlich von etwa Schnittpunkten, Straßenverbindungen, Koordinaten, Formen und Attributen in der Form von Kartendaten an, gibt das Bezugszeichen 102 eine Positionssetzeinrichtung zum Eingeben der Positionen des Abfahrtpunktes und des Zielpunktes an, gibt das Bezugszeichen 103 eine Suchstart-/Suchendpunkt-Setzeinrichtung zum Setzen des Suchstartpunktes und Suchendpunktes auf den Kartendaten aus dem durch die Positionssetzeinrichtung 102 eingegebenen Abfahrtspunkt und Zielpunkt an, gibt das Bezugszeichen 104 eine Sucheinrichtung zum Auswählen einer Route vom durch die Suchstart-/Suchendpunkt-Setzeinrichtung gesetzten Suchstartpunkt zum Suchendpunkt unter Verwendung der in der Straßennetz-Aufzeichnungseinrichtung 101 gespeicherten Kartendaten an, und gibt das Bezugszeichen 105 eine Ausgabeeinrichtung zum Wiedergeben der in der Sucheinrichtung 104 bestimmten Route als Bild oder Stimme an.
Im folgenden wird der Betrieb der derartig aufgebauten Führungsvorrichtung mit Routenempfehlung in der ersten Ausführungsform beschrieben. Fig. 2(a) ist ein Diagramm, welches ein Beispiel eines Straßennetzwerkes in der ersten Ausführungsform zeigt, Fig. 2(b) ist ein Diagramm, welches ein Beispiel der Knoteninformation in diesem Straßennetzwerk zeigt, und Fig. 2(c) ist ein Diagramm, welches ein Beispiel der Verbindungsinformation in diesem Straßennetzwerk zeigt. Fig. 3 ist ein Flußdiagramm, welches eine ganze Operation der Führungsvorrichtung mit Routenempfehlung in der ersten Ausführungsform der vorliegenden Erfindung zeigt, und Fig. 4 ist ein Flußdiagramm des Prozesses zum Setzen der Position in der ersten Ausführungsform der vorliegenden Erfindung.
Wie in Fig. 2(a) gezeigt, speichert in dem durch zehn Knoten N1 bis N10 und neun Verbindungen L1 bis L9 wiedergegebenen Straßennetzwerk die Straßennetzwerk-Aufzeichnungseinrichtung 101 die Knoteninformation mit wenigstens wie in Fig. 2(b) gezeigt der Knotenpositionsinformation "Länge/Breite" und der Information "Verbindung" zu den Verbindungen, mit welchen der Knoten verbunden ist, sowie die Verbindungsinformation mit wenigstens wie in Fig. 2(c) gezeigt der Information "Verbindungsknoten 1, Verbindungsknoten 2" zu den Knoten an beiden Enden der Verbindung und der Forminformation "Verbindungsform- Differenzdaten" der Verbindung. In Fig. 2(a) gibt Δ(S) den Abfahrtpunkt an, gibt (D) den Zielpunkt an, gibt O einen Knoten an und gibt eine durchgezogene Linie eine Verbindung an (die Dicke gibt dabei den Wichtigkeitsgrad an). Die Geschwindigkeitsangabe von (?? km/h) gibt die durchschnittliche Fahrtgeschwindigkeit auf dieser Straße an. Insbesondere werden hier die Knoteninformation in Fig. 2(b) und die Verbindungsinformation in Fig. 2(c) beschrieben. Zuerst wird die Knoteninformation in Fig. 2(b) erläutert. Die "Länge/Breite"-Information ist die Information der Koordinaten, an welchen jeder Knoten tatsächlich positioniert ist. Wenn eine Karte in zwei Karten unterteilt wird, wird ein Knoten auf jeder Karte am Kreuzungspunkt der Straße mit der Grenze der zwei Karten aufgezeichnet, wobei eine "Nachbarknoten"-Information aufgezeichnet wird, welche die Beziehung des Knotens angibt. Die "Nachbarknoten"-Information ist die Information des Knotens in der benachbarten Karte, welcher tatsächlich derselbe Knoten ist. Im Fall des Straßennetzwerks in Fig. 2(a) wird jedoch der Einfachheit halber eine Karte verwendet, wobei die "Nachbarknoten"-Information nicht verwendet wird. Die "Verbindung"-Information ist die Information, welche angibt, mit welchen Verbindungen der Knoten verbunden ist. Im folgenden wird die Verbindungsinformation in Fig. 2(c) erläutert. Als "Distanz"-Information wird die Distanz auf der tatsächlichen Straße aufgezeichnet und zum Beispiel mit der Einheit Meter angegeben. Diese Information kann zwar aus den weiter unten beschriebenen Verbindungsformdaten berechnet werden, es ist jedoch wegen der erforderlichen Rechenzeit vorzuziehen, diese Information in der Form von Daten vorzusehen. Die "Kosten"-Information variiert mit dem bei der Auswahl der Route verwendeten Kriterium. Um zum Beispiel die Route mit der minimalen Fahrtzeit zu bestimmen, soll angenommen werden, daß die Fahrtzeit in der Verbindung in der Einheit 0,1 s angegeben ist. In diesem Fall gibt (?? km/h) die durchschnittliche Fahrtgeschwindigkeit (pro Stunde) in der Verbindung an. Die Kosten können zwar aus der Distanz und der Geschwindigkeit berechnet werden, wobei es jedoch wegen der für die Berechnung erforderlichen Zeit vorzuziehen ist, die Kosten zuvor aufzuzeichnen. "Verbindungsknoten 1, Verbindungsknoten 2" gibt an, mit welchen Knoten die beiden Enden der Verbindung verbunden sind. Die "Einbahnverkehr"-Information gibt die Einbahnverkehrsregelung an. In dem Diagramm bedeutet "N3 → N2", daß der Verkehr nur in der Richtung vom Knoten N3 zum Knoten N2 erlaubt ist. Die "Verbindungsform-Differenzdaten" zeigen, wie die Verbindung vom "Verbindungsknoten 1" zum "Verbindungsknoten 2" geformt ist, indem sie die Differenzdaten von der Position des "Verbindungsknotens 1" aufzeichnen. Es soll hier angenommen werden, daß der Benutzer die Route erfahren möchte, um vom Abfahrtpunkt Δ zum Zielpunkt in Fig. 2(a) zu gelangen. Die dabei durchgeführte Verarbeitung wird im folgenden ausführlich mit Bezug auf die Flußdiagramme in Fig. 3 und Fig. 4 beschrieben.
Zuerst setzt der Benutzer in Schritt 301 in Fig. 3 den Punkt auf der Abfahrtseite. Diese Verarbeitung ist in Fig. 4 ausführlich beschrieben. In Schritt 401 in Fig. 4 bestimmt der Benutzer die Position der Abfahrtpunktes, indem er einen Cursor bewegt, der zum Beispiel auf der auf einer Kathodenstrahlröhre (CRT) angezeigten Karte erscheint und in ein gewünschtes Koordinatensystem umgesetzt wird, um die Positionsinformation zu erhalten. In Schritt 402 wird um den Koordinatensatz des Abfahrtpunktes herum die Karteninformation innerhalb eines Kreisbereichs mit einem Radius von limit_dist (gestrichelter Kreis in Fig. 2; z. B. ein Bereich von 50 m) gelesen. Wenn sich der Bereich innerhalb dieses Kreises über mehrere Karten erstreckt, müssen mehrere Karten gelesen werden, wobei es aber in dem dargestellten Fall der Einfachheit halber genügen soll, nur eine Karte zu lesen. In Schritt 403 wird sequentiell die Distanz zu jedem der Knoten (N1 bis N12) aus der Länge-/Breite-Information in Fig. 2(b) und aus der in Schritt 401 erhaltenen Positionsinformation des Abfahrtpunktes berechnet, wobei sequentiell N (zum Beispiel vier) kürzeste Distanzen ausgewählt und aufgezeichnet werden. In dem Fall von Fig. 2(a) ist nur der Knoten N3 in dem Bereich des Kreises vorhanden, so daß der Knoten N3 und seine Distanz DN3 gespeichert werden. Als nächstes wird in Schritt 404 geprüft, ob es sich um die Abfahrtseite handelt. Wenn ja, wird in Schritt 405 ein Suchstartpunkt-Flag am Knoten N3 gesetzt. Weiterhin werden in Schritt 406 für jeden vorhergehend ausgewählten Knoten die Anfangskosten beim Start der Suche mit einem spezifischen Wert gesetzt (zum Beispiel 0). Damit schließt die Verarbeitung in Schritt 301 ab.
Als nächstes wird in Schritt 302 die Position an der Zielseite mit derselben Verarbeitung wie in Schritt 301 gesetzt. Der Unterschied gegenüber der Abfahrtseite besteht darin: wenn in Schritt 404 bestimmt wird, daß es sich um die Zielseite handelt, wird in Schritt 407 ein Suchendpunkt-Flag an dem ausgewählten Knoten gesetzt. Durch die Verarbeitung in Schritt 302 werden in dem in Fig. 2(a) gezeigten Beispiel drei Knoten N5, N7, N8 als Suchendpunkt gesetzt. Die Anfangskosten werden ähnlich gehandhabt.
In Schritt 303 wird der Routensuchprozeß ausgeführt. Fig. 5 zeigt ein Flußdiagramm des Routensuchprozesses in der ersten Ausführungsform der vorliegenden Erfindung, Fig. 6(a), (b), (c) zeigen ein Flußdiagramm des Suchprozesses auf der Abfahrtseite in der ersten Ausführungsform der vorliegenden Erfindung, und Fig. 7(a), (b), (c) zeigen ein Flußdiagramm des Suchprozesses auf der Zielseite in der ersten Ausführungsform der vorliegenden Erfindung. Weitere Details werden im folgenden mit Bezug auf diese Diagramme beschrieben. In Schritt 501 wird der Knoten N3 mit dem Suchstartpunkt-Flag in den Abfahrtseite-Suchkandidatzustand versetzt, und werden die Knoten N5, N7 und N8 mit dem Suchendpunkt-Flag in den Zielseite-Suchkandidatzustand versetzt. Als nächstes werden in Schritt 502 andere Knoten als die Knoten im Abfahrtseite- und Zielseite-Suchkandidatzustand initialisiert, um in den Nichtsuch-Zustand versetzt zu werden und um die Anfangskosten unendlich zu setzen. Weiterhin wird in Schritt 503 das maximale Suchbereich-Limit auf den Wert der Suchkosten gesetzt. Dieses maximale Suchbereich-Limit sollte ausreichend größer sein als der Suchbereich (zum Beispiel 10 Stunden). Die Suche wird gestoppt, wenn dieses Limit überschritten wird. In Schritt 504 wird der Abfahrtseite-Suchprozeß ausgeführt. Die Details dieses Prozesses sind in Fig. 6(a), (b), (c) gezeigt und werden in Übereinstimmung mit dem Flußdiagramm beschrieben.
Zuerst wird in Schritt 601 der Knoten mit den geringsten Abfahrtseite-Suchkosten aus den Knoten im Abfahrtseite-Suchkandidatzustand als Bezugsschnittpunkt bestimmt. Dabei weist hier nur der Knoten N3 den Abfahrtseite-Suchkandidatzustand auf, so daß der Knoten N3 der Bezugsschnittpunkt ist. Wenn die Kosten im Fall einer Vielzahl dieselben sind, dann gelten die oben in bezug auf die Abfahrtseite-Suchkandidaten gegebenen Erläuterungen, so daß hier auf weitere Erläuterungen verzichtet werden kann. In Schritt 602 wird entschieden, ob zur Suche auf der Zielseite übergegangen werden soll oder nicht. Dabei ist der Bezugsschnittpunkt vorhanden und wird das maximale Suchbereich-Limit als ausreichend groß angenommen, so daß die Operation zu Schritt 603 fortschreitet. In Schritt 603 wird entschieden, ob die Route etabliert ist oder nicht, indem entschieden wird, ob die Abfahrtseite- Suchkosten die Abfahrtseite-Routenetablierungskosten (Anfangswert: unendlich) überschritten haben. Schließlich wird die Route durch den Zielseite-Suchprozeß bestimmt. Dabei bleiben die Abfahrtseite-Routenetablierungskosten unendlich (Anfangswert) und schreitet die Operation zu dem Prozeß in Schritt 604 fort. In Schritt 604 wird entschieden, ob der Bezugsschnittpunkt ein mit der benachbarten Karte verbundener Knoten (benachbarten Knoten) ist oder nicht. Wenn ja, werden die Prozesse in den Schritten 614, 615, 616 durchgeführt, und wird der Bezugsschnittpunkt auf den benachbarten Knoten der benachbarten Karte übertragen, wobei in dem Straßennetzwerk in Fig. 2(a) der Einfachheit halber nur eine Karte verwendet wird, so daß der benachbarte Knoten nicht in Betracht gezogen wird. In Schritt 605 werden die mit dem Bezugsschnittpunkt verbundenen Verbindungen aufeinanderfolgend als Suchzielverbindungen gesetzt. In Übereinstimmung mit der Knoteninformation von Fig. 2(b) sind vier Verbindungen L1, L2, L3, L4 mit dem Knoten N3 verbunden. Zuerst wird die Verbindung L1 als Untersuchungszielverbindung ausgewählt. Es wird in Schritt 606 geprüft, ob unter Verwendung der Verbindung L1 vom Knoten N3 zum Knoten N1 fortgeschritten werden kann. Wenn wegen einer Einbahnverkehrsbeschränkung nicht vom Knoten N3 zum Knoten N1 fortgeschritten werden kann, springt die Operation zu Schritt 611. Da in Übereinstimmung mit der Verbindungsinformation in Fig. 2(c) die Verbindung L1 eine Verbindung in beiden Richtungen ist, schreitet die Operation zu Schritt 607 fort. In Schritt 607 wird entschieden, ob der andere Knoten der Untersuchungszielverbindung im Zielseite-Suchkandidatzustand ist oder nicht. Wenn der andere Knoten der Untersuchungszielverbindung im Zielseite-Suchkandidatzustand ist, wird mit Schritt 617 fortschreitend bestimmt, ob die Route aufgezeichnet wird oder nicht, wenn die Abfahrtseite und die Zielseite verbunden sind. Dabei ist der andere Knoten N1 der Untersuchungszielverbindung im Nichtsuche-Zustand, so daß die Operation zu Schritt 608 fortschreitet. In Schritt 608 werden die Kosten für das Erreichen des Knotens N1 berechnet. Der Knoten N3 ist der Abfahrtpunkt, die Anfangskosten sind gleich 0, und aus
Knoten zum Erreichen von Knoten N1 ← Kosten zum Erreichen des Bezugsschnittpunktes [Anfangskosten: 0] + Kosten der Untersuchungszielverbindung L1 [43]
ergibt sich, daß die Kosten zum Erreichen von Knoten N1 gleich "43" sind. Als nächstes wird in Schritt 609 entschieden, ob der Knoten N3 bis dahin mit minimalen Kosten erreicht wird. Wenn ein Erreichen mit den geringsten Kosten möglich ist, wird zu Schritt 611 fortgeschritten, wobei das Ergebnis des vorliegenden Suche nicht im Knoten N1 gespeichert wird. Da der Knoten N3 jedoch den Anfangszustand aufweist, wird er jetzt zum erstenmal erreicht. Dementsprechend wird zu Schritt 610 fortgeschritten und wird das Suchergebnis im Knoten N1 gespeichert. Die zu speichernden Daten umfassen folgendes:
vorhergehender Knoten ← Knoten N3
vorhergehende Verbindung ← Verbindung L1
Abfahrtseite-Suchkosten ← 43
Weiterhin wird der Knoten N1 in den Abfahrtseite-Suchkandidatzustand versetzt. Als nächstes wird in Schritt 611 entschieden, ob alle mit dem Knoten N3 verbundenen Verbindungen als Untersuchungszielverbindungen ausgewählt wurden. Es verbleiben die Verbindungen L2, L3 und L4, so daß der Prozeß zu Schritt 605 zurückkehrt. In Schritt 605 wird die Verbindung L2 als Untersuchungszielverbindung ausgewählt. In Schritt 606 wird geprüft, ob auf der Verbindung L2 vom Knoten N3 zum Knoten N2 fortgeschritten werden kann, wobei aus der Verbindungsinformation in Fig. 2(c) bekannt ist, daß der Verkehr in der Fortbewegungsrichtung auf eine Richtung beschränkt ist, so daß die Verarbeitung zu Schritt 607 fortschreitet. Der Prozeß von Schritt 607 zu Schritt 611 wird wie oben beschrieben wiederholt, und das nächste Suchergebnis wird im Knoten N2 gespeichert.
vorhergehender Knoten ← Knoten N3
vorhergehende Verbindung ← Verbindung L2
Abfahrtseite-Suchkosten ← "180"
Weiterhin wird der Knoten N2 in den Abfahrtseite-Suchkandidatzustand versetzt. Da in Schritt 611 die Verbindungen L3 und L4 verbleiben, wird zu Schritt 605 zurückgekehrt und wird L3 als Untersuchungszielverbindung gesetzt. In Schritt 606 kann jedoch wegen der Einbahnverkehrsregelung nicht auf der Verbindung L3 vom Punkt N3 zum Punkt N4 fortgeschritten werden, so daß die Verarbeitung zu Schritt 611 fortschreitet. Das Suchergebnis wird also nicht im Knoten N4 gespeichert. In Schritt 611 verbleibt L4 als mit dem Knoten N3 zu verbindende Verbindung, so daß zu Schritt 605 zurückgekehrt wird und L4 als Untersuchungszielverbindung gesetzt wird. Bis zu Schritt 606 ist die Operation mit dem Stand der Technik identisch, da jedoch in Schritt 607 ein weiterer Knoten N7 der Untersuchungszielverbindung im Zielseite-Suchkandidatzustand ist, schreitet die Operation zu Schritt 617 fort, um die Route auszuwählen und zu entscheiden. Dabei werden die Gesamtkosten der Route berechnet.
Routengesamtkosten ← Kosten zum Erreichen des Bezugsschnittpunktes N3 [Anfangskosten: 0] + Kosten der Untersuchungszielverbindung [173] + Kosten des Schnittpunkts N7 im Zielseite-Suchkandidatzustand [Anfangskosten: O]
Dementsprechend werden die Routengesamtkosten mit "173" berechnet. Als nächstes wird in Schritt 618 entschieden, ob die berechneten Routengesamtkosten die minimalen Kosten der zuvor bestimmen Routen sind. Wenn es nicht die minimalen Kosten sind und bestimmt wird, daß zuvor eine Route vom Abfahrtpunkt zum Zielpunkt mit geringeren Kosten bestimmt wurde, kehrt die Operation zu Schritt 611 zurück und wird das aktuelle Suchergebnis nicht gespeichert. Da in diesem Fall jedoch die Abfahrtseite und die Zielseite zum erstenmal miteinander verbunden wurden, springt die Operation zu Schritt 619, wobei die folgende Information als Routenverbindung-Punktinformation gespeichert wird.
Abfahrtseite-Verbindungsschnittpunkt ← Knoten N3
Zielseite-Verbindungschnittpunkt ← Knoten N7
Abfahrtseite-Routenetablierungskosten ← "173"
Zielseite-Routenetablierungskosten ← "0"
Routenverbindungsgesamtkosten ← "173"
Verbindung ← Verbindung L4
Dann wird zu Schritt 611 fortgeschritten und entschieden, ob alle mit dem Bezugsschnittpunkt N3 verbundenen Verbindungen als Untersuchungszielverbindungen gesetzt wurden. Da bereits alle Verbindungen untersucht wurden, schreitet die Operation zu Schritt 612 fort. In Schritt 612 wird der Bezugsschnittpunkt N3 in den Abfahrtseite-Suchkandidatzustand versetzt und wird die Suchverarbeitung in bezug auf den Knoten N3 beendet. Es wird zu Schritt 601 zurückgekehrt und es werden alle Knoten untersucht, wobei nach dem Knoten mit den minimalen Abfahrtseite-Suchkosten im Abfahrtseite-Suchkandidatzustand gesucht wird. Dabei weisen in dem vorliegenden Fall die zwei mit dem Knoten N3 verbundenen Knoten N1 und N2 jeweils die Abfahrtseite-Suchkosten "43" und "180" auf und sind im Abfahrtseite- Suchkandidatzustand. Der Knoten N1 ist also der Knoten im Abfahrtseite-Suchkandidatzustand, der gegenwärtig die geringsten Abfahrtseite-Suchkosten aufweist. Dementsprechend wird der Knoten N1 als Bezugsschnittpunkt ausgewählt. Die folgende Verarbeitung in den Schritten 602 bis 608 ist mit der oben beschriebenen identisch (der Nachbarknoten wird nicht berücksichtigt, weil angenommen wird, daß der Einfachheit halber nur eine Karte durchsucht wird), so daß L1 als die Untersuchungszielverbindung wird und "43 + 43" als Suchkosten zum Knoten N3 bestimmt werden. Weil jedoch in Schritt 610 die Anfangskosten "0" als Suchstartpunkt im Knoten N3 gegeben sind, wird entschieden, daß derselbe bis jetzt noch nicht mit minimalen Kosten erreicht wurde, so daß die Operation zu Schritt 611 fortschreitet. In Schritt 611 werden alle mit dem Knoten N1 verbundenen Verbindungen als untersucht bestätigt, wobei zu Schritt 612 fortgeschritten wird und der Knoten N1 in den Abfahrtseite- Suche-abgeschlossen-Zustand versetzt wird. Es wird zu Schritt 601 zurückgekehrt und es wird in ähnlicher Weise N2 als nächster Bezugsschnittpunkt gesetzt. Da in Schritt 603 die Abfahrtseite-Suchkosten "180" des Knotens N2 größer als "173" der Abfahrtseite-Routenetablierungskosten sind, wird zu Schritt 613 fortgeschritten und wird ein Flag gesetzt, um den Kontakt auf der Abfahrtseite in dem Abfahrtseite-Routensuchprozeß anzugeben. Damit wird der Abfahrtseite-Suchprozeß in Schritt 504 beendet.
Es wird als nächstes zu Schritt 505 fortgeschritten und es wird der Zielseite-Suchprozeß durchgeführt. Die Details dieses Prozesses sind in Fig. 7(a), (b), (c) gezeigt. Der Prozeß unterscheidet sich in zwei Punkten von dem Abfahrtseite-Suchprozeß. Erstens wird die Einbahnverkehrsregelung umgekehrt betrachtet, wenn in Schritt 706 geprüft wird, ob die mit dem Bezugsschnittpunkt verbundene Untersuchungszielverbindung durchlaufen werden kann oder nicht, weil die Suche bei der Zielseitensuche in der zur tatsächlichen Fahrtrichtung des Fahrzeugs entgegengesetzten Richtung erweitert wird. Zweitens wird der Kontaktzustand des Zielseite-Suchbereichs und des Abfahrtseite-Suchbereichs in Schritt 707 im Abfahrtseite-Suche-abgeschlossen-Zustand des anderen Knotens der Untersuchungszielverbindung entschieden. In anderen Punkten ist der Suchprozeß mit demjenigen auf der Abfahrtseite identisch. In diesem Fall sind die Knoten N6, N9, N10 im Zielseite-Suchkandidatzustand und weisen jeweils die Zielseite-Suchkosten "90", "90" und "58" auf. Wenn der Knoten N10 als der nächste Bezugsschnittpunkt ausgewählt wird, dann sind die Zielseite- Routenetablierungskosten "0" und sind die Zielseite-Suchkosten "58", so daß auf die Entscheidung in Schritt 703 der Prozeß von Schritt 713 folgt. Hier wird ein Flag gesetzt, um die feste Entscheidung der Zielseitenroute und die Etablierung der gesamten Route zu bestätigen. Damit endet der Zielseite-Suchprozeß in Schritt 505.
Es wird in Schritt 506 bestätigt, daß die Route etabliert wurde. Wenn die Route nicht etabliert wurde, wird ein Suchmißerfolg-Flag in Schritt 507 gesetzt. Da jedoch in diesem Fall das Flag für das Etablieren der gesamten Route in Schritt 713 gesetzt wurde, wird entschieden, daß die gesamte Route in Schritt 506 etabliert wurde, so daß der Routensuchprozeß in Schritt 303 beendet wird.
In Schritt 304 wird geprüft, ob das Suchmißerfolg-Flag gesetzt wurde oder nicht. Wenn die Suche als erfolgreich bestimmt wird, schreitet die Operation zu Schritt 305 fort, wobei die Route durch zum Beispiel das Durchlaufen der bestimmten Route in der Fahrtsequenz in der Reihe der Kartennummer und der Verbindungsnummer (einschließlich der Richtung) gebildet wird. Weiterhin wird die in Schritt 306 bestimmte Route in Übereinstimmung mit der auf der CRT angezeigten Karte für den Benutzer angezeigt. Wenn in Schritt 304 das Suchmißerfolg- Flag gesetzt ist, dann wird ein Suchmißerfolg bestimmt, wobei auf den Suchmißerfolg zum Beispiel dadurch reagiert wird, daß dem Benutzer in Schritt 307 mitgeteilt wird, daß die Route nicht bestimmt wurde. Wenn in diesem Fall die Route aus der Routenpunktverbindungsinformation gebildet wird, dann wird die Route vom Punkt N3 zum Punkt N7 über die Verbindung L4 erhalten. Folglich bleibt das folgende Routenbildungsergebnis:
Kartennummer 1 ← * (nicht erforderlich, weil nur eine Karte verwendet wird)
Verbindungsnummer 1 ← Verbindung L4
Richtung ← von "Verbindungsknoten 1" zu "Verbindungsknoten 2"
Indem auf diese Weise in Übereinstimmung mit der ersten Ausführungsform mehrere Punkte als Abfahrtpunkt oder Zielpunkt in zum Beispiel dem Straßennetzwerk von Fig. 2(a) ausgewählt werden, wird das Ausgeben der vor dem Zielpunkt vorbeiführenden Route in der Sequenz von Knoten N3, Verbindung L4, Knoten N7, Verbindung L7, Knoten N8, Verbindung L5 und Knoten N5 verhindert.
Im folgenden wird eine zweite Ausführungsform der vorliegenden Erfindung beschrieben. Ein Blockdiagramm der Führungsvorrichtung mit Routenempfehlung der zweiten Ausführungsform der vorliegenden Erfindung ist mit demjenigen der ersten Ausführungsform identisch.
Im folgenden wird der Betrieb der derart aufgebauten Führungsvorrichtung mit Routenempfehlung der zweiten Ausführungsform beschrieben. Fig. 8(a) ist ein Diagramm, welches ein Beispiel eines Straßennetzwerks in der zweiten Ausführungsform zeigt, Fig. 8(b) ist ein Diagramm, welches ein Beispiel der Knoteninformation in dem Straßennetzwerk zeigt und Fig. 8(c) ist ein Diagramm, welches ein Beispiel der Verbindungsinformation in dem Straßennetzwerk zeigt. Fig. 9 ist ein Flußdiagramm des Prozesses zum Setzen der Position in der zweiten Ausführungsform der vorliegenden Erfindung.
Mit Bezug auf das Straßennetzwerk von Fig. 8 und das Flußdiagramm des Prozesses zum Setzen der Position in Fig. 9 wird im folgenden der Unterschied zu der ersten Ausführungsform erläutert. Zuerst werden in dem in Fig. 8(a) gezeigten durch zwölf Knoten N1 bis N12 und elf Verbindungen L1 bis L11 wiedergegebenen Straßennetzwerk die in Fig. 8(b) gezeigte Knoteninformation und die in Fig. 8(c) gezeigte Verbindungsinformation in der Straßennetzwerk-Aufzeichnungseinrichtung 101 gespeichert. Die Bezugszeichen sind mit denjenigen von Fig. 2 identisch.
Wenn im Fall dieses Netzwerkes die Route wie in der ersten Ausführungsform bestimmt wird, wenn angenommen wird, daß die in Schritt 403 in Fig. 4 ausgewählte Anzahl der Schnittpunkte N gleich 4 ist, und weil der Knoten N6 in Fig. 8 in einem der Suchendpunkte enthalten ist, dann ist die schließlich auszuwählende Route die Route aus Knoten N3, Verbindung L4 und Knoten N6 mit den geringsten Kosten aus den verschiedenen Verbindungskombinationen der Suchstartpunktgruppe (Knoten N3) und der Suchendpunktgruppe (Knoten N6, N7, N9, N10). Es kann also nur die Route bis zum Knoten N6 bestimmt werden, so daß die Route nur bis zu einem beträchtlich vom Zielpunkt entfernten Punkt bekannt ist. Dieses Problem wird in der zweiten Ausführungsform gelöst, indem der Prozeß zum Setzen der Position wie in Fig. 9 gezeigt variiert wird.
Der Prozeß zum Setzen der Position in der zweiten Ausführungsform unterscheidet sich von dem Prozeß zum Setzen der Position in der ersten Ausführungsform durch das Setzen der Anfangskosten in Schritt 906. In der ersten Ausführungsform wird allgemein derselbe Wert (0) wie in Schritt 406 gezeigt verwendet, während in der zweiten Ausführungsform ein zu der Distanz proportionaler Wert wie in Schritt 906 gezeigt vorgesehen wird. Der proportionale Faktor m in Schritt 906 ist eine positive reelle Zahl. Wenn insbesondere eine virtuelle Verbindung VL1 zwischen dem Abfahrtpunkt S und dem Knoten N3 angenommen wird und wenn virtuelle Verbindungen zwischen dem Zielpunkt D und den Knoten N6, N7, N9, N10 angenommen werden, dann werden jeder virtuellen Verbindung Virtuellverbindungskosten in Übereinstimmung mit den Anfangskosten zugewiesen, wobei dasselbe Ergebnis erhalten wird, wie wenn die Route mit minimalen Kosten auf dem Straßennetzwerk einschließlich der virtuellen Verbindung vom Abfahrtpunkt S zum Zielpunkt D bestimmt wird, ohne daß ein Prozeß zu den Kartendaten hinzugefügt wird.
Zum Beispiel ist unter den Verbindungen in Fig. 8(a) die geringste durchschnittliche Fahrtgeschwindigkeit gleich 10 km/h, wobei jedoch ein Wert gleich der Fahrt entlang einer linearen Distanz mit einer Geschwindigkeit von 5 km/h als Anfangskosten gegeben ist. So werden die nächsten Anfangskosten zu dem Knoten N3 gegeben.
5 (m) / 5 (km/h) · 36 (10&supmin;¹ s)
Entsprechend weist jeder Suchstartpunkt und Suchendpunkt die in Tabelle 1 gezeigten Anfangskosten auf. [Tabelle 1.] Beispiel von Anfangskosten am Suchstartpunkt und am Suchendpunkt in der zweiten Ausführungsform
Es gibt vier Kombinationen von Suchstartpunkt und Suchendpunkt. Bei diesen Anfangskosten werden die Gesamtkosten dieser Routen in allen Routenkombinationen Tabelle 2 verglichen. [Tabelle 2.] Gesamtkosten der Routen in Routenkombinationen in der zweiten Ausführungsform
In diesem Fall ist die Route mit minimalen Kosten ein Kanal vom Knoten N3 zum Knoten N9 und sind die Gesamtkosten gleich 353.
Indem die Routensuche wie in der ersten Ausführungsform unter Verwendung der Technik zum Setzen der Position verarbeitet wird, welche ein Merkmal der zweiten Ausführungsform ist, kann die Route mit minimalen Kosten vom Knoten N3, über die Verbindung L4, die Verbindung L6 zum Knoten N9 bestimmt werden, welche den Suchstartpunkt und den Suchendpunkt verbindet. Wie im Fall der Technik zum Setzen der Position in der ersten Ausführungsform kann vermieden werden, daß die Route nur bis zu einem beträchtlich vom Zielpunkt entfernten Punkt bestimmt werden kann, so daß die Route bis kurz vor dem Zielpunkt bestimmt werden kann.
In Schritt 906 in Fig. 9 werden die Anfangskosten proportional zu der Distanz gesetzt, wobei eine Proportionalität jedoch nicht immer erforderlich ist. Fig. 10 zeigt ein Beispiel eines andersartigen Setzens der Anfangskosten. Die Anfangskosten können wie in Fig. 10(a) gezeigt diskontinuierlich sein; der proportionale Koeffizient m kann jedoch auch in Abhängigkeit von der in Fig. 10(b) gezeigten Distanz variiert werden.
Im folgenden wird eine dritte Ausführungsform der vorliegenden Erfindung beschrieben. Ein Blockdiagramm der Führungsvorrichtung mit Routenempfehlung der dritten Ausführungsform der vorliegenden Erfindung ist mit demjenigen der ersten Ausführungsform identisch.
Im folgenden wird der Betrieb der derart aufgebauten Führungsvorrichtung mit Routenempfehlung der dritten Ausführungsform beschrieben. Fig. 11(a) ist ein Diagramm, welches ein Beispiel eines Straßennetzwerks in der dritten Ausführungsform zeigt, Fig. 11(b) ist ein Diagramm, welches ein Beispiel der Knoteninformation in dem Straßennetzwerk zeigt und Fig. 11(c) ist ein Diagramm, welches ein Beispiel der Verbindungsinformation in dem Straßennetzwerk zeigt. Fig. 12(a), (b) zeigen ein Flußdiagramm des Prozesses zum Setzen der Position in der dritten Ausführungsform der vorliegenden Erfindung.
Mit Bezug auf das Beispiel des Straßennetzwerkes von Fig. 11 und das Flußdiagramm des Prozesses zum Setzen der Position in Fig. 12(a), (b) wird im folgenden der Unterschied zu der ersten Ausführungsform erläutert. Zuerst werden in dem in Fig. 11(a) gezeigten durch dreizehn Knoten N1 bis N13 und zwölf Verbindungen L1 bis L12 wiedergegebenen Straßennetzwerk die in Fig. 11(b) gezeigte Knoteninformation und die in Fig. 11(c) gezeigte Verbindungsinformation in der Straßennetzwerk-Aufzeichnungseinrichtung 101 gespeichert. Die Bezugszeichen sind mit denjenigen von Fig. 2 identisch.
Wenn in einem derartigen Netzwerk die Route wie in der ersten und in der zweiten Ausführungsform bestimmt wird, wird nur der Knoten N5 in Fig. 8 als Suchendpunkt ausgewählt, und ist die schließlich ausgewählte Route ein Kanal vom Knoten N3, über die Verbindung L4 zum Knoten N5. Die Route wird also bis zum Knoten N5 bestimmt, so daß die Route nur bis zu einem beträchtlich vom Zielpunkt entfernten Punkt bekannt ist. In der dritten Ausführungsform wird dieses Problem gelöst, indem der Prozeß zum Setzen der Position zu dem in Fig. 12(a), (b) gezeigten Prozeß geändert wird.
Der Prozeß zum Setzen der Position in der dritten Ausführungsform unterscheidet sich von dem Prozeß zum Setzen der Position in der ersten und in der zweiten Ausführungsform darin, daß der Setzstandard des Suchstartpunktes oder des Suchendpunktes jeweils auf die Verbindung oder auf den Punkt gesetzt wird. In der ersten und in der zweiten Ausführungsform wird der Punkt nahe dem Abfahrtpunkt oder dem Zielpunkt als Suchstartpunkt oder Suchendpunkt gewählt, während in der dritten Ausführungsform eine Verbindung nahe der Position des Abfahrtpunktes oder Zielpunktes ausgewählt wird, wobei der Endknoten auf dieser Verbindung als Suchstartpunkt oder Suchendpunkt verwendet wird. Dies wird im folgenden im Detail mit Bezug auf das Flußdiagramm in Fig. 12(a), (b) beschrieben. In Schritt 1201 in Fig. 12(a) bestimmt der Benutzer die Position des Abfahrtpunktes (Zielpunktes), indem er einen Cursor bewegt, welcher auf einer Karte angezeigt wird, die zum Beispiel auf der CRT angezeigt wird, wobei eine Umsetzung zu einem gewünschten Koordinatensystem vorgesehen wird, um die Positionsinformation zu erhalten. In Schritt 1202 wird die Karteninformation in einem Kreisbereich mit dem Radius limit_dist (gestrichelte Linie in Fig. 2: zum Beispiel ein Bereich von 50 m) um die gesetzten Koordinaten des Abfahrtpunktes (Zielpunktes) herum gelesen, wobei der Bereich jedoch in diesem Fall der Einfachheit halber auf eine Karte begrenzt ist. In Schritt 1203 wird die Distanz (die nächste Distanz zu jeder Differenzdatenkomponente) zu jeder Verbindung (L1 bis L12) sequentiell aus der Längengrad- /Breitengradinformation in Fig. 11(b), den Verbindungsformdaten in Fig. 11(c) und der in Schritt 1201 erhaltenen Positionsinformation des Abfahrtpunktes (Zielpunktes) berechnet, wobei die N (zum Beispiel zwei) kürzesten Distanzen sequentiell ausgewählt werden und die Position und die Distanz des Schnittpunktes der vertikalen Linie mit der Verbindung aufgezeichnet werden. In dem Fall von Fig. 12(a) werden auf der Abfahrtseite die Positionskoordinaten von Punkt P1 auf der Verbindung L1 und die Distanz DP1 sowie die Positionskoordinaten von Punkt P2 auf der Verbindung L3 und die Distanz DP2 aufgezeichnet und werden auf der Zielseite die Positionskoordinaten von Punkt P3 auf der Verbindung L8 und die Distanz DP3 sowie die Positionskoordinaten von Punkt P4 auf der Verbindung L11 und die Distanz DP4 aufgezeichnet. In Schritt 1204 wird entschieden, ob es sich um die Abfahrtseite handelt oder nicht. Wenn entschieden wird, daß es sich um die Abfahrtseite handelt, wird zu Schritt 1205 fortgeschritten und werden Suchstartpunkte an den Knoten N1 und N3, die durch die Einbahnverkehrsregelung vom Punkt P1 auf der ausgewählten Verbindung L1 erreicht werden können, und am Knoten N3 gesetzt, der durch die Einbahnverkehrsregelung vom Punkt P2 auf der ausgewählten Verbindung L3 erreicht werden kann. Die Distanz zwischen dem Schnittpunkt P1 und dem Knoten N1 wird im Knoten N1 gespeichert, und die Distanz zwischen dem Schnittpunkt P1 und dem Knoten N3 oder die Distanz zwischen dem Schnittpunkt P2 und dem Knoten N3, je nachdem welche die kürzere ist, wird im Knoten N3 gespeichert. Weiter wird in Schritt 1206 ein Suchstartpunkt-Flag an den ausgewählten Knoten N1, N3 gesetzt. Wenn andererseits in Schritt 1204 entschieden wird, daß es sich um die Zielseite handelt, wird zu Schritt 1208 gesprungen, wo Suchstartpunkte im Knoten N7, von welchem in Übereinstimmung mit der Einbahnverkehrsregelung auf der ausgewählten Verbindung L8 zum Knoten P3 fortgeschritten werden kann, und im Knoten N11 gesetzt werden, von welchem in Übereinstimmung mit der Einbahnverkehrsregelung auf der ausgewählten Verbindung L11 zum Knoten P4 fortgeschritten werden kann. Die Distanz zwischen dem Schnittpunkt P3 und dem Knoten N7 wird im Knoten N7 aufgezeichnet, und die Distanz zwischen dem Schnittpunkt P4 und dem Knoten N11 wird im Knoten N11 aufgezeichnet. Weiter wird in Schnitt 1209 ein Suchendpunkt-Flag auf den ausgewählten Knoten N7, N11 gesetzt. Schließlich wird in Schritt 1207 ein spezifischer Wert (zum Beispiel 0) als Anfangskosten für die Suchstartpunkte (Knoten N1, N3) und Suchendpunkte (Knoten N7, N11) gesetzt. Damit wird der Prozeß zum Setzen der Position beendet.
Übrigens gibt es vier Kombinationen aus Suchstartpunkt und Suchendpunkt, wobei für alle Routenkombinationen die Gesamtkosten dieser Routen in Tabelle 3 verglichen werden. [Tabelle 3.] Beispiele für Gesamtkosten von Routen für die Routenkombinationen in der dritten Ausführungsform
In diesem Fall ist die Route mit minimalen Kosten eine Route vom Knoten N3 zum Knoten N7 mit den Gesamtkosten von 266.
Indem auf diese Weise die Routensuche wie in der ersten und der zweiten Ausführungsform unter Verwendung der Technik zum Setzen der Position verarbeitet wird, welche ein Merkmal der dritten Ausführungsform ist, wird ein Kanal vom Knoten N3, über die Verbindung N4, über die Verbindung L6 zum Knoten N7 als die Route mit den minimalen Kosten bestimmt.
Wie bei der Verwendung der Technik zum Setzen der Position der ersten und der zweiten Ausführungsform wird dabei verhindert, daß die Route bis zu dem Schnittpunkt auf der Straße bestimmt wird, welche von der Straße in der Nähe des Zielpunktes entfernt ist, so daß eine richtige Route zum Erreichen des Zielpunktes bestimmt wird.
In Schritt 1205 in Fig. 12(b) wird währenddessen die Distanz vom Schnittpunkt P1 zum Knoten N3 oder die Distanz vom Schnittpunkt P2 zum Knoten N3, je nachdem welche die kürzere ist, im Knoten N3 aufgezeichnet, wobei jedoch auch die kürzere Gesamtdistanz vom Abfahrtpunkt oder die kürzere Distanz bis zum Ankommen bei der Verbindung aufgezeichnet werden kann. Durch das Speichern der Formdaten zwischen dem Schnittpunkt der vertikalen Linie, welche zuvor vom Abfahrtpunkt auf die Verbindung gezogen wurde, und dem Suchstartpunkt sowie der Formdaten zwischen dem Schnittpunkt der vertikalen Linie, welche zuvor vom Zielpunkt auf die Verbindung gezogen wurde, und dem Suchendpunkt, kann eine Routenanzeige oder -führung zu einem Punkt in der Mitte einer Verbindung durchgeführt werden. Wenn keine vertikale Linie auf die Verbindungsform gezeichnet werden kann, kann der Punkt mit der kürzesten Distanz zum Wendepunkt der Formdaten als Schnittpunkt mit der Verbindung verwendet werden.
Im folgenden wird eine vierte Ausführungsform der vorliegenden Erfindung beschrieben. Ein Blockdiagramm der Führungsvorrichtung mit Routenempfehlung der zweiten Ausführungsform der vorliegenden Erfindung ist mit demjenigen der ersten Ausführungsform identisch.
Im folgenden wird der Betrieb der derart aufgebauten Führungsvorrichtung mit Routenempfehlung der vierten Ausführungsform beschrieben. Fig. 13(a) ist ein Diagramm, welches ein Beispiel eines Straßennetzwerks in der dritten Ausführungsform zeigt, Fig. 13(b) ist ein Diagramm, welches ein Beispiel der Knoteninformation in dem Straßennetzwerk zeigt und Fig. 13(c) ist ein Diagramm, welches ein Beispiel der Verbindungsinformation in dem Straßennetzwerk zeigt. Fig. 14(a), (b) zeigen ein Flußdiagramm des Prozesses zum Setzen der Position in der vierten Ausführungsform der vorliegenden Erfindung.
Der Unterschied zu der dritten Ausführungsform wird im folgenden mit Bezug auf das Straßennetzwerk in Fig. 13 und das Flußdiagramm des Prozesses zum Setzen der Position in Fig. 14(a), (b) erläutert. Zuerst wird wie in Fig. 13(a) gezeigt in dem durch zwölf Knoten N1 bis N12 und elf Verbindungen L1 bis L11 wiedergegebenen Straßennetzwerk die Knoteninformation wie in Fig. 13(b) gezeigt und die Verbindungsinformation wie in Fig. 13(c) gezeigt in der Straßennetzwerk-Aufzeichnungseinrichtung 101 gespeichert. Die Bezugszeichen sind mit denjenigen von Fig. 2 identisch.
Wenn in einem derartigen Netzwerk die Route wie in der ersten und der zweiten Ausführungsform bestimmt wird, wird der Knoten N3 als Suchstartpunkt und der Knoten N6 als Suchendpunkt ausgewählt, so daß die schließlich ausgewählte Route die den Knoten N3 und den Knoten N6 verbindende Route ist, d. h. vom Knoten N3, über die Verbindung L4, über die Verbindung L6 und zum Knoten N6. Die Route wird also nur bis zum Knoten N6 bestimmt, so daß die Route nur bis zu einem beträchtlich vom Zielpunkt entfernten Punkt bekannt ist. Oder wenn die Route wie in der dritten Ausführungsform bestimmt wird, wird der Knoten N3 als Suchstartpunkt ausgewählt und werden die Knoten N5, N8, N9 und N12 als Suchendpunkte ausgewählt, so daß die schließlich ausgewählte Route die Route mit den minimalen Kosten ist, welche die Suchstartpunktgruppe (Knoten N3) und die Suchendpunktgruppe (Knoten N5, N8, N9, N12) miteinander verbindet, d. h. vom Knoten N3, über die Verbindung L4 zum Knoten N5. Dementsprechend wird nur die durch den Knoten N5 hindurchgehende und den Punkt P3 erreichende Route bestimmt, so daß keine richtige, den Zielpunkt erreichende Route bestimmt wird. Dieses Problem wird in der vierten Ausführungsform gelöst, indem der Prozeß zum Setzen der Position zu dem in Fig. 14(a), (b) gezeigten Prozeß geändert wird.
Der Prozeß zum Setzen der Position in der vierten Ausführungsform unterscheidet sich von dem Prozeß zum Setzen der Position in der dritten Ausführungsform durch das Setzen der Anfangskosten in Schritt 1407. In der dritten Ausführungsform war der Wert wie in Schritt 1207 gezeigt allgemein (0), während die Anfangskosten in der vierten Ausführungsform wie in Schritt 1407 gezeigt mit der zu der Distanz der auf der Verbindung gezogenen vertikalen Linie und den Fahrtkosten auf der Verbindung proportionalen Kostensumme gesetzt werden. Dabei sind die proportionalen Koeffizienten m1, m2 in Schritt 1407 positive reelle Zahlen. Wenn die vom Abfahrtpunkt S auf die Verbindung L1 gezogene vertikale Linie eine virtuelle Verbindung VL1 ist (Schnittpunkt mit Verbindung L1 gleich P1), die auf die Verbindung L3 gezogene vertikale Linie eine virtuelle Verbindung VL2 ist (Schnittpunkt mit Verbindung L3 gleich P2), die vom Zielpunkt D auf die Verbindung L5 gezogene vertikale Linie eine virtuelle Verbindung VL3 ist (Schnittpunkt mit Verbindung L5 gleich P3) und die auf die Verbindung L10 gezogene vertikale Linie eine virtuelle Verbindung VL4 ist (Schnittpunkt mit Verbindung L10 gleich P4), dann werden jeder Verbindung virtuelle Verbindungskosten zugewiesen, die den Anfangskosten äquivalent sind, so daß dieselben Effekte erhalten werden, wie wenn die Route mit minimalen Kosten auf dem Straßennetzwerk einschließlich der virtuellen Verbin dungen vom Abfahrtpunkt S zum Zielpunkt D bestimmt werden, ohne daß die Kartendaten verarbeitet werden.
Zum Beispiel ist bei den Verbindungen in Fig. 13(a) die kleinste durchschnittliche Fahrtgeschwindigkeit 10 km/h, wobei aber als virtuelle Verbindungskosten ein Wert gleich einer Fahrtgeschwindigkeit von 5 km/h auf der virtuellen Verbindung gegeben wird. Als Kosten für das Fortschreiten von dem Punkt, wo eine virtuelle Verbindung auf eine gewöhnliche Verbindung trifft, zu dem nächsten Schnittpunkt wird ein Wert gesetzt, welcher die Gesamtkosten einer gewöhnlichen Verbindung in Übereinstimmung mit dem Verhältnis der Fahrtdistanz verteilt. Es werden also die folgenden Anfangskosten in Knoten N3 gesetzt.
[1] 5 (m) / 5 (km/h) · 36 ... virtuelle Verbindungskosten + 43 (Kosten der Verbindung L1) / 60 (m) · 5 (m) ... verteilte Kosten auf Verbindung L1 = 40 (10&supmin;¹ s) [Anfangskosten über die Verbindung L1]
[2] 5 (m) / 5 (km/h) · 36 ... virtuelle Verbindungskosten + 252 (Kosten der Verbindung L3) / 140 (m) · 5 (m) ... verteilte Kosten auf Verbindung L3 = 45 (10&supmin;¹ s) [Anfangskosten über die Verbindung L3]
Die Anfangskosten über die Verbindung L1 sind kleiner als diejenigen über die Verbindung L3, und die Information über die Verbindung L1 wird am Knoten N3 gelassen. Deshalb sind die Anfangskosten gleich 40.
Entsprechend sind die Anfangskosten am Suchstartpunkt und am Suchendpunkt wie in Tabelle 4 gezeigt. [Tabelle 4.] Beispiele von Anfangskosten am Suchstartpunkt und am Suchendpunkt in der vierten Ausführungsform
Es gibt insgesamt acht Kombinationen aus Suchstartpunkt und Suchendpunkt. Tabelle 5 vergleicht die Gesamtkosten dieser Routen in allen Routenkombinationen mit den oben angeführten Anfangskosten. [Tabelle 5.] Beispiele von Gesamtroutenkosten in Routenkombinationen in der vierten Ausführungsform
In diesem Fall ist die Route mit den minimalen Kosten eine Route vom Knoten N3 zum Knoten N8 mit Gesamtkosten von 436.
Indem die Routensuche wie in der ersten Ausführungsform unter Verwendung der Technik zum Setzen der Position Setztechnik verarbeitet wird, welche ein Merkmal der vierten Ausführungsform ist, wird die Route mit den geringsten Kosten, welche den Suchstartpunkt und den Suchendpunkt verbindet, in dem Kanal vom Knoten N3, über die Verbindung L4, die Verbindung L6, die Verbindung L8 zum Knoten N8 bestimmt. Im Gegensatz zu den Techniken zum Setzen der Position in der ersten, zweiten und dritten Ausführungsform wird hier vermieden, daß eine falsche Route zum Erreichen des Zielpunktes ausgewählt wird, so daß eine richtige Route zum Zielpunkt bestimmt werden kann.
In Schritt 1407 in Fig. 14(b) werden Virtuellverbindungskosten proportional zu der Distanz zur Verbindung gesetzt, wobei diese jedoch auch diskontinuierlich wie in Fig. 10(a) gezeigt sein können oder der Proportionalitätsfaktor wie in Fig. 10(b) gezeigt in Abhängigkeit von der Distanz variiert werden kann. Außerdem wurden als Kosten vom Schnittpunkt mit der vertikalen Linie auf der Verbindung zum Verbindungsendknoten die Kosten der gesamten Verbindung in Übereinstimmung mit der Distanz verteilt, wobei die Verbindungskosten jedoch auch neu unter Annahme einer spezifischen virtuellen Fahrtgeschwindigkeit gesetzt werden können. Weiterhin können die Anfangskosten proportional zu der linearen Distanz zum Knoten gegeben werden. In diesem Fall können diese auch wie in Fig. 10(a) mit Bezug auf die lineare Distanz zum Knoten gezeigt diskontinuierlich sein, oder es kann der Proportionalitätsfaktor in Abhängigkeit von der linearen Distanz wie in Fig. 10(b) gezeigt variiert werden. Auf der Basis der Konfiguration der Verbindung mit einer vom Zielpunkt gezogenen vertikalen Linie können die Zusatzkosten für das Rechts- oder Linksabbiegen, welche in Abhängigkeit davon bestimmt werden, ob beim Fortschreiten von dieser Verbindung zum Zielpunkt auf der Route nach rechts oder nach links abgebogen werden muß, zu den Anfangskosten auf der Zielseite addiert werden.
Allgemein kann in der ersten bis vierten Ausführungsform der Abfahrtseite-Suchstartpunkt gesetzt werden, indem die aktuelle Position und die Fahrtrichtung des Fahrzeugs erhalten werden. Wenn das Fahrzeug zum Beispiel nicht auf der Verbindung ist, dann kann der Abfahrtseite-Suchstartpunkt in Übereinstimmung mit der Ausführungsform auf der Basis der erhaltenen Positionsinformation gesetzt werden, oder wenn das Fahrzeug auf der Verbindung ist, kann der Endknoten der Verbindung in der Vorwärtsrichtung des Fahrzeugs im Abfahrtseite-Suchstartpunkt gesetzt werden. Dem Suchstartpunkt können Anfangskosten in Übereinstimmung mit dem Verbindungsfahrtteil zugewiesen werden. Wenn das Fahrzeug auf der Verbindung ist und wenn in der zur Fahrtrichtung des Fahrzeugs entgegengesetzten Richtung in Übereinstimmung mit der Einbahnverkehrsregelung fortgeschritten werden kann, dann kann der gegenüberliegende Endknoten der Verbindung zu dem Suchstartpunkt auf der Abfahrtseite addiert werden. In diesem Fall kann die Summe aus den dem Verbindungsfahrtteil entsprechenden Verbindungskosten und aus den Zusatzkosten für das Wenden als Anfangskosten addiert werden. Wenn die aktuelle Position nicht auf der Verbindung ist, können die Zusatzkosten in Abhängigkeit von dem zwischen der Fahrtrichtung und der Verbindung gebildeten Winkel zu den Anfangskosten addiert werden.
Schließlich können die Kosten in Abhängigkeit von dem Wendewinkel am Schnittpunkt oder dem Verlassen der Straße während des Suchens addiert werden, oder kann der Bewertungsstandard der Suche (Kostenziel) das Konzept von Gebühren oder einer mühelosen Reise umfassen. Das Suchverfahren beinhaltet eine Suche aus zwei Richtungen, welche von sowohl der Abfahrtseite wie der Zielseite aus sucht, wobei jedoch auch eine Suche aus nur einer Richtung verwendet werden kann, welche entweder von der Abfahrtseite oder von der Zielseite aus sucht. In diesem Fall werden die Anfangskosten am Suchendpunkt als Extrakosten zu den Fahrtkosten addiert, wenn der Punkt den Suchkandidatzustand aufweist. Daraus folgt, daß die Route mit den minimalen Gesamtkosten einschließlich der Extrakosten ausgewählt wird. Bei einer Suche in nur einer Richtung kann weiterhin die Zielseite als Suchstartpunkt gesetzt werden und kann der Suchbereich zur Abfahrtseite hin erweitert werden. In dem Suchverfahren kann weiterhin eine hierarchisch strukturierte Karte für die Suche verwendet werden, wobei das Verfahren nicht auf das Dijkstra-Verfahren beschränkt ist und ein beliebiges Verfahren verwendet werden kann, welches die Route mit den minimalen Kosten bestimmen kann. Die Ausgabeeinrichtung kann die Route nicht nur anzeigen, sondern kann auch mit Hilfe einer Stimme eine Führung zu den Schnittpunkten für das Abbiegen vorsehen, indem die aktuelle Position des Fahrzeugs erhalten wird. Das Verfahren zum Setzen der Position muß nicht notwendigerweise an der Abfahrtseite und an der Zielseite dasselbe sein.
Mit Hilfe der ersten Einrichtung der vorliegenden Erfindung kann durch das Setzen des Suchstartpunktes und des Suchendpunktes an mehreren Schnittpunkten in der Nähe der festgesetzten Position eine am Ziel vorbei führende Führung oder eine andere falsche Routenauswahl verhindert werden, ohne daß eine neue Eingabe erforderlich ist.
Mit Hilfe der zweiten Einrichtung kann durch das Setzen der Anfangskosten in Abhängigkeit von der Distanz von der an mehreren Schnittpunkten gesetzten und durch die ersten Einrichtung ausgewählten Position effektiv verhindert werden, daß ein Schnittpunkt als Suchstartpunkt oder Suchendpunkt der Route gesetzt wird, der von der festgesetzten Position entfernt ist.
Mit Hilfe der dritten Einrichtung kann durch das Setzen von in Übereinstimmung mit den Verkehrsregelungen erreichbaren Schnittpunkten an beiden Enden von einer oder mehreren Straßen in der Nähe der festgesetzten Position als Suchstartpunkt oder Suchendpunkt effektiv verhindert werden, daß ein Schnittpunkt als Suchstartpunkt oder Suchendpunkt der Route gesetzt wird, der nicht mit der Straße in der Nähe der festgesetzten Position verbunden ist.
Mit Hilfe der vierten Einrichtung kann durch das Setzen von Anfangskosten für die mehreren durch die dritten Einrichtung ausgewählten Schnittpunkte mit der Summe aus den Kosten in Abhängigkeit von der Distanz zu der Straße in der Nähe der festgesetzten Position und aus den Kosten in Abhängigkeit von der Fahrtdistanz auf der nahegelegenen Straße die beste Route zum Erreichen des Zielpunktes vom Abfahrtpunkt aus ausgewählt werden.

Claims

1. Führungsvorrichtung mit Routenempfehlung, welche umfaßt:

eine Straßennetzwerk-Aufzeichnungseinrichtung (101) zum Aufzeichnen von Positionen und Verbindungsbeziehungen von Schnittpunkten und Straßen,

eine Positionssetzeinrichtung (102) zum Setzen eines Abfahrtpunktes und eines Zielpunktes,

eine Suchstart-/Suchendpunkt-Setzeinrichtung (103) zum Auswählen einer Vielzahl von innerhalb eines bestimmten Bereichs auf einer Karte liegenden Suchstartpunkten oder Suchendpunkten auf der Basis des durch die Positionssetzeinrichtung gesetzten Abfahrtpunktes oder Zielpunktes,

eine Sucheinrichtung (104) zum Suchen einer Vielzahl von Routen von der ausgewählten Vielzahl von Suchstartpunkten zu der ausgewählten Vielzahl von Suchendpunkten oder umgekehrt, wobei die Suche mit der Information in der Straßennetzwerk-Aufzeichnungseinrichtung in Übereinstimmung mit einer bestimmten Regel durchgeführt wird, und zum Auswählen einer empfohlenen Route aus der Vielzahl von Routen auf der Basis eines vorbestimmten Kriteriums, und

eine Ausgabeeinrichtung (105) zum Ausgeben einer durch die Sucheinrichtung erhaltenen Route.

2. Führungsvorrichtung mit Routenempfehlung nach Anspruch 1, wobei die Suchstart-/Suchendpunkt-Setzeinrichtung (103) dadurch gekennzeichnet ist, daß Anfangskosten beim Start der Suche oder Zusatzkosten beim Erreichen des Suchendpunktes in Abhängigkeit von der Distanz zwischen jedem ausgewählten Schnittpunkt und dem Abfahrtpunkt oder Zielpunkt addiert werden.

3. Führungsvorrichtung mit Routenempfehlung nach Anspruch 1, wobei die Suchstart-/Suchendpunkt-Setzeinrichtung (103) eine oder mehrere Straßenverbindungen jeweils nahe den durch die Positionsinformation des Abfahrtpunktes und Zielpunktes definierten Positionen auswählt und jeweils Schnittpunkte an beiden Enden einer Straßenverbindung, welche dem Abfahrtpunkt und Zielpunkt nahe sind, als Suchstartpunkte und Suchendpunkte auswählt.

4. Führungsvorrichtung mit Routenempfehlung nach Anspruch 3, wobei die Suchstart-/Suchendpunkt-Setzeinrichtung (103) nur einen Schnittpunkt aus den Schnittpunkten an beiden Enden der Straßenverbindungen auswählt, der unter Einhaltung der Verkehrsregelungen erreicht werden kann.

5. Führungsvorrichtung mit Routenempfehlung nach Anspruch 4, wobei die Suchstart-/Suchendpunkt-Setzeinrichtung (103) den nächsten Punkt auf jeder Straßenverbindung zum Abfahrtpunkt oder Zielpunkt sowie die Distanz zu diesem Punkt bestimmt und Anfangskosten beim Start der Suche oder Zusatzkosten beim Erreichen des Suchendpunktes in Abhängigkeit von dieser Distanz setzt.

6. Führungsvorrichtung mit Routenempfehlung nach Anspruch 4, wobei die Suchstart-/Suchendpunkt-Setzeinrichtung (103) den nächsten Punkt auf jeder Straßenverbindung zum Abfahrtpunkt oder Zielpunkt bestimmt und Anfangskosten beim Start der Suche oder Zusatzkosten beim Erreichen des Suchendpunktes in Abhängigkeit von der Distanz zwischen diesem Punkt und einem Schnittpunkt an beiden Enden der Straßenverbindung setzt.

7. Führungsvorrichtung mit Routenempfehlung nach Anspruch 4, wobei die Suchstart-/Suchendpunkt-Setzeinrichtung (103) den nächsten Punkt auf jeder Straßenverbindung zum Abfahrtpunkt oder Zielpunkt sowie die Distanz zu diesem Punkt bestimmt und Anfangskosten beim Start der Suche oder Zusatzkosten beim Erreichen des Suchendpunktes mit einer Summe aus Kosten in Abhängigkeit von dieser Distanz und aus Kosten in Abhängigkeit von der Distanz zwischen diesem Punkt und einem Schnittpunkt an beiden Enden der Straßenverbindung setzt.

8. Führungsvorrichtung mit Routenempfehlung nach Anspruch 4, wobei die Suchstart-/Suchendpunkt-Setzeinrichtung (103) Anfangskosten beim Start der Suche oder Zusatzkosten beim Erreichen des Suchendpunktes in Abhängigkeit von der Distanz zwischen dem Abfahrtpunkt oder Zielpunkt und jedem Suchstartpunkt und Suchendpunkt setzt.

9. Führungsvorrichtung mit Routenempfehlung nach Anspruch 4, wobei die Suchstart-/Suchendpunkt-Setzeinrichtung (103) den Suchstartpunkt der Abfahrtseite oder den Suchendpunkt der Abfahrtseite aus der Position und der Richtung eines Fahrzeugs bestimmt.

10. Führungsvorrichtung mit Routenempfehlung nach Anspruch 4, wobei die Suchstart-/Suchendpunkt-Setzeinrichtung (103) weitere Zusatzkosten in Abhängigkeit von dem zwischen der Richtung eines Fahrzeugs und einer Straßenverbindung gebildeten Winkel zu den Anfangskosten beim Start der Suche auf der Abfahrtseite oder den Zusatzkosten beim Erreichen des Suchendpunktes auf der Abfahrtseite addiert.

11. Führungsvorrichtung mit Routenempfehlung nach Anspruch 4, wobei die Suchstart-/Suchendpunkt-Setzeinrichtung (103) weitere Zusatzkosten für das Rechts- oder Linksabbiegen in Abhängigkeit von der Positionsbeziehung zwischen dem Zielpunkt und der Straßenverbindung zu den Anfangskosten beim Start der Suche auf der Zielseite oder zu den Zusatzkosten beim Erreichen des Suchendpunktes auf der Zielseite addiert.