[go: up one dir, main page]

WO1999020981A1 - Verfahren und anordnung zur ermittlung einer route von einem startpunkt zu einem zielpunkt - Google Patents

Verfahren und anordnung zur ermittlung einer route von einem startpunkt zu einem zielpunkt Download PDF

Info

Publication number
WO1999020981A1
WO1999020981A1 PCT/DE1998/002891 DE9802891W WO9920981A1 WO 1999020981 A1 WO1999020981 A1 WO 1999020981A1 DE 9802891 W DE9802891 W DE 9802891W WO 9920981 A1 WO9920981 A1 WO 9920981A1
Authority
WO
WIPO (PCT)
Prior art keywords
partial
route
sub
module
starting point
Prior art date
Application number
PCT/DE1998/002891
Other languages
English (en)
French (fr)
Inventor
Donald Steiner
Hartmut Dieterich
Alastair Burt
Jürgen LIND
Original Assignee
Siemens Aktiengesellschaft
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Siemens Aktiengesellschaft filed Critical Siemens Aktiengesellschaft
Priority to DE59802765T priority Critical patent/DE59802765D1/de
Priority to US09/529,785 priority patent/US6421605B1/en
Priority to JP2000517253A priority patent/JP2001521142A/ja
Priority to AT98955356T priority patent/ATE209338T1/de
Priority to EP98955356A priority patent/EP1025423B1/de
Publication of WO1999020981A1 publication Critical patent/WO1999020981A1/de

Links

Classifications

    • GPHYSICS
    • G01MEASURING; TESTING
    • G01CMEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
    • G01C21/00Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
    • G01C21/26Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
    • G01C21/34Route searching; Route guidance
    • G01C21/3446Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes

