Data processing: vehicles – navigation – and relative location – Navigation – Employing position determining equipment
Reexamination Certificate
2001-12-19
2004-08-31
Chin, Gary (Department: 3661)
Data processing: vehicles, navigation, and relative location
Navigation
Employing position determining equipment
C701S202000, C701S210000, C340S995190
Reexamination Certificate
active
06785608
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a system and method for calculating an optimized route in a navigation program.
BACKGROUND
Computer-based navigation systems are able to provide end users, such as vehicle drivers and other travelers, with various navigating functions and features. For example, some navigation systems are able to determine an optimum route to travel by driving and/or walking between two physical locations in a geographic region. Using input from the end user, and optionally from equipment that can determine the end user's physical location (such as a global positioning system), a navigation system can identify and examine various routes between the two locations in the geographic region to determine an optimum route between the locations.
The navigation system may then provide the end user with information about the route in the form of instructions that identify the maneuvers required to be taken by the end user to travel from the starting location to the destination location. The navigation system may be located in an automobile or at an office remote from the end user, and the instructions may take the form of textual and/or audio instructions that are provided to the end user. Some navigation systems are capable of providing detailed moving map displays outlining the route between locations, the types of maneuvers to be taken along the route, locations of certain types of features or points of interest, and so on.
To provide these and other navigating functions, present navigation systems include navigation application programs and use one or more detailed databases that include data, which represent physical geographic navigable features. The detailed database(s) include data representing the road networks in a geographic region, including the roads and intersections in the region and information about the particular roads and intersections, such as one-way streets, turn restrictions at intersections, speed limits along the roads, street names of the various roads, address ranges along the various roads and so on. Further, the data may include information about points-of-interest such as restaurants, hotels, and so on. Presently, the collection of such geographic data and the provision of such data in a computer-usable database format are provided by Navigation Technologies of Chicago, Ill.
Present navigation systems may then use the data represented in the one or more detailed database(s) to provide a route optimized for time or distance between the designated physical locations. To do this, the navigation application program may exhaustively search the data that represents the road networks in a particular geographic region. Accordingly, the navigation application program may calculate and subsequently compare many possible routes between the two locations to determine the optimal solution.
This laborious approach, however, requires that the program calculate and then compare as many possible routes as the program can find in the particular geographic region, some of which are clearly less optimal than the previously calculated routes when parameters such as time or distance are considered. Moreover, this methodology may require that the program completely calculate a route between the two locations before the route can be compared to other previously calculated routes. This approach may then be a computationally intensive one and may unnecessarily slow the route calculation process especially when trying to optimize the route for a particular parameter such as time or distance.
Accordingly, it is an objective to provide a method and system for an optimized route and calculation thereof.
SUMMARY
A system and method provide for an optimized route and calculation thereof. The exemplary embodiments are implemented with a route calculation program used with a map database stored on a computer readable storage medium. The route calculation program is adapted to find a solution route between a first location on a road network represented by the map database and a second location on the road network represented by the map database. The road network is represented in the map database by data that represent each segment of each road between endpoints thereof that correspond to intersections of the segment of road with other segments of roads.
In an exemplary embodiment, a “bounding route” is calculated with a relatively fast algorithm between two physical locations to determine a boundary value for which subsequent route calculations or portions thereof may be compared to. The bounding route may be calculated by selecting segments of roads that are optimized for a specific criterion. The criterion may be based on weighting factors or parameters such as the “least distance traveled” or the “least travel time.”
In another exemplary embodiment, a boundary value may provide any route calculation program with criteria used to determine whether a search at a particular location should continue. That is, if a search at a particular location has exceeded the criteria, or equivalently, the search has gone beyond the boundary, the search is stopped because it will result in an un-optimal route for the criterion. Moreover, the route calculation program may use its resources to pursue a potentially better route at a different location. This process may then be an iterative one until an optimal solution is found.
The navigation application program may efficiently calculate a bounding route and value that has a characteristic that meets a specific criterion. Moreover, the program may subsequently compare many possible routes between the two locations to determine the optimal solution for the specific criterion in a quick and efficient manner. Furthermore, the program can compare values for subsequent routes with the boundary value before having to completely calculate a route. This provides for a less computational process especially when trying to optimize the route's characteristic such as travel time or distance traveled for a specific criterion such as “least travel time” or “least distance traveled.”
REFERENCES:
patent: 5041983 (1991-08-01), Nakahara et al.
patent: 5371678 (1994-12-01), Nomura
patent: 5608635 (1997-03-01), Tamai
patent: 5729458 (1998-03-01), Poppen
patent: 5774073 (1998-06-01), Maekawa et al.
patent: 5899955 (1999-05-01), Yagyu et al.
patent: 6034626 (2000-03-01), Maekawa et al.
patent: 6125323 (2000-09-01), Nimura et al.
patent: 6192314 (2001-02-01), Khavakh et al.
patent: 6249742 (2001-06-01), Friederich et al.
patent: 6317685 (2001-11-01), Kozak et al.
patent: 6321158 (2001-11-01), DeLorme et al.
patent: 6321161 (2001-11-01), Herbst et al.
patent: 6363319 (2002-03-01), Hsu
patent: 6505120 (2003-01-01), Yamashita et al.
patent: 6577949 (2003-06-01), Robinson et al.
patent: 2003/0069683 (2003-04-01), Lapidot et al.
Milici Mike
Tan Xue
Chin Gary
Kaplan Lawrence M.
Kozak Frank J.
Navteq North America, LLC
Shutter Jon D.
LandOfFree
System and method for calculating an optimized route and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for calculating an optimized route and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for calculating an optimized route and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3349373