JP4941046B2 - Route calculator - Google Patents

Description

  The present invention relates to a route calculation apparatus that calculates a route from a current location of a host vehicle to a set destination.

  The navigation device installed in the vehicle measures the current position of the vehicle, calculates the route from the measured current position to the destination set by the user, and provides a function to guide the host vehicle based on the calculated route To do. This function allows the user to reach the destination easily and reliably.

  However, when performing the route calculation as described above, the route calculation takes time, such as when there are many route candidates, that is, when there are many branch points on the road, and the user may feel stressed.

Therefore, in Patent Document 1, when detection of the current position is started, a route starting from the memory location stored in advance or a point set as the destination in the past as the end point and starting from the current position is calculated. The route is stored in the storage unit. When the user sets a memory point or a point that has been set as a destination in the past as a destination, a route that has already been calculated with the destination set by the user as an end point is read from the storage unit, and the read route There has been proposed a navigation device that uses the for route guidance.
JP 2003-156349 A

  However, in the navigation device described in Patent Document 1, since all the calculated routes having the destination set by the user as the end point are stored in the storage unit as history information, the history information stored in the storage unit The storage capacity required in proportion to the number of files may become enormous. In addition, since the storage capacity necessary for storing history information depends on the distance between the departure point and the destination, when recording a plurality of long-distance history information with a large distance between the departure point and the destination, This could put a lot of pressure on the limited resources of the memory.

  In recent years, portable navigation systems that can be carried and do not have large-capacity hard disks have been introduced to the market, and a path calculation device that saves storage capacity and performs route calculation at high speed is anxious. It had been.

  The present invention has been made in view of the above problems, and an object of the present invention is to provide a route calculation apparatus that performs route calculation at high speed with a small storage capacity.

In order to solve the above object, the first feature of the route calculation apparatus according to the present invention is that the present location information indicating the current location, the destination information indicating the destination, the search condition information indicating the search condition, and the route calculation requesting the route calculation. The route from the current location to the destination is calculated from the input information receiving means to which the request signal is supplied, the current location information, the destination information, and the search condition information, and the route that best suits the search condition is calculated among the calculated routes. A first route calculation unit that sets a recommended branch route as a recommended route and a route that branches from a branch point existing on the recommended route, and a calculation time required for calculating the recommended route by the first route calculation unit is measured. A road link indicating the branch point information indicating the branch point and the number of routes connecting the branch point and the branch point existing on the recommended branch route when the measured calculation time is equal to or longer than the predetermined time. Number and Feature point candidate calculation means that calculates the direction of travel information indicating the direction of travel at the branch point existing on the recommended route as feature point candidate information, and the portion of the calculation time exceeding the predetermined time is calculated as the over time. , the first path calculation means calculates the number of excess road links is the number of road links that are calculated in the over time, a feature point candidate information at each branch point on the recommended route, in order of the most number of road links, the excess Feature point information calculating means for extracting as feature point information until the number of road links is reached, current location information, destination information, search condition information, feature point information when a route calculation request signal is supplied to the input information receiving means, a feature point storing means for storing a feature point history information in association with the read feature point history information stored in the feature point storing means, proceeds on the basis of the read feature point history information The path between the feature points indicated by the characteristic point information including the direction information to calculate a second path calculation means for calculating a route from the current position to the destination based on the route between the calculated feature points, the input information receiving means When the route calculation request signal is supplied to the feature point, the feature point history information stored in the feature point storage unit is read, and the current location information, destination information, and search condition information supplied to the input information receiving unit are read out. It is determined whether the current location information, the destination information, and the search condition information in the feature point history information match each other. If they match, the second route calculation means calculates the route. And a route calculation determination unit that causes the route calculation unit to calculate a route.

  The route calculation apparatus according to the present invention can perform route calculation at high speed with a small storage capacity.

  The best mode for carrying out the present invention will be described below with reference to the drawings.