Definitions

  • the invention relates to the determination of a route from a starting point to a destination.
  • a specifiable starting point i.e. to determine a starting point at which a user of the route planning system wants to start a journey and a destination to which the user wants to travel to find a route in such a way that both the determination of the route itself takes place as quickly as possible and the route with regard to various, specifiable requirements is optimized.
  • Requirements in this sense can be, for example, a travel time required for the entire route, the route length or certain requirements that certain means of transport should be used preferentially.
  • a route description i.e. a set of nodes and edges when the path is represented by a graph that has nodes and edges from a starting point to a destination.
  • the route should be determined as quickly and flexibly as possible.
  • the problem is solved by the method according to claim 1 and by the arrangement according to claim 9.
  • the route is determined from a starting point to a destination in an iterative process.
  • the starting point and the destination point are in different partial route maps, the partial route maps being stored in digital form.
  • the process comprises the following steps:
  • Sub-modules which are each assigned to a sub-route map, are supplied with digital messages, each containing at least one sub-starting point and at least one sub-destination, which are located in the sub-route map of the sub-module that receives the respective message;
  • At least one partial route between the respective partial starting point and the partial target point is determined from each partial module
  • the route is formed from the partial routes.
  • the arrangement has a processor unit which is set up in such a way that an iterative method is used to determine a route from a starting point to a destination, which are each in different sub-route maps, the sub-route maps being stored in digital form.
  • the process comprises the following steps:
  • Sub-modules each of which is assigned to a sub-route map, are supplied with digital messages, each of which contains at least one sub-starting point and at least one sub-destination, which are located in the sub-route map of the sub-module that receives the respective message;
  • At least one partial route between the respective partial starting point and the partial target point is determined from each partial module; - The route is formed from the partial routes.
  • the invention ensures a quick, flexible determination of a route for a user from a predeterminable starting point to a predefinable destination (at a predeterminable point in time).
  • the extremely complex problem of route determination is split up into sub-problems, which are solved independently of each other, thereby it becomes possible to have both central and local knowledge in secondary conditions for the determination of partial routes or. the route.
  • the partial route maps are stored in the form of partial route graphs with nodes and edges, and a method for determining the shortest paths is used to determine the partial route.
  • the process determination of the shortest paths it is possible in a simple manner in the individual sub-modules to form optimized sub-routes with regard to the predefinable optimization criteria.
  • the use of methods for determining the shortest paths is to be understood in such a way that in each case a partial route is determined in an optimized manner with respect to a predetermined cost function (optimization criteria).
  • the edges are each assigned cost values that correspond to the specified optimization criterion.
  • predefinable optimization criteria can also be, for example, the minimization of turning processes, in particular left-turning processes in cities.
  • the time for which the route is to be planned can also be taken into account in the invention.
  • the time of travel can be important, since the decision for the route is the most important
  • FIG. 1 shows a block diagram in which the arrangement and exchange of messages between the software agents is described
  • Figure 2 is a sketch of several sub-route maps, on the basis of which sketch the invention is described.
  • An arrangement 101 for determining a route based on a user request 102, which is supplied to the arrangement 101, has the following components:
  • a software agent is to be understood as a program for a data processing system which, based on internal targets, is able to independently accomplish its task without any external influence.
  • a software agent is referred to as an agent.
  • the determination of routes is carried out and coordinated in a central agent.
  • the arrangement 101 stores various maps and transport networks in the form of a graph with nodes and edges.
  • a traffic network is to be understood as a rail network, for example.
  • timetables of a public transport network can be assigned to the transport networks. These are also stored in digital form.
  • a sub-route map is assigned to each sub-module.
  • a partial The route map is, for example, a traffic network that comprises at least a part of the entire geographic area taken into account by the arrangement.
  • the sub-route maps can contain different geographical areas, or also overlapping geographic areas, in which case different traffic networks (tram network, bus network, railway network) can be contained in the sub-route maps.
  • Each sub-module which is implemented by a software agent, is set up in such a way that at least one sub-route is ascertained using methods for determining the shortest paths in the sub-route map that is assigned to the respective sub-module.
  • the result of the partial route is a partial target point and a partial starting point, which lie on the edge of the partial route map, and the route within the partial route map that leads from the partial starting point to the partial target point.
  • a first sub-module Us is assigned to a first sub-route map TUg, which contains a road network for individual traffic in the city of Kunststoff.
  • Individual traffic is further understood to mean traffic using motor vehicles or bicycles.
  • a second sub-module Uy is assigned to a second sub-route map TU V , which, in the form of a graph, contains the road network of the Bavarian motorways and trunk roads digitally stored.
  • a third sub-module Up_ is assigned to a third sub-route map TUp, which describes a road network for individual traffic in the Nuremberg-Er Weg-Fürth area.
  • a fourth sub-module Ug is assigned to a fourth sub-route map TU E , which contains a network in which all public transport (bus, tram, rail transport) is stored in the state of Bavaria.
  • Starting point S and a destination Z contains a route that is as optimized as possible, i.e. to determine a set of connected nodes and edges from the starting point S to the destination point Z, it being possible to use different means of transport.
  • a set of agents, ie sub-modules Ug, U v , U R , Ug, is determined by a central agent I for the starting point S and the destination Z, which are used to determine a route between the starting point S and the destination Z come into question.
  • All sub-modules Ug, Uy, U R , U E send a second message 2 back to the central agent I, which contains a response, ie a positive or a negative message.
  • the first sub-module Ug and the fourth sub-module U E know the starting point S, ie the starting point S lies in their respective sub-route map TU S , TU E.
  • the third sub-module U R and the fourth sub-module U E know the destination Z, ie the destination Z lies in their respective sub-route map TU R , TU E.
  • the second submodule Uy contains neither the starting point S nor the destination point Z in the subroutine map assigned to it.
  • the second submodule Uy and further submodules U j _ (not shown), which are contained in the arrangement, send back a second message 2, in which is indicated that both the starting point S and the destination point Z are unknown to the submodule Uy, U j _, ie they are not in their respective subroutine map TUy, TU j _.
  • an identification information is contained with which the starting point S or the destination point Z can be uniquely identified in the partial route map.
  • the central agent I determines a number of sequences in which it is specified which sequences of sub-modules U s , U R , U E , Uy determine the route from the starting point S to the destination Z come into question.
  • a local knowledge base KB j in the form of a database is used, which is accessible to the central agent I.
  • sequences of sub-modules are stored, the sub-routes of which are used one after the other in order to get from the starting point S to the destination point Z.
  • the local knowledge base KBj sends a third message 3 to the central agent I, which contains the determined sequences, in this case:
  • the route can as a sequence of the partial route map TUg of the first partial module Ug, followed by a partial route of the partial route map TUy of the second partial module Uy and finally a partial route of the partial route map TU R of the third partial module U.
  • partial starting points and partial destination points of the partial routes which are formed by the first partial module Ug, the second partial module Uy and the third partial module U R , are determined.
  • transition points Ügy, Üy R a list of all theoretically possible partial target points and partial starting points, which are hereinafter referred to as transition points Ügy, Üy R, is stored for the respective partial route maps TUg, TUy, TU R.
  • the smallest possible number of partial starting points and partial destination points is selected from the set of all possible transition points Ügy, Üy R in order to keep the number of partial routes to be determined as low as possible.
  • the selection is made taking into account local knowledge, which is incorporated in a heuristic to determine transition points Ügy, Üy R.
  • a fourth message 4 the knowledge base KB of the central agent I is given the request to determine the transition points Ügy, Üy R.
  • a set of transition points Ügy between the partial route maps TUg, TUy of the first submodule Ug and the second partial module Uy and a set of transition points Üy £ between partial route maps TUy, TU is provided by the knowledge base KB in a fifth message 5 R of the second sub-module Uy and the third sub-module U are sent back.
  • the transition points Ügy, Üy R are identified by points in FIG.
  • the list consists of taxi ranks.
  • the list consists of predetermined points at which one street at a time passes from one network to the other network.
  • a sixth message 6 which is sent by the central agent I to the first sub-module Ug, the second sub-module Uy and the third sub-module U R , the sub-modules Ug, Uy, U R are asked whether they are local Framework conditions, each in a local knowledge base KBg, KBy, KB R , which is clearly assigned to the respective sub-module Ug, Uy, U R , other transition points Ügy, Üy R , which are suitable with regard to the specified optimization criterion.
  • Such local knowledge can be seen in the fact that the first sub-module Ug, using its associated local knowledge base KBg, knows that - due to heuristics and domain-specific knowledge from the local knowledge base KBg - for a longer trip north from the specified starting point S , which is located relatively far in the south of Kunststoff, transition points Ügy in the southeast and north of the first partial route map TUg must be taken into account.
  • the central agent I From the additional suggestions that are supplied to the central agent I by the individual sub-modules Ug, Uy, U R, the central agent I becomes a subset TÜgy for transitions from the first partial route map TUg and the second partial route map TUy.
  • a second subset TÜy j ⁇ of transition points Ü ⁇ is determined for the transition points Ü ⁇ , which represent transitions between the second partial route map TUy and the third partial route map TU.
  • a seventh message 7 is sent by the central agent I to the first sub-module Ug, the second sub-module Uy and the third sub-module U R.
  • the seventh message 7 in each case contains a request for determining one or more sub-routes which are optimal with regard to the predefined optimization criterion time.
  • the determination of sub-routes from the starting point S to the five transition points Ügy of the first subset TÜgy is requested.
  • the seventh message 7, which is fed to the second sub-module Uy, contains a request for determining sub-routes of all combinations between the transition points Ügy of the first subset TÜgy and the transition points Üy j ⁇ of the second subset Üyj ⁇ .
  • the seventh message 7, which is fed to the third sub-module U R , contains a request for determining sub-routes from the two transition points Üy ⁇ of the second subset TÜy to the destination point Z.
  • the partial routes in the partial modules are determined using methods for determining the shortest paths, for example the method according to Dijkstra.
  • the respective nodes and / or edges of the partial route map are each assigned cost values which are used in the optimization to determine the partial route within the partial route map in one Cost function are taken into account.
  • the cost values and the type of consideration depend on the type of optimization criterion. Possible optimization criteria are the total time required for the trip, the total route length to be minimized, or other general conditions.
  • the respective sub-module that is "responsible" for the means of transport is not commissioned to calculate a partial route.
  • a route is determined by the central agent I, the route being a set of connected nodes and edges, starting from the starting point S to the destination node Z.
  • the central agent I selects the best route with regard to the optimization criterion “time”.
  • transition times for changing the means of transport and discrete departure times of the respective public transport must be taken into account. This is not necessary for the transition between networks for individual traffic.
  • the route selected is that which is optimized with regard to the optimization criterion.
  • the selected route is made available to the user as a response 103 to his user request 102 as a result, for example displayed on a screen or output in some other form.
  • the central agent I is aware of all significant sub-modules that are required for determining the route. In a variant, however, it is provided that the information about required sub-modules is stored in further agents. The information is then queried by the central agent I.
  • the possible sequences of partial route maps are not stored in the knowledge base KB of the central agent I, but in a further agent. In this case, this information would also be queried by the further agent through the central agent I.
  • the variant can occur in which the last section of the trip is covered by a taxi.
  • the sequence should be supplemented by the further sub-module U (supplementing the sequences by the postfix "-» U R "), since the last sub-module U is not the exact route to the destination point Z, but that for the last section time would have to determine.

