Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2001-02-12
2003-05-20
Louis-Jacques, Jacques H. (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
C701S200000, C701S201000, C701S207000, C701S208000
Reexamination Certificate
active
06567743
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to a method for determining a route from a departure point to a destination, which is based on a digital map showing a real road network in segments with resistances and nodes, in which route segments are optimized by means of a route-searching algorithm and are stored in a route table, and at least one intermediate destination is predetermined. The invention also relates to an apparatus for determining a route from a departure point to a destination by the aforesaid method, which has a digital map stored in a memory.
2. Description of the Related Art
In means of locomotion, for example motor vehicles, airplanes or ships, permanently installed navigation systems guide the operator of the means of locomotion rapidly, simply and safely to a desired destination without the need for any prior, tedious route planning and for the acquisition and study of appropriate map material. To this end, appropriate navigation data based on, for example, maps, country maps or road maps, are stored in the navigation system, for example on CD-ROM. The navigation device uses, for example, GPS (global positioning system) to determine the instantaneous position and to calculate the required navigation instructions that will lead to a predetermined destination. The navigation data in this case preferably contain data about streets and roads for motor vehicles.
In conventional navigation systems, the driver of a motor vehicle can in various ways influence the course of a route to be calculated, namely by selecting cog different optimization criteria, such as “short route”, “fast route”, “avoid superhighways”, by influencing road sections manually or by traffic telecommunications, which in the route calculation are then by-passed or facilitated, or by defining one or more intermediate destinations which the driver then passes sequentially on his way to the final destination. If the driver wishes “to travel from Kassel to Minden via Hannover”, only the last-said alternative is open to him. In Hannover, he must define an intermediate destination, which, for example, is the center of the city, after which two route calculations are made. A first route from Kassel to Hannover and a second route from Hannover to Minden are calculated. Linking the two routes together then gives the overall route. With the Alpine navigation system “GP Shuttle, NVE-N055VP”, for example, it is possible to select up to five intermediate destinations.
However it is a disadvantage that, when intermediate destinations are used, several route calculations, independent of each other, must be performed, their number depending on the number of intermediate destinations. Namely, it is first necessary to calculate the partial routes from the current position to the intermediate destination, then from said intermediate destination to the next one and finally to the actual destination. In this manner, however, the partial routes and not the overall one are optimized. Even when the indicated intermediate destination is not a city but a region, for example the region of the city of Hannover, the optimization of the route is carried out only as far as the boundary of the region so that the first partial route in the afore-described case ends somewhere at the outskirts of the city of Hannover. The exact location of this point on the periphery of Hannover depends only on the route from the departure point to this intermediate destination. Optimization of the point on the periphery of Hannover or of the subsequent route, for example, to the final destination or to the next intermediate destination, however, is not possible. In the area of the intermediate destination, this may result in unfavorable routing, nonsensical turns or avoidable city crossings.
SUMMARY OF THE INVENTION
The object of the present invention is to provide an improved method of the above-described type for determining a route from a departure point to a final destination based on a digital map, which represents a real road network with segments with resistances and nodes, which method eliminates the above-said disadvantages and ensures calculation of an optimal route, even when the user of a navigational method specifies intermediate destinations.
This method according to the invention comprises the steps of:
a) predetermining at least one intermediate destination through which the route must pass, each intermediate destination consisting of a respective transition region formed by a corresponding group of segments;
b) then optimizing segments for the route by means of a route search ok algorithm to obtain optimized segments and storing the optimized segments in a route table, and
c) minimizing an overall resistance of the route from the departure point to the final destination, with the proviso that the route is constrained to pass through the respective transition region of each intermediate destination.
The advantage of this is that the determination of the route to be calculated can be intentionally influenced by specifying transition regions (via areas). In contrast to conventional methods with intermediate destinations, the route is optimized from the departure position through the transition region to the destination as a whole and not in sections. Moreover, the driver need not worry about the definition of an actual intermediate destination. The use of the invention ensures that, after the calculation of the route, at any point in time, the optimum route from any possible departure point or any possible position of a motor vehicle to the final destination is possible by passing through the transition region or transition regions. In this manner, the distance to the destination and the remaining travel time or the estimated time of arrival can be indicated. In the route calculation from the departure point to the final destination, besides the conventional, predeterminable criteria, for example “short route”, “fast route” or the like, one or more via areas are taken into consideration, the via areas being included by the user into the calculated route in a predetermined sequence.
In a preferred embodiment, each intermediate destination is defined as a transition region in the form of a surface region of the digital map, and corresponding segments located in the area of the transition region in question are assigned and stored in a transition region list. A first segment optimization is performed starting from a destination segment corresponding to the destination, and the result is stored in a first route table, additional sectional segment optimizations corresponding to the number of predetermined transition regions being performed and stored in separate sectional route tables. At the end of the first segment optimization, the segments stored in the originally initialized and destination-initialized transition region list with the corresponding resistances from the first route table are updated. Furthermore, at the beginning of each sectional segment optimization, the current resistances of the segments of the transition region list are entered into the originally initialized sectional route table. Furthermore, at the end of the first and up to the penultimate sectional segment optimization, the resistances of the segments stored in the current transition region list with the resistances of the corresponding segments of the sectional route table are updated, and after the last sectional segment optimization, starting with the last sectional route table, and up to the first route table, a route list is compiled from these tables so as to minimize the overall resistance of the route from the departure point through one or more intermediate destinations to the final destination.
Advantageously, the compilation of the route list is accomplished in that, starting with the sectional route table of the last-performed sectional segment optimization, the relevant segments are entered into the route list one after the other until no follower to a segment is defined in the sectional route table. The pr
Fabian Thomas
Mueller Guido
Louis-Jacques Jacques H.
Robert & Bosch GmbH
Striker Michael J.
LandOfFree
Method and device for determining a route from a starting... 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 device for determining a route from a starting..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for determining a route from a starting... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3028911