<First Embodiment>
FIG. 1 is a block diagram showing a configuration of a route calculation apparatus according to the first embodiment for carrying out the present invention.

  As shown in FIG. 1, the route calculation device 1 includes a CPU 10, a feature point storage unit 11, an input unit 12, a GPS sensor 13, a voice output unit 14, and a display unit 15 connected to the CPU 10.

  The CPU 10 includes an input information receiving unit 10a, a first route calculating unit 10b, a time measuring unit 10c, a feature point candidate calculating unit 10d, a feature point information calculating unit 10e, a second route calculating unit 10f, A route calculation determination unit 10g and an output control unit 10h are provided, and various processes such as a route calculation determination process and a route calculation process are executed according to a program such as a route guidance program.

  The feature point storage unit 11 is a storage medium such as a memory or an HDD, and stores a destination history information table and a destination history detailed information table as feature point history information. In addition, the CPU 10 such as a route guidance program performs processing. Information necessary for execution is stored.

  FIG. 2 is an explanatory diagram showing an example of the destination history information table stored in the feature point storage unit 11.

  As shown in FIG. 2, the feature point storage unit 11 includes a column name “destination name” (reference numeral 21), a column name “destination position” (reference numeral 22), and a column name “search condition detailed number as an external key. "(Reference numeral 23) is stored in association with the destination history information table. Here, the column name “destination name” (reference numeral 21) or the column name “destination position” (reference numeral 22) is the destination information.

  FIG. 3 is an explanatory diagram showing an example of the destination history detailed information table stored in the feature point storage unit 11.

  As shown in FIG. 3, the feature point storage unit 11 has a column name “search condition detail number” (reference numeral 31), a column name “departure location information” (reference numeral 32), and a column name “search condition information” as primary keys. "(Reference numeral 33), column name" number of feature point information "(reference numeral 34), and column name" feature point information "(reference numeral 43) are stored in association with each other as a destination history detailed information table.

  The input unit 12 is a touch panel, a remote control device, or the like, and destination information that is information indicating a destination by a user's operation, search condition information that is information indicating search conditions, and a route calculation request for requesting route calculation A signal is generated, and the generated destination information, search condition information, and route calculation request signal are transmitted to the CPU 10.

  The GPS sensor 13 receives a GPS signal from a GPS satellite for detecting the position of the vehicle, generates current location information indicating the current location based on the received GPS signal, and transmits the generated current location information to the CPU 10.

  The voice output unit 14 is a speaker, for example, and outputs voice guidance on the route at an appropriate timing during traveling. The display unit 15 is a liquid crystal display, for example, and is a device that receives an output signal from the CPU 10 and displays a map, a route, an instruction guide, and the like.

  The input information receiving means 10a of the CPU 10 receives current location information indicating the current location, destination information indicating the destination, search condition information indicating the search conditions, and a route calculation request signal for requesting route calculation.

  The first route calculation means 10b of the CPU 10 calculates a route from the current location to the destination from the current location information, the destination information, and the search condition information, and recommends a route that best matches the search condition among the calculated routes. A route that branches from a branch point existing on the recommended route is defined as a recommended branch route.

  The time measuring means 10c of the CPU 10 measures the calculation time required for the calculation of the recommended route by the first route calculating means 10b.

  The feature point candidate calculation means 10d of the CPU 10 determines the branch point information indicating the branch point and the number of routes connecting the branch point and the branch point existing on the recommended branch route when the measured calculation time is equal to or longer than the predetermined time. And the traveling direction information indicating the traveling direction at the branch point existing on the recommended route are calculated as feature point candidate information.

  The feature point information calculation means 10e of the CPU 10 calculates a portion exceeding the predetermined time as the over time in the calculation required time, and each branch on the recommended route calculated within the over time by the first route calculation means 10b. Feature point candidate information at points is extracted as feature point information in descending order of the number of road links.

  The second path calculation unit 10f of the CPU 10 reads the feature point history information stored in the feature point storage unit 11, calculates the path between the feature points indicated by the feature point information based on the read feature point history information, A route from the current location to the destination is calculated based on the calculated route between feature points.

  The route calculation determination unit 10g of the CPU 10 reads the feature point history information stored in the feature point storage unit 11 when the route calculation request signal is supplied to the input information reception unit 10a, and is supplied to the input information reception unit 10a. It is determined whether the current location information, the destination information, and the search condition information match the current location information, the destination information, and the search condition information of the read feature point history information. The route calculation unit 10f calculates the route, and if they do not match, the first route calculation unit 10c calculates the route.

  The output control unit 10h of the CPU 10 provides route guidance to the voice output unit 14 and the display unit 15 based on the route from the current location to the destination calculated by the first route calculation unit 10b or the second route calculation unit 10f. Output.

