Beschreibung

Verfahren und Vorrichtung zum Ermitteln von Mindestkosten von einem Startort zu einem Zielort für die Planung einer Route

Die Erfindung betrifft ein Verfahren und eine Vorrichtung zum Ermitteln von Mindestkosten von einem Startort zu einem Zielort für eine Planung einer Route von dem Startort zu dem Zielort. Abhängig von dem Startort wird ein Startknoten er- mittelt und abhängig von dem Zielort wird ein Zielknoten ermittelt.

Aus der US 2002/0059025 Al ist ein Verfahren bekannt, um in einem Verkehrsnetzwerk einen kürzesten Weg von einem Startort zu einem Zielort zu finden. Dabei werden ein Dijkstra- und ein Floyd-Warshal-Algorithmus verwendet.

Es ist Aufgabe der Erfindung, ein Verfahren und eine Vorrichtung zu schaffen, das bzw. die einfach eine effektive Routen- planung ermöglicht.

Die Aufgabe wird gelöst durch die Merkmale der unabhängigen Ansprüche. Vorteilhafte Ausgestaltungen der Erfindung sind in den Unteransprüchen gekennzeichnet.

Die Erfindung zeichnet sich aus durch ein Verfahren und eine Vorrichtung zum Ermitteln von Mindestkosten zwischen einem Startort und einem Zielort. Die Mindestkosten werden ermit ^¬ telt für eine Planung einer Route von dem Startort zu dem Zielort. Abhängig von dem Startort wird ein Startknoten ermittelt. Dem Startknoten sind Startknotenkosten zu zumindest einer vorgegebenen Startlandkartenmarkierung aus einer vorgegebenen Menge an Startlandkartenmarkierungen zugeordnet. Die Menge an Startlandkartenmarkierungen umfasst eine vorgegebene erste Anzahl der zu dem Startknoten nächstliegenden Landkartenmarkierungen. Die vorgegebene erste Anzahl ist kleiner als die Gesamtanzahl aller Landkartenmarkierungen. Abhängig von

dem Startknoten werden die entsprechenden Startknotenkosten zu jeder Startlandkartenmarkierung ermittelt. Abhängig von dem Zielort wird ein Zielknoten ermittelt. Dem Zielknoten sind zumindest Zielknotenkosten von dem Zielknoten zu zumin- dest einer vorgegebnen Ziellandkartenmarkierung aus einer vorgegebenen Menge an Ziellandkartenmarkierungen zugeordnet. Die Menge an Ziellandkartenmarkierungen umfasst eine vorgegebene zweite Anzahl der zu dem Zielknoten nächstliegenden Landkartenmarkierungen. Die vorgegebene zweite Anzahl ist kleiner als die Gesamtanzahl aller Landkartenmarkierungen. Abhängig von dem Zielknoten werden die entsprechenden Zielknotenkosten zu jeder Ziellandkartenmarkierung ermittelt. Landkartenmarkierungskosten von jeder Startlandkartenmarkierung zu jeder Ziellandkartenmarkierung werden ermittelt an- hand einer Tabelle, die die Landkartenmarkierungskosten aller Landkartenmarkierungen zueinander umfasst. Die Mindestkosten werden abhängig von den ermittelten Startknotenkosten, den ermittelten Zielknotenkosten und den ermittelten Landkartenmarkierungskosten ermittelt.

Gegenüber einem Verfahren, bei dem jedem Knoten die Kosten bis zu allen Landkartenmarkierungen zugeordnet sind, ermöglicht dies, die benötigte Datenmenge zum Ermitteln der Min ^¬ destkosten stark zu reduzieren und damit so viel Speicher- platz zu sparen, dass das Verfahren ausschließlich auf einem mobilen Gerät zur Planung der Route durchgeführt werden kann. Das Ermitteln der Mindestkosten ermöglicht, den Suchraum bei der Suche nach der Route stark einzuschränken, und trägt somit zu einem schnellen Ermitteln der Route bei. Insbesondere eine erste Richtungsausgabe des mobilen Geräts zum Planen der Route nach einer Eingabe eines Benutzers des Geräts kann sehr schnell ausgegeben werden.

