Verfahren und System zur Optimierung der Parkplatzsuche eines Fahrzeuges und ein Computerprogrammprodukt

Die vorliegende Erfindung betrifft ein Verfahren und ein System zur Optimierung der Parkplatzsuche eines Fahrzeuges sowie ein diesbezügliches

Computerprogrammprodukt.

Aufgrund der stets steigenden Anzahl von Fahrzeugen und der steigenden

Populationsdichte gibt es Gebiete mit zeitweilig weniger Parkraum als

parkplatzsuchenden Fahrzeugen. Es sind heutzutage bereits Dienste bekannt, die dieses Problem adressieren, indem eine Wahrscheinlichkeit straßenrandseitig einen Parkplatz zu finden bestimmt wird und diese dem Fahrer angezeigt wird. Zudem sind digitale Straßenkarten und Navigationssysteme bekannt.

Heutzutage, leiten Navigationssysteme den Fahrer in der Art, dass sichergestellt wird, dass das Fahrzeug das Ziel erreicht. Ein solcher Ansatz verlangt, dass das endgültige Ziel des Fahrers mit dem Fahrzeug erreichbar ist. Diese Vermutung trifft nicht für viele Fälle zu. Insbesondere wenn Parkplätze rar sind, kann der Fahrer sein Fahrzeug normalerweise nicht direkt an seinem Ziel parken. Aufgabe der vorliegenden Erfindung ist es daher eine Lösung zu schaffen, mittels derer die Parkplatzsuche optimiert werden kann.

Der Erfindung liegt die Erkenntnis zugrunde, dass diese Aufgabe gelöst werden kann, indem eine oder mehrere Lösungsoptionen ermittelt werden, wobei die

Wahrscheinlichkeit der Verfügbarkeit zumindest zusammen mit der relativen Position des Parkplatzes zu einem Zielort, zu einem Startort und gegebenenfalls zu mindestens einem weiteren Parkplatz berücksichtigt wird. Aus den Lösungsoptionen wird dann vorzugsweise die optimale Lösungsoption ausgewählt. Diese kann auch als Optimierungslösung bezeichnet werden.

Gemäß einem ersten Aspekt wird die Aufgabe daher gelöst durch ein Verfahren zum Optimieren der Parkplatzsuche eines Fahrzeuges. Das Verfahren ist dadurch gekennzeichnet, dass bei dem Verfahren zumindest eine Lösungsoption ermittelt und aus dieser mindestens einen Lösungsoption eine Optimierungslösung ermittelt wird, wobei als ein Optimierungsparameter die Wahrscheinlichkeit der Verfügbarkeit mindestens eines Parkplatzes, als ein weiterer Optimierungsparameter die relative Position des mindestens einen Parkplatzes zu einem Zielort, ausgedrückt als Dauer zum Erreichen des Zielortes von dem mindestens einen Parkplatz, und als ein weiterer Optimierungsparameter die Fahrtdauer von einem Startort zu dem

mindestens einen Parkplatz verwendet wird. Die Parkplatzsuche eines Fahrzeuges erfolgt vorzugsweise durch den Fahrer des Fahrzeuges, der vorzugsweise zumindest teilweise Informationen zur Verbesserung der Parkplatzsuche erhält. Beispielsweise kann die Parkplatzsuche durch ein

Fahrerassistenzsystem oder ein Navigationssystem unterstützt sein. Bei autonomen Fahrzeugen kann die Parkplatzsuche auch durch das Fahrzeug selber unter

Verwendung solcher Fahrerassistenzsysteme oder Navigationssysteme erfolgen.

Bei dem erfindungsgemäßen Verfahren wird mindestens eine Lösungsoption ermittelt. Aus der mindestens einen Lösungsoption wird dann eine

Optimierungslösung ermittelt. Als Lösungsoption wird eine Option, insbesondere ein Parkplatz bezeichnet, der eventuell geeignet sein könnte eine Optimierungslösung darzustellen. Als Optimierungslösung wird eine Lösung eines Optimierungsproblems bezeichnet.

Als Optimierungsproblem wird hierbei eine Problemstellung oder Aufgabenstellung bezeichnet, deren Lösung zu der für den Fahrer bevorzugten Auswahl eines oder mehrere Parkplätze führt. Als Optimierungsproblem kann beispielsweise das

Problem formuliert werden, dass ein oder mehrere Optimierungskriterien in einem vorgegebenen Bereich liegen oder einen bestimmten Zahlenwert erreichen. Als Optimierungskriterien werden erfindungsgemäß beispielsweise die minimale Zeit und/oder ein maximaler Anspruch des Fahrers verstanden. Als Anspruch des

Fahrers kann insbesondere dessen Erwartung einen Parkplatz zu finden verstanden werden. Als Formulierung des Optimierungsproblems wird insbesondere die Vorgabe von Werten, Bereichen oder Verhältnissen für Optimierungskriterien für die

erwünschte Optimierungslösung verstanden. Die Optimierungslösung stellt daher vorzugsweise einen oder mehrere Parkplätze dar, die den Optimierungskriterien, die in dem Optimierungsproblem genauer definiert sind, entsprechen beziehungsweise diese erfüllen.

Erfindungsgemäß werden bei der Ermittlung der mindestens einen

Optimierungslösung mehrere Optimierungsparameter verwendet. Als ein

