Route selection method and system

• US 6,338,021 B1
• Filed: 09/28/2000
• Issued: 01/08/2002
• Est. Priority Date: 09/29/1999
• Status: Expired due to Fees

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Fushimi, Makoto, Yagyu, Takeshi, Ueyama, Yoshiki
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): Hernandez, Olga
• Application Number:
  US09/671,109
• Time in Patent Office: 467 Days
• Field of Search: 701/209, 701/200, 701/208, 701/211, 701/213, 340/990, 340/995
• US Class Current: 701/209
• CPC Class Codes: G01C 21/3461 Preferred or disfavoured areas, e.g. dangerous zones, toll or emission zones, intersections, manoeuvre types, segments such as motorways, toll roads, ferries

Abstract

In a route selection process, an optimal route searcher 5 refers to a traffic light flag included in route selecting data stored in a second storage 4 to see whether a target intersection has any traffic light or not. When the optimal route searcher 5 determines that the target intersection has a traffic light s, a traffic light cost calculator 6 calculates a traffic light cost relevant to a waiting time due to the traffic light s. Based on the traffic light cost thus calculated by the traffic light cost calculator 6, the optimal route searcher 5 calculates a passage cost relevant to a time taken for passing the target intersection. In this manner, with consideration for the waiting time due to the traffic light, a time for going through an entire route can be estimated with higher correctness, thereby rendering the route thus searched more optimal.

Claims

1. A route selection method for selecting an optimal route on a map,

road network data representing an intersection and a road, and route selecting data including a traffic light flag which indicates if the intersection has a traffic light or not are previously stored, the method comprising:

a first step of determining, during a route search process for selecting an optimal route between a designated starting point and a destination, whether a target intersection has a traffic light by referring to the traffic light flag included in the route selecting data; and

a second step of calculating, based on the determination made in said first step, a passage cost for passing said target intersection, wherein

the passage cost calculated in said second step is used on to select the optimal route.

2. The route selection method according to claim 1, wherein, in said second step,

when said target intersection is determined as having the traffic light in said first step, a traffic light cost relevant to a waiting time due to the traffic light is calculated, and

based on the calculated traffic light cost, the passage cost is calculated for said target intersection.

3. The route selection method according to claim 1, wherein said route selecting data further includes road type information for specifying a road by type, and

in said second step,

when said target intersection is determined as having the traffic light in said first step, the road type information for a road connected to the target intersection is referred to for calculating a traffic light cost relevant to a waiting time due to the traffic light, and

based on the calculated traffic light cost, the passage cost is calculated for said target intersection.

4. The route selection method according to claim 1, wherein said route selecting data further includes road width information for specifying a road by width,

in said second step,

when said target intersection is determined as having the traffic light in said first step, the road width information for a road connected to the target intersection is referred to for calculating a traffic light cost relevant to a waiting time due to the traffic light, and

based on the calculated traffic light cost, the passage cost is calculated for said target intersection.

5. The route selection method according to claim 1, wherein said route selecting data further includes lane information for specifying a road by a number of lanes,

in said second step,

when said target intersection is determined as having the traffic light in said first step, the lane information for a road connected to the target intersection is referred to for calculating a traffic light cost relevant to a waiting time due to the traffic light, and

based on the calculated traffic light cost, the passage cost is calculated for said target intersection.

6. The route selection method according to claim 1, wherein said route selecting data includes a predetermined reference waiting time cost, and a ratio of waiting time on roads leading to an intersection having a traffic light to the reference waiting time cost, and

in said second step,

when said target intersection is determined as having the traffic light in said first step, said reference waiting time cost and a waiting time ratio on the roads leading to a target intersection are referred to for calculating the traffic light cost relevant to the waiting time due to the traffic light, and

based on the calculated traffic light cost, the passage cost is calculated for said target intersection.

7. The route selection method according to claim 6, wherein said reference waiting time cost is an averaged value for waiting times at every intersection having a traffic light.

8. The route selection method according to claim 6, wherein said route selecting data includes the ratio of waiting time to said reference waiting time cost for some of the roads leading to the intersection having the traffic light, and

in said second step,

even if the ratio of waiting time for a road leading to said target intersection is not included, the ratio of waiting time for another road leading thereto is referred to for calculating the traffic light cost for the target intersection.

9. The route selection method according to claim 1, wherein said road network data represents a road network by a combination of node and link, and several intersections are represented by several nodes and at least one link,

said route selecting data includes an intersection flag which indicates whether the link representing said road network is an intra-intersection link or an extra-intersection link, and

in said second step,

when said target intersection is determined as having the traffic light in said first step, said intersection flag is referred to for calculating a traffic light cost relevant to a waiting time at the target intersection, and

based on the calculated traffic light cost, the passage cost is calculated for said target intersection.

10. The route selection method according to claim 9, wherein, in said second step,

said intersection flag is referred to for determining whether a link representing the road leading to said target intersection is the intra-intersection link or the extra-intersection link, and

