Navigation system

• US 20060129314A1
• Filed: 12/09/2005
• Published: 06/15/2006
• Est. Priority Date: 12/09/2004
• Status: Abandoned Application

• Current Assignee: LG Electronics, Inc. (LG Corporation)
• Original Assignee: LG Electronics, Inc. (LG Corporation)
• Inventors: Gi Ryoong, Kim
• Application Number:
  US11/299,194
• Publication Number:
  US 20060129314A1
• Time in Patent Office: Days
• US Class Current: 701/209
• 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/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem

Abstract

A navigation system is provided. The navigation system includes a path analyzer, a weight generator, an algorithm pre-processor, a genetic algorithm processor, and a path selector. The path analyzer combines a plurality of inputted intermediate point information to analyze movement path information, and the weigh generator generates weight information according to duration between the intermediated points. The algorithm pre-processor combines the intermediate point information to generate an initial solution group. The genetic algorithm processor generates a new candidate solution using a candidate solution contained in the initial solution group and replaces a candidate solution contained in the initial solution group by the new candidate solution depending on movement path information of the new candidate solution. The path selector selects a candidate solution having optimized movement path information from the candidate solutions contained in the solution group.

Claims

1. A navigation system comprising:

a path analyzer for combining a plurality of inputted intermediate point information to analyze movement path information;

a weight generator for generating weight information according to a movement duration between intermediate points;

an algorithm pre-processor for combining the intermediate point information to generate an initial solution group;

a genetic algorithm processor for generating a new candidate solution using a candidate contained in the initial solution group and replacing the candidate solution contained in the initial solution group by the new candidate solution depending on movement path information of the new candidate solution; and

a path selector for selecting a candidate solution having optimized movement path information from candidate solutions contained in the solution group.

2. The navigation system according to claim 1, wherein the optimized movement path information is a minimum movement duration.

3. The navigation system according to claim 1, wherein the generation of the new candidate using the candidate solution contained in the initial solution group comprises exchanging some of intermediate points between at least two candidate solutions.

4. The navigation system according to claim 1, wherein the generation of the new candidate using the candidate solution contained in the initial solution group is performed using a cycle crossover method.

5. The navigation system according to claim 1, wherein the genetic algorithm processor repeatedly generates a new candidate solution and replaces the candidate solution contained in the solution group by the new candidate solution until a predetermined stop condition is satisfied.

6. The navigation system according to claim 1, wherein the path analyzer analyzes the movement path information that is combined using a weighted graph method.

7. The navigation system according to claim 1, wherein the plurality of intermediate point information comprises sequence information between some of the intermediate points.

8. The navigation system according to claim 7, wherein the algorithm pre-processor excludes a candidate solution that is not matched with the sequence information between some of the intermediate points when generating the initial solution group.

9. The navigation system according to claim 1, wherein the weight information comprises at least one of distance information between intermediate points, traffic information, traffic signal information, and street status information.

10. The navigation system according to claim 4, wherein the genetic algorithm processor sets the sequence information between some of the intermediate points as a unit of a cycle crossover when performing the cycle crossover on the candidate solution contained in the solution group.

11. A method for selecting a path in a navigation system, the method comprising:

generating a solution group consisting of a plurality of candidate solutions each combining a plurality of intermediate points;

generating a new candidate solution by exchanging some of the intermediate points contained in the candidate solution;

replacing the candidate solution contained in the solution group by the new candidate solution depending on movement path information of the new candidate solution; and

selecting a candidate solution having optimized movement path information from the candidates contained in the solution group.

12. The method according to claim 11, wherein the optimized movement path information is a minimum movement duration.

13. The method according to claim 11, wherein the generating of the new candidate using the candidate solution contained in the initial solution group is performed using a cycle crossover method.

14. The method according to claim 11, wherein the replacing of the candidate solution contained in the solution group by the new candidate solution is repeated until a predetermined stop condition is satisfied.

15. The method according to claim 11, wherein the generating of the solution group comprises excluding a candidate solution that is not matched with sequence information between some of the intermediate points.

16. The method according to claim 11, further comprising, when the weight information of the new candidate solution is smaller than that of the candidate solution contained in the solution group, replacing the candidate solution having the greater weight by the new candidate solution.

17. The method according to the claim 11, wherein the weight information comprises at least one of distance information between intermediate points, traffic information, traffic signal information, and street status information.