≪Operation of route calculation device≫
Next, a processing procedure in the route calculation apparatus 1 according to the first embodiment will be described with reference to the flowchart of FIG.

  First, the input information receiving means 10a of the CPU 10 of the route calculation apparatus 1 receives current location information that is information indicating the current location generated by the GPS sensor 13, and is further information indicating the destination generated by the input unit 12. It receives certain destination information, search condition information that is information indicating a search condition, and a route calculation request signal for requesting route calculation.

  When the route calculation request signal, the current location information, and the destination information are supplied from the input information receiving unit 10a, the route calculation determination unit 10g of the CPU 10 is a point where the destination indicated by the destination information is newly set. It is determined whether or not there is a point that has been set in the past. Specifically, the route calculation determining unit 10g of the CPU 10 reads the destination history information from the feature point storage unit 11, and the destination information supplied from the input information receiving unit 10a is the destination of the read destination history information. It is determined whether or not the information matches (step S100).

  If the route calculation determination unit 10g determines that the destination indicated by the destination information is a newly set point, whether the search condition indicated by the search condition information is a newly set condition, Alternatively, it is determined whether the condition has been set in the past. Specifically, the route calculation determining unit 10g of the CPU 10 reads the destination history detailed information from the feature point storage unit 11, and the search condition information supplied from the input information receiving unit 10a is the information of the read destination history detailed information. It is determined whether or not it matches the search condition information (step S101).

  Then, the route calculation determination unit 10g of the CPU 10 determines that the destination indicated by the destination information is newly set in step S100, or the search condition indicated by the search condition information is newly set in step S101. If it is determined that the conditions are satisfied, the time measuring unit 10c starts measuring the calculation time required for the first route calculating unit 10b to perform route calculation (step S102).

  Next, the route calculation determination unit 10g of the CPU 10 transmits a route calculation instruction signal for calculating a route to the first route calculation unit 10b. Then, the first route calculation means 10b that has received the route calculation instruction signal calculates a route from the current location to the destination based on the current location information, the destination information, and the search condition information supplied to the input information reception means 10a. (Step S103). Then, the first route calculation means 10b sets a route that best matches the search condition among the calculated routes as a recommended route, and sets a route that branches from a branch point existing on the recommended route as a recommended branch route.

  FIG. 5 is an explanatory diagram showing recommended routes calculated by the first route calculation means 10b.

  As shown in FIG. 5, a recommended route 52 from the current location 50 indicated by the current location information supplied to the input information receiving means 10a to the destination 51 indicated by the destination information is calculated. Here, the recommended route refers to a route that is most suitable for the search condition supplied to the input information receiving means 10a among the routes calculated.

  FIG. 6 is an explanatory diagram showing recommended routes and recommended branch routes calculated by the first route calculation means 10b.

  As shown in FIG. 6, branch points P <b> 1 to P <b> 8 exist on the recommended route 52 from the current location 50 to the destination 51. Therefore, the first route calculation means 10b sets the routes 53 to 60, which are routes other than the recommended route 52 branched from the branch points P1 to P8, as recommended branch routes (drawn with broken lines in FIG. 6).

  Next, when the route calculation is completed by the first route calculation means 10b, the time measurement means 10c finishes measuring the time required for calculation, which is the time required for the route calculation by the first route calculation means 10b. (Step S104).

  Next, the feature point candidate calculation unit 10d of the CPU 10 determines whether or not the required calculation time measured by the time measurement unit 10c is equal to or longer than a predetermined time (step S105).

  Here, the predetermined time is set in advance by the provider of the route calculation apparatus 1 or the like, and is preferably set according to the hardware capability of the route calculation apparatus 1. For example, when the route calculation apparatus 1 is realized with a hardware configuration with relatively low capacity, the predetermined time is set to 10 seconds, and when the route calculation takes 10 seconds or more, the calculation required time is a predetermined time. It determines with it being above.

  When the characteristic point candidate calculation unit 10d of the CPU 10 determines that the required calculation time is equal to or longer than the predetermined time, the feature point candidate calculation unit 10d obtains the information on the branch points of the recommended route and the recommended branch route calculated by the first route calculation unit 10b. The branching point information, the number of road links, and the traveling direction information indicating the traveling direction at the branching point on the recommended route are calculated as feature point candidate information (step S106).

  Here, the number of road links indicates the number of routes between the branch points on the recommended branch route. For example, as shown in FIG. 6, the recommended branch path 55 includes a branch point S1 and a branch point S2, and a path 55-1 that is a path from the branch point P3 to the branch point S1 between the recommended path and the recommended branch path. Since there is a route 55-2 which is a route from the branch point S1 to the branch point S2, and a route 55-3 which is a route from the branch point S2 to the branch point S3, the number of road links in the recommended branch route 55 is , “3”.

  Then, the feature point candidate calculation unit 10d rearranges the feature candidate point information so that the number of road links for each feature candidate point is in the descending order, that is, the order in which the number of routes between the branch points on the recommended branch route is in descending order.

  Next, the feature point information calculation unit 10e of the CPU 10 calculates a portion exceeding the predetermined time in the calculation required time as an over time, and the feature point candidate calculated within the over time by the first route calculation unit 10b. The number of information is determined as the number of feature point information (step S107).

  For example, the number of road links a calculated for the route within the overtime is calculated by the following formula 1.