In einer vorteilhaften Ausgestaltung des Verfahrens werden die Mindestkosten anhand einer vorgegebenen Landkarte ermittelt. Die vorgegebene Landkarte ist in vorgegebene Landkar ^¬ tenausschnitte unterteilt. Die Knotenkosten von den Knoten

bis zu den nächstliegenden Landkartenmarkierungen werden lediglich den Knoten zugeordnet, die übergänge von einem der vorgegebenen Landkartenausschnitte der Landkarte zu einem an ^¬ deren der vorgegebenen Landkartenausschnitte der Landkarte repräsentieren. Falls die Landkartenausschnitte auf einem Speichermedium eines Geräts zum Ermitteln der Route jeweils in zusammenhängenden Speicherbereichen abgelegt sind, so ermöglicht dies zum Planen der Route für je einen Startort und je einen Zielort lediglich zwei Landkartenausschnitte laden zu müssen. Dies trägt zu einem sehr schnellen Ermitteln der Mindestkosten bei.

In einer weiteren vorteilhaften Ausgestaltung des Verfahrens werden die Mindestkosten anhand der vorgegebenen Landkarte ermittelt. Die vorgegebene Landkarte ist in die vorgegebenen Landkartenausschnitte unterteilt. Für einen der Landkarten ^¬ ausschnitte, der einen ausgezeichneten Startort und/oder Zielort umfasst, wird zumindest eine Zusatzinformation vorge ^¬ geben gegenüber einem der Landkartenausschnitte, der keinen ausgezeichneten Startort bzw. Zielort umfasst. Dies kann in den Fällen, in denen der Startort und/oder der Zielort den ausgezeichneten Startorten bzw. Zielorten entsprechen, dazu beitragen, dass die Route besonders schnell geplant werden kann .

In einer weiteren vorteilhaften Ausgestaltung des Verfahrens wird als Zusatzinformation zumindest eine zusätzliche Land ^¬ kartenmarkierung vorgegeben. Dies kann dazu beitragen, die Route besonders schnell zu planen.

In einer weiteren vorteilhaften Ausgestaltung des Verfahrens wird als Zusatzinformation eine der Landkartenmarkierungen so vorgegeben, dass sie dem ausgezeichneten Startort und/oder Zielort entspricht. Dies kann dazu beitragen, die Route be- sonders schnell zu planen, falls der Startort und/oder der Zielort den ausgezeichneten Startorten bzw. Zielorten entsprechen .

In einer weiteren vorteilhaften Ausgestaltung des Verfahrens werden räumliche und/oder zeitliche Kosten der Knoten zu den Landkartenmarkierungen und/oder der Landkartenmarkierungen zueinander vorgegeben. Die räumlichen Kosten repräsentieren räumliche Abstände zwischen den Knoten und den Landkartenmarkierungen bzw. zwischen den Landkartenmarkierungen zueinander. Die zeitlichen Kosten repräsentieren eine durchschnittliche Fahrdauer von einem der Knoten zu einem anderen der Knoten bzw. von einer der Landkartenmarkierungen zu einer an- deren der Landkartenmarkierungen. Dies ermöglicht, dynamische Verkehrsbedingungen, wie Staus, Baustellen und/oder Pendelverkehr, und/oder Geschwindigkeitsbegrenzungen und/oder Mautgebühren bei der Planung der Route zu berücksichtigen.

In einer weiteren vorteilhaften Ausgestaltung des Verfahrens werden die zeitlichen und/oder räumlichen Kosten gewichtet abhängig von einem Benutzerwunsch. Die Route und/oder die Mindestkosten werden abhängig von den gewichteten Kosten ermittelt. Dies ermöglicht, dass der Benutzer von Route zu Rou- te selbst entscheiden kann, wie wichtig ihm Geschwindigkeit, Zeit und/oder die Streckenlänge bei der Planung der Route sind.