only when the link representing the road leading to said target intersection is determined as being the extra-intersection link, the traffic light cost is calculated for the traffic light at the target intersection.

11. The route selection method according to claim 9, wherein, in said second step,

said intersection flag is referred to for determining whether a not-searched link connected to a node representing said target intersection is the intra-intersection link or the extra-intersection link, and

only when said not-searched link is determined as being the extra-intersection link, the traffic light cost is calculated for the traffic light at the target intersection.

12. The route selection method according to claim 9, wherein, in a case where said route search process is done in a bi-directional manner, and started from said designated starting point and from said destination,

in said second step,

for said route search process started from the destination, said intersection flag is referred to for determining whether a not-searched link connected to a node representing said target intersection is the intra-intersection link or the extra-intersection link, and

only when said not-searched link is determined as being the extra-intersection link, the traffic light cost is calculated for the traffic light at the target intersection.

13. The route selection method according to claim 9, wherein, in a case where said route search process is done in a bi-directional manner started from said designated starting point and from said destination,

in said second step,

for said route search process started from the destination, said intersection flag is referred to for determining whether an accessible link to a node representing said target intersection is the intra-intersection link or the extra-intersection link, and

only when said accessible link is determined as being the extra-intersection link, the traffic light cost is calculated for the traffic light at the target intersection.

14. The route selection method according to claim 1, wherein said route selecting data includes a linkage table in which a set of intersections each having a traffic light working in a synchronous manner is stored as a linkage, and

in said second step,

when said target intersection is determined as having the traffic light in said first step, said linkage table is referred to for calculating a traffic light cost relevant to a waiting time due to the traffic light, and

based on the calculated traffic light cost, the passage cost is calculated for said target intersection.

15. The route selecting method according to claim 14, wherein, in said second step,

when said target intersection is determined as having the traffic light in said first step, said linkage table is referred to for comparing a linkage of a previous intersection with a linkage of said target intersection,

based on a result of the comparison, the traffic light cost relevant to the waiting time due to the traffic light at said target intersection is calculated, and

based on the calculated traffic light cost, the passage cost is calculated for said target intersection.

16. The route selection method according to claim 15, wherein, in said second step,

when said target intersection is determined as having the traffic light in said first step, said linkage table is referred to for determining whether an intersection one before the target intersection and the target intersection belong to a same linkage, and

based on the calculated traffic light cost, the passage cost is calculated for said target intersection.

17. The route selection method according to claim 15, wherein, in said second step,

when said target intersection is determined as having the traffic light in said first step, said linkage table is referred to for comparing whether an intersection two before the target intersection and the target intersection belong to a same linkage,

when the linkage of said intersection two before the target intersection is different from the linkage of said target intersection, the traffic light cost relevant to the waiting time due to the traffic light at the intersection is calculated, and

based on the calculated traffic light cost, the passage cost is calculated for said target intersection.

18. The route selection method according to claim 15, wherein, in said second step,

when said target intersection is determined as having the traffic light in said first step, said linkage table is referred to for determining whether said previous intersection and the target intersection belong to a same linkage,

immediately after said previous intersection and the target intersection are determined as belonging to the same linkage for a predetermined number of times in a row, the traffic light cost relevant to the waiting time due to the traffic light at the target intersection is calculated, and

based on the calculated traffic light cost, the passage cost is calculated for said target intersection.

19. The route selection method according to claim 15, wherein, in said second step,

when said target intersection is determined as having the traffic light in said first step, said linkage table is referred to for determining whether said previous intersection and said target intersection belong to a same linkage,

immediately after said previous intersection and the target intersection are determined as belonging to the same linkage for a predetermined amount of time, the traffic light cost relevant to the waiting time due to the traffic light at the target intersection is calculated, and

based on the calculated traffic light cost, the passage cost is calculated for said target intersection.

20. The route selection method according to claim 14, wherein said linkage table has a set of intersections each having a traffic light working in a synchronous manner recorded as a linkage, and

in said second step,

when said target intersection is determined as having the traffic light in said first step, a time for passing the target intersection is estimated,

said linkage table is referred to for determining a linkage to which said target intersection belongs at said estimated time,

the linkage of said target intersection is compared with a linkage of a previous intersection, and based on a result of the comparison, the traffic light cost relevant to the waiting time due to the traffic light at the target intersection is calculated, and

based on the calculated traffic light cost, the passage cost is calculated for said target intersection.

21. A route selection system for selecting an optimal route on a map, comprising:

a route selecting data storage for storing road network data representing an intersection and a road, and route selecting data including a traffic light flag which indicates if the intersection has a traffic light or not;

an optimal route searcher for carrying out a route search process for selecting an optimal route between a starting point and a destination based on the route selecting data stored in said route selecting data storage; and

a traffic light cost calculator which operates when said optimal route searcher is looking for the optimal route, wherein,

in said route search process, said optimal route searcher refers to the traffic light flag in the route selecting data stored in said route selecting data storage to determine whether a target intersection has a traffic light,