(Equation 1)
a = ((L1 + L2) / T) × t
L1: Number of recommended road links
L2: Number of road links on all recommended branch routes
T: Time required for calculation (seconds)
t: Over time (seconds)
a: The number of road links calculated during the overtime and the number of road links calculated during the overtime. The feature candidate point information has the highest number of road links in the feature candidate point information. The number of road links is subtracted, and the number of subtractions when a becomes zero or less is determined as the number of feature point information.

  In step S105, if the feature point candidate calculation unit 10d determines that the required calculation time is less than the predetermined time, the number of feature point information is set to “0”, and the process ends.

  Next, the feature point information calculation unit 10e extracts feature point candidate information corresponding to the determined number of feature point information as feature point information, and current location information when the route calculation request signal is supplied to the input information reception unit 10a. The starting point information, destination information, search condition information, and extracted feature point information are associated with each other and stored in the feature point storage unit 11 as feature point history information (step S109).

  Specifically, the feature point information calculation means 10e divides the feature point history information into a destination history information table and a destination history detailed information table, and associates these two tables with “search condition detailed number” to feature. It is stored in the point storage unit 11.

  As shown in FIG. 2, a column name “destination name” (reference numeral 21), a column name “destination position” (reference numeral 22), and a column name “search condition detailed number” (reference numeral 23) as an external key are provided. The feature points are stored in the feature point storage unit 11 as a destination history information table. Here, the column name “destination name” (reference numeral 21) and the column name “destination position” (reference numeral 22) are the destination information.

  Further, as shown in FIG. 3, the feature point information calculation means 10e uses the column name “search condition detailed number” (reference numeral 31), the column name “departure information” (reference numeral 32), and the column name “ The search condition information ”(reference numeral 33), the column name“ number of feature point information ”(reference numeral 34), and the column name“ feature point information ”(reference numeral 43) are associated with each other as the feature detail storage table 11 as the history detailed information table. Remember me.

  FIG. 7 is an explanatory diagram illustrating the feature points indicated by the feature point information extracted by the feature point information calculation unit 10e.

  As shown in FIG. 7, among the feature candidate points P1 to P8 on the recommended route 52, feature points P3, P4, and P6 are extracted as feature point information corresponding to the number of feature point information. As a result, feature points are extracted from the feature candidate points in the descending order of the number of road links, that is, in the order that requires time for route calculation.

  In step S101, if the route calculation determination unit 10g of the CPU 10 determines that the search condition indicated by the search condition information is a condition set in the past, the route calculation instruction signal for calculating the route is the second route calculation. Transmit to means 10f. Then, the second route calculation means 10f that has received the route calculation instruction signal reads the number of feature point information of the feature point history information stored in the feature point storage unit 11 (step S110), and further, departure point information and purpose The ground information, search condition information, and feature point information are read out (step S111).

  Next, the second route calculation unit 10f calculates a route between feature points indicated by the feature point information based on the read feature point history information (step S112).

  FIG. 8 is a flowchart showing a route calculation processing procedure by the second route calculation means 10f.

  The second route calculation means 10f determines whether or not feature point information whose starting point information, destination information, and search condition information match remains, and the starting point information, destination information, and search condition information match. Until there is no feature point information, route calculation is performed for all the feature points (step S200).

  Specifically, the second route calculation unit 10f sets feature points as the start point and the end point (step S201), and performs route calculation between the feature points (step S202).

  In the diagram shown in FIG. 7, the second route calculation means 10f first calculates the route from the current location 50 to the feature point P3 by setting the current location 50 as the start point and the feature point P3 as the end point. Next, the feature point P3 is set as the start point, the feature point P4 is set as the end point, and the route from the feature point P3 to the feature point P4 is calculated. Thus, the second route calculation means 10f calculates a route from the current location 50 to the destination 51 as a route between feature points.

  Then, in step S200, when it is determined that the route calculation has been completed for all the paths between the feature points until there is no feature point information whose starting point information, destination information, and search condition information match, the calculation is performed in step S202. The routes between the feature points are connected, and a recommended route is calculated as a route from the current location 50 to the destination 51 (step S203).

  This eliminates the need for route calculation of recommended branch routes connected to feature points that require time for route calculation, so that route calculation from the current location to the destination can be performed quickly. Moreover, since only the information of the branch point used as a feature point is memorize | stored in the feature point memory | storage part 11 among many branch points from the present location to the destination, storage capacity can be saved.

  As described above, according to the route calculation apparatus 1 according to the first embodiment, route calculation can be performed at high speed with a small storage capacity.