Die vorteilhaften Ausgestaltungen des Verfahrens können ohne weiteres auf vorteilhafte Ausgestaltungen der Vorrichtung ü- bertragen werden.

Die Erfindung ist im Folgenden anhand von schematischen Zeichnungen näher erläutert. Es zeigen:

Figur 1 eine erste Ansicht einer Landkarte,

Figur 2 eine Tabelle mit Landkartenmarkierungskosten,

Figur 3 eine zweite Ansicht der Landkarte mit Landkarten ^¬ ausschnitten,

Figur 4 eine dritte Ansicht der Landkarte mit weiteren Landkartenausschnitten,

Figur 5 ein Ablaufdiagramm zum Ermitteln von Mindestkosten,

Figur 6 eine Berechnungsvorschrift zum Gewichten von Kos ^¬ ten .

Elemente gleicher Konstruktion oder Funktion sind figuren- übergreifend mit den gleichen Bezugszeichen gekennzeichnet.

Eine Landkarte MAP (Figur 1) umfasst Knoten KN, Landkartenmarkierungen und mindestens einen Startort STO und mindestens einen Zielort ZIO. Jeder der Knoten KN ist vorzugsweise re- präsentativ für eine Straßenkreuzung. Die Landkartenmarkierungen umfassen zumindest eine Ziellandkartenmarkierung LM_ZI und zumindest eine Startlandkartenmarkierung LM_ST, erste bis fünfte Landkartenmarkierungen LM_1-LM_5 (siehe Figur 3) und vorzugsweise zumindest eine ausgezeichnete Landkartenmarkie- rung HOME (siehe Figur 3) . Die Knoten KN umfassen zumindest einen Startknoten STK und einen Zielknoten ZIK. Der Startknoten STK repräsentiert den nächstliegenden Knoten KN zu dem Startort STO. Der Startknoten STK weist Startknotenkosten STK_KOST zu der Startlandkartenmarkierung LM_ST auf. Der Zielknoten ZIK repräsentiert den nächstliegenden Knoten KN zu dem Zielort ZIO. Der Zielknoten ZIK weist Zielknotenkosten ZIK_KOST zu der Ziellandkartenmarkierung LM_ZI auf. Die Startlandkartenmarkierung LM_ST und die Ziellandkartenmarkierung LM_ZI weisen Landkartenmarkierungskosten LM_KOST zuein- ander auf.

Die Kosten umfassen Knotenkosten und die Landkartenmarkie ^¬ rungskosten LM_KOST. Die Knotenkosten umfassen die Startknotenkosten STK_KOST, die Zielknotenkosten ZI_KOST und weitere Knotenkosten von einem der Knoten KN zu einem anderen der

Knoten KN. Die Kosten sind beispielsweise repräsentativ für räumliche Abstände zwischen den Knoten und den Landkartenmar-

kierungen, für räumliche Abstände zwischen den Landkartenmarkierungen untereinander, für Fahrdauern DUR die durchschnittlich benötigt werden um die räumlichen Abstände zurückzule ^¬ gen, für Geschwindigkeitsbegrenzungen und/oder für Mautstel- len.

Jedem Knoten KN sind die Knotenkosten zu einer vorgegebenen Anzahl an nächstliegenden Landkartenmarkierungen zugeordnet. Zugeordnet kann in diesen Zusammenhang beispielsweise bedeu- ten, dass auf einem Speichermedium, auf dem die Landkarte MAP gespeichert ist, jeweils einer der Knoten KN und die entspre ^¬ chenden Knotenkosten in einem zusammenhängenden Speicherbereich abgespeichert sind. Dies ist besonders vorteilhaft, da bei einem Laden des Knotens KN zum Ermitteln einer Route und/oder von Mindestkosten MIN_KOST, die für die Route benötigt werden, dann automatisch auch die entsprechenden Knotenkosten geladen werden. Somit wird zum Ermitteln der Knotenkosten keine zusätzliche Zeit benötigt. Die vorgegebene An ^¬ zahl an Landkartenmarkierungen ist vorzugsweise weitaus klei- ner als die Gesamtzahl aller Landkartenmarkierungen. Beispielsweise kann die Anzahl der nächstliegenden Landkartenmarkierungen einem Prozent aller Landkartenmarkierungen entsprechen. Die Anzahl an nächstliegenden Landkartenmarkierungen kann von Konten KN zu Knoten KN variieren, sie kann aber auch für alle Knoten KN fest vorgegeben sein.