Optimierungsparameter wird hierbei die Wahrscheinlichkeit der Verfügbarkeit mindestens eines Parkplatzes verwendet. Die Wahrscheinlichkeit der Verfügbarkeit kann beispielsweise durch Nutzung historisch abgeleiteter Parkplatz-Auffinde- Wahrscheinlichkeiten aus anderen Diensten bestimmt werden. Zusätzlich oder alternativ können aktuell online gemeldete oder absehbare zukünftige

Parkplatzverfügbarkeiten zur Bestimmung der Wahrscheinlichkeit verwendet werden. Bei einer aktuell online gemeldeten Parkplatzverfügbarkeit kann es sich um das Melden eines Ausparkers oder eines Parkplatzsuchenden in der Nähe, der einen Ausparkvorgang beobachtet, handeln. Die absehbare zukünftige

Parkplatzverfügbarkeit kann beispielsweise durch vermutlich bald ausparkende Carsharing-Fahrzeuge ermittelt werden oder durch zu einem Fahrzeug

zurückkehrende Fahrer.

Als ein weiterer Optimierungsparameter wird die relative Position des mindestens einen Parkplatzes zu einem Zielort, ausgedrückt als Dauer zum Erreichen des Zielortes von dem mindestens einen Parkplatz, verwendet. Die Dauer zum Erreichen des Zielortes von dem mindestens einen Parkplatz kann auch als Zieldauer bezeichnet werden. Der Zielort kann durch den Fahrer des Fahrzeuges beispielsweise in ein Navigationssystem eingegeben werden.

Die relative Position des Parkplatzes zu dem Zielort kann durch Verwendung von digitalen Karten oder Angaben aus einem Navigationssystem bestimmt werden. Gemäß der vorliegenden Erfindung wird vorzugsweise zur Ermittlung der

Lösungsoptionen der Abstand eines Parkplatzes zu einem Zielort bestimmt. Dies kann beispielsweise durch Bestimmung eines Umkreises um einen Zielort erfolgen. Zudem werden vorzugsweise für möglichen Parkplätze Wahrscheinlichkeiten ermittelt. Nur wenn ein Parkplatz beispielsweise innerhalb eines vorgegebenen

Umkreises um einen Zielort liegt und vorzugsweise eine gewisse Wahrscheinlichkeit der Verfügbarkeit gegeben ist, wird der Parkplatz als Lösungsoption betrachtet, die dann zur Ermittlung der Optimierungslösung herangezogen werden kann. Für die Optimierung wird erfindungsgemäß als Optimierungsparameter die relative Position eines Parkplatzes, das heißt einer Lösungsoption, zu dem Zielort verwendet. Hierbei wird aber nicht nur der relative Abstand des Parkplatzes zu dem Zielort verwendet, der beispielsweise durch Bestimmung eines Umkreises um den Zielort vorgegeben werden kann. Erfindungsgemäß wird vorzugsweise zusätzlich zu der Bestimmung des Abstandes des Parkplatzes zu dem Zielort, insbesondere zur Ermittlung von Lösungsoptionen, die Dauer zum Erreichen des Zielortes von dem Parkplatz als Optimierungsparameter ermittelt. Somit können auch gegebenenfalls örtlich weiter vom Zielort entfernte Parkplätze, das heißt Lösungsoptionen, als mögliche

Optimierungslösung zu dem Optimierungsproblem identifiziert werden, sofern, beispielsweise aufgrund einer zu Fuß erreichbaren Abkürzung das Erreichen des Zielortes in einer geringeren Zeit möglich ist, als bei einem örtlich näher an dem Zielort befindlichen Parkplatz.

Erfindungsgemäß wird als ein weiterer Optimierungsparameter die Fahrtdauer von einem Startort zu dem mindestens einen Parkplatz verwendet. Als Fahrtdauer wird hierbei die Zeit verstanden, die notwendig ist, um von dem Startort zu mindestens einer der Lösungsoptionen, das heißt mindestens einem Parkplatz zu gelangen. Die Strecke, die hierbei zurückgelegt werden muss und die auch als Fahrtstrecke bezeichnet werden kann, kann die Summe der Abstände von dem Startort zu einem ersten Parkplatz und von diesem zu einem zweiten Parkplatz umfassen. Die

Fahrtdauer ist dabei die Summe der für die einzelnen Teilstrecken benötigten Zeiten. Als Startort wird insbesondere eine Position verstanden, ab der sich das Fahrzeug in einem definierten Umkreis um den Zielort befindet. Dieser Umkreis kann auch als Zielgebiet bezeichnet werden. Der Umkreis kann durch den Fahrer eingegeben werden oder erfindungsgemäß in dem System voreingestellt sein. Die Strecke, die ein Fahrer gegebenenfalls zwischen seiner aktuellen Position und dem Startort zurücklegen muss, kann auch als Anfahrtstrecke bezeichnet werden.

Als Fahrtdauer wird hierbei die vom Fahrer des Fahrzeuges in dem Fahrzeug vom Startort bis zu einem tatsächlich verfügbaren Parkplatz benötigte Zeit bezeichnet. Wird beispielsweise ein Parkplatz identifiziert, bei dem die Wahrscheinlichkeit, dass dieser verfügbar ist, gering ist, so wird vorzugsweise mindestens ein weiterer Parkplatz identifiziert, an dem die Wahrscheinlichkeit größer ist auch wenn die Fahrtdauer zu diesem weiteren Parkplatz länger als die Fahrtdauer zu dem ersten identifizierten Parkplatz ist. Da die Wahrscheinlichkeit an dem weiteren Parkplatz höher ist, kann nämlich die Fahrtdauer bei diesem Parkplatz höher sein und dennoch die Erwartung des Fahrers erfüllt werden.

