Route search method

• US 6,195,611 B1
• Filed: 12/15/1997
• Issued: 02/27/2001
• Est. Priority Date: 07/23/1997
• Status: Expired due to Fees

• Current Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Denki Kabushiki Kaisha (Mitsubishi Electric Corporation)
• Inventors: Hayashi, Yukio, Sakamoto, Tadashi
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): ARTHUR JEANGLAUDE, GERTRUDE
• Application Number:
  US08/990,799
• Time in Patent Office: 1,170 Days
• Field of Search: 701/200, 701/201, 701/206, 701/207, 701/209, 701/211, 701/214, 701/23, 701/25, 340/988, 340/990, 340/995
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3446 Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags, using precalculated routes

Abstract

A route from a departure point to a destination point is searched. When a route R1 does not exist in a search area A1 which is in the form of an ellipse focusing a departure point S and a destination point E, the area is expanded to a search area A2 to find a route R2.

Claims

1. A route search method for searching a plurality of nodes linked with each other for a specific route from a departure point to a destination point, said plurality of nodes including said departure point and said destination point,

said route search method comprising the steps of:

a judging step of judging which of said plurality of nodes is adopted into said specific route in a search area including said departure point and said destination point,

said judging step being repeated when said search area is updated, wherein said search area after being updated includes said search area before being updated, wherein

said judging step includes the steps of;

(a) adopting one of said plurality of nodes as an expansion node from a list, said one being included in said search area and its passing flag being “

0”

;

(b) setting said passing flag of said expansion node at “

1”

; and

(c) finding a node ahead of the link with said expansion node regardless of inside and outside said search area, and registering said node ahead of the link in said list along with said passing flag of “

0” and

an accumulated total distance from said departure point via said expansion node to said node ahead of the link, said step (c) returning to said step (a) after the registration.

2. The route search method as set forth in claim 1, wherein

said step (c) includes the steps of:

(c-1) making a comparison, when said node ahead of the link has already been registered in said list, between said accumulated total distance which has already been registered in said list, and said accumulated total distance which is newly found, and then modifying said accumulated total distance by a shorter one; and

(c-2) registering said passing flag of said node ahead of the link as “

0”

in said list.

3. The route search method as set forth in claim 2, wherein

said steps (c-1) and (c-2) are performed even if said passing flag of said node ahead of the link has already been registered as “

0”

in said list.

4. A route search method for searching a plurality of nodes linked with each other for a specific route from a departure point to a destination point, said plurality of nodes including said departure point and said destination point,

said route search method comprising the steps of:

a judging step of judging which of said plurality of nodes is adopted into said specific route in a search area including said departure point and said destination point,

said judging step being repeated when said search area is updated wherein said search area after being updated includes said search area before being updated,

wherein said search area is in the form of an ellipse which has two focal points including said departure point and said destination point, wherein

whether said one of said plurality of nodes is included in said search area or not is determined by comparing the sum of distances from a certain point of a boundary of said search area to each of said focal points, with the sum of distances from said one of said plurality of nodes to each of said focal points.

5. A route search method for searching a plurality of nodes linked with each other for a specific route from a departure point to a destination point, said plurality of nodes including said departure point and said destination point,

said route search method comprising the steps of:

a judging step of judging which of said plurality of nodes is adopted into said specific route in a search area including said departure point and said destination point,

said judging step being repeated when said search area is updated, wherein said search area after being updated includes said search area before being updated, wherein

said judging step includes the steps of;

(a) selecting an expansion node out of said plurality of nodes included in said search area;

(b) selecting a node linked with said expansion node as a node ahead of the link, regardless of inside and outside said search area;

(c) finding a distance from said departure point via said expansion node to said node ahead of the link;

(d) adopting a shorter one of said distances as an accumulated total distance to a first node ahead of the link, when said node ahead of the link obtained by said step (b) is common to said first node ahead of the link with a different expansion node, every time said step (c) is performed on said different expansion node; and

(e) finding said specific route by linking said expansion node giving said accumulated total distance adopted in said step (d),

wherein at least said steps (a) and (b) are performed on a node which as not been adopted as said expansion node yet.

6. The route search method as set forth in claim 5, wherein

said search area is in the form of an ellipse focusing said departure point and said destination point.

7. The route search method as set forth in claim 5, wherein

said steps (a) and (b) is performed also on a node which has already been adopted as said expansion node.

8. The route search method as set forth in claim 7, wherein

said search area is in the form of an ellipse focusing said departure point and said destination point.