Die Landkartenmarkierungskosten LM_KOST aller Landkartenmarkierungen zueinander sind bevorzugt in einer Tabelle (Figur 2) hinterlegt. Die Tabelle ist vorzugsweise auf dem Speicher- medium gespeichert. Beispielsweise sind die Kosten zwischen der Startlandkartenmarkierung LM_ST und der ersten Landkartenmarkierung LM_1 für ein Fahrzeug im Durchschnitt hundert Kilometer und eine Stunde. Das heißt, das Fahrzeug legt die hundert Kilometer zwischen der Startlandkartenmarkierung LM_ST und der ersten Landkartenmarkierung LM_1 durchschnittlich in einer Stunde zurück. Die Tabelle muss nicht symmet ^¬ risch sein. Das heißt in diesem Zusammenhang, dass beispiels-

weise von dem Startknoten STK zu der Startknotenmarkierung LM_ST andere Startknotenkosten anfallen als von der Startknotenmarkierung LM_ST hin zu dem Startknoten STK. Dies kann beispielsweise durch eine Einbahnstraße entlang der Route hervorgerufen werden. Ferner können alle Kosten abhängig von der Richtung sein, in der die Route durchfahren wird.

Vorzugsweise ist die Landkarte MAP in Landkartenausschnitte PARC unterteilt (Figur 3) . Vorzugsweise ist jeder der Land- kartenartenausschnitte PARC als zusammenhängendes Datenpaket, beispielsweise als binary large object (BLOB) , in einem zu ^¬ sammenhängenden Speicherbereich des Speichermediums gespeichert .

Bevorzugt wird zumindest ein ausgezeichneter Start- und/oder Zielort vorgegeben. Vorzugsweise entspricht der ausgezeichne ^¬ te Start- bzw. Zielort einem Start- bzw. Zielort STO, ZIO, den ein Benutzer eines Geräts zum Planen der Route häufig auswählt. Dem ausgezeichneten Start- bzw. Zielort wird dann vorzugsweise die ausgezeichnete Landkartenmarkierung HOME zu ^¬ geteilt. Die Landkartenmarkierungskosten LM_KOST der ausgezeichneten Landkartenmarkierung HOME zu den anderen Landkartenmarkierungen werden dann in der Tabelle der Landkartenmarkierungskosten LM_KOST abgespeichert. Bei einer Routenplanung ausgehend von bzw. ankommend an der ausgezeichneten Landkartenmarkierung HOME können dann die Mindestkosten MIN_DIST und/oder die Route sehr schnell berechnet werden, da kein Startknoten STK bzw. Zielknoten ZIK ermittelt werden muss. Insbesondere erübrigt sich dadurch das Ermitteln der Start- knotenkosten STK_KOST bzw. der Zielknotenkosten ZIK_KOST. Die ausgezeichnete Landkartenmarkierung HOME kann beispielsweise repräsentativ sein für einen Arbeitsplatz des Benutzers, für einen Wohnort und/oder beispielsweise eine beliebte Freizeit ^¬ anlage des Benutzers.

Das Versehen des ausgezeichneten Start- und/oder Zielorts STO, ZIO mit der ausgezeichneten Landkartenmarkierung HOME kann als