Indem bei der vorliegenden Erfindung aus Lösungsoptionen zumindest eine

Optimierungslösung ermittelt wird, wobei sowohl die Fahrtdauer als auch das letzte Stück zwischen dem Parkplatz und dem Zielort, das heißt die Zielstrecke,

berücksichtigt wird und zudem die Wahrscheinlichkeit der Verfügbarkeit

berücksichtigt wird, führt die Optimierungslösung zu einer zuverlässigen Aussage bezüglich eines optimalen Parkplatzes und vorzugsweise zu einer zuverlässigen Aussage bezüglich einer Route entlang derer eine hohe Wahrscheinlichkeit besteht, einen Parkplatz zu finden, der den Erwartungen des Fahrers entspricht.

Insbesondere ist es bei dem erfindungsgemäßen Verfahren möglich auch Parkplätze zumindest in Betracht zu ziehen, die bei einem herkömmlichen Verfahren aufgrund eines größeren Abstandes zum Zielort nicht berücksichtigt oder erkannt werden würden. Vorzugsweise wird die Optimierungslösung aus den Lösungsoptionen ermittelt, indem ein Erwartungswert des Fahrers berücksichtigt wird. Der Erwartungswert stellt in der einfachsten Ausführungsform das Produkt aus Wahrscheinlichkeit der

Verfügbarkeit und der Zeit, nämlich der Summe aus der Fahrtdauer und der

Zieldauer dar. Hierbei kann von dem Fahrer vorgegeben sein, ob die

Wahrscheinlichkeit oder die Zeit für ihn von größerer Bedeutung ist. Das heißt die Gewichtung der Optimierungsparameter kann durch den Fahrer vorgegeben werden. Dies kann der Fahrer beispielsweise durch Eingabe in ein Navigationssystem oder eine Eingabeeinheit des Optimierungssystems angeben. Beispielsweise kann der Fahrer angeben, dass die maximale Suchdauer minimiert werden soll. In diesem Fall kann gegebenenfalls eine längere Zieldauer in Kauf genommen werden, die

Wahrscheinlichkeit der Verfügbarkeit des Parkplatzes wird aber maximiert. In einem anderen Fall kann der Fahrer beispielsweise angeben, dass die maximale Zieldauer minimiert werden soll. In dem Fall kann eine längere Suchdauer in Kauf genommen werden und die Wahrscheinlichkeit der Verfügbarkeit verringert sein.

Gemäß einer bevorzugten Ausführungsform wird der Aufwand, der zum Erreichen des Zielortes von dem mindestens einen Parkplatz notwendig ist, ermittelt. Gemäß einer Ausführungsform berücksichtigt der Aufwand hierbei zumindest die Dauer zum Erreichen des Zielortes von dem mindestens einen Parkplatz, das heißt die

Zieldauer. In einer alternativen oder zusätzlichen Ausführungsform wird der Aufwand als ein Parameter verwendet, um die Dauer zum Erreichen des Zielortes von dem mindestens einen Parkplatz, das heißt die Zieldauer ermitteln zu können. Als

Aufwand wird hierbei der für den jeweiligen Fahrer bestehende Aufwand verstanden. Zur Ermittlung des Aufwandes werden daher vorzugsweise persönliche Präferenzen und/oder Eigenschaften des Fahrers verwendet. So kann beispielsweise bei der Ermittlung des Aufwandes die maximal tolerierte Gehdauer berücksichtigt werden. In diesem Fall dient der Aufwand als Grenzwert. Alternativ oder zusätzlich kann beispielsweise die Gehgeschwindigkeit des Fahrers berücksichtigt werden. In diesem Fall dient der Aufwand zur Bestimmung der Zieldauer, das heißt diese wird unter Verwendung des Aufwandes berechnet. Der Aufwand kann auch als Kosten bezeichnet werden und insbesondere als Zielkosten oder Geh-Kosten. Der Aufwand wird beispielsweise durch eine Funktion ausgedrückt.

Gemäß einer weiteren Ausführungsform wird der Aufwand, der zum Erreichen des mindestens einen Parkplatzes von einem Startort notwendig ist, ermittelt. Gemäß einer Ausführungsform berücksichtigt der Aufwand hierbei zumindest die Fahrtdauer von dem Startort zu dem mindestens einen Parkplatz, das heißt der mindestens einen Lösungsoption. In einer alternativen oder zusätzlichen Ausführungsform wird der Aufwand zur Bestimmung der Fahrtdauer verwendet. Als Aufwand wird hierbei der für den jeweiligen Fahrer bestehende Aufwand verstanden. Zur Ermittlung des Aufwandes werden daher vorzugsweise persönliche Präferenzen des Fahrers und/oder Eigenschaften des Fahrzeuges verwendet. So kann beispielsweise bei der Ermittlung des Aufwandes der maximal vom Fahrer tolerierte Brennstoffverbrauch berücksichtigt werden. In diesem Fall dient der Aufwand als Grenzwert. Alternativ oder zusätzlich kann beispielsweise die maximale Fahrtgeschwindigkeit des

Fahrzeuges berücksichtigt werden. In diesem Fall dient der Aufwand zur

Bestimmung der Fahrtdauer, das heißt diese wird unter Verwendung des Aufwandes berechnet. Der Aufwand kann auch als Kosten bezeichnet werden und insbesondere als Fahrtkosten. Der Aufwand wird beispielsweise durch eine Funktion ausgedrückt.

Gemäß einer bevorzugten Ausführungsform wird zur Bestimmung der Dauer zum Erreichen zum Zielort von dem mindestens einen Parkplatz zumindest eine