when said optimal route searcher determines that said target intersection has the traffic light, said traffic light cost calculator calculates a traffic light cost relevant to a waiting time due to the traffic light, and

based on the traffic light cost calculated by said traffic light cost calculator, said optimal route searcher calculates a passage cost relevant to a time for passing said target intersection.

22. The route selection system according to claim 21, wherein said route selecting data further includes a predetermined reference waiting time cost, and ratio of waiting time on the roads leading to an intersection having a traffic light to the predetermined reference waiting time cost, and

when said optimal route searcher determines that said target intersection has the traffic light, said traffic light cost calculator calculates the traffic light cost relevant to the waiting time due to the traffic light based on said reference waiting time cost and the waiting time ratio at the intersection.

23. The route selection system according to claim 22, wherein said route selecting data includes the ratio of waiting time to said reference waiting time cost for some of the roads leading to the intersection having the traffic light, and

even if the ratio of waiting time for a road leading to said target intersection is not included, said traffic light cost calculator calculates the traffic light cost for the target intersection based on the ratio of waiting time for another road leading thereto.

24. The route selection system according to claim 21, wherein said road network data represents a road network by a combination of node and link, and several intersections are represented by several nodes and at least one link,

said route selecting data further includes an intersection flag which indicates whether the link representing said road network is an intra-intersection link or an extra-intersection link, and

said traffic light cost calculator refers to said intersection flag to calculate the traffic light cost relevant to the waiting time due to the traffic light at said target intersection.

25. The route selection system according to claim 21, wherein said route selecting data further includes a linkage table in which a set of intersections each having a traffic light working in a synchronous manner is recorded as a linkage, and

said traffic light cost calculator refers to said linkage table to calculate the traffic light cost relevant to the waiting time due to the traffic light at said target intersection.

26. The route selection method according to claim 25, wherein said traffic light cost calculator

refers to said linkage table, when said optimal route searcher determines that said target intersection has the traffic light, to determine whether an intersection two before the target intersection and said target intersection belong to a same linkage, and

calculates, when the linkage of said intersection two before the target intersection is different from the linkage of said target intersection, the traffic light cost relevant to the waiting time due to the traffic light at the target intersection.

27. The route selection system according to claim 26, wherein said linkage table has a set of intersections each having a traffic light working in a synchronous manner stored as a linkage on a time range basis, and

said traffic light cost calculator

estimates a time to pass said target intersection, and refers to the linkage table having a linkage stored on the time range basis for determining to which linkage the target intersection belongs at the estimated time, and

compares the linkage of said previous intersection and the linkage of said target intersection, and based on a result of the comparison, calculates the traffic light cost relevant to the waiting time due to the traffic light at the target intersection.

28. A recording medium on which a program is recorded for realizing, on a computer device, a process for selecting an optimal route on a map, the recording medium previously storing road network data representing an intersection and a road, and route selecting data including a traffic light flag which indicates if the intersection has a traffic light, the program comprising:

a first step of determining, during a route search process for selecting an optimal route between a designated starting point and a destination, whether a target intersection has a traffic light by referring to the traffic light flag included in the route selecting data; and

a second step of calculating, based on the determination made in said first step, a passage cost for passing said target intersection, wherein

based on the passage cost calculated in said second step, the optimal route is selected.

29. The recording medium according to claim 28, wherein, in said second step,

when said target intersection is determined as having the traffic light in said first step, a traffic light cost relevant to a waiting time at the traffic light at the target intersection is calculated, and

based on the calculated traffic light cost, the passage cost is calculated for said target intersection.

30. The recording medium according to claim 28, wherein said route selecting data includes a predetermined reference waiting time cost, and a ratio of waiting time on a road leading to an intersection having a traffic light to the reference waiting time, and

in said second step,

when said target intersection is determined as having the traffic light in said first step, said predetermined reference waiting time cost and the waiting time ratio on the roads leading to the target intersection are referred to for calculating a traffic light cost relevant to a waiting time due to the traffic light, and

based on the calculated traffic light cost, the passage cost is calculated for said target intersection.

31. The recording medium according to claim 28, wherein said road network data represents a road network by a combination of node and link, and an intersection appearing therein may be represented by several nodes and at least one link,

said route selecting data includes an intersection flag which indicates whether the link representing said road network is an intra-intersection link or an extra-intersection link, and

in said second step,

when said target intersection is determined as having the traffic light in said first step, said intersection flag is referred to for calculating a traffic light cost relevant to a waiting time at the target intersection, and

based on the calculated traffic light cost, the passage cost is calculated for said target intersection.

32. The recording medium according to claim 28, wherein said route selecting data includes a linkage table in which a set of intersections each having a traffic light working in a synchronous manner is stored as a linkage, and

in said second step,

when said target intersection is determined as having the traffic light in said first step, said linkage table is referred to for calculating a traffic light cost relevant to a waiting time due to the traffic light, and

based on the calculated traffic light cost, the passage cost is calculated for said target intersection.