eigenständiger Aspekt der Erfindung gesehen werden. Falls der Startort STO oder der Zielort ZIO der ausgezeichneten Landkartenmarkierung HOME entspricht und falls jedem Knoten KN die Knotenkosten zu allen Landkartenmarkierungen zugeordnet sind, müssen dann zum Ermitteln der Mindestkosten MIN_KOST lediglich die Zielknotenkosten ZIK_KOST bzw. die Startknotenkosten STK_KOST ermittelten werden. Falls der Startort STO oder der Zielort ZIO der ausgezeichneten Landkartenmarkierung HOME entspricht und falls jedem Knoten KN lediglich die Knotenkosten zu den nächstliegenden Landkartenmarkierungen zugeordnet sind, müssen dann zum Ermitteln der Mindestkosten MIN_KOST lediglich die Zielknotenkosten ZIK_KOST bzw. die Startknotenkosten STK_KOST und der Landkartenmarkierungsabstand LM_KOST von der Ziellandkartenmarkierung LM_ST zu der ausgezeichneten Landkar- tenmarkierung HOME anhand der Tabelle der Landkartenmarkie ^¬ rungskosten LM_KOST ermittelt werden.

Alternativ oder zusätzlich können lediglich den Knoten KN Knotenkosten bis zu den nächstliegenden Landkartenmarkierun- gen zugeordnet werden, die einen übergang von einem Landkartenausschnitt PARC zu einem anderen Landkartenausschnitt PARC repräsentieren. Beispielsweise können die Knoten KN, die die übergänge repräsentieren, auf oder direkt an den Rändern des entsprechenden Landkartenausschnitts PARC liegen (Figur 4). Falls sich die Landkartenausschnitte PARC überlappen, können beispielsweise die Knoten KN die übergänge repräsentieren, die in dem überlappungsbereich der Landkartenausschnitte PARC liegen. Zum Ermitteln der Route müssen dann lediglich ein Startlandkartenausschnitt und ein Ziellandkartenausschnitt aus den Landkartenausschnitten PARC ermittelt werden, die den Startort STO bzw. den Zielort ZIO umfassen. Die ermittelten Landkartenausschnitte PARC müssen dann geladen werden. Zusammen mit dem Startlandkartenausschnitt wird auch der Startkno ^¬ ten STK geladen, der auf dem Rand des Startlandkartenaus- Schnitts PARC liegt. Mit dem Startknoten STK werden vorzugs ^¬ weise auch die Startknotenkosten STK_KOST geladen. Befindet sich in dem Ziellandkartenausschnitt eine der Landkartenmar-

kierungen so müssen nun lediglich die Kosten von dem Zielort ZIO zu der entsprechenden Ziellandkartenmarkierung LM_ZI ermittelt werden. Befindet sich beispielsweise keine der Land ^¬ kartenmarkierungen in dem Ziellandkartenausschnitt, so kann abhängig von dem Zielort ZIO des Ziellandkartenausschnitts der Zielknoten ZIK ermittelt werden, der auf dem Rand des Ziellandkartenausschnitts liegt. Abhängig von dem Zielknoten ZIK kann dann die Ziellandkartenmarkierung LM_ZI ausgewählt werden. Die Landkartenausschnitte PARC, die die Start- bzw. Ziellandkartenmarkierungen LM_ST, LM_ZI umfassen, müssen nicht unbedingt geladen werden, da deren Landkartenmarkie ^¬ rungskosten LM_KOST in der Tabelle der Landkartenmarkierungs ^¬ kosten LM_KOST hinterlegt sind.

Das Ermitteln der Mindestkosten MIN_KOST kann weiterhin beschleunigt werden, indem der Landkartenausschnitt PARC, der den ausgezeichneten Start- bzw. Zielort umfasst, mit Zusatzinformationen ausgestattet wird, die über die Informationen hinausgehen, die den Landkartenausschnitten PARC zugeordnet sind, die keinen ausgezeichneten Start- bzw. Zielort umfas ^¬ sen. Die Zusatzinformationen können beispielsweise zusätzliche Landkartenmarkierungen, wie die ausgezeichnete Landkartenmarkierung HOME, den ausgezeichneten Start- bzw. Zielort selbst, zusätzliche Knoten KN auf dem Rand des entsprechenden Landkartenausschnitts PARC mit entsprechenden Knotenkosten und/oder weitere Zusatzinformationen umfassen.