<Second Embodiment>
In the route calculation device according to the second embodiment, the feature point information calculation unit 10e uses a threshold value when the number of feature point candidate information calculated by the feature point candidate calculation unit 10d is larger than a predetermined threshold value. The number of point information is determined, and feature point candidate information corresponding to the determined number of feature point information is extracted as feature point information in descending order of the number of road links.

≪Operation of route calculation device≫
Next, a processing procedure in the route calculation apparatus 101 according to the second embodiment will be described with reference to the flowchart of FIG.

  First, the input information receiving unit 10a of the CPU 10 of the route calculation apparatus 101 receives current location information that is information indicating the current location generated by the GPS sensor 13, and is further information indicating the destination generated by the input unit 12. It receives certain destination information, search condition information that is information indicating a search condition, and a route calculation request signal for requesting route calculation.

  When the route calculation request signal, the current location information, and the destination information are supplied from the input information receiving unit 10a, the route calculation determination unit 10g of the CPU 10 is a point where the destination indicated by the destination information is newly set. It is determined whether or not there is a point that has been set in the past. Specifically, the route calculation determining unit 10g of the CPU 10 reads the destination history information from the feature point storage unit 11, and the destination information supplied from the input information receiving unit 10a is the destination of the read destination history information. It is determined whether or not the information matches (step S300).

  Furthermore, when the route calculation determination unit 10g of the CPU 10 determines that the destination indicated by the destination information is a newly set point, the search condition indicated by the search condition information is a newly set condition. Or a condition that has been set in the past. Specifically, the route calculation determining unit 10g of the CPU 10 reads the destination history detailed information from the feature point storage unit 11, and the search condition information supplied to the input information receiving unit 10a is the information of the read destination history detailed information. It is determined whether or not it matches the search condition information (step S301).

  Then, the route calculation determination unit 10g of the CPU 10 determines that the destination indicated by the destination information is a newly set point in step S300, or newly sets the search condition indicated by the search condition information in step S301. If it is determined that the conditions are satisfied, a route calculation instruction signal for calculating a route is transmitted to the first route calculation means 10b.

  Next, the first route calculation unit 10b that has received the route calculation instruction signal calculates a route from the current location to the destination from the current location information, destination information, and search condition information supplied to the input information reception unit 10a. (Step S302). The first route calculation means 10b sets a route that best matches the search condition among the calculated routes as a recommended route, and sets a route that branches from a branch point on the recommended route as a recommended branch route.

  Next, the feature point candidate calculation unit 10d of the CPU 10 includes branch point information indicating branch point information between the recommended route and the recommended branch route calculated by the first route calculation unit 10b, the number of road links, and the recommended route. Travel direction information indicating the travel direction at the upper branch point is calculated as feature point candidate information (step S303).

  Further, the feature point candidate calculation means 10d has the feature candidate point information so that the number of road links for each feature candidate point is in descending order, that is, in the order in which the number of routes between the branch points on the recommended branch route is large. Sort by.

  Next, the feature point information calculation unit 10e determines whether or not the number of feature point candidate information calculated by the feature point candidate calculation unit 10d of the CPU 10 is larger than a predetermined threshold (step S304).

  Here, the threshold value is set in advance by the provider of the route calculation apparatus 101 or the like, and is preferably set according to the hardware capability of the route calculation apparatus 101. For example, when the path calculation apparatus 101 is realized with a hardware configuration with relatively low capability, the threshold is set to “10”.

  If it is determined that the number of feature point candidate information calculated by the feature point candidate calculation unit 10d is larger than a predetermined threshold, this threshold is determined as the number of feature point information (step S305). Feature point candidate information corresponding to the number of feature point information is extracted as feature point information in descending order of the number of road links.

  In step S304, when the feature point candidate calculation unit 10d determines that the number of feature point candidate information is equal to or less than a predetermined threshold, the number of feature point information is set to “0”, and the process ends. .

  Next, the feature point information calculation unit 10e extracts feature point candidate information corresponding to the determined number of feature point information as feature point information, and current location information when the route calculation request signal is supplied to the input information reception unit 10a. The starting point information, the destination information, the search condition information, and the extracted feature point information are associated with each other and stored as feature point history information in the feature point storage unit 11 (step S307).

  Specifically, the feature point information calculation means 10e divides the feature point history information into a destination history information table and a destination history detailed information table, and associates these two tables with “search condition detailed number” to feature. It is stored in the point storage unit 11.

  As shown in FIG. 2, a column name “destination name” (reference numeral 21), a column name “destination position” (reference numeral 22), and a column name “search condition detailed number” (reference numeral 23) as an external key are provided. The feature points are stored in the feature point storage unit 11 as a destination history information table. Here, the column name “destination name” (reference numeral 21) and the column name “destination position” (reference numeral 22) are the destination information.

  Further, as shown in FIG. 3, the feature point information calculation means 10e uses the column name “search condition detailed number” (reference numeral 31), the column name “departure information” (reference numeral 32), and the column name “ The search condition information ”(reference numeral 33), the column name“ number of feature point information ”(reference numeral 34), and the column name“ feature point information ”(reference numeral 43) are associated with each other as the feature detail storage table 11 as the history detailed information table. Remember me.

  In step S301, when the route calculation determination unit 10g of the CPU 10 determines that the search condition indicated by the search condition information is a condition set in the past, the route calculation instruction signal for calculating the route is the second route calculation. Transmit to means 10f. Then, the second route calculation means 10f that has received the route calculation instruction signal reads the number of feature point information of the feature point history information stored in the feature point storage unit 11 (step S308), and further, the departure point information and the destination Information, search condition information, and feature point information are read out (step S309).

  Next, the second route calculation means 10f calculates a route between feature points based on the read departure point information, destination information, search condition information, and feature point information (step S310).

  The detailed processing procedure of the route calculation by the second route calculation means 10f is the same as the processing flow of the route search in the route calculation device 1 according to the first embodiment shown in FIG. Omitted.

  Thus, according to the route calculation device 101 according to the second embodiment, by determining whether the number of feature point candidate information calculated by the feature point candidate calculation unit 10d is larger than a predetermined threshold value. Since the number of feature point information is calculated, the number of feature point information can be calculated more simply.

  Thereby, the route calculation from the present location to the destination can be performed more quickly. Moreover, since only the information of the branch point used as a feature point is memorize | stored in the feature point memory | storage part 11 among many branch points from the present location to the destination, storage capacity can be saved.

  As described above, according to the route calculation apparatus 101 according to the second embodiment, route calculation can be performed at high speed with a small storage capacity.