Bewegung zu Fuß berücksichtigt. Es werden daher zur Bestimmung der Dauer zum Erreichen des Zielortes vorzugsweise Wege verwendet, die von dem Fahrer zu Fuß zurückgelegt werden können. Zudem können Erfahrungswerte oder andere Werte aus einer Datenbank verwendet werden, um die Dauer des Fußweges zu

bestimmen.

Alternativ oder zusätzlich kann gemäß einer Ausführungsform mindestens eine alternative Fortbewegungsart bei der Bestimmung der Dauer zum Erreichen des

Zielortes von dem Parkplatz berücksichtigt werden. Als alternative Fortbewegungsart wird eine Fortbewegungsart bezeichnet, die weder die Fortbewegung zu Fuß noch mittels des eigenen Fahrzeuges darstellt. Als alternative Fortbewegungsart kommen beispielsweise öffentliche Verkehrsmittel, Taxi und/oder Leihfahrräder in Betracht. Indem alternative Fortbewegungsarten überprüft werden, kann die Anzahl der Lösungsoptionen erhöht werden, da beispielsweise ein zwar weiter entfernt liegender Parkplatz, an dem aber Leihfahrräder zur Verfügung stehen, eine kürzere Dauer zum Erreichen des Zielortes von dem Parkplatz hervorruft, als ein Parkplatz, der zwar näher am Ziel ist, bei dem aber die Zielstrecke bis zum Zielort zu Fuß zurückgelegt werden muss. Gemäß einer bevorzugten Ausführungsform werden, wenn mindestens zwei

Lösungsoptionen erkannt werden, diese Lösungsoptionen in eine

Optimierungsreihenfolge gebracht. Hierbei können dem Fahrer dann mehrere

Lösungsoptionen angegeben, beispielsweise angezeigt werden. Alternativ ist es aber auch möglich, beim Auffinden einer Lösungsoption, die gleichzeitig eine

Optimierungslösung für das formulierte Optimierungsproblem darstellt, zunächst diese Optimierungslösung auszugeben und nur bei einem Misserfolg, beispielsweise, wenn der Parkplatz entgegen einer Wahrscheinlichkeitsabschätzung besetzt war, weitere Lösungsoptionen zu ermitteln und eine weitere Optimierungslösung zu suchen. Als Optimierungsreihenfolge, in die die Lösungsoptionen bei der Ermittlung mehrerer Lösungsoptionen gebracht werden können, wird insbesondere ein

Priorisierung nach einem der Optimierungskriterien oder einem Verhältnis der Optimierungskriterien verstanden. Die Reihenfolge der Lösungen kann dem Fahrer des Fahrzeuges angezeigt werden oder anderweitig ausgegeben, beispielsweise an eine Einheit eines Navigationssystems übermittelt werden.

Gemäß einer Ausführungsform wird als erste Optimierungslösung in der

Optimierungsreihenfolge eine Optimierungslösung angegeben, bei der die erwartete Gesamtdauer, das heißt die Summe aus Fahrtdauer und Zieldauer, zum Erreichen des Zielortes am geringsten ist. Hierbei wird die Optimierungsreihenfolge somit durch die Optimierungskriterien der Dauer zum Erreichen des Zielortes von dem Parkplatz und der Suchdauer zum Suchen des Parkplatzes bestimmt. Das Optimierungskriterium der Wahrscheinlichkeit wird hierbei als untergeordnet behandelt.

Gemäß einer weiteren Ausführungsform wird als erste Optimierungslösung in der Optimierungsreihenfolge eine Optimierungslösung angegeben, bei der die

Wahrscheinlichkeit der Verfügbarkeit des mindestens einen Parkplatzes am höchsten ist. Bei dieser Ausführungsform kann beispielsweise ein Parkplatz, bei dem die Wahrscheinlichkeit der Verfügbarkeit hoch ist, der aber einen relativ großen Abstand zu dem Zielort aufweist, bevorzugt sein, da der Fahrer dann sicher einen Parkplatz hat und den Fußweg oder die Beförderung mit alternativen

Fortbewegungsarten in Kauf nimmt.

Durch Modellierung der Wahrscheinlichkeit erhält jede Optimierungsreihenfolge, das heißt jede potentielle Route eine erwartete Gesamtdauer, das heißt Summe aus Fahrtdauer und Zieldauer. Zudem erhält jede Optimierungsreihenfolge eine maximale Gesamtdauer mit zumindest einer Wahrscheinlichkeit p und/oder eine minimale Gesamtdauer mit zumindest einer Wahrscheinlichkeit p. Der Fahrer kann daher angeben, welches der Optimierungskriterien maßgeblich sein soll. Gemäß einer bevorzugten Ausführungsform wird eine Route ermittelt, die die

Lösungsoptionen in der Optimierungsreihenfolge abdeckt. Hierbei addiert sich die Fahrtdauer von mehreren Lösungsoptionen auf. Insbesondere ist die von dem Startort zu der ersten Lösungsoption ermittelte Fahrtdauer mit der Dauer zum Erreichen einer zweiten Lösungsoption von der ersten Lösungsoption

aufzusummieren. Diese aufsummierte Fahrtdauer muss daher bei einer Optimierung nach der Gesamtzeit für die zweite Optimierungslösung berücksichtigt werden. Die Route kann beispielsweise über das Navigationssystem des Fahrzeuges

