Route selection system and method utilizing integrated crossings, a starting route, and/or route numbers

• US 6,067,499 A
• Filed: 09/08/1995
• Issued: 05/23/2000
• Est. Priority Date: 09/08/1994
• 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, Nakamura, Yasuhiro, Ueyama, Yoshiki, Yagyu, Takeshi
• Primary Examiner(s): Cuchlinski, Jr., William A.
• Assistant Examiner(s): PIPALA, EDWARD J
• Application Number:
  US08/523,865
• Time in Patent Office: 1,719 Days
• Field of Search: 364/449.3, 364/449.6, 364/460, 364/424.027, 364/424.029, 364/443, 364/444.1, 364/444.2, 340/995, 701/23, 701/25, 701/200, 701/201, 701/202, 701/208, 701/209, 701/210, 701/211, 701/212
• US Class Current: 701/201
• CPC Class Codes: G01C 21/34 Route searching; Route guidance
• 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

Abstract

A route selection data storage unit 7 stores route selection data which are created from original data describing a detailed road system. When a plurality of crossings and a plurality of roads which are expressed on the road system in the original data satisfy prescribed conditions, these crossings and roads are integrated with each other respectively and recorded in the route selection data. The route selection data include a passage link table, so that links which are deleted by integration of the crossings are not missed. The passage link table records links which are deleted due to the integration of the crossings but passed in practice with reference to approach and escape links as to the respective crossings integrated with each other. An optimum route search unit 6 searches for the optimum route between a starting place and a destination which are designated by a position detection unit and/or a spot input unit 5 through the route selection data. When the optimum route obtained through the search passes through the integrated crossings, the optimum route search unit 6 supplements the deleted links with corresponding passage links recorded in the passage link table.

Claims

1. A route selection method for selecting an optimum route on a map, comprising:

a first step of integrating crossings, which satisfy predetermined conditions, with each other in original data which describes a detailed road system having an actual number of crossings, thereby creating route selection data with a reduced number of crossings than the actual number of crossings; and

a second step of searching for the optimum route between a starting place and a destination as being designated through said route selection data.

2. The route selection method in accordance with claim 1, wherein said route selection data includes:

road system data which describes the road system after integration of the crossings, and

a passage link table, which records links that are deleted due to the integration of crossings but are passed in practice, with reference to approach and escape links as to respective crossings that are integrated with each other;

said second step being adapted to supplement the deleted links with corresponding passage links being described in the passage link table when the optimum route obtained by a search passes through integrated crossings.

3. The route selection method in accordance with claim 2, wherein said first step is adapted to integrate crossings in the original data with each other when a traffic control is present over a plurality of crossings in an actual road system, and

said passage link table records the traffic control which is applied to crossings which are integrated with each other in relation to the traffic control.

4. The route selection method in accordance with claim 2, wherein the passage link table further records evaluation values in passage of integrated crossings with reference to the approach and escape links, and

said second step being adapted to search for the optimum route by reading the passage evaluation values corresponding to approach and escape links of integrated crossings from the passage link table and referring thereto.

5. The route selection method in accordance with claim 2, wherein the passage link table further records traffic information provision numbers of integrated crossings with reference to the approach and escape links, and

said second step being adapted to search for the optimum route in consideration of traffic information which is provided in correspondence to the traffic information provision numbers.

6. The route selection method in accordance with claim 5, wherein the road system being described in the original data is divided into predetermined regions, the traffic information being provided for respective regions,

the passage link table also records traffic information provision numbers corresponding to regions to which crossings which are integrated with each other beyond boundaries between regions belong before integration of the crossings in road system data in the route selection data, in addition to traffic information provision numbers corresponding to regions to which the crossings belong after the integration.

7. The route selection method in accordance with claim 1, wherein said first step is adapted to integrate a plurality of roads, which are present between two adjacent crossings due to the integration of the crossings, with each other.

8. A route selection system for selecting an optimum route on a map, comprising:

a route selection data storage means for storing route selection data which are created from original data describing a detailed road system, and which includes a reduced number of crossings by integration of crossings, which satisfy predetermined conditions in the original data, with each other; and

an optimum route search means for searching for the optimum route between a starting place and a destination as being designated through the route selection data.

9. The route selection system in accordance with claim 8, wherein said route selection data includes:

road system data which describes the road system after integration of crossings and

a passage link table, which records links that are deleted by integration of crossings but are passed in practice with reference to approach and escape links as to respective integrated crossings;

said optimum route search means is for supplementing the deleted links with corresponding passage links being recorded in the passage in table when the optimum route obtained by a search passes through integrated crossings.

10. The route selection system in accordance with claim 9, wherein crossings in the original data are integrated with each other in the route selection data when a traffic control is present over a plurality of crossings in an actual road system, and

said passage link table records the traffic control which is applied to crossings which are integrated with each other in relation to the traffic control.

11. The route selection system in accordance with claim 9, wherein the passage link table further records evaluation values in passage of integrated crossings with reference to the approach and escape links, and

said optimum route search means searching for the optimum route by reading the passage evaluation values corresponding to approach and escape link of integrated crossings from the passage link table and referring thereto.

12. The route selection system in accordance with claim 9, wherein the passage link table further records traffic information provision numbers of integrated crossings with reference to the approach and escape links, and

said optimum route search means is for searching for the optimum route in consideration of traffic information which is provided in correspondence to the traffic information provision numbers.

13. The route selection system in accordance with claim 12, wherein the road system described in the original data is divided into predetermined regions, the traffic information being provided for respective regions,

the passage link table also records traffic information provision numbers corresponding to regions to which crossings which are integrated with each other beyond boundaries between regions belong before the integration of the crossings in road system data in the route selection data, in addition to traffic information provision numbers corresponding to regions to which the crossings belong after the integration.

14. The route selection system in accordance with claim 8, wherein a plurality of roads, which are present between two adjacent crossings due to the integration of the crossings, are integrated with each other in the route selection data.

15. A route selection system for selecting an optimum route on a map, comprising:

starting route search means for searching for optimum routes from a starting place to respective spots which are present in a prescribed range and for selecting any one of the optimum routes as a starting route;

output means for outputting the starting route obtained by said starting route search means for guidance; and

optimum route search means for searching for an optimum route to a destination after the starting route is outputted from the output means.

16. The route selection system in accordance with claim 15, wherein said starting route search means is for searching for the optimum routes to respective spots which are present in a range which is reachable in a constant time from the starting place, and for selecting any one of the optimum routes as the starting route.

17. The route selection system in accordance with claim 15, wherein said starting route search means is for searching for the optimum routes to respective spots which are present at constant distances from the starting place, and for selecting any one of the optimum routes as the starting route.

18. The route selection system in accordance with claim 15, wherein said starting route search means presumes arrival evaluation values from terminal spots of respective optimum routes obtained by the search to the destination, and for selecting an optimum route having a minimum sum of an arrival evaluation value of the optimum route from the starting place to the terminal spot and the presumed arrival evaluation value from the terminal spot to the destination as the starting route.

19. The route selection system in accordance with claim 18, further comprising storage means for storing starting route decision data,

said starting route decision data including arrival evaluation values necessary for traveling along the optimum route between two arbitrary spots as to each of a plurality of spots which are previously picked on the map,

said starting route search means presumes the arrival evaluation values from terminal spots of respective optimum routes obtained by the search to the destination on the basis of the starting route decision data being stored in said storage means.

20. The route selection system in accordance with claim 19, wherein the map employed for the route search in said starting route search means and said optimum route search means, is previously divided into units,

the starting route decision data assumes spots on roads which are present on boundaries between the units as starting place side spots for storage of the arrival evaluation values, and

said starting route search means is for searching for the optimum routes to respective spots which are present in the units including the starting place for selecting any one of the optimum routes as the starting route.

21. The route selection system in accordance with claim 19, wherein said storage means is for storing the arrival evaluation values while reducing the number of destination side spots as compared to starting place side spots.

22. The route selection system in accordance with claim 18, wherein said starting route search means is for obtaining arrival evaluation values necessary for traveling along one-line distances between terminal spots of the optimum routes obtained by the search and the destination for selecting the route having the minimum sum of an arrival evaluation value of the optimum route from the starting place to the terminal spot and the presumed arrival evaluation value from the terminal spot to the destination as the starting route.

23. The route selection system in accordance with claim 15, further comprising storage means for storing starting route decision data,

said starting route decision data including information on a spot to be passed for traveling along the optimum route between two arbitrary spots as to each of a plurality of spots which are previously picked on the map, and

said starting route search means is for acquiring the optimum route between the starting place and the destination from the starting route decision data, and for regarding a passage spot being included in the optimum route acquired from the starting route decision data as a temporary destination for selecting the starting route among a plurality of optimum routes being obtained by the search.

24. The route selection system in accordance with claim 15, wherein said starting route search means is for selecting a route most approaching the direction of the destination as the starting route among a plurality of optimum routes obtained by said search.

25. The route selection system in accordance with claim 15, wherein said optimum route search means is for searching for a first optimum route from the starting place to the destination, for searching for a second optimum route for reaching said first optimum route from a current position, and for connecting the first and second routes with each other to define the optimum route from the current position to the destination.

26. The route selection system in accordance with claim 25, wherein said optimum route search means is for searching for said second route in a prescribed range from the current position to define a route, between the current position to a spot intersecting with the first route on a boundary of the range, as the second route.

27. The route selection system in accordance with claim 15, wherein said optimum route search means is for searching for the optimum route from a terminal spot of the starting route being obtained by said starting route search means to the destination.

28. The route selection system in accordance with claim 15, wherein said starting route search means is for preparing data which is necessary for the search during a user'"'"'s operation of setting the destination of the route.

29. A route selection method comprising:

accessing route selection data which represents a road system and route numbers each of which are arbitrarily set for prescribed roads; and

obtaining a route from a starting place or its vicinity to a destination or its vicinity on the basis of the route numbers.

30. The route selection method in accordance with claim 29, wherein route numbers of roads passing through the vicinity of the starting place are compared with route numbers of roads passing through the vicinity of the destination so that roads having the same route number are selected as a route connecting the vicinity of the starting place with the vicinity of the destination.

31. The route selection method in accordance with claim 30, wherein an optimum route between the starting place and the road of the selected route number is further searched for.

32. The route selection method in accordance with claim 31, wherein the optimum route between the road of the selected route number and said destination is further searched for.

33. The route selection method in accordance with claim 30, wherein any one road is selected by the user when a plurality of roads having the same route number are found as the result of comparison.

34. The route selection method in accordance with claim 29, wherein optimum routes to respective spots which are present in a predetermined constant range from the starting place are searched for and thereafter route numbers of roads passing through the searched range are compared with route numbers of roads passing through the vicinity of the destination so that, upon finding of roads having a same route number, a combination of (1) the optimum route between the starting place and the road having the same route number, and (2) the road having the same route number, is selected as the route connecting the starting place with the vicinity of the destination.

35. The route selection method in accordance with claim 34, wherein an optimum route between the road of the selected route number and the destination is further searched for.

36. The route selection method in accordance with claim 34, wherein any one road is selected by the user when a plurality of roads having the same route number are found as the result of the comparison.

37. The route selection method in accordance with claim 29, wherein optimum routes to respective spots which are present in a predetermined constant range from the starting place, and optimum routes to respective spots which are present in a predetermined constant range from the destination, are searched for respectively, and thereafter route numbers of roads passing through both searched ranges are compared with each other so that a combination of the optimum route between the starting place and a road having a certain route number and the optimum route between the road having the certain route number and the destination is selected as the route connecting the starting place with the destination upon a finding of roads having the same route number.

38. The route selection method in accordance with claim 37, wherein any one road is selected by the user when a plurality of roads of the same route number are found as the result of the comparison.

39. The route selection method in accordance with claim 29, wherein a user designates a spot to be passed and a route number corresponding to the designated spot is obtained from the route selection data, so that an optimum route between the starting place and a road having the corresponding route number is obtained in the vicinity of the starting place, while the optimum route between the road having the corresponding route number and the destination is obtained in the vicinity of the destination.

40. A route selection system, employing route selection data which represents a road system and predetermined route numbers for prescribed roads, for selecting a route between a starting place and a destination, comprising:

first search means for searching for optimum routes to respective spots which are present in a predetermined constant range from the starting place;

second search means for searching for optimum routes to respective spots which are present in a predetermined constant range from the destination;

comparing means for comparing roads passing both the ranges being searched by said first and second search means with each other; and

route selection means for selecting a combination of (1) an optimum route between the starting place and a road having a route number, (2) a road having the route number, and (3) the optimum route between the road having the route number and the destination, as the route connecting the starting place with the destination, when roads having a same route number are present as a result of the comparison by said comparing means.

41. The route selection system in accordance with claim 40, further comprising user designation means for making the user designate any one road when a plurality of roads having the same route number are present as the result of the comparison by said comparing means.

42. A route selection system employing route selection data which represents a road system and predetermined route numbers for prescribed roads, for selecting a route from a starting place to a destination, comprising:

designation means for making the user designate a spot to be passed;

retrieval means for retrieving a route number corresponding to the spot being designated by said designation means from the route selection data;

first search means for searching for an optimum route between the starting place and a road having the retrieved route number;

second search means for searching for an optimum route between the road having the retrieved route number and the destination; and

route selection means for selecting a combination of the optimum route in a vicinity of the starting place searched for by said first search means, the road having the retrieved route number, and the optimum route in a vicinity of the destination searched for by said second search means, as a route connecting the starting place with the destination.

43. A route selection method comprising:

accessing route selection data which represents a road system and predetermined route numbers which are set for a plurality of continuous roads which become one route; and

obtaining a route from a starting place or its vicinity to a destination or its vicinity on the basis of the route numbers without searching on parts of the plurality of continuous roads for which the route numbers are set.