It is the block diagram which showed the structure of the path | route calculation apparatus which is 1st Embodiment for implementing this invention. It is explanatory drawing which showed an example of the destination log | history information table which the feature point memory | storage part has memorize | stored. It is explanatory drawing which showed an example of the destination log | history detailed information table which the feature point memory | storage part has memorize | stored. It is the flowchart which showed the process sequence in the route calculation apparatus which is 1st Embodiment. It is explanatory drawing which showed the recommendation path | route calculated by the 1st path | route calculation means. It is explanatory drawing which showed the recommendation path | route calculated by the 1st path | route calculation means, and the recommendation branch path | route. It is explanatory drawing explaining the feature point which the feature point information which the feature point information calculation means extracted showed. It is the flowchart which showed the processing procedure of the route search by the 2nd route calculation means. It is the flowchart which showed the process sequence in the route calculation apparatus which is 2nd Embodiment.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1,101 ... Route calculation apparatus 10 ... CPU
DESCRIPTION OF SYMBOLS 10a ... Input information receiving means 10b ... 1st route calculation means 10c ... Time measurement means 10d ... Feature point candidate calculation means 10e ... Feature point information calculation means 10f ... Second route calculation means 10g ... Path calculation judgment means 10h ... Output Control means 11 ... feature point storage section (feature point storage means)
DESCRIPTION OF SYMBOLS 12 ... Input part 13 ... GPS sensor 14 ... Audio | voice output part 15 ... Display part