ausgegeben und insbesondere angezeigt werden oder bei vollautomatischen Fahrzeugen vorgegeben werden. Hierdurch wird sichergestellt, dass der Fahrer beziehungsweise das Fahrzeug die Lösungsoptionen in der gewünschten

Reihenfolge, das heißt entlang einer durch die Lösungsoptionen in der

Optimierungsreihenfolge definierte Route, abfährt. Bei einer Ausführungsform des erfindungsgemäßen Verfahrens, bei der nur eine Optimierungslösung betrachtet wird, das heißt ein einziger optimaler Parkplatz identifiziert wird, kann eine geeignete Route für das individuelle Fahrzeug zu diesem optimalen Parkplatz ermittelt werden.

Gemäß einer Ausführungsform erfolgt die Auswahl der Optimierungslösungen anhand eines Entscheidungsbaumes. Die Verwendung eines Entscheidungsbaumes weist den Vorteil auf, dass nicht alle möglichen Kombinationen von Routen entlang Lösungsoptionen analysiert werden müssen. Vielmehr kann durch Wichtung der einzelnen Zweige des Entscheidungsbaumes ein gezieltes Auffinden einer oder mehrerer Lösungen des Optimierungsproblems erfolgen. Insbesondere wird hierbei ein Entscheidungsbaum verwendet, bei dem der Wurzelknoten den Startpunkt der Optimierung angibt, das heißt der Punkt ab dem eine Parkplatzsuche erfolgt. Der Startpunkt der Optimierung ist in der Regel abweichend von dem aktuellen Ort des Fahrzeuges. Der Startpunkt der Optimierung kann beispielsweise durch einfache Entfernungsbetrachtung, das heißt Definition eines Suchbereiches um den Zielort bestimmt werden. In diesem Suchbereich werden dann die Lösungsoptionen, das heißt Parkplätze, von denen zumindest einer eine Wahrscheinlichkeit der

Verfügbarkeit von 1 besitzt, anhand der Baustruktur überprüft.

Gemäß einer weiteren Ausführungsform werden bei der Auswahl der

Optimierungslösungen Obergrenzen und Untergrenzen für zumindest ein

Optimierungskriterium überprüft. Diese auch als Upper Bound / Lower Bound bekannte Prüfungsmethode verbessert das Ergebnis der Optimierung insbesondere die Lösung(en) des Optimierungsproblems weiter.

Besonders bevorzugt wird ein sogenanntes Branch-and-Bound-Verfahren verwendet, das heißt die Optimierungslösungen werden durch Verwendung eines

Entscheidungsbaumes und dem Vergliche von Obergrenzen und Untergrenzen unterschiedlicher Knoten bestimmt. Als Optimierungsproblem wird hierbei

vorzugsweise der Erwartungswert des Fahrers verwendet. Dieser berücksichtigt vorzugsweise die Wahrscheinlichkeit der Verfügbarkeit sowie den Fahrtaufwand und den Zielaufwand. Durch die Verwendung eines Branch-and-Bound-Verfahrens werden suboptimale Lösungen erkannt und aussortiert beziehungsweise der entsprechende Ast wird nicht weiterverfolgt. In dem Branch-Schritt kann hierbei das Optimierungsproblem in Teilprobleme aufgeteilt werden. Alternativ ist es aber auch möglich, dass in dem Branchschritt die Baumstruktur durch Aufteilung der möglichen Parkplätze nach einer unterschiedlichen Reihenfolge bestimmt wird. In dem Bound- Schritt wird bestimmt, welche Zweige des Entscheidungsbaumes nicht weiterverfolgt werden. Hierdurch wird der Berechnungsaufwand begrenzt. Vorzugsweise werden hierbei ein oberer Grenzwert (Upper Bound UB) und ein unterer Grenzwert (Lower Bound LB) berechnet und die Werte des jeweiligen Knotens, insbesondere die Erwartungswerte des jeweiligen Knotens mit Grenzwerten eines weiteren Knotens verglichen.

Gemäß einem weiteren Aspekt betrifft die vorliegende Erfindung ein System zur Optimierung der Parkplatzsuche eines Fahrzeuges. Das System ist dadurch gekennzeichnet, dass das System zumindest eine Lösungseinheit zur Ermittlung mindestens einer Optimierungslösung aus mindestens einer Lösungsoption, mindestens eine Bestimmungseinheit zur Bestimmung der Wahrscheinlichkeit der Verfügbarkeit mindestens eines Parkplatzes, mindestens eine Ermittlungseinheit zur Ermittlung der Dauer zum Erreichen des Zielortes von dem Parkplatz und

mindestens eine Berechnungseinheit zur Berechnung der Fahrtdauer von einem Startort zu mindestens einem Parkplatz umfasst und die Lösungseinheit mit der Bestimmungseinheit, der Ermittlungseinheit und der Berechnungseinheit verbunden ist.

Die Einheiten des erfindungsgemäßen Systems können als separate Einheiten ausgeführt sein. Es liegt jedoch auch im Rahmen der Erfindung, dass die Einheiten zumindest teilweise zusammengefasst sind. Die Einheiten können zumindest teilweise als Software umgesetzt sein. Die Bestimmungseinheit zur Bestimmung der Wahrscheinlichkeit der Verfügbarkeit ist vorzugsweise mit mindestens einer Datenbank und/oder einem Diensteserver verbunden, und kann über die Verbindung aktuelle und/oder historische Daten zu der Verfügbarkeit eines Parkplatzes erhalten.

Zumindest die Ermittlungseinheit zur Ermittlung der Dauer zum Erreichen des

