Rechenzeiteffiziente Routenbestimmung entlang mehrerer vorgegebener Wegpunkte mit dazwischenliegenden gegebenen Verbindungsstrecken

摘要

Die Erfindung betrifft ein Verfahren zur Bestimmung einer Route entlang mehr als zwei aufeinander folgender vorgegebener Wegpunkte mit gegebenen Verbindungsstrecken dazwischen. Dabei ist zwischen zumindest einem Paar von zwei aufeinander folgenden Wegpunkten eine Mehrzahl von Verbindungstrecken gegeben. Jeder Verbindungsstrecke sind jeweilige Kosten und vorzugsweise auch eine jeweilige Zeitdauer zugeordnet. In einem ersten Schritt des Verfahrens wird ein Baum umfassend Kanten und durch Kanten verbundene Knoten (11.1; 12.1-12.3; 13.1-13.5) erzeugt. Jeder Knoten ist einem bestimmten Wegpunkt zugeordnet und jede Kante entspricht einer Verbindungsstrecke. Die Route wird basierend auf einer Auswahl von Kanten des Baumes bestimmt.