Ein Programm (Figur 5) zum Ermitteln der Mindestkosten MIN_KOST ist vorzugsweise auf dem Speichermedium des Geräts zum Ermitteln der Route gespeichert. Das Gerät kann bei ^¬ spielsweise ein PC, ein Laptop, ein Pocket-Computer, ein Routenplanungssystem und/oder ein Navigationssystem sein. Das Gerät kann auch als Vorrichtung zum Ermitteln der Mindestkosten zwischen dem Startort STO und dem Zielort ZIO für die Planung der Route von dem Startort STO zu dem Zielort ZIO be ^¬ zeichnet werden. Das Programm wird vorzugsweise bei einer Suchanfrage des Benutzers des Geräts nach der Route von dem

Startort STO zu dem Zielort ZIO in einem Schritt Sl gestar ^¬ tet. In dem Schritt Sl werden gegebenenfalls Variablen initi ^¬ alisiert .

In einem Schritt S2 werden die beim Stellen der Anfrage nach der Route von dem Benutzer eingegebenen und gespeicherten Orte ausgelesen.

In einem Schritt S3 wird abhängig von dem Startort STO der Startknoten STK ermittelt. Vorzugsweise ist der Startknoten STK der Knoten KN der dem Startort STO am nächsten liegt.

In einem Schritt S4 werden abhängig von dem Startknoten STK die Startlandkartenmarkierungen LM_ST ermittelt. Die Start- landkartenmarkierungen LM_ST sind eine vorgegebene erste Anzahl an Startlandkartenmarkierungen LM_ST, die dem Startknoten STK am nächsten liegen. Die Startknotenkosten STK_DIST von dem Startknoten STK zu den Startlandkartenmarkierungen LM_ST sind dem Startknoten STK zugeordnet, und insbesondere vorzugsweise zusammenhängend mit dem Startknoten STK abge ^¬ speichert. Die vorgegebene erste Anzahl nächstliegender Startlandkartenmarkierungen LM_ST kann beispielsweise 10 sein, sie kann aber auch einen vorgegeben prozentualen Anteil aller Landkartenmarkierungen repräsentieren, beispielsweise ein bis zehn Prozent.

In einem Schritt S5 werden abhängig von dem Startknoten STK und den entsprechenden Startlandkartenmarkierungen LM_ST die Startknotenkosten STK_DIST ermittelt. Sind die Startknoten- kosten STK_DIST zusammen mit den Startknoten STK abgespeichert, so wird keine zusätzliche Bearbeitungszeit zum Ermit ^¬ teln der Startknotenkosten STK_DIST benötigt.

In einem Schritt S6 wird abhängig von dem Zielort ZIO der Zielknoten ZIK ermittelt. Der Zielknoten ZIK ist vorzugsweise der Knoten KN, der dem Zielort ZIO am nächsten liegt.

In einem Schritt S7 werden abhängig von dem Zielknoten ZIK die Ziellandkartenmarkierungen LM_ZI ermittelt entsprechend den Startlandkartenmarkierungen LM_ST in dem Schritt S4.

In einem Schritt S8 werden die Zielknotenkosten ZIK_KOST ermittelt entsprechend den Startknotenkosten STK_KOST in dem Schritt S5.

In einem Schritt S9 werden anhand der Tabelle der Landkarten- markierungskosten LM_KOST die entsprechenden Landkartenmarkierungskosten LM_KOST ermittelt abhängig von den Ziellandkartenmarkierungen LM_ZI und den Startlandkartenmarkierungen LM_ST.

