Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2000-04-19
2002-07-16
Zanelli, Michael J. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
C701S201000
Reexamination Certificate
active
06421605
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a method and system for the computer-supported determination of a route from a starting point to a destination point wherein the route is determined from a plurality of sub-routes which, in turn, are determined from a plurality of sub-modules respectively associated with the starting point and destination point.
2. Description of the Prior Art
The invention is directed to the determination of a route from a starting point to a destination point.
What is of concern in computer-supported route planning systems is to determine a route between a prescribable starting point, i.e. a departure location at which a user of the route planning system would like to begin a trip, and a destination point to which the user would like to travel. Such determination should be done in such a way that the determination of the route itself occurs as quickly as possible and the route is optimized in view of various, prescribable requirements. Requirements in this sense can be, for example, a travel time required for the overall route, the route length, or specific particulars with regard to specific means of transportation which are preferably are to be utilized.
What is to be understood below by a route is a path description, i.e. a set of nodes and edges, when the path is represented by a graph that includes such nodes and edges, from a starting point to a destination point. The determination of the route should be implemented optimally quickly and flexibly. An overview of methods for determining shortest paths can be found, for example, in B. V. Cherkassky et al., Shortest Path Algorithms, Theory and Experimental Evaluation Mathematical Programming, Vol. 73, No. 2, pp. 129-174, 1993.
SUMMARY OF THE INVENTION
B. V. Cherkassky et al, Shortest Path Algorithms, Theory and Experimental Evaluation Mathematical Programming, Vol. 73, No. 2, pp. 129-174, 1996.
In accordance with the teachings of the present invention, therefore, the route from a starting point to a destination point is determined in an iterative method. The starting point and the destination point lie in different sub-route maps, wherein the sub-route maps are stored in digital form. The method includes the following steps:
sub-modules that are respectively allocated to a sub-route map are supplied with digital messages that respectively contain at least one sub-starting point and at least one sub-destination point that lie in the sub-route map of the sub-module that receives the respective message;
each sub-module determines at least one sub-route between the respective sub-starting point and the sub-destination point; and
the route is formed from the sub-route.
The system includes a processor unit that is configured such that a route from a starting point to a destination point that respectively lie in different sub-route maps is determined in an iterative method, wherein the sub-route maps are stored in digital form. The system includes the following:
sub-modules that are respectively allocated to a sub-route map which are supplied with digital messages that respectively contain at least one sub-starting point and at least one sub-destination point that lie in the sub-route map of the sub-module that receives the respective message;
at least one sub-route between the respective sub-starting point and the sub-destination point which is determined by each sub-module; and
the route which is formed from the sub-routes.
The present invention assures a fast, flexible determination of a route for a user from a prescribable starting point to a prescribable destination point (at a prescribable point in time). The extremely complex problem of route determination is thereby split into sub-problems that are respectively solved independently of one another. As a result a it becomes possible to consider both central and local knowledge in secondary conditions of determining sub-routes or, respectively, the route.
It is advantageous in one development of the present invention that the sub-route maps are stored in the form of sub-route graphs having nodes and edges, wherein a method for determining shortest paths is respectively utilized for the determination of the sub-route. By utilizing the methodology of determining shortest paths, it is possible to form optimized sub-routes in view of the prescribable optimization criteria in the individual sub-modules in a simple way. The use of methods for determining shortest paths is to be understood such that a respective sub-route is determined optimized in view of a predetermined cost function (optimization criteria). Respective cost values that correspond to the predetermined optimization criterion are allocated to the edges.
Prescribable optimization criteria also can be, for example, the minimization of turning events, particularly left-turn events in cities, in addition to the path length or the duration of a route. Further, the point in time for which the route is to be planned can be taken into consideration in the present invention. Thus, for example, the time of the trip definitely can be of significance since the decision of selecting individual transportation or public transportation for the route can be dependent on the selected point in time (during rush hour one will presumably need more time with an automobile in a central city than given employment of public transportation; the situation might be exactly opposite at night).
An exemplary embodiment of the present invention is shown in the Figures and is explained in greater detail below.
REFERENCES:
patent: 5170353 (1992-12-01), Verstraete
patent: 5272638 (1993-12-01), Martin et al.
patent: 5502640 (1996-03-01), Yagyu et al.
patent: 5752217 (1998-05-01), Ishizaki et al
patent: 5845228 (1998-12-01), Uekawa et al.
patent: 5893081 (1999-04-01), Poppen
patent: 6014607 (2000-01-01), Yagyu et al.
patent: 0 547 548 (1993-06-01), None
patent: 63286909 (1988-11-01), None
Shortest paths Algorithms: Theory and Experimental Evaluation, Boris Cherkassky, Aug. 1993.
Personal Dynamic Maps Based on Distributed Geographic Information Servers, Arikawa, pp. 591-596, Aug. 1994.
Burt Alastair
Dieterich Hartmut
Lind Jürgen
Steiner Donald
Bell Boyd & Lloyd LLC
Gibson Eric M.
Siemens Aktiengesellschaft
Zanelli Michael J.
LandOfFree
Method and system for computer-supported determination of a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for computer-supported determination of a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for computer-supported determination of a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2830770