Zielortes von dem Parkplatz und/oder die Berechnungseinheit zur Berechnung der Fahrtdauer von einem Startort zu mindestens einem Parkplatz ist vorzugsweise mit einer weiteren Datenbank verbunden, in der beispielsweise Präferenzen des

Fahrers, Eigenschaften des Fahrers und/oder des Fahrzeuges hinterlegt sind.

Indem die Lösungseinheit mit den weiteren Einheiten des Systems verbunden ist, kann bei der Ermittlung der mindestens einen Optimierungslösung aus mindestens einer Lösungsoption die Wahrscheinlichkeit der Verfügbarkeit sowie die Fahrtdauer und die Dauer zum Erreichen des Zielortes von dem Parkplatz berücksichtigt werden. Die Lösungseinheit kann zudem mit mindestens einer Datenbank, in der beispielsweise Präferenzen des Fahrers hinterlegt sein können, verbunden sein und aufgrund der aus dieser Datenbank erhaltenen Informationen der Präferenzen kann das Optimierungsproblem in der Lösungseinheit entsprechend formuliert werden. Zusätzlich ist gemäß einer Ausführungsform die Lösungseinheit oder eine weitere Einheit des Systems vorzugsweise mit einer Datenbank verbunden, in der zumindest Informationen zu alternativen Fortbewegungsmitteln an Parkplätzen enthalten sind. Die zum Identifizieren von Parkplätzen und der Berechnung der unterschiedlichen Zeitdauern (Fahrtdauer und Zieldauer) erforderlichen geographischen Angaben werden vorzugsweise aus einer digitalen Karte erhalten.

Gemäß einer bevorzugten Ausführungsform umfasst das System ein

Navigationssystem oder weist zumindest eine Schnittstelle zur Kommunikation mit einem Navigationssystem auf. Die Verbindung des Systems zu einem

Navigationssystem oder die Integration des Systems in einem Navigationssystem weist den Vorteil auf, dass zum einen erforderliche Informationen, wie Positionen von Parkplätzen, der Zielort, Straßenverläufe, Fußwegverläufe und dergleichen von dem System auf einfache Weise erhalten werden können. Zudem ist an einem Navigationssystem in der Regel eine Ausgabeeinheit zur optischen und/oder akustischen Ausgabe von Informationen vorgesehen. Diese Ausgabeeinheit kann durch das erfindungsgemäße System genutzt werden und darüber können die Optimierungslösungen, beispielsweise in Form einer Route ausgegeben werden.

Gemäß einem weiteren Aspekt betrifft die Erfindung ein Computerprogrammprodukt, das in einen digitalen Rechner oder Rechnersystem, insbesondere in den internen Speicher, geladen werden kann und Softwarecodeabschnitte umfasst, mit denen die Schritte des erfindungsgemäßen Verfahrens ausgeführt werden, wenn das Produkt auf dem Rechner oder Rechnersystem läuft.

Der Rechner oder das Rechnersystem kann beispielsweise die Rechnereinheit des erfindungsgemäßen Systems und vorzugsweise die Rechnereinheit eines

Navigationssystems sein.

Die Softwarecodeabschnitte können auch als Algorithmus bezeichnet werden.

Vorzugsweise umfasst das Computerprogrammprodukt zumindest zwei

Softwarecodeabschnitte, wobei einer zur Bestimmung der Wahrscheinlichkeit und mindestens ein weiterer zur Bestimmung der Zeitdauern (Fahrtdauer, Zieldauer) und/oder zur Bestimmung des Aufwandes (Fahrtaufwand, Zielaufwand) dient.

Das Computerprogrammprodukt und insbesondere die Softwarecodeabschnitte weisen vorzugweise mindestens eine Schnittstelle zu einem Navigationssystem des Fahrzeuges auf. Diese Schnittstelle kann als ein Abrufbefehl in dem

Softwarecodeabschnitt hinterlegt sein. Über diese Schnittstelle, können die für das erfindungsgemäße Verfahren notwendigen Kartendaten oder andere Informationen, wie beispielsweise die Position des Zielortes, von dem Navigationssystem abgefragt werden.

Vorteile und Merkmale, die bezüglich des erfindungsgemäßen Verfahrens oder des erfindungsgemäße Systems beschrieben werden, gelten - soweit anwendbar - ebenfalls für das erfindungsgemäße Computerprogrammprodukt und jeweils umgekehrt. Die Vorteile und Merkmale werden hierbei gegebenenfalls nur einmalig beschrieben. Mit der vorliegenden Erfindung wird somit eine Möglichkeit geschaffen, in dem Fall, in dem an einem Ort mit zu wenigen Parkplätzen auf der Straße nach einem Platz für das Fahrzeug gesucht wird, eine Unterstützung zu geben, wie einerseits schnell und andererseits nicht zu weit vom Zielort ein Parkplatz gefunden werden kann.

Insbesondere kann mit der vorliegenden Erfindung für die„letzte Meile" zu einem Ziel in einem Fahrzeug eine Route generiert werden.

Die vorliegende Erfindung wird im Folgenden erneut unter Bezugnahme auf die beiliegenden Figuren genauer beschrieben. Es zeigen: Figur 1 : eine schematische Darstellung mehrerer Positionen eines Fahrzeuges;

Figur 2: eine schematische Darstellung eines Entscheidungsbaumes; und

Figur 3: eine schematische Darstellung einer Überprüfung eines

Entscheidungsbaumes.