In einem Schritt SlO werden die Mindestkosten MIN_KOST abhängig von den Startknotenkosten STK_KOST, den Zielknotenkosten ZIK_KOST und den entsprechenden Landkartenmarkierungskosten LM_KOST ermittelt. Bevorzugt werden die Mindestkosten MIN_KOST ermittelt durch Differenzbildung, bei der die Start- knotenkosten STK_KOST und die Zielknotenkosten ZIK_KOST von den entsprechenden Landkartenmarkierungskosten LM_KOST abgezogen werden, für alle Paare von ermittelten Startlandkartenmarkierungen LM_ST und ermittelten Ziellandkartenmarkierungen LM_ZI und durch anschließendes Ermitteln des Paares von er- mittelten Startlandkartenmarkierungen LM_ST und ermittelten

Ziellandkartenmarkierungen LM_ZI, dessen Differenz der Kosten am größten ist. Vorzugsweise ist dann die größte Differenz der Kosten des ermittelten Paares repräsentativ für die Mindestkosten MIN_KOST.

Das Programm kann in einem Schritt Sil beendet werden. Bevorzugt wird das Programm jedoch erneut gestartet. Falls sich das Gerät zum Planen der Route während dem Durchfahren der Route bis zu dem erneuten Starten des Programms zu einem an- deren Knoten KN bewegt hat als bei dem ersten Starten des

Programms, so kann dieser Knoten KN bevorzugt als neuer Star-

tort STO und/oder als neuer Startknoten STK zum Ermitteln von neuen Mindestkosten MIN_KOST herangezogen werden.

In Zusammenhang mit den räumlichen und zeitlichen Kosten ist es besonders vorteilhaft, wenn bei der Routenplanung nicht nur entweder die räumlichen, die zeitlichen Kosten oder die weiteren Kosten berücksichtigt werden, sondern alle gleichzeitig. Dazu ist es besonders vorteilhaft, wenn der Benutzer selbst gewichten kann, wie wichtig ihm eine Optimierung der Route beispielsweise bezüglich der Fahrdauer DUR, der zurückzulegenden Streckenlänge LENGTH und/oder Mautgebühren ist. Beispielsweise können gewichtete Kosten KOST (Figur 6) als Funktion der Fahrdauer DUR, einer durchschnittlich möglichen Geschwindigkeit SPEED des Kraftfahrzeugs, der Streckenlänge LENGTH und eines Gewichtungsfaktors a ermittelt werden, vor ^¬ zugsweise nach der in Figur 6 angegebenen Berechnungsvorschrift. Der Gewichtungsfaktor a ist vorzugsweise eine pro ^¬ zentuale Größe. Als Daten werden jeweils nur die hundertpro ^¬ zentigen Werte an den entsprechend Knoten KN abgespeichert und die individuelle Gewichtung erfolgt abhängig von einem Benutzerwunsch des Benutzers in Echtzeit während dem Ermit ^¬ teln der Route, insbesondere während dem Ermitteln der Mindestkosten MIN_KOST. Somit können nahezu unendlich viele Kombinationen unterschiedlicher Gewichtungsmöglichkeiten bereit- gestellt werden, obwohl lediglich eine stark begrenzte abzu ^¬ speichernde Datenmenge dazu verwendet wird.

Die Erfindung ist nicht auf die angegebenen Ausführungsbei ^¬ spiele beschränkt. Beispielsweise können die unterschiedli- chen Ausführungsbeispiele miteinander kombiniert werden. Bei ^¬ spielsweise kann ein Landkartenausschnitt PARC, der den aus ^¬ gezeichneten Start- bzw. Zielort umfasst, mit der ausgezeichneten Landkartenmarkierung HOME und/oder weiteren zusätzlichen Landkartenmarkierungen und/oder mit mehr Knoten KN die die Kosten zu den nächstliegenden Landkartenmarkierungen umfassen, auf dem Rand des entsprechenden Landkartenausschnitts PARC versehen werden. Ferner können mehrere Landkartenaus-

schnitte PARC mit den zusätzlichen Informationen versehen werden, insbesondere können mehrere ausgezeichnete Landkar ^¬ tenmarkierungen HOME gesetzt werden.