Navigation system

• US 8,467,960 B2
• Filed: 03/16/2009
• Issued: 06/18/2013
• Est. Priority Date: 03/14/2008
• Status: Active Grant

• Current Assignee: Harman Becker Automotive Systems GmbH (Samsung Electronics Co. Ltd.)
• Original Assignee: Harman Becker Automotive Systems GmbH (Samsung Electronics Co. Ltd.)
• Inventors: Rinscheid, Ansgar
• Primary Examiner(s): Nguyen, Kira
• Application Number:
  US12/405,098
• Publication Number:
  US 20090234577A1
• Time in Patent Office: 1,555 Days
• Field of Search: 701/201, 701/416, 701/417, 701/411
• US Class Current: 701/416
• CPC Class Codes: G01C 21/3415 Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
• CPC Class Codes: G01C 21/343 Calculating itineraries, i.e. routes leading from a starting point to a series of categorical destinations using a global route restraint, round trips, touristic trips travelling salesman problem G06Q10/04; optimisation of routes G06Q10/047
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

A method of operating a navigation system for a vehicle and a vehicle navigation system are provided, where an initial route to a destination is determined, the initial route that includes a plurality of links, each of which is associated with an initial cost. The initial route may be calculated such that it passes within a predetermined distance of one or more predetermined waypoints. One or more of the predetermined waypoints may be designated as an obligatory waypoint, which will be taken into account when calculating a new route. The initial cost associated with a link in the initial route may be decreased and a new route calculated in the event the vehicle deviates from the initial route.

Claims

1. A computer-implemented method of operating a navigation system for a vehicle, the method comprising the steps of:

providing an initial route to a predetermined destination comprising a plurality of links, each of which is associated with an initial cost;

for at least one link of the initial route, decreasing the initial cost associated with the at least one link;

providing a plurality of predetermined waypoints;

designating at least one of the predetermined waypoints as an obligatory waypoint;

providing the at least one link associated with a decreased initial cost for a further route calculation by the navigation system; and

in response to the vehicle deviating from the initial route, calculating, with the navigation system, a new route from, a current position of the vehicle to the destination, taking into account the decreased initial cost and the at least one obligatory waypoint such that the new route to the destination must pass the obligatory waypoint at least within a predetermined distance.

2. The method of claim 1, where the initial route is provided in the form of a list of designators of links that is included in map data provided in the navigation system.

3. The method of claim 1, where the decreasing of the initial cost associated with the at least one link includes the step of setting the cost associated with said link to a predetermined value less than the initial cost associated with the at least one link or of weighting the initial cost associated with the at least one link with a predetermined weighting factor.

4. The method of claim 1, further comprising the step of:

determining a route to the destination passing within a predetermined distance of the at least one predetermined waypoint as the initial route.

5. The method of claim 4, where the locations of the predetermined waypoints are specified by geographic coordinates.

6. The method of claim 1, where a predetermined waypoint located on a loop of the initial route is designated as an obligatory waypoint.

7. The method of claim 1, where for each loop of the initial route, at least one predetermined waypoint is designated as an obligatory waypoint.

8. The method of claim 1, where at least one of the predetermined waypoints corresponds to a point of interest, with the point of interest being designated as an obligatory waypoint.

9. The method of claim 1, where the designation of an obligatory waypoint is performed automatically by the navigation system and/or by user input.

10. The method of claim 1, further comprising the step of providing route guidance along the route provided by the navigation system to a user of the vehicle.

11. The method of claim 1, where the cost is decreased in only one direction of travel of the at least one link of the initial route.

12. A navigation system for a vehicle, the navigation system comprising:

a data providing unit configured to provide an initial route to a predetermined destination, where the initial route comprises a plurality of links, each of which is associated with an initial cost, and where the data providing unit is configured to provide a plurality of predetermined waypoints including at least one obligatory waypoint;

a processing unit for decreasing the initial cost of at least one link of the initial route;

a position determination unit for determining a current position of the vehicle; and

a route determination unit that calculates a new route from the current position to the destination in the event the vehicle deviates from the initial route, the route determination unit takes into account the decreased initial cost of the at least one link and the at least one obligatory waypoint in calculating the new mute such that the new route to the destination must pass the obligatory waypoint at least within a predetermined distance.

13. The navigation system of claim 12, where the route determination unit determines a route to the destination passing within a predetermined distance of at least one of the plurality of predetermined waypoints as the initial route.

14. A non-transitory computer-readable medium that can be loaded into the internal memory of a computer system, said computer-readable medium comprising software code portions that, when executed on the computer system, perform steps comprising:

providing an initial route to a predetermined destination comprising a plurality of links, each of which is associated with an initial cost;

for at least one link of the initial route, decreasing the cost associated with the at least one link;

providing a plurality of predetermined waypoints;

designating at least one of the predetermined waypoints as an obligatory waypoint;

providing the at least one link associated with a decreased cost for a further route calculation by the navigation system; and

in response to the vehicle deviating from the initial route, calculating, with the navigation system, a new route from a current position of the vehicle to the destination, taking into account the decreased initial cost and the at least one obligatory waypoint such that the new route to the destination must pass the obligatory waypoint at least within a predetermined distance.

15. A computer-implemented method of operating a navigation system for a vehicle, the method comprising the steps of:

providing an initial route to a predetermined destination comprising a plurality of links, each of which is associated with an initial cost;

for at least one link of the initial route, decreasing the cost associated with the at least one link;

providing the at least one link associated with a decreased cost for a further route calculation by the navigation system;

providing a plurality of predetermined waypoints including at least one obligatory waypoint; and

in response to the vehicle deviating from the initial route, calculating, with the navigation system, a new route from a current position of the vehicle to the destination taking into account the decreased cost and the at least one obligatory waypoint such that the new route to the destination must pass the obligatory waypoint at least within a predetermined distance.

16. A computer-implemented method of operating a navigation system for a vehicle, the method comprising the steps of:

providing a plurality of predetermined waypoints;

determining an initial route to a predetermined destination passing within a predetermined distance of at least one of the predetermined waypoints, where the initial route comprises a plurality of links, each of which is associated with an initial cost;

for at least one link of the initial route, decreasing the initial cost associated with the at least one link; and

providing the at least one link associated with a decreased cost for a further route calculation by the navigation system,

where at least one predetermined waypoint located on a loop of the initial route is designated as an obligatory waypoint and is provided for further route calculation by the navigation system, and where the navigation system calculates, in response to the vehicle deviating from the initial route, a new route from a current position of the vehicle to the destination, the calculated new route taking into account the decreased cost and the at least one obligatory waypoint such that the new route to the destination must pass the obligatory waypoint at least within a predetermined distance.