In Figur 1 ist eine mögliche Route eines Fahrzeuges durch Angabe von Positionen x gezeigt. Das Fahrzeug (nicht dargestellt) befindet sich beispielsweise an der Position x _s . Als Zielort, der auch als endgültige Position bezeichnet werden kann, gibt der Fahrer die Position xt an. Diese Angabe kann der Fahrer beispielsweise in ein

Navigationssystem des Fahrzeuges eingeben. Ist an der Position xt kein Parkplatz vorhanden oder zumindest kein Parkplatz verfügbar, muss der Fahrer nach Optionen suchen. Bei dem in Figur 1 gezeigten Szenario werden in der Nähe des Zielortes mehrere Parkplätze erkannt. Die Parkplätze befinden sich an den Positionen xi , X2, X3. Ohne Anwendung des erfindungsgemäßen Verfahrens würde der Fahrer voraussichtlich die Parkplätze, die auch als Optionen bezeichnet werden, in der Reihenfolge xi , X2, und dann X3 abfahren. Mit einer Wahrscheinlichkeit pi ist der Fahrer dabei erfolgreich an xi parken zu können und von dort zu xt gehen zu können. Ist der Fahrer nicht erfolgreich ist, fährt er bei X2 fort und verfährt so weiter.

Bei dieser Verfahrensweise kann es sein, dass der Fahrer unnötig die Positionen xi und X2 anfährt, wenn deren Wahrscheinlichkeit der Verfügbarkeit zu gering ist oder den Parkplatz an Position xi wählt, obwohl der Parkplatz an X2 einen geringeren relativen Abstand zu dem Zielort xt aufweist.

Dieses Problem adressiert die vorliegende Erfindung.

Insbesondere wird erfindungsgemäß ein Optimierungsproblem gelöst, bei dem zumindest die Optimierungsparameter der Wahrscheinlichkeit der Verfügbarkeit, der Fahrtdauer und die relative Position des Parkplatzes zu dem Zielort berücksichtigt werden.

Vorzugsweise werden bei dem erfindungsgemäßen Verfahren einige Bedingungen vorgegeben, die einzuhalten sind:

1 ) Vorhandensein eines Satzes von Lösungsoptionen, , xi , .. . , x _n mit

Wahrscheinlichkeiten = [pi ... p _n ] für den Erfolg. Die Lösungsoptionen, die im Folgenden auch als Optionen bezeichnet werden, stellen insbesondere

Parkplätze dar.

2) Das Problem muss realisierbar sein. Erfindungsgemäß muss zumindest eine der Optionen eine Erfolgswahrscheinlichkeit von 1 besitzen. Beispielsweise kann eine Parkgarage vorliegen. Besitzt keine der Optionen eine

Erfolgswahrscheinlichkeit von 1 , so ist es möglich dass der Fahrer keinen Parkplatz findet.

3) Vorhandensein einer Kostenfunktion c _w (j) mit 1 < j < n, die die Kosten

quantifiziert, um von Xj zu xt zu gehen. Die Kosten können auch als Aufwand bezeichnet werden. Die Kostenfunktion wird insbesondere bei der

Bestimmung des Optimierungsparameters der relativen Position des

Parkplatzes zu dem Zielort berücksichtigt. Außer dem Abstand des Zielortes zu dem Parkplatz wird vorzugsweise die Zeit, das heißt die Dauer als

Kostenfunktion angeben, die benötigt wird um von dem Parkplatz zu dem Zielort zu gelangen, insbesondere dorthin zu laufen. Hierbei kann der

Aufwand berücksichtigt werden, beispielsweise die Gehgeschwindigkeit des Fahrers.

4) Vorzugsweise ist erfindungsgemäß auch eine Kostenfunktion Cd (i, j, s) mit 0 < j, i < n, die die Kosten quantifiziert, um von Xj nach xi zu fahren, wenn die aktuelle Lage des Fahrzeuges s ist, gegeben. Diese Lage kann zum Beispiel dazu genutzt werden, um zwischen Richtungen in die das Fahrzeug gerichtet ist, zu unterscheiden. Z.B. können die Kosten die Differenz für ein Fahrzeug, das an der linken Spur in Richtung Norden gerichtet ist, und einem Fahrzeug, das auf der rechten Spur das nach Süden gerichtet ist, sein. Zudem werden die Kosten, die auch als Aufwand bezeichnet werden, auch bei der

Bestimmung des Optimierungsparameters der Suchdauer verwendet.

Beispielsweise kann die mögliche Fahrgeschwindigkeit oder die vom Fahrer vorgebaren zumutbaren Brennstoffkosten berücksichtigt werden.

Mit der vorliegenden Erfindung wird es möglich eine optimale Reihenfolge von Lösungsoptionen zu finden, die die zu erwartenden Kosten der Tour von xo das heißt dem Startort nach xt minimiert.

Erfindungsgemäß wird hierzu vorzugsweise davon ausgegangen, dass π: {1 , ... , n} — » ^■ {1 , ... , n} eine Permutation, die die Reihenfolge beschreibt, ist. Ziel ist es dabei die Permutation zu finden, die Folgendes minimiert: arg min E (π, )

π

Mit der Definition (1 ), die dem Erwartungswert des Fahrers entspricht Ε(π, ρ = P _ni {c _d (0, 77:0 + cw^)) + Ρπ^ο^π^ ^) + cw(n ₂ )) + P„ ₃ (c _d (7r ₂ , 7r ₃ ) + cw(n ₃ )) + ... mit π (/) = π.

Und Definition 2:

Pn Vn

Ρπ ₂ = (1 - Ρ _πι )Ρπ ₂

Ρπ ₃ = (1 - Ρ _πι ^~ Ρπ ₂ ) π ₃

Ρη, = (1 - Ρ _πι ^~ Ρη ₂ ^~ Ρπ ₃ )Ρ

Ρ _π . definiert die Wahrscheinlichkeit, dass der j-ste Versuch nach zuvor j-1 - erfolglosen Versuchen erfolgreich ist. Natürlich ist Σ;=ι P _nj = 1. wenn zumindest ein k existiert, für das p _nk = 1 ist. Ohne Verlust der Allgemeingültigkeit wird davon ausgegangen, dass k = n ist. sl + Plwl + P2(tl2 + w2) + P3(tl2 + t23 + w3) + ···

sl + Plwl + P2w2 + P3w3 + ··· P2tl2 + P3(tl2 + t23) + ...

sl + Plwl + (1 - P _! )t ₁₂ + P2w2 + (1 - P ₁ - P ₂ )t ₂₃ + P3w3 + (1 - P ₁ - P ₂ - P ₃ )t ₃

+ ...

Die optimale Permutation π , das heißt die Optimierungslösung, kann durch Evaluierung aller Permutationen gefunden werden. Jedoch können diese zahlreich sein. Für n Optionen, müssen n! verschiedenen Permutationen überprüft werden. Um eine geeignete Lösung in einer akzeptablen Zeit zu erhalten wird erfindungsgemäß vorzugsweise ein Branch-and-Bound Schema verwendet.

Offensichtlich ist der Wurzelknoten, an dem die Optimierung beginnt und der auch als Startort bezeichnet wird, xo (dargestellt als 0). Von diesem Startort aus sind mehrere Entscheidungen möglich. Insbesondere kommt der Parkplatz xi als eine Option in Betracht. Auch die Parkplätze X2 und X3 könnten in Betracht kommen.

Erfindungsgemäß wird nun ein intelligenter Weg verwendet, um die beste

Permutation zu finden, ohne den gesamten Entscheidungsbaum zu untersuchen. Dies kann durch das Branch-and-Bound Schema erreicht werden.

Es wird ein Satz an Optionen der Größe N betrachte und angenommen, dass p = [Pi■■■ P _N Y die Verfügbarkeit / Wahrscheinlichkeit des Erfolges an jeder Option angibt. Hierbei wird angenommen, dass N groß genug ist, dass zumindest ein j existiert, für das pj = 1 ist.

Weiterhin soll π = [π^ ... π _η ] ^τ die optimale Permutation aller Optionen so angeben, dass E (π) < E (*) ist.

Offensichtlich ist:

• n < N und

• p^ _n = 1 sowie

· pj < l fürj E { _fti p _{ftn i} }

Für den trivialen Nachweis werden die Definitionen (1 ) und (2) überprüft. Wenn es eine Option π _; - gibt mit p^ _n = 1 und j < 1 , dann ist P _n = 0 und Option π _η hat keinen Einfluss auf Ε(π) und kann demgemäß von der optimalen Lösung entfernt werden. Andererseits, gibt es, wenn _Sn 1 weiterhin weitere Optionen, die Ε(π) beeinflussen und untersucht werden müssen. Daher kann π _η nicht optimal sein. Wenn weiterhin angegeben wird, dass p _ft = 1 mit j < n, dann kann mit dem selben

Argument eine untere Grenze (Lower Bound LB) für die optimale Lösung geschaffen werden. Dahingehend soll = [ _x ... p _{nj i} l p _n . _+i ... p _N ] ^T den künstlichen Satz an

Wahrscheinlichkeiten angeben.

Dann ist

Ε(π, ρί) < E t, p) Dies ist einfach zu verstehen. Die allgemeine Situation, bei der alle Optionen berücksichtigt wurden, verbessert sich mit der Änderung von p zu p ^j und daher können die zu erwarteten Kosten für die optimale Lösung nicht größer sein. Oder anders ausgedrückt, wenn dies nicht der Fall ist, dann ist es besser wenn man an der Option π _; - nicht erfolgreich ist, was ein Widerspruch zu dem Optimum von ft ist.

Es ist zu bemerken, dass E ft, p ^j ) evaluiert werden kann, ohne n _j , ... , π _η zu berücksichtigen.

Zudem wird vorzugsweise eine obere Grenze (Upper Bound UB) bestimmt.

Konstruiert man die folgende suboptimale Lösung n ^j = [π^ ... π _/ _ ₁ π _η ] ^Γ , dann

E t, p) < E(n ^J , p)

Dies ist einfach zu erkennen. Wir haben eben die optimale Permutation in eine andere Permutation geändert. Da ρ _πη = 1, kann man danach anhalten.

Bei der Optimierung geht es darum, wie man die optimale Permutation findet, ohne den gesamten Entscheidungsbaum, der oben vorgestellt wurde, zu untersuchen. Dies wird durch die in Figur 3 gezeigten Schritte gelöst: 1 ) Sofern nicht unbeendet, muss der meistversprechende Knoten identifiziert werden

2) Der identifizierte Knoten wird expandiert

3) Die neu expandierten Knoten werden evaluiert und die Obergrenze (Upper Bound) und Untergrenze (Lower Bound) werden berechnet.

4) Basierend auf UB/LB werden Knoten die nicht optimal sein können

geschlossen und von t entfernt.

Die vorliegende Erfindung bringt unter anderem den Vorteil mit sich, dass diese eine Zeitersparnis für den Fahrer darstellt. Zudem können Verkehrs- und

Emissionsersparnisse erzielt werden.