Claims (1)

In addition to detecting the current location of the device itself, one point on the map displayed on the display unit is set as the destination, and the route from the current location to the destination is calculated based on the search condition input by the user operation. A route calculation device,
Input information receiving means to which current location information indicating the current location, destination information indicating the destination, search condition information indicating the search conditions, and a route calculation request signal for requesting the route calculation;
A route from the current location to the destination is calculated from the current location information, the destination information, and the search condition information, and a route that best meets the search condition is selected as a recommended route from the calculated routes. A first route calculation means that uses a route branched from an existing branch point as a recommended branch route;
Time measuring means for measuring the time required for calculation of the recommended route by the first route calculating means;
When the measured calculation time is a predetermined time or more, the branch point information indicating the branch point, the number of road links indicating the number of routes connecting the branch point and the branch point existing on the recommended branch route, Feature point candidate calculating means for calculating, as feature point candidate information, traveling direction information indicating a traveling direction at a branch point existing on the recommended route;
Of the time required for the calculation , the portion exceeding the predetermined time is calculated as an over time, and the number of excess road links, which is the number of road links calculated within the over time by the first route calculation means , is calculated. the feature point candidate information at each branch point on the recommended route, the descending order of the number of road links, until reaching the number of excess road links, and the feature point information calculating means for extracting a feature point information,
Feature point storage means for associating and storing current position information, destination information, search condition information, and feature point information when a route calculation request signal is supplied to the input information receiving means;
The feature point history information stored in the feature point storage means is read out, the path between the feature points indicated by the feature point information including the traveling direction information is calculated based on the read feature point history information, and between the calculated feature points A second route calculating means for calculating a route from the present location to the destination based on the route of
When a route calculation request signal is supplied to the input information receiving means, feature point history information stored in the feature point storage means is read, and current location information, destination information, and search that are supplied to the input information receiving means It is determined whether or not the condition information matches the current location information, the destination information, and the search condition information of the read feature point history information, and if they match, the route is calculated by the second route calculation means. And a route calculation determination means for causing the first route calculation means to calculate a route if they do not coincide with each other.

Images