Landscapes

  • Engineering & Computer Science (AREA)
  • Radar, Positioning & Navigation (AREA)
  • Remote Sensing (AREA)
  • Automation & Control Theory (AREA)
  • Physics & Mathematics (AREA)
  • General Physics & Mathematics (AREA)
  • Navigation (AREA)
  • Instructional Devices (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

In einem iterativen Verfahren wird eine Route von einem Startpunkt zu einem Zielpunkt ermittelt. Dabei werden Teilmodulen digitale Nachrichten zugeführt, die jeweils mindestens einen Teilstartpunkt und einen Teilzielpunkt enthalten, die in der Teilroutenkarte enthalten sind, die dem jeweiligen Teilmodul zugeordnet ist, welches die jeweilige Nachricht empfängt. Von jedem Teilmodul wird eine Teilroute zwischen dem jeweiligen Teilstartpunkt und dem jeweiligen Teilzielpunkt ermittelt. Aus den Teilrouten wird die Route gebildet.

Description

Beschreibung
Verfahren und Anordnung zur Ermittlung einer Route von einem Startpunkt zu einem Zielpunkt
Die Erfindung betrifft die Ermittlung einer Route von einem Startpunkt zu einem Zielpunkt.
In rechnergestützten Routenplanungssystemen gilt es, zwischen einem vorgebbaren Startpunkt, d.h. einem Ausgangsort, an dem ein Benutzer des RoutenplanungsSystems eine Reise beginnen möchte und einem Zielpunkt, zu dem der Benutzer reisen möchte, eine Route zu ermitteln in einer Weise, daß sowohl die Ermittlung der Route selbst möglichst schnell erfolgt und die Route hinsichtlich verschiedener, vorgebbarer Anforderungen optimiert ist.
Anforderungen in diesem Sinne können beispielsweise sein eine für die gesamte Route benötigte Reisezeit, die Routenlänge oder auch bestimmte Vorgaben, daß bestimmte Verkehrsmittel bevorzugt benutzt werden sollen.
Unter einer Route ist im weiteren eine Wegbeschreibung, d.h. eine Menge von Knoten und Kanten, wenn der Weg durch einen Graphen repräsentiert wird, der Knoten und Kanten aufweist, von einem Startpunkt zu einem Zielpunkt, zu verstehen.
Die Ermittlung der Route soll möglichst schnell und flexibel durchgeführt werden.
Eine Übersicht über Verfahren zur Ermittlung kürzester Pfade ist in [1] zu finden.
Das Problem wird durch das Verfahren gemäß Patentanspruch 1 sowie durch die Anordnung gemäß Patentanspruch 9 gelöst. Die Route wird von einem Startpunkt zu einem Zielpunkt in einem iterativen Verfahren ermittelt. Der Startpunkt und der Zielpunkt liegen in unterschiedlichen Teilroutenkarten, wobei die Teilroutenkarten in digitaler Form gespeichert sind. Das Verfahren umfaßt folgende Schritte :
- Teilmodulen, die jeweils einer Teilroutenkarte zugeordnet sind, werden digitale Nachrichten zugeführt, die jeweils mindestens einen Teilstartpunkt und mindestens einen Teilzielpunkt enthalten, die in der Teilroutenkarte des Teilmoduls liegen, das die jeweilige Nachricht empfängt;
- von jedem Teilmodul wird mindestens eine Teilroute zwischen dem jeweiligen Teilstartpunkt und dem Teilzielpunkt ermittelt;
- aus den Teilrouten wird die Route gebildet.
Die Anordnung weist eine Prozessoreinheit auf, die derart eingerichtet ist, daß in einem iterativen Verfahren eine Route von einem Startpunkt zu einem Zielpunkt, die jeweils in unterschiedlichen Teilroutenkarten liegen, ermittelt wird, wobei die Teilroutenkarten in digitaler Form gespeichert sind. Das Verfahren umfaßt folgende Schritte:
- Teilmodulen, die jeweils einer Teilroutenkarte zugeordnet sind, werden digitale Nachrichten zugeführt, die jeweils mindestens einen Teilstartpunkt und mindestens einen Teilziel- punkt enthalten, die in der Teilroutenkarte des Teilmoduls liegen, das die jeweilige Nachricht empfängt;
- von jedem Teilmodul wird mindestens eine Teilroute zwischen dem jeweiligen Teilstartpunkt und dem Teilzielpunkt ermittelt; - aus den Teilrouten wird die Route gebildet.
Durch die Erfindung wird eine schnelle, flexible Ermittlung einer Route für einen Benutzer von einem vorgebbaren Startpunkt zu einem vorgebbaren Zielpunkt (zu einem vorgebbaren Zeitpunkt) gewährleistet. Dabei wird das äußerst komplexe Problem der Routenermittlung in Teilprobleme aufgespaltet, welches jeweils unabhängig voneinander gelöst wird, wodurch es möglich wird, sowohl zentrales als auch lokales Wissen in Nebenbedingungen der Ermittlung von Teilrouten bzw . der Route zu berücksichtigen .
Weiterbildungen der Erfindung ergeben sich aus den abhängigen Ansprüchen .
Es ist in einer Weiterbildung vorteilhaft , daß die Teilroutenkarten in Form von Teilroutengraphen mit Knoten und Kanten gespeichert sind und zur Ermittlung der Teilroute j eweils ein Verfahren zur Ermittlung kürzester Pfade eingesetzt wird .
Durch Einsatz der Verfahrensermittlung kürzester Pfade ist es in den einzelnen Teilmodulen auf einfache Weise möglich, op- timierte Teilrouten hinsichtlich der vorgebbaren Optimierungskriterien zu bilden . Der Einsatz von Verfahren zur Ermittlung kürzester Pfade ist derart zu verstehen, daß jeweils eine Teilroute hinsichtlich einer vorgegebenen Kostenfunktion (Optimierungskriterien) optimiert ermittelt wird . Den Kanten sind jeweils Kostenwerte zugeordnet , die dem vorgegebenen Optimierungskriterium entsprechen .
Vorgebbare Optimierungskriterien können neben der Weglänge oder der Dauer einer Route beispielsweise auch die Minimie- rung von Abbiegevorgängen, insbesondere von Linksabbiege orgängen in Städten sein .
Ferner kann der Zeitpunkt , für den die Route geplant werden soll , bei der Erf indung berücksichtigt werden . So kann beispielsweise die Zeit der Rei- se durchaus von Bedeutung sein, da die Entscheidung, für die Route den
Individualverkehr oder den öffentlichen Verkehr zu wählen, vom gewählten Zeitpunkt abhängen kann (während der Berufsverkehrszeit wird man von in einer Innenstadt mit dem Auto vermutlich länger brauchen, als unter Verwendung des öffentlichen Verkehrs ; nachts mag die Situation umgekehrt sein) . Ein Ausführungsbeispiel der Erfindung ist in den Figuren dargestellt und wird im weiteren näher erläutert.
Es zeigen
Figur 1 ein Blockdiagramm, in dem die Anordnung sowie der Austausch von Nachrichten zwischen den Software- Agenten beschrieben ist;
Figur 2 eine Skizze von mehreren Teilroutenkarten, anhand welcher Skizze die Erfindung beschrieben wird.
Eine Anordnung 101 zur Ermittlung einer Route aufgrund einer Benutzeranfrage 102, die der Anordnung 101 zugeführt wird, weist folgende Komponenten auf:
Mehrere Software-Agenten. Unter einem Software-Agenten ist ein Programm für eine Datenverarbeitungsanlage zu verstehen, das aufgrund interner Zielvorgaben in der Lage ist, ohne weitere Beeinflussung von außen seine ihm gestellte Aufgabe ei- genständig zu lösen. Im weiteren wird ein Software-Agent als Agent bezeichnet.
In einem zentralen Agenten wird die Ermittlung von Routen durchgeführt und koordiniert.
In diesem Ausführungsbeispiel wird davon ausgegangen, daß in der Anordnung 101 verschiedene Landkarten und Verkehrsnetze in Form eines Graphen mit Knoten und Kanten gespeichert sind. Unter einem Verkehrsnetz ist beispielsweise ein Schienennetz zu verstehen.
Den Verkehrsnetzen zugeordnet können beispielsweise Fahrpläne eines öffentlichen Verkehrsnetzes sein. Diese sind ebenfalls in digitaler Form gespeichert .
In der Anordnung 101 sind mehrere Teilmodule vorgesehen. Jedem Teilmodul ist eine Teilroutenkarte zugeordnet. Eine Teil- routenkarte ist beispielsweise ein Verkehrsnetz, das mindestens einen Teil des gesamten, durch die Anordnung berücksichtigten geographischen Gebiets umfaßt.
Die Teilroutenkarten können unterschiedliche geographische Gebiete, oder auch sich überschneidende geographische Gebiete enthalten, wobei in diesem Fall unterschiedliche Verkehrsnetze (Straßenbahnnetz, Busnetz, Eisenbahnnetz) in den Teilroutenkarten enthalten sein können.
Jedes Teilmodul, das durch einen Software-Agenten realisiert ist, ist derart eingerichtet, daß unter Verwendung von Verfahren zur Ermittlung kürzester Pfade in der Teilroutenkarte, die dem jeweiligen Teilmodul zugeordnet ist, mindestens eine Teilroute ermittelt wird. Ergebnis der Teilroute sind jeweils ein Teilzielpunkt und ein Teilstartpunkt, die am Rand der Teilroutenkarte liegen, sowie die Route innerhalb der Teilroutenkarte, die von dem Teilstartpunkt zu dem Teilzielpunkt führt .
Das Verfahren zur Ermittlung der Route aus den Teilrouten wird im weiteren detailliert beschrieben.
Es wird im weiteren davon ausgegangen, daß ein erstes Teilmo- dul Us einer ersten Teilroutenkarte TUg zugeordnet ist, das ein Straßennetz für den Individualverkehr in der Stadt München enthält .
Unter Individualverkehr ist im weiteren der Verkehr unter Verwendung von Kraftfahrzeugen oder auch Fahrrädern zu verstehen.
Ein zweites Teilmodul Uy ist einer zweiten Teilroutenkarte TUV zugeordnet, die in Form eines Graphen digital gespeichert das Straßennetz der Bayerischen Autobahnen und Fernstraßen enthält . Ein drittes Teilmodul Up_ ist einer dritten Teilroutenkarte TUp zugeordnet, die ein Straßennetz für den Individualverkehr des Großraums Nürnberg-Erlangen-Fürth beschreibt.
Ein viertes Teilmodul Ug ist einer vierten Teilroutenkarte TUE zugeordnet, die ein Netz enthält, in dem der gesamte öffentliche Verkehr (Bus, Straßenbahn, Schienenverkehr) in dem Bundesland Bayern gespeichert ist .
Es gilt nun, aufgrund der Benutzeranfrage 102, die einen
Startpunkt S und einen Zielpunkt Z (sowie optional Abfahrtsoder Ankunftszeitpunkt) enthält, eine möglichst optimierte Route, d.h. eine Menge zusammenhängender Knoten und Kanten von dem Startpunkt S zu dem Zielpunkt Z, zu ermitteln, wobei die Nutzung unterschiedlicher Verkehrsmittel möglich ist.
In dem Ausführungsbeispiel ist in der Benutzeranfrage 102 angegeben, daß der Benutzer eine Reise vom Otto-Hahn-Ring 6 in München (Startpunkt S) nach Nürnberg, Flaschenhofstr. 55 (Zielpunkt Z) am Montag, den 06. Oktober 1997, machen möchte. Der Benutzer muß spätestens um 10.00 Uhr am Zielpunkt Z eingetroffen sein (Nebenbedingung für die Routenermittlung) . Einschränkungen bei der Wahl des Verkehrsmittels gibt es in diesem Ausführungsbeispiel nicht. Das Optimierungskriterium ist die für die Reise benötigte Zeit.
In einem ersten Schritt wird von einem zentralen Agenten I für den Startpunkt S und den Zielpunkt Z eine Menge von Agenten, d.h. Teilmodulen Ug, Uv, UR, Ug, ermittelt, die für die Ermittlung einer Route zwischen dem Startpunkt S und dem Zielpunkt Z in Frage kommen.
Hierfür übersendet der zentrale Agent I an alle ihm bekannten Teilmodule U-^ (i = 1 ... m, m = Anzahl der Teilmodule Uj_) ei- ne erste Nachricht 1. In der ersten Nachricht 1 ist eine Anfrage enthalten, ob der Startpunkt S und/oder der Zielpunkt Z in der Teilroutenkarte TUg, TUy, TUR, TUE des jeweiligen Teilmoduls Us, Uy, UR, UE enthalten ist.
Alle Teilmodule Ug, Uy, UR, UE senden an den zentralen Agen- ten I eine zweite Nachricht 2, in der eine Antwort enthalten ist, d.h. eine positive oder eine negative Nachricht, zurück.
Dem ersten Teilmodul Ug und dem vierten Teilmodul UE ist der Startpunkt S bekannt, d.h. der Startpunkt S liegt in ihrer jeweiligen Teilroutenkarte TUS, TUE .
Dem dritten Teilmodul UR und dem vierten Teilmodul UE ist der Zielpunkt Z bekannt, d.h. der Zielpunkt Z liegt in ihrer jeweiligen Teilroutenkarte TUR, TUE .
Die zweite Nachricht 2 von dem ersten Teilmodul Ug, dem dritten Teilmodul U sowie dem vierten Teilmodul U , die jeweils zu dem zentralen Agenten I übertragen werden, enthalten die Information, daß das jeweilige Teilmodul Ug, UR, UE bei der Ermittlung der Route involviert ist.
Das zweite Teilmodul Uy enthält in der ihm zugeordneten Teilroutenkarte weder den Startpunkt S noch den Zielpunkt Z. Somit sendet das zweite Teilmodul Uy sowie weitere Teilmodule Uj_ (nicht dargestellt) , die in der Anordnung enthalten sind, eine zweite Nachricht 2 zurück, in der angegeben ist, daß sowohl der Startpunkt S als auch der Zielpunkt Z dem Teilmodul Uy, Uj_ unbekannt sind, d.h. nicht in ihrer jeweiligen Teilroutenkarte TUy, TUj_ liegen.
In der zweiten Nachricht 2 ist für den Fall, daß der Startpunkt S oder der Zielpunkt Z in der jeweiligen Teilroutenkarte enthalten ist, eine Identifikationsangabe enthalten, mit der der Startpunkt S bzw. der Zielpunkt Z in der Teilrouten- karte eindeutig identifiziert werden kann. In diesem Beispiel sind mehrere Teilmodule Ug, UR, UE jeweils für den Startpunkt
S bzw. Zielpunkt Z "zuständig", da es sich bei dem ersten Teilmodul Ug und dem dritten Teilmodul UR um Teilmodule zur Ermittlung von Routen für den Individualverkehr handelt, wäh- rend das vierte Teilmodul UE Routen für den öffentlichen Verkehr ermittelt .
In einem weiteren Schritt wird von dem zentralen Agenten I eine Menge von Folgen ermittelt, in denen angegeben ist, wel- ehe Folgen von Teilmodulen Us, UR, UE , Uy bei der Ermittlung der Route ausgehend von dem Startpunkt S zu dem Zielpunkt Z in Frage kommen. Hierzu wird eine lokale Wissensbasis KBj in Form einer Datenbank verwendet, die dem zentralen Agenten I zugänglich ist. In der Wissensbasis sind für jede Kombination von Teilmodulen, in denen ein Start- oder Zielpunkt liegen kann, Folgen von Teilmodulen gespeichert, deren Teilrouten nacheinander verwendet werden, um vom Startpunkt S zum Zielpunkt Z zu gelangen.
Auf Anfrage des zentralen Agenten I wird von der lokalen Wissensbasis KBj eine dritte Nachricht 3 an den zentralen Agenten I gesendet, der die ermittelten Sequenzen enthält, in diesem Fall :
1. Us → Uy → UR
2. Ug → Uy → UE
3. Ug → UR → UE
4. Ug → UE
5. UE
Diese Sequenzen sind wie im folgenden für den Fall 1
(Ug -> Uy - U ) beschrieben, zu verstehen. Die Route kann als Sequenz der Teilroutenkarte TUg des ersten Teilmoduls Ug, gefolgt von einer Teilroute der Teilroutenkarte TUy des zweiten Teilmoduls Uy und abschließend einer Teilroute der Teilroutenkarte TUR des dritten Teilmoduls U gebildet werden.
Entsprechendes gilt für die weiteren oben dargestellten Fälle 2 bis 5.
In einem weiteren Schritt werden Teilstartpunkte und Teil- Zielpunkte der Teilrouten, die von dem ersten Teilmodul Ug, dem zweiten Teilmoduls Uy und dem dritten Teilmoduls UR gebildet werden, ermittelt. Anschaulich bedeutet dies, daß mögliche Übergangspunkte ÜSy, Üyj^ zwischen Teilroutenkarten TUg, TUy, TUR, die den einzelnen Teilmodulen Ug, Uy, UR, zugeord- net sind, ermittelt werden.
In der Wissensbasis KBj des zentralen Agenten I ist eine Liste aller theoretisch möglichen Teilzielpunkte und Teilstartpunkte, die im weiteren als Übergangspunkte Ügy, ÜyR bezeich- net werden, für die jeweiligen Teilroutenkarten TUg, TUy, TUR gespeichert. Aus der Menge aller möglichen Übergangspunkte Ügy, ÜyR wird eine möglichst kleine Anzahl von Teilstartpunkten und Teilzielpunkten ausgewählt, um somit die Anzahl der zu ermittelnden Teilrouten so gering wie möglich zu halten.
Die Auswahl erfolgt unter Berücksichtigung lokalen Wissens, welches in einer Heuristik zur Ermittlung von Übergangspunkten Ügy, ÜyR einfließt.
Gemäß der Heuristik wird bei einer Gesamtentfernung von dem Startpunkt S zu dem Zielpunkt Z von über 100 km (die Luftlinienentfernung von München nach Nürnberg ist größer als 100 km) , versucht, einen möglichst großen Anteil der Route unter Verwendung von Autobahnen abzudecken. Dies bedeutet, daß der zentrale Agent I in seiner Wissensbasis KB nach Übergangs- punkte Ügy, Üy sucht, die einen Teil einer Autobahn repräsentieren, d.h. z.B. einen Autobahnanschluß repräsentieren. Anschaulich bedeutet dies, daß zwischen der ersten Teilroutenkarte TUg und der zweiten Teilroutenkarte TUy bzw. der zweiten Teilroutenkarte TUy und der dritten Teilroutenkarte TUR Übergangspunkte ermittelt werden, deren Knoten Orte repräsentieren, die in einer Autobahn enthalten sind oder direkt zu einer Autobahn führen.
In einer vierten Nachricht 4 wird der Wissensbasis KB des zentralen Agenten I die Anforderung zur Ermittlung der Übergangspunkte Ügy, ÜyR übergeben.
Von der Wissensbasis KB wird in einer fünften Nachricht 5 das Ergebnis, d.h. eine Menge von Übergangspunkten Ügy zwi- sehen den Teilroutenkarten TUg, TUy des ersten Teilmoduls Ug und des zweiten Teilmoduls Uy und eine Menge von Übergangs- punkte Üy£ zwischen Teilroutenkarten TUy, TUR des zweiten Teilmoduls Uy und des dritten Teilmoduls U zurückgesendet. Die Übergangspunkte Ügy, ÜyR sind in Figur 2 durch Punkte ge- kennzeichnet.
Eine Menge von Übergangspunkte ÜXγ (X,Y e N) zwischen Teilroutenkarten besteht im Fall des Übergangs von einem Netz für den Individualverkehr zu einem Netz für den öffentlichen Ver- kehr, in diesem Fall U — UE, Uy —► UE und UR —» UE aus einer Menge von Parkplätzen für Kraftfahrzeuge, die sich in der Nähe einer Station für ein öffentliches Verkehrsmittel befinden.
Im Fall des Übergangs von einem Netz für den öffentlichen
Verkehr und einem Netz für den Individualverkehr besteht die Liste aus Taxiständen.
Im Fall des Übergangs von einem Netz für den Individualver- kehr zu einem angrenzenden weiteren Netz für den Individualverkehr besteht die Liste aus vorgegebenen Punkten, an denen jeweils eine Straße von einem Netz zu dem anderen Netz übergeht .
In einer sechsten Nachricht 6, die von dem zentralen Agen- ten I an das erste Teilmodul Ug, das zweite Teilmodul Uy und das dritte Teilmodul UR gesendet werden, wird bei den Teilmodulen Ug, Uy, UR angefragt, ob es durch Berücksichtigung lokaler Rahmenbedingungen, die jeweils in einer lokalen Wissensbasis KBg, KBy, KBR, die eindeutig dem jeweiligen Teilmo- dul Ug, Uy, UR zugeordnet ist, andere Übergangspunkte Ügy, ÜyR gibt, die sich hinsichtlich des vorgegebenen Optimierungskriteriums eignen.
Ein solches lokales Wissen ist darin zu sehen, daß dem ersten Teilmodul Ug unter Verwendung seiner ihm zugeordneten lokalen Wissensbasis KBg bekannt ist, daß - aufgrund von Heuristiken und domänenspezifischem Wissen aus der lokalen Wissensbasis KBg - für eine längere Reise Richtung Norden von dem vorgegebenen Startpunkt S, der sich relativ weit im Süden Münchens befindet, Übergangspunkte Ügy im Südosten und im Norden der ersten Teilroutenkarte TUg zu berücksichtigen sind.
In der lokalen Wissensbasis KBy, die dem zweiten Teilmodul Uy zugeordnet ist, ist angegeben, daß für eine Reise von München nach Nürnberg die Übergangspunkte Üyp_ der zweiten Teilroutenkarte TUy des zweiten Teilmoduls Uy vorteilhaft sind, die im Norden der zweiten Teilroutenkarte TUy liegen.
Aus den zusätzlichen Vorschlägen, die von den einzelnen Teil- modulen Ug, Uy, UR dem zentralen Agenten I zugeführt werden, wird von dem zentralen Agenten I eine Teilmenge TÜgy für Übergänge von der ersten Teilroutenkarte TUg und der zweiten Teilroutenkarte TUy. Analog wird für die Übergangspunkte Ü ^, die Übergänge zwischen der zweiten Teilroutenkarte TUy und der dritten Teilroutenkarte TU repräsentieren, eine zweite Teilmenge TÜyj^ von Übergangspunkten Ü^ ermittelt. Eine siebte Nachricht 7 wird von dem zentralen Agenten I an das erste Teilmodul Ug, das zweite Teilmodul Uy und das dritte Teilmodul UR gesendet. Die siebte Nachricht 7 enthält jeweils eine Anfrage zur Ermittlung einer oder mehrerer Teil- routen, die hinsichtlich des vorgegebenen Optimierungskriteriums Zeit optimal sind.
In diesem Beispiel wird in der siebten Nachricht 7, die dem ersten Teilmodul Ug zugeführt wird, die Ermittlung von Teil- routen von dem Startpunkt S zu den fünf Übergangspunkten Ügy der ersten Teilmenge TÜgy, angefragt.
Die siebte Nachricht 7, die dem zweiten Teilmodul Uy zugeführt wird, enthält eine Anfrage zur Ermittlung von Teilrou- ten aller Kombinationen zwischen den Übergangspunkten Ügy der ersten Teilmenge TÜgy und den Übergangspunkten Üyj^ der zweiten Teilmenge Üyj^.
Die siebte Nachricht 7, die dem dritten Teilmodul UR zuge- führt wird, enthält eine Anfrage zur Ermittlung von Teilrouten von den zwei Übergangspunkten Üy^ der zweiten Teilmenge TÜy zum Zielpunkt Z.
Die Gesamtzahl der zu ermittelnden Teilrouten beträgt bei dieser Vorgehensweise 5 + 10 + 2 = 17. Bei Ermittlung aller möglichen Teilrouten für alle in Frage kommenden Übergangs- punkte Üyg, Üyj^ der Teilroutenkarten wäre im vorliegenden Fall eine Größenordnung von 2000 bis 3000 Ermittlungen erforderlich (ausgehend von einer Gesamtzahl möglicher Übergangs- punkte in der Größenordnung von 50) .
Die Ermittlung der Teilrouten in den Teilmodulen erfolgt unter Verwendung von Verfahren zur Ermittlung kürzester Pfade, beispielsweise dem Verfahren nach Dijkstra. Den jeweiligen Knoten und/oder Kanten der Teilroutenkarte sind jeweils Kostenwerte zugeordnet, die im Rahmen der Optimierung zur Ermittlung der Teilroute innerhalb der Teilroutenkarte in einer Kostenfunktion berücksichtigt werden. Die Kostenwerte und die Art der Berücksichtigung hängen ab von der Art des Optimierungskriteriums. Mögliche Optimierungskriterien sind die für die Reise insgesamt benötigte Zeit, die zu minimierende gesamte Routenlänge, oder weiteren Rahmenbedingungen. So wird für den Fall, daß ein bestimmtes Verkehrsmittel nicht verwendet werden soll, das jeweilige Teilmodul, das für das Verkehrsmittel „zuständig" ist, nicht mit der Berechnung einer Teilroute beauftragt.
Nachdem alle Teilrouten von den Teilmodulen dem zentralen Agenten I zugeführt wurden, wird von dem zentralen Agenten I eine Route ermittelt, wobei die Route eine Menge zusammenhängender Knoten und Kanten, ausgehend von dem Startpunkt S hin zu dem Zielknoten Z, ist. Die hinsichtlich des Optimierungskriteriums „Zeit" beste Route wird von dem zentralen Agenten I ausgewählt .
Das für die erste Sequenz Ug —» Uy —> UR oben beschriebene Verfahren wird für alle weiteren Sequenzen entsprechend durchgeführt .
Es ist jedoch zu beachten, daß bei Übergängen zwischen einem Netz für den Individualverkehr und einem Netz für den öffent- liehen Verkehr jeweils noch Übergangszeiten für den Wechsel des Verkehrsmittels und diskrete Abfahrtszeiten des jeweiligen öffentlichen Verkehrsmittels zu berücksichtigen sind. Dies ist bei dem Übergang zwischen Netzen für den Individualverkehr nicht erforderlich.
Als Route wird im Gesamtergebnis diejenige ausgewählt, die hinsichtlich des Optimierungskriteriums optimiert ist.
Die ausgewählte Route wird dem Benutzer als Antwort 103 sei- ner Benutzeranfrage 102 als Ergebnis zur Verfügung gestellt, beispielsweise auf einem Bildschirm angezeigt oder in anderer Form ausgegeben. Im weiteren werden einige Alternativen zu dem oben beschriebenen Ausführungsbeispiel aufgezeigt.
In dem Ausführungsbeispiel sind dem zentralen Agenten I alle erheblichen Teilmodule, die für die Ermittlung der Route erforderlich sind, bekannt. In einer Variante ist jedoch vorgesehen, daß die Information über erforderliche Teilmodule in weiteren Agenten gespeichert ist. Die Information wird dann von dem zentralen Agenten I abgefragt.
In einer Variante der Erfindung ist es ferner vorgesehen, daß die möglichen Folgen von Teilroutenkarten nicht in der Wissensbasis KB des zentralen Agenten I, sondern in einem wei- teren Agenten gespeichert ist. In diesem Fall würde auch diese Information von dem weiteren Agenten durch den zentralen Agenten I abgefragt .
Für die Sequenzen 2 bis 5 kann in einer Variante der Fall eintreten, daß der letzte Abschnitt der Reise mit einem Taxi zurückgelegt wird. Dies bedeutet, daß die Folge um das weitere Teilmodul U (Ergänzung der Folgen um das Postfix „-» UR") ergänzt werden müßte, da zwar das letzte Teilmodul U nicht den genauen Weg zu dem Zielpunkt Z, jedoch die für das letzte Teilstück benötigte Zeit ermitteln müßte.
Im Rahmen dieses Dokuments wurden folgende Veröffentlichungen zitiert :
[1] B. V. Cherkassky et al , Shortest Path Algorithms, Theory and Experimental Evaluation Mathematical Programming, Vol. 73, Nr. 2, S. 129 - 174, 1996

Claims

Patentansprüche
1. Verfahren zur rechnergestützten Ermittlung einer Route von einem Startpunkt zu einem Zielpunkt, die jeweils in unter- schiedlichen Teilroutenkarten liegen, wobei die Teilroutenkarten in digitaler Form gespeichert sind, bei dem in einem iterativen Verfahren, welches folgende Schritte umfaßt, die Route von dem Startpunkt zu dem Zielpunkt ermittelt wird: - Teilmodulen, die jeweils einer Teilroutenkarte zugeordnet sind, werden digitale Nachrichten zugeführt, die jeweils mindestens einen Teilstartpunkt und mindestens einen Teilzielpunkt enthalten, die in der Teilroutenkarte des Teilmoduls liegen, das die jeweilige Nachricht empfängt, - von jedem Teilmodul wird mindestens eine Teilroute zwischen dem jeweiligen Teilstartpunkt und dem Teilzielpunkt ermittelt, - aus den Teilrouten wird die Route gebildet.
2. Verfahren nach Anspruch 1, bei dem die Teilroutenkarten in Form von Teilroutengraphen mit Knoten und Kanten gespeichert sind.
3. Verfahren nach Anspruch 2, bei dem die Route eine Menge zusammenhängender Knoten und Kanten zwischen dem Startpunkt und dem Zielpunkt ist.
4. Verfahren nach einem der Ansprüche 1 bis 3, bei dem in einem Zentralmodul eine Datenbank gespeichert ist, anhand der mögliche Verkettungen von Teilmodulen ermittelt werden .
5. Verfahren nach einem der Ansprüche 1 bis 4, bei dem die Teilmodulen Software-Agenten sind.
6. Verfahren nach einem der Ansprüche 1 bis 5, bei dem in jedem Teilmodul eine Teil-Datenbank gespeichert ist, anhand der mindestens eine optimierte Route in dem Teil- modul ermittelt wird.
7. Verfahren nach einem der Ansprüche 1 bis 6, bei dem zur Ermittlung der Teilroute jeweils ein Verfahren zur Ermittlung kürzester Pfade eingesetzt wird.
8. Verfahren nach einem der Ansprüche 1 bis 7, bei dem die Ermittlung der Teilroute derart erfolgt, daß die Teilroute hinsichtlich einer Kostenfunktion optimiert wird.
9. Anordnung zur rechnergestützten Ermittlung einer Route von einem Startpunkt zu einem Zielpunkt, die jeweils in unter- schiedlichen Teilroutenkarten liegen, wobei die Teilroutenkarten in digitaler Form gespeichert sind, mit mindestens einer Prozessoreinheit, die derart eingerichtet ist, daß in einem iterativen Verfahren, welches folgende Schritte umfaßt, die Route von dem Startpunkt zu dem Ziel- punkt ermittelt wird:
- Teilmodulen, die jeweils einer Teilroutenkarte zugeordnet sind, werden digitale Nachrichten zugeführt, die jeweils mindestens einen Teilstartpunkt und mindestens einen Teilzielpunkt enthalten, die in der Teilroutenkarte des Teilmoduls liegen, das die jeweilige Nachricht empfängt,
- von jedem Teilmodul wird mindestens eine Teilroute zwischen dem jeweiligen Teilstartpunkt und dem Teilzielpunkt ermittelt,
- aus den Teilrouten wird die Route gebildet .
10. Anordnung nach Anspruch 9, bei der die Prozessoreinheit derart eingerichtet ist, daß die Teilroutenkarten in Form von Teilroutengraphen mit Knoten und Kanten gespeichert sind.
11. Anordnung nach Anspruch 10, bei der die Prozessoreinheit derart eingerichtet ist, daß die Route eine Menge zusammenhängender Knoten und Kanten zwischen dem Startpunkt und dem Zielpunkt ist.
12. Anordnung nach einem der Ansprüche 9 bis 11, bei der die Prozessoreinheit derart eingerichtet ist, daß in einem Zentralmodul eine Datenbank gespeichert ist, anhand der mögliche Verkettungen von Teilmodulen ermittelt werden.
13. Anordnung nach einem der Ansprüche 9 bis 12, bei der die Prozessoreinheit derart eingerichtet ist, daß die Teilmodulen Software-Agenten sind.
14. Anordnung nach einem der Ansprüche 9 bis 13 , bei der die Prozessoreinheit derart eingerichtet ist, daß in jedem Teilmodul eine Teil-Datenbank gespeichert ist, anhand der mindestens eine optimierte Route in dem Teilmodul ermittelt wird.
15. Anordnung nach einem der Ansprüche 9 bis 14, bei der die Prozessoreinheit derart eingerichtet ist, daß zur Ermittlung der Teilroute jeweils ein Verfahren zur Ermittlung kürzester Pfade eingesetzt wird.
16. Anordnung nach einem der Ansprüche 9 bis 15, bei der die Prozessoreinheit derart eingerichtet ist, daß die Ermittlung der Teilroute derart erfolgt, daß die Teilroute hinsichtlich einer Kostenfunktion optimiert wird.
PCT/DE1998/002891 1997-10-21 1998-09-30 Verfahren und anordnung zur ermittlung einer route von einem startpunkt zu einem zielpunkt WO1999020981A1 (de)

Priority Applications (5)

Application Number Priority Date Filing Date Title
DE59802765T DE59802765D1 (de) 1997-10-21 1998-09-30 Verfahren und anordnung zur ermittlung einer route von einem startpunkt zu einem zielpunkt
US09/529,785 US6421605B1 (en) 1997-10-21 1998-09-30 Method and system for computer-supported determination of a route from a starting point to a destination point
JP2000517253A JP2001521142A (ja) 1997-10-21 1998-09-30 出発地点から目的地点までのルートを求める方法および装置
AT98955356T ATE209338T1 (de) 1997-10-21 1998-09-30 Verfahren und anordnung zur ermittlung einer route von einem startpunkt zu einem zielpunkt
EP98955356A EP1025423B1 (de) 1997-10-21 1998-09-30 Verfahren und anordnung zur ermittlung einer route von einem startpunkt zu einem zielpunkt

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
DE19746417 1997-10-21
DE19746417.3 1997-10-21

Publications (1)

Publication Number Publication Date
WO1999020981A1 true WO1999020981A1 (de) 1999-04-29

Family

ID=7846128

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/DE1998/002891 WO1999020981A1 (de) 1997-10-21 1998-09-30 Verfahren und anordnung zur ermittlung einer route von einem startpunkt zu einem zielpunkt

Country Status (6)

Country Link
US (1) US6421605B1 (de)
EP (1) EP1025423B1 (de)
JP (1) JP2001521142A (de)
AT (1) ATE209338T1 (de)
DE (1) DE59802765D1 (de)
WO (1) WO1999020981A1 (de)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2001000480A1 (de) 1999-06-17 2001-01-04 Kageneck Karl Erbo Graf Tretantrieb, insbesondere für fahrräder
JP2003528362A (ja) * 1999-07-21 2003-09-24 センター・インコーポレイテッド 動的分散型問題解決実行用知識管理システム

Families Citing this family (16)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6351710B1 (en) * 2000-09-28 2002-02-26 Michael F. Mays Method and system for visual addressing
US7865306B2 (en) 2000-09-28 2011-01-04 Michael Mays Devices, methods, and systems for managing route-related information
US7894938B1 (en) * 2005-03-31 2011-02-22 Cantaloupe Systems, Inc. Vending machine service scheduling
US8138907B2 (en) * 2005-08-11 2012-03-20 University Of South Florida Travel assistant device
US7418342B1 (en) 2007-12-03 2008-08-26 International Business Machines Corporation Autonomous destination determination
US8311867B1 (en) * 2009-04-21 2012-11-13 Cantaloupe Systems, Inc. Vending machine service scheduling taking into account hardness data indicating importance of minimizing the number of service visits to a vending machine and/or to the vending machine's location
US8725407B2 (en) * 2009-11-09 2014-05-13 United Parcel Service Of America, Inc. Enhanced location information for points of interest
US9157745B2 (en) * 2010-01-14 2015-10-13 Qualcomm Incorporated Scalable routing for mobile station navigation with location context identifier
US9140570B1 (en) * 2011-09-08 2015-09-22 Amazon Technologies, Inc. Time-inclusive route and trip planning
DE102015226224B3 (de) * 2015-12-21 2017-05-24 Siemens Ag Verfahren zum Ermitteln einer Verkehrsbelastung
US10730626B2 (en) 2016-04-29 2020-08-04 United Parcel Service Of America, Inc. Methods of photo matching and photo confirmation for parcel pickup and delivery
WO2017204998A2 (en) 2016-04-29 2017-11-30 United Parcel Service Of America, Inc. Unmanned aerial vehicle pick-up and delivery systems
US10775792B2 (en) 2017-06-13 2020-09-15 United Parcel Service Of America, Inc. Autonomously delivering items to corresponding delivery locations proximate a delivery route
WO2019068076A1 (en) 2017-09-29 2019-04-04 United Parcel Service Of America, Inc. IDENTIFICATION, ANALYSIS AND PREDICTIVE MITIGATION OF PARCEL DAMAGE
US20220219727A1 (en) * 2021-01-12 2022-07-14 Motional Ad Llc Vehicle path planning
CN116625378B (zh) * 2023-07-18 2023-10-31 上海仙工智能科技有限公司 一种跨区域路径规划方法及系统、存储介质

Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0547548A1 (de) * 1991-12-18 1993-06-23 Honda Giken Kogyo Kabushiki Kaisha Fahrtleitvorrichtung für Fahrzeug

Family Cites Families (8)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPS63286909A (ja) * 1987-05-19 1988-11-24 Sanyo Electric Co Ltd 作業車の作業経路決定装置
US5170353A (en) * 1988-11-17 1992-12-08 U.S. Philips Corporation Bucket-oriented route planning method, and navigation system comprising a route planner for carrying out such a method
JP2874397B2 (ja) * 1991-03-19 1999-03-24 松下電器産業株式会社 経路選出装置
US5272638A (en) * 1991-05-31 1993-12-21 Texas Instruments Incorporated Systems and methods for planning the scheduling travel routes
JP3381459B2 (ja) * 1995-05-30 2003-02-24 株式会社デンソー 車両用走行案内装置
JP3223782B2 (ja) * 1996-02-08 2001-10-29 三菱電機株式会社 車両経路算出装置
JP3446930B2 (ja) * 1996-09-30 2003-09-16 松下電器産業株式会社 経路選出方法および経路選出装置
US5893081A (en) * 1996-11-25 1999-04-06 Etak, Inc. Using multiple levels of costs for a pathfinding computation

Patent Citations (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
EP0547548A1 (de) * 1991-12-18 1993-06-23 Honda Giken Kogyo Kabushiki Kaisha Fahrtleitvorrichtung für Fahrzeug

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
ARIKAWA M: "PERSONAL DYNAMIC MAPS BASED ON DISTRIBUTED GEOGRAPHIC INFORMATION SERVERS", PROCEEDINGS OF THE VEHICLE NAVIGATION AND INFORMATION SYSTEMS CONFERENCE, YOKOHAMA, AUG. 31 - SEPT. 2, 1994, 31 August 1994 (1994-08-31), INSTITUTE OF ELECTRICAL AND ELECTRONICS ENGINEERS, pages 591 - 596, XP000641362 *

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2001000480A1 (de) 1999-06-17 2001-01-04 Kageneck Karl Erbo Graf Tretantrieb, insbesondere für fahrräder
JP2003528362A (ja) * 1999-07-21 2003-09-24 センター・インコーポレイテッド 動的分散型問題解決実行用知識管理システム

Also Published As

Publication number Publication date
DE59802765D1 (de) 2002-02-21
ATE209338T1 (de) 2001-12-15
EP1025423A1 (de) 2000-08-09
JP2001521142A (ja) 2001-11-06
EP1025423B1 (de) 2001-11-21
US6421605B1 (en) 2002-07-16

Similar Documents

Publication Publication Date Title
EP1025423B1 (de) Verfahren und anordnung zur ermittlung einer route von einem startpunkt zu einem zielpunkt
EP0323485B1 (de) Verfahren und vorrichtung zur bestimmung einer fahrtroute zwischen einem startpunkt und einem zielpunkt
EP1092127B1 (de) Verfahren zur beeinflussung von quelldaten zur bestimmung einer route bei einem navigationssystem
DE69935184T2 (de) Verfahren und System zur Generierung einer Navigationsroute
DE10217880B4 (de) Verfahren zum Kompilieren von Navigationsrouteninhalt
EP1497618B1 (de) Verfahren und system zur dynamischen zielführung eines fahrzeuges
EP1297310B1 (de) Verfahren zur auswahl von karteninformationen und navigationsvorrichtung
EP0902406B1 (de) Verfahren zur Übertragung von Wegedaten und zur Analyse des Verkehrswegenetzes sowie Verkehrserfassungszentrale und Endgerät
DE19930796A1 (de) Verfahren und Vorrichtung zur Übermittlung von Navigationsinformationen von einer Datenzentrale an ein fahrzeugbasiertes Navigationssystem
EP2507589B1 (de) Verfahren zur vereinfachung einer beschreibung einer fahrtroute
DE102016100427A1 (de) Fahrzeugsteuerung
EP2288872A1 (de) Verfahren und vorrichtung zur berechnung einer navigationsroute zu zusammenhängenden zielpunkten
DE102009006183B4 (de) Verfahren und System zum Anpassen von Routenplanungs-Ergebnissen
EP1397643B1 (de) Verfahren zum erzeugen von navigationsdaten für eine routenführung sowie navigationssystem
EP1027578B1 (de) Verfahren und anordnung zur rechnergestüzten bearbeitung eines graphen
EP1092950A1 (de) Verfahren zur Bestimmung einer Fahrtroute für ein Strassenfahrzeug
DE102012212815B4 (de) Verfahren zur Auswahl und Aufbereitung von Verkehrsinformationen
EP1779067B1 (de) Verfahren zur navigation
DE102006013297B4 (de) Verfahren zum Betrieb eines Navigationssystems
EP1339247B1 (de) Verfahren zum Erzeugen von Informationsdaten für mobile Nutzer eines Informations-Übertragungssystems
DE102004032499B3 (de) Verfahren und Routenplanungssystem zur Generierung und Speicherung von für eine dynamische Routenplanung benötigten Daten
DE102006057286A1 (de) Navigationseinrichtung
DE102023003338A1 (de) Verfahren und System zur Planung der Navigationsroute eines Fahrzeugs
DE102023001135A1 (de) Koordination von Fahrzeugen mit geplantem Treffpunkt
DE102004052908B3 (de) System und Verfahren zur Routenführung im Nahbereich des Routenziels

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): JP US

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): AT BE CH CY DE DK ES FI FR GB GR IE IT LU MC NL PT SE

DFPE Request for preliminary examination filed prior to expiration of 19th month from priority date (pct application filed before 20040101)
121 Ep: the epo has been informed by wipo that ep was designated in this application
WWE Wipo information: entry into national phase

Ref document number: 1998955356

Country of ref document: EP

WWE Wipo information: entry into national phase

Ref document number: 09529785

Country of ref document: US

WWP Wipo information: published in national office

Ref document number: 1998955356

Country of ref document: EP

WWG Wipo information: grant in national office

Ref document number: 1998955356